Using the RSA Algorithm for Encryption and Digital Signatures

February 16, 2019

“Public key cryptography,” a method for encrypting messages to be transmit over an insecure channel, and “digital signatures,”

a method for authenticating the author of a message transmitted over an insecure channel,

are emerging as fundamental tools for conducting business securely over the Internet.

Image result for RSA Algorithm

These technologies are widely expected to be used to conduct billions of dollars in electronic commerce within the next few years.

However,

the broad deployment of these technologies is substantially burdened by licensing demands being made by the owner of United States Patent No. 4,405,829, which is known as the “RSA Patent.”

It has become commonly accepted Internet lore that the RSA Patent covers most of the commonly used techniques for public key encryption and digital signatures,

and that a patent license from the owner of the RSA Patent is necessary to employ these techniques.

As this article explores in some detail, however, the RSA Patent is far more limited in scope and far more vulnerable to a validity challenge than is generally assumed.

The RSA Algorithm and the RSA Patent

The RSA Algorithm was named after Ronald Rivest, Adi Shamir and Leonard Adelman, who first published the algorithm in April, 1977.[1] Since that time, the algorithm has been employed in the most widely-used Internet electronic communications encryption program, Pretty Good Privacy (PGP).

It is also employed in both the Netscape Navigator and Microsoft Explorer web browsing programs in their implementations of the Secure Sockets Layer (SSL), and by Mastercard and VISA in the Secure Electronic Transactions (SET) protocol for credit card transactions.

The RSA Algorithm is claimed in the RSA Patent,

which was issued to Drs. Rivest, Shamir and Adelman, who exclusively licensed the patent nine days later to RSA Data Security, Inc., a company which was originally controlled by the inventors but is now a wholly-owned subsidiary of a Boston based company called Security Dynamics Technology, Inc. RSA Data has to date filed three lawsuits alleging infringement of the RSA Patent.

Two were settled prior to trial, and the third is still pending. Other litigation threats have been made regarding alleged infringements of the patent, including threats against non-commercial implementations for use by the Internet community. The patent expires on September 20, 2000, but that will be enough time for the patent to have a profound impact on the development of electronic commerce.

The existence of the patent, and RSA Data’s aggressive litigation posture,

have chilled the interest in both commercial and non-commercial implementations of public key encryption and digital signature technologies. Many have taken for granted the bald assertion that the “RSA Algorithm is patented,” without examining the patent itself, or more particularly, the claims of the patent.

As we set forth in this article, however, a careful review of the patent reveals that the patent is not necessarily as broad as publicly asserted. More particularly, the decryption operation, standing alone, is not independently claimed at all in the patent.

These weaknesses in the patent may be particularly relevant for digital signature operations because they may allow a developer to implement the protocol for verifying an RSA-generated digital signature without infringing the patent. In addition, if one separates the generation of the key pairs from the encryption operation, the claims of the patent do not cover the encryption (or signing) function by itself.

Basic Uses of Public Key Encryption and Digital Signatures

The RSA Algorithm is only one implementation of the more general concept of public key cryptography, which permits two parties who have never met and who can only communicate on an insecure channel to nonetheless send secure and verifiable messages to each other. The Internet as currently structured is an insecure communications channel with an obvious use for such technologies. Indeed, the greatest expected growth for public key techniques is in Internet-related communications.

With public key techniques, each user has two different keys, one made available to the public and the other kept secret.[4] One of the keys is used to encrypt a message, and the other is used to decrypt the message. If Alice wants to send a secret message to Bob,

for example, she looks up Bob’s public key and uses it to encrypt the message.

Because Bob’s public key cannot undo the encryption process, no one who intercepts the message can read it. Only Bob, who possesses the secret key corresponding to his public key, can read the message.

Alice never has to meet Bob out of the hearing of others to exchange keys or passwords; this is a substantial improvement over older encryption methods in which an exchange of private keys was necessary.

This system can also be used as a means for Bob to be sure a message comes from Alice. If Alice wants to sign a message, she can encrypt it with her private key.[5] When Bob receives an encrypted message which purports to be from Alice, he can obtain Alice’s public key and decrypt the message.

If a readable message emerges, Bob can have confidence that the message came from Alice, because Alice’s public key would only properly unlock a message which was locked with her private key (known only to Alice).[6]

Of course,

digitally signing the message does not make the content of the message private, because anyone with Alice’s public key can read a message she encrypted with her private key. Alice can send a private, signed message to Bob, however, by first encrypting the message with Bob’s public key (so only Bob can read it with his private key) and then encrypting the message a second time with her private key, forming her signature.

Anyone who receives the message can use Alice’s public key to undo the second encryption, but only Bob (or someone with Bob’s private key) can undo the first encryption step and actually read the message. All of these complex-sounding manipulations can be made quite manageable with well-written software.

The RSA Implementation of Public Key Encryption and Digital Signatures

The Arithmetic in the RSA System

Typical encryption techniques use mathematical operations to transform a message (represented as a number or a series of numbers) into a ciphertext. Mathematical operations called one way functions are particularly suited to this task. A one way function is one which is comparatively easy to do in one direction but much harder to do in reverse. As a trivial example, it is comparatively easy to square a two digit number; with a little concentration, many people can probably multiply 24 by 24 without using a pencil and paper. One the other hand, calculating the square root of the number 576 is much harder, even with a pencil and paper.

The RSA system uses one way functions of a more complex nature.

Specifically, the system uses modular arithmetic to transform a message (or pieces of the message, one piece at a time) into unreadable ciphertext. Modular arithmetic is often called “clock” arithmetic, because addition, subtraction, and the like, work like telling time.

In a 12-hour system, four hours after 10:00 is not 14:00 (10 + 4 is not equal to 14); it is 2:00. This is because we subtract out 12 (or any multiples of 12) after doing the addition. In modular arithmetic notation, the operation might look like this:

2 = (10+4) mod 122 = 14 mod 12

One can do multiplication in modular arithmetic much the same way addition is going in the above example:

2 = (7*2) mod 122 = 14 mod 12

This process is sometimes callĀ modular reduction. By subtracting out the modulus (and all multiples of the modulus) a number is “reduce” to a much smaller number. When the number 14 is “reduce” to the number 2 in the above example, one can say that “14 is reduce modulo 12.”

The RSA system uses multiplication in modular arithmetic. Instead of multiplying one number by a different number (as (7) is multiply by (2) in the above example), The RSA system multiplies one number (called the base) by itself a number of times. The number of times a base is multiplied by itself is called the exponent:

16 = 2*2*2*216 = 24

In this example,

the number (2) is the base, and is multiplied by itself four times, making the exponent the number (4).

In the RSA encryption formula,

the message (represented by a number M) is multiplied by itself (e) times (called “raising (M) to the power (e)”), and the product is then divided by a modulus (n), leaving the remainder as a ciphertext (C):[7]

C = Me mod n
This is a hard operation to undo — when (n) is very large (200 digits or so) —

even the fastest computers using the fastest known methods

could not feasibly recover the message (M) simply from knowing the ciphertext (C) and the key used to create the message ((e) and (n)).

In the decryption operation, a different exponent, (d) is used to convert the ciphertext back into the plain text:

C = Md mod n
The modulus (n) is a composite number, constructed by multiplying two prime numbers,[8] (p) and (q), together:

n = p * q
The encryption and decryption exponents, (d) and (e), are related to each other and the modulus (n) in the following way:[9]

d = e-1 mod ((p-1) (q-1))[10]
To calculate the decryption key, one must know the numbers (p) and (q) (called the factors) used to calculate the modulus (n). When (n) is a sufficiently large number, it is infeasible, using known algorithms and the fastest computing techniques, to calculate the prime number factors of (n).

The RSA Algorithm may be divide, then, into three steps:

(1) key generation: in which the factors of the modulus (n) (the prime numbers (p) and (q)) are choose and multiply together to form (n), an encryption exponent (e) is chosen, and the decryption exponent (d) is calculate using (e), (p), and (q).

(2) encryption: in which the message (M) is raise to the power (e), and then reduce modulo (n).

(3) decryption: in which the ciphertext (C) is rais to the power (d), and then reduce modulo (n).

Using the RSA Algorithm for Privacy and Digital Signatures

When the RSA Algorithm is used in a public key system, the modulus (n) and one of the exponents (arbitrarily, we can assume (e)) are published. The other exponent (d) is kept secret, as are (p) and (q), the factors of (n). Each user holds his or her own keys, and knows the public key of the other user or users. Alice, for example, knows her own public key (ealice and nalice), her own private key (dalice), and Bob’s public key (ebob and nbob). Bob knows the converse: his public key (ebob and nbob), his private key (dbob) and Alice’s public key (ealice and nalice).

For Alice to send Bob a private message only Bob can read, she performs the following operation on the message (M):

C = Mebob mod nbob

Bob, who is the only one to possess his private key (dbob), performs the following to recover the message (M):

M = Cdbob mod nbob
To sign the message, Alice encrypts with her own private key:

C = Mdalice mod nalice
Because only Alice possesses dalice, only she can create this ciphertext C. Anyone in possession of her public key (ealice and nalice) can verify the signature, however:

M = Cealice mod nalice
It bears note that (p) and (q), the factors of (n), are not needed for encryption or decryption; they are only used in the key generation step (creating the modulus (n) and the second exponent). In addition, while it is important for key generation purposes that the modulus (n) be the product of two prime numbers, the exponentiation and modular arithmetic operation would work just as well with prime numbers (which are by definition evenly divisible only by themselves and the number 1).

The RSA Patent

Anyone who “makes, uses, offers to sell or sells” a patented invention without the permission of the patent owner can be liable for patent infringement.[11] The boundaries of the patent are defined in the claims portion of the patent.[12] Accordingly, in order to determine whether a particular product, method or process infringes a patent, one must start with the text of the claims themselves.

There are 40 claims in the RSA Patent, but only ten of them are independent claims.[13] Independent claims are claims which do not incorporate other claims by reference. To infringe a dependent claim, one must first infringe the independent claim (or claims) incorporated by reference in the dependent claim.

Conversely,

if one does not infringe the independent claim(s) incorporated by the dependent claim, by definition one does not infringe the dependent claim. Accordingly, a review of the independent claims in the RSA Patent is sufficient for purposes of this discussion.

As we will also see, a detailed review of the broadest independent claim in the RSA Patent (Claim 23) will lead without much further ado to a logical conclusion about the other nine independent claims, and in turn to a conclusion about all the claims in the RSA Patent: that none of these claims are infringed by performing a typical digital signature verification.

The claim with the least number of elements (and thus the broadest claim in the patent) is Claim 23,

which provides:

23. A method for establishing cryptographic communications comprising the step of:

encoding a digital message word signal M to a ciphertext word signal C, where M corresponds to a number representative of a message and

0 <= M <= n-1
where n is a composite number of the form

n=p*q
where p and q are prime numbers, and

where C is a number representative of an encoded form of message word M,

wherein said encoding step comprises the step of:

transforming said message word signal M to said ciphertext word signal C whereby

C [is congruent to] Me (mod n)

where e is a number relatively prime to (p-1)*(q-1).

Accordingly, the elements of this claim require an accused infringer to perform the following steps:[14]

  • Establish cryptographic communications;
  • Ensure that the message (M) is greater than or equal to zero and less than or equal to (n-1);
  • Define the modulus (n) by selecting prime numbers (p) and (q) and multiplying them together;
  • Define the encryption exponent (e) such that it is relatively prime[15] to (p-1)*(q-1); and
  • Encode message (M) into ciphertext (C) by raising (M) to the power of (e) and
  • then reducing modulo (n).

Does Claim 23 Cover Signature Verification?

As noted above, to verify an RSA-generated digital signature,

the recipient takes the ciphertext transmitted to him and decrypts the ciphertext with the sender’s public key. If the message decrypts properly, the signature is genuine.

Importantly, two of the three fundamental steps in the RSA system are not perform in the signature verification step: key generation,

where the parameters of the modulus (n) and the exponents (e) and (d) are set; and encryption, where the message (M) is raise to the power of (e) and then reduce by the modular operation. Only the third, decryption step is perform. The keys are generate by the sender (signer) and the encryption step has already been complete in the signing step.

Accordingly,

a person who merely verifies an RSA signature arguably does none of the steps contained in Claim 23,

and certainly does not do them all. Most significantly, the decryption operation plainly does not constitute “encoding a digital message word signal” into “ciphertext.”

The verification operation transforms “ciphertext” into a “message word signal,” not the reverse. The patent makes clear, moreover, what constitutes a “message” and what constitutes “ciphertext,” and how “decoding” and “encoding” are different.

These terms are not interchangeable.

The RSA signature verification steps of transforming ciphertext C into a message M using the decryption exponent (d) are separately claimed in dependent claim 24:

24. The method according to claim 23 comprising the further step of:

decoding said ciphertext word signal C to said message word signal M,

wherein said decoding step comprises the step of:

transforming said ciphertext word signal C, whereby:

M [is congruent to] Cd (mod n)
where d is a multiplicative inverse of e (mod (lcm ((p-1), (q-1)))).

Because Claim 24 incorporates all of the elements of Claim 23 by reference, one cannot infringe Claim 24 simply by performing the decryption steps alone.

Do the Other RSA Patent Independent Claims Cover Signature Verification?

The analysis of Claim 23 above should apply with equal force to the other independent claims. Claims 1, 13, and 18 require key generation, encoding, and de-coding. Claims 3, 8, 25, 29 do not contain the decoding step (subsequent dependent claims add that step), but have at least the elements of Claim 23, plus others.

The Claims 33 and 37 claim a special case of the use of the RSA method, and thus are also more limited than Claim 23. Thus, under this analysis none of the independent claims of the RSA Patent (and therefore none of the dependent claims) are infringed by performing a typical digital signature verification.

Does Claim 23 Cover Generation of a Digital Signature?

It appears that the process of generating an RSA signature also may be done without infringing Claim 23. To create an RSA digital signature, the sender encrypts the message M with her private key, and transmits it to the receiver. The encoding step is clearly claimed in Claim 23 (and other independent claims), and thus the argument stated above regarding verification (decryption) is not available.

However,

Claim 23 also requires key generation, and that step need not be performed by software creating a digital signature if the keys are already supplied. (All of the other independent claims require the generation of the keys meeting the RSA Algorithm parameters.)

The step of generating the numbers comprising RSA keys (p, q, n, e and d) can easily be separated from the encryption step. The same keys can be used over and over again for multiple signatures; indeed, they can be used for as long as one has confidence that the keys have not been compromised.

Moreover,

many RSA-license products generate keys which can be separate from the software which generate them. Thus, as a practical matter, it should be possible to use keys generated by licensed RSA software in order to create digital signatures with other, unlicensed software.

The owner of the RSA Patent would have difficulty arguing successfully that the encryption operation itself is cover by the patent, separate from the generation of the keys. This is because the concept of using exponents in modular arithmetic for encryption was invented and disclose before the RSA system was invent.

In 1975,

two years before the RSA method was invented, Martin Hellman and Stephen Pohlig at Stanford University invented the Pohlig-Hellman encryption system,[18] which is identical to the RSA method, except that the modulus is a prime number, as opposed to the product of two primes:

Comparison of RSA and Pohlig-Hellman

RSA System Pohlig-Hellman
Encryption Operation C = Me mod n C = Me mod p
Decryption Operation M = Ce mod n M = Ce mod p
modulus p * q (prime numbers) p (prime number)
Encryption exponent (e) e relatively prime to
(p-1)*(q-1)
e relatively prime to (p-1)
Decryption exponent (d) d = e-1 mod ((p-1)*(q-1)) d = e-1 mod (p-1)

The exponentiation and modular reduction steps in RSA and Pohlig-Hellman will work exactly the same regardless of whether the modulus is a prime number or the product of two primes.

Once the modulus and the exponents are defined,

the mathematical operations for encryption and decryption are identical in both the Pohlig-Hellman and RSA systems. A software module written to perform Pohlig-Hellman encryption or decryption would work just as well using a modulus and exponents generated with an RSA system. Accordingly,

even if the inventors had attempted to claim the encryption step alone,

without regard to key generation, the prior Pohlig-Hellman invention would have prevented such a claim from being valid.[19]

What About Contributory Infringement?

The discussion above relates to direct infringement of RSA Patent — whether one performs all of the steps one of the claims –

– but does not consider all of the possible ways in which one can be liable for patent infringement.

Patent law also makes liable someone who “actively induces” infringement of a patent, or someone who contributes to the infringement by another if he “offers to sell or sells within the United States . . . a component of a patented machine, manufacture, combination or composition,

or a material or apparatus for use in practicing a patented process,

constituting a material part of the invention, knowing the same to be especially made or especially adapted for use in an infringement of such patent, and not a staple article or commodity of commerce suitable for substantial noninfringing use . . . .”

The owner of the right to enforce the RSA Patent could attempt to attack those who sign or verify as contributory infringers, and those who develop the software which enables this activity as active inducers of infringement.

The major flaw in such claims is that for there to be either contributory infringement or inducement to infringe, there must be direct infringement.[21] One who merely verifies an RSA generated signature simply has not performed all of the steps claimed in the patent. The missing encryption and key generation steps have been performed by another (presumably licensed) user of the technology.

Similarly,

assuming a signer uses a licensed method for generating the keys, or if the signer does not herself generate or cause to be generated the RSA keys, there is no direct infringement by using an unlicensed method to perform the signing operation.

As long as the user only performs the signing or verification steps, there is no direct infringement. With no direct infringement, supplying the means for signing or verification is not contributory infringement.

A closer question of contributory infringement would arise if a developer of signing software knew of the unlicensed generation of RSA keys and deliberately adapted the software to assist in the use of those unlicensed keys in performing signature operations.

(This issue is not present for verification;

by definition, the person who verifies an RSA signature does not generate, or have access to, the private keys used for signing.) The RSA Patent rights owner could argue that the signing software was “especially adapted” for use in infringing the patent.

Then, the argument would run, a user who both generated the keys using unlicensed means and the developer’s software for signing directly infringed the patent. This would supply the missing direct infringement and expose the developer to contributory infringement liability.

The outcome to this argument would turn in large measure on the nature of the developer’s signing software. When an article is accuse of being “especially adapt” for use in an infringing process or method, the article as a whole is consider, not just some particular feature or ingredient.

If, taken as a whole, the article has substantial,

non-infringing uses, the contributory infringement is not present, even if in some modes the article can assist in conduct which otherwise infringes the patent.[24] For example, software adapted to encrypt a message using Pohlig-Hellman keys, for example, would work as easily with RSA Keys.

Assuming that Pohlig-Hellman operations were consider “substantial,” the use of the identical encryption and decryption operations certainly would be non-infringing. Accordingly, it is quite possible to conceive of software which, while capable of performing RSA encryption, would be found as a whole to have substantial non-infringing uses.

If software were developed which, taken as a whole, had substantial non-infringing uses,

then the developer should not be found liable for contributory infringement merely because the keys were generated by unlicensed means.

A Real World Example — Secure Sockets Client

One of the most common uses of public key technology is in the Secure Sockets Layer (SSL) protocol,

used by Netscape Navigator and other web browsers for secure communications over the internet.

Secure sockets allows the user — typically an individual working from a personal computer at home

(called the client) — to communicate with a web site computer (called the server).

The server might be operating by a merchant and the user might wish to have the client computer send a credit card number to the server to order goods.

The secure sockets protocol uses public key techniques to encrypt the credit card number so that the number is not send in plaintext over the internet.

According to the analysis set forth in this article,

the client should be able to perform all of the RSA encryption and verifications steps without infringing the RSA Patent.

In simplified form, the secure sockets protocol using the RSA method works as follows.[26] After a client makes context with the web site server, and a secure session is to be established, the server transmits a message the client containing (1) the server’s public key; and (2) a digital signature from a certificate authority certifying that the public key the server claims as its own is, in fact, its own.

The client next verifies the server’s public key using the signature authority’s public key which is install with the browser software on the client’s computer.[27] In this way, the client can be assured that the server is who it claims to be. The client is then ready to send confidential information (such as a credit card number) to the server.

The client will encrypt the credit card number,

but will not use RSA or another public key technique to actually encrypt the data. RSA is much slower than other conventional encryption methods which use the same key to encrypt and decrypt.

While this might not matter if all that is being encrypt is a single credit card number, in practice a secure session with a web browser may involve the transmission of thousands of bytes of information.

To avoid painfully long delays, the client will generate a random number for use as a conventional, symmetric key to encrypt the all of the data being send during the secure session. The client then encrypts this key using the server’s RSA public key transmitted in the opening message from the server.

The server receives this encrypted key, and decrypts it using its secret key. Both the client and the server are now in possession of a share, symmetric key which both use to encrypt and decrypt all subsequent data being send during the secure session.

In this protocol,

the client does only two public key steps, and does not perform any key generation steps. First, the client verifies the server’s public key. To perform the verification step, it uses the certificate authority’s public key. That key, necessarily generated by the certificate authority, can be assumed reasonably to be generated by a licensed entity.

[28] The second step — encrypting the symmetric encryption key for the session — uses the public key supplied by the server.

That key also can be presumed to have been generated by a licensed method.

Although both decryption (verification) and encryption (of the session key) steps are performed by the client,

there is every reason to believe that the key generation steps are performed by licensed methods.

Accordingly,

because the client software does not generate any keys, the client does not directly infringe the any of the claims of the RSA patent. Although the client does use two public keys

(the server’s and the certificate authority) for encryption and decryption,

those keys are almost certainly generated licensed means. Accordingly,

the client does not contribute to, or induce the infringement of, the RSA Patent.

Some Questions About the Validity of the RSA Patent Claims

The analysis in this article thus far has assumed that the broad claims of the RSA Patent, and particularly Claim 23,

are valid. While patents are presumed valid, and an infringer has the burden of proving invalidity by clear and convincing evidence,

some vulnerabilities of the RSA Patent have been exposed in the litigation RSA Data has been involved in. Among other weaknesses, the following appear:

(1) some of the RSA claims may not cover patentable subject matter,

(2) the inventors appear not to have disclosed in the specification the “best mode” of implementing the invention, as required by the patent laws,

and (3) a real question exists regarding whether the invention is obvious in light of the Pohlig-Hellman work. Each of these weaknesses will be consider below.

How Can You Patent an Algorithm?

Those with passing familiarity with patent law may be startle at the assertion that a cryptographic algorithm can be claim in a patent. The United States Supreme Court ruled in 1972 that an algorithm, which it defined as a “procedure for solving a given type of mathematical problem,” was not a “process, machine, manufacture, or composition of matter” within the meaning of section 101 of the Patent Act,[29] and thus was not patentable subject matter.

Six years later, the Court reaffirmed this rule, holding that even if the applicant wanted to limit the claim to use of the algorithm in a specific application, it was still not within the allowable subject matter of section 101.[31] Cryptographic algorithms would seem to fall squarely within this proscription against patenting algorithms.

In 1981, however,

a breakthrough Supreme Court decision paved the way for patent claims containing algorithms. The case, Diamond v. Dehr,[32] involved an improved process for making rubber. The improvement centered on an algorithm used to treat the rubber at specified temperatures.

The Court held that when an algorithm is part of an otherwise patentable process (which manufacturing rubber certainly was), the presence of the algorithm among the other elements of the claim did not push the claim outside the bounds of section 101.

While the Supreme Court was deciding these cases,

a trio of appellate court decisions refined the rules regarding when and how an algorithm may be incorporated into a patent. The three cases, In re Freeman,[33] In re Walter,[34] and In re Abele,[35] establish what the Federal Circuit refers to as the Freeman-Walter-Abele test for patentability when an algorithm is implicated in a patent claim. The test is state as follows:

It is first determine whether a mathematical algorithm is recite directly or indirectly in the claim.

If so,

it is next determin whether the claim invention as a whole is no more than the algorithm itself; that is,

whether the claim is direct to a mathematical algorithm that is not apply to or limit by physical elements or process steps. Such claims are nonstatutory. However,

when the mathematical algorithm is apply in one or more steps of an otherwise statutory process claim,

or one or more elements of an otherwise statutory apparatus claim, the requirements of section 101 are meet.

Arrhythmia Research Technology,

Inc. v. Corazonix Corp. In other words,

the fact that an algorithm is one of the elements of a claim of a patent does not make the claim invalid. If the algorithm is using as part of a physical process

(such as the manufacture of rubber, as in Dehr,) or is part of a physical device

(such as an electrocardiograph device, as in Arrhythmia), the invention is patentable subject matter.

Many of the existing cryptography patents contain attempts to meet this test by reciting the cryptographic algorithm as an element within a physical device.

In the RSA Patent,

this approach is stretch near if not beyond the breaking point. The only elements of the physical device claim which are not descriptions of the algorithm are “a communications channel,” “an encoding means,” and a “decoding means.”

The broadest method (or process) claim of the RSA Patent describes using the algorithm to “encode” a “message word signal.”[38] By using the most generic references to a device (“encoding means”), and the most generic reference possible to a physical process (encoding a “message word signal”), this type of patent comes as close as possible to claiming the algorithm by claiming the use of the algorithm in essentially all possible machines or with all possible processes.

Indeed,

it is difficult to imagine how one could use the algorithm without a physical device which could be characterized as an “encoding means,” or how one could apply the algorithm in a way which did not “encode” a “signal.”

Three recent Federal Circuit cases give insight into how the courts might apply the Freeman-Walter-Abele test to a cryptographic algorithm. First, in In re Alappat,[39] the Federal Circuit used that test to find valid a patent which claimed an algorithm for displaying a smooth waveform from digital data.

“Although many,

or arguably even all, of the means elements recited in [the disputed claim] represent circuitry elements that perform mathematical calculations, which is essentially true of all digital electrical circuits,” the Federal Circuit noted, the patent was nonetheless proper because “the claimed invention as a whole is directed to a combination of interrelated elements which combine to form a machine for converting discrete waveform data samples into . . . data to be displayed on a display means.

“Alappat can read to stand for the proposition that,

if the physical machine which performs the algorithm is a computer,

and if the output from the algorithm is otherwise display,

it may well be that the “physical device,” or “physical process” requirements of the Freeman-Walter-Abele test are meet.

Another Federal Circuit case, In re Warmerdam,[41] further confirms that court’s generous view of algorithm-based patents. In Warmerdam, the court found patentable an invention claiming a “bubble hierarchy” algorithm used by computer-operated robots to avoid obstructions. Because a claim covered a “machine” (the computer and memory controlling the robot) it was patentable,

even though the novelty of the invention consisted solely of the use of the algorithm.[42]

The Federal Circuit has, however,

limited the patentability of algorithm claims in at least one recent case. In In re Schrader,[43] the court found unpatentable a claim to an invention for processing auction bids. The court distinguished Abele and Arrhythmia based on the nature of the input to the algorithm.

In Abele, the input was data from an X-ray CAT scan; in Arrhythmia, the input was data from a electrocardiograph. Both sources of input data, the Federal Circuit reasoned, involved “subject matter representative of or constituting physical activity or objects.”

Bid data from auction bidders was mere “data gathering,

” according to the Schrader court, and thus was materially different from X-ray or heart-rate data.[45] The fact that the patent specification discussed displaying the resulting data on display screens did not affect patentability, nor did a claim element for entering the bid data in a “record.

One possible way to apply these cases to a cryptographic algorithm patent is to ask this question:

is the input to a cryptographic system more like the data from auctioneers,

or is it more like electro-cardiograph, CAT-scan, or rubber temperature data? The latter are representations of a physical object — a part of the body. Bid data, in contrast, seems much closer to the plaintext message input of a cryptographic system.

Both are merely abstract messages intend to be communicate from one party to another. The bid data algorithm of Schrader simply transformed the message in a way to extract certain information to the auctioneer. An encryption algorithm simply transforms the message to protect privacy or security.

If the test is, indeed,

whether the input to the algorithm is data descriptive of a physical object existing in the real world

(such as a heartbeat or the temperature of rubber) as oppose to an abstract message compose by a human being,

the validity of a broad cryptography patent such as the RSA Patent is subject to genuine question.

It bears emphasis that the patentability of the claims in the RSA Patent will vary, claim by claim. The attorneys who drafted the claims may have anticipated this problem; they added dependent claims which recite “register means” for accomplishing the steps claimed in the algorithm.

(Other dependent and independent claims simply add additional qualifications to the algorithm,

and do not add any other physical structures to the claims.)

The use of the term “register means”
appears to be intend to encompass a generic computer system at its most basic level.

Under the current procedures applied by the Patent Office to patents claiming algorithms, however,

one cannot transmute an unpatentable series of algorithm steps into a patentable machine merely by claiming the algorithm along with a generic computer performing the steps.

Thus, the addition of the “register means” elements to the claims did not materially improve their validity,

and may in fact have limited the scope of the claims.

As written, all of the RSA Patent claims consist solely of algorithms combined with the most minimum,

generic hardware means possible.

A genuine question remains whether, in that form, they claim patentable subject matter.

It is true that patents are presumed valid, and that clear and convincing evidence[50] of invalidity is required to attack an issued patent.

This rule exists largely out of deference to the expertise of the Patent and Trademark Office. The question of patentable subject matter, however, has been treat as a question of law; the courts decide such questions de novo without deference to any administrative body.

Moreover, the RSA Patent was issue at a time when the law on algorithm-based claims was unclear.

Indeed, under the current examination guidelines, it is doubtful whether any of the RSA Patent claims would be allowed.[52] Accordingly, one could not have confidence in every case that the examiner was aware of the proper legal standard to be applied.

Does the Patent Disclose the Best Mode?

Section 112 of the Patent Act requires an inventor to fulfill certain requirements

in making the details of the invention known in the specification of the patent. One of these obligations requires the inventor to “set forth the best mode contemplated by the inventor of carrying out his invention.”[53] The best mode requirement “is intended to ensure that a patent applicant plays ‘fair and square’ with the patent system.

It is a requirement that the quid pro quo of the patent grant be satisfy. One must not receive the right to exclude others unless at the time of filing he has provided an adequate disclosure of the best mode known to him of carrying out his invention.”[54] Whether the best mode requirement has been met is as a question of fact.[55]

It appears that the principal inventor of the RSA Algorithm,

Ronald Rivest, believed that certain criteria in the selection of the prime numbers ((p) and (q)) were important.[56] Evidence of his subjective belief comes from papers he wrote both before and after he applied for his patent. In August, 1977, before he applied for the patent, he wrote:

To gain additional protection against sophisticated factoring algorithms,
both (p-1) and (q-1) should contain large prime factors and gcd(p-1,q-1) should be small.[57]

In January, 1978, Dr. Rivest published a paper in response to a proposed attack on his system,

in which he gave more details about his preferred method of constructing his system.[58] In this later paper, Dr. Rivest noted that the prior paper “makes definite suggestions as to how the prime numbers p and q should be chosen,” but that “this note should help make those suggestions less mysterious.”[59] This January paper goes on to give more details about the selection of prime numbers, and further provides yet more details regarding the selection of the exponent (e) which Dr. Rivest preferred for additional security.[60]

While Dr. Rivest’s papers may have discussed his best mode of implementing the invention, the patent disclosure does not. The RSA Patent specification does refer to one of these papers — the one whose discussion Dr. Rivest later characterize as “mysterious.” The best mode requirement cannot meet merely by references to other papers, however. The disclosure must be in the specification of the patent itself.[61] Accordingly, there is good reason to believe the RSA Patent is invalid because the inventors did not comply with the best mode requirement.

Was the RSA Algorithm Obvious?

Section 103 of the Patent Act provides that a patent is invalid

“if the differences between the subject matter sought to be patent and the prior art are such

that the subject matter as a whole would have been obvious at the time the invention

was made to a person having ordinary skill in the art . . . .” Section 102 of the Patent Act defines what is and

what is not prior art for the purpose of applying the obviousness test of section 103.[62] Under section 102(a), prior art includes matters “known or used by others in this country, or patented or described in a printed publication in this or a foreign country,

before the invention thereof by the applicant” (emphasis added), and under section 102(g) prior art includes prior inventions by another.

The Pohlig-Hellman paper[63] is likely to be held as prior art under sections 102(a) or (g), as a printed publication, as public knowledge, or as a prior invention.

The file wrapper of the RSA Patent reveals that the inventors of the RSA Patent did not disclose the Pohlig-Hellman paper to the Patent Office

and that the examiner did not consider whether the use of a non-prime number in lieu of a prime number

(the only difference between Pohlig-Hellman and RSA) was obvious.

While the presumption of validity is available even where prior art has not been considered during the prosecution of a patent,

that presumption is not as strong where the art is not submit to the examiner. There are a number of references in the prior art, moreover,

to using the problem of factoring composite numbers in cryptography,

dating back to the 19th century.

Accordingly, should the RSA Patent ever become subject to further litigation,

it may not survive a validity challenge based on the Pohlig-Hellman work.

Conclusion

Due largely to luck, bluster, and the naivet?of potential competitors, the owner of United States Patent No. 4,405,829 has enjoyed a virtual monopoly on all uses of the RSA Algorithm. However,

a careful scrutiny of the RSA Patent claims, and other details of its disclosure and prosecution,

reveal both significant limits to the scope of the patent and material questions regarding its validity.

While this article is not intend by the authors as legal advice

to the reader nor as an invitation or encouragement to infringe the RSA Patent or any other patent,

those interested in implementing this technology should take a close look at the patent –

– and obtain the advice of a competent attorney familiar with the proposed project —

before accepting at face value the oft-repeat notion that “RSA is patent.”