Using the RSA Algorithm for Encryption and Digital Signatures:

"Public key cryptography," a method for encrypting messages to be transmitted 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. 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 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.[3] 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.

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 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:

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

The RSA system uses multiplication in modular arithmetic. Instead of multiplying one number by a different number (as (7) is multiplied 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:

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]

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:

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

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

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 divided, then, into three steps:

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

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

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

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 (e_alice and n_alice), her own private key (d_alice), and Bob's public key (e_bob and n_bob). Bob knows the converse: his public key (e_bob and n_bob), his private key (d_bob) and Alice's public key (e_alice and n_alice).

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

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

To sign the message, Alice encrypts with her own private key:

Because only Alice possesses d_alice, only she can create this ciphertext C. Anyone in possession of her public key (e_alice and n_alice) can verify the signature, however:

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).

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

where n is a composite number of the form

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

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).

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 performed 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 raised to the power of (e) and then reduced by the modular operation. Only the third, decryption step is performed. The keys are generated by the sender (signer) and the encryption step has already been completed 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.[16] These terms are not interchangeable.[17]

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:

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.

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. 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.

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-licensed products generate keys which can be separated from the software which generated 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 covered 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 disclosed before the RSA system was invented. 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:

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]

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 . . . ."[20]

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.[22] 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 accused of being "especially adapted" for use in an infringing process or method, the article as a whole is considered, not just some particular feature or ingredient.[23] 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 considered "substantial," the use of the identical encryption and decryption operations certainly would be non-infringing.[25] 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.

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 operated 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 sent 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 installed 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 encrypted 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 sent 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 shared, symmetric key which both use to encrypt and decrypt all subsequent data being sent 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.

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 considered below.

Those with passing familiarity with patent law may be startled at the assertion that a cryptographic algorithm can be claimed 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.[30] 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 stated as follows:

It is first determined whether a mathematical algorithm is recited directly or indirectly in the claim. If so, it is next determined whether the claimed invention as a whole is no more than the algorithm itself; that is, whether the claim is directed to a mathematical algorithm that is not applied to or limited by physical elements or process steps. Such claims are nonstatutory. However, when the mathematical algorithm is applied 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 met.

Arrhythmia Research Technology, Inc. v. Corazonix Corp.[36] 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 used 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 stretched 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."[37] 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."[40] Alappat can be 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 displayed, it may well be that the "physical device," or "physical process" requirements of the Freeman-Walter-Abele test are met.

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."[44] 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."[46]

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 intended to be communicated 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 opposed to an abstract message composed 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.[47] (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 have been intended 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.[48] 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.[49] 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 treated as a question of law; the courts decide such questions de novo without deference to any administrative body.[51] Moreover, the RSA Patent was issued 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.

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 satisfied. 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 characterized as "mysterious." The best mode requirement cannot be met 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.

Section 103 of the Patent Act provides that a patent is invalid "if the differences between the subject matter sought to be patented 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 was not submitted 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.[64] Accordingly, should the RSA Patent ever become subject to further litigation, it may not survive a validity challenge based on the Pohlig-Hellman work.

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 intended 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-repeated notion that "RSA is patented."

[*] Mr. Flinn and Mr. Jordan practice with the law firm of Alston & Bird, LLP, located in Atlanta Georgia. Mr. Flinn is a member of the California and Georgia Bars, and Mr. Jordan is a member of the Georgia Bar and is admitted to practice before the United States Patent & Trademark Office. They have represented clients in litigation against RSA Data Security, Inc., regarding, among other things, the validity of the RSA Patent. The opinions expressed in this article are personal, however, and do not necessarily reflect the opinions of their firm, or any client of their firm.

This article consists of statements of personal opinion by the authors, and is neither legal advice nor an invitiation to any person to practice any invention claimed in any patent. Because the specific circumstances of any individual or entity will determine the extent of exposure to liability for infringing a patent, reliance on this or any other article of general applicability should not be substituted for legal advice from an attorney familiar with your particular circumstances.

Portions of this article were previously published in the March, 1997 and June, 1997 editions of Electronic Banking Law and Commerce Report (Glasser LegalWorks).

[1] Ronald L. Rivest, Adi Shamir, Len Adelman, "On Digital Signatures and Public Key Cryptosystems," MIT Laboratory for Computer Science Technical Memorandum 82 (April 1977).

[2] The latest version of the PGP program for personal use is PGP for Personal Privacy, Version 5.0, which is available in beta form for download at http://www.pgp.com, and will be in final form in late May 1997. This new version offers a choice between the RSA algorithm, on the one hand, and the DSS/Diffie-Hellman algorithms, on the other.

[3] For example, Bruce Schneier's otherwise excellent book, APPLIED CRYPTOGRAPHY (2d ed.), John Wiley & Sons (1996) at 474, (hereinafter Schneier) contains this overstatement.

[4] A "key" in these systems is not a physical device, but is a number (akin to a password). The encryption key is used as an input to the mathematical formula which transforms a readable message into apparently meaningless gibberish. The decryption key is the number used as an input to the formula which transforms the apparent gibberish back into the original message.

[5] Alice does not have to encrypt the whole message just to sign it. In fact, because such large numbers are used in real-world implementations of this technology, the encryption operation can be quite slow. Instead, Alice can use something called a "hashing algorithm" to transform a message of any size in to a string of numbers of a fixed (and usually smaller) size. If the hashing algorithm is designed properly (and there are a number in current use), different messages should not produce the same hash. Accordingly, the hash acts as a digital "fingerprint" of the message. Alice can then encrypt the hash, not the message itself, with her private key. To verify the signature, Bob simply re-hashes the message using the same hashing algorithm Alice used, and then decrypts Alice's hash with her public key. If the hashes match, the message is authentic and has not been altered in transit.

[6] Bob should have some way of being confident that the number he thinks is Alice's public key is, in fact, her public key. There are a number of alternative proposals and methods for allowing for the verification of public keys, and the debate over them is lively, but the details the competing systems are beyond the scope of this discussion.

[7] Substituting numbers for variables, a modular arithmetic operation looks like this: 1 = 2⁴ mod 5 The base (2) multiplied by itself four times (the exponent (4) is equal to 16 (2*2*2*2=16)

1 = 16 mod 5

When there are 3 five's in 16 (3 times 5 is 15) and a remainder of 1.

[8] A prime number is one which is divisible only by itself and the number 1. The numbers 17 and 31 are prime, for example, but 15 (divisible by 1, 3, 5 and 15) and 21 (divisible by 1, 3, 7 and 21) are not.

[9] The number representing the message (M) should be less than the modulus (n) if decryption is to succeed. In addition, the multiplicative inverse (d) only exists if (e) is relatively prime to (has no prime number factors in common with) the number (p-1)*(q-1).

[10] The patent defines (d) and (e) as multiplicative inverses modulo the "least common multiple" (or "lcm") of (p-1) and (q-1), a value which divides the value (p-1)*(q-1) used here, resulting in additional possible values for d beyond the simplified version given here. This detail is not important to the discussion in this article, however.

[11] 35 U.S.C. section 271(a).

[12] E.g., Texas Instruments, Inc. v. U.S. Int'l Trade Commission, 805 F.2d 1558, 1562 (Fed. Cir. 1986), reaff'd, reh'g denied, 846 F.2d 1369 (1988) .

[13] The independent claims are: 1, 3, 8, 13, 18, 23, 25, 29, 33, and 37.

[14] In patent law, as in horseshoes and hand grenades, "almost" counts. One can be liable for patent infringement even if one does not literally infringe all of the elements of a claim. Under a theory called the "doctrine of equivalents," recently upheld by the U.S. Supreme Court, infringement can be found as long as the defendant infringes a "substantial equivalent" of an element of a claim not literally infringed. Warner Jenkinson Co. v. Hilton Davis Chemical Co., 520 U.S. ___, 117 S.Ct. 1352 (March 31, 1997).

[15] A number is "relatively prime" to another number if the two numbers have no factors in common except for the number 1. For example, the numbers 8 and 21 are not prime numbers (each has a factor other than itself and 1) but 8 and 21 are relatively prime to one another because the only common factor they have is the number 1 (the factors of 8 are 1, 2, 4, and 8; the factors of 21 are 1, 3, 7 and 21).

[16] As these terms are used in the RSA Patent the "message" is "encoded" into "ciphertext" and "ciphertext" is sent from the first party to the second. See RSA Patent at Col. 1, Line 56- Col.2, Line 10. The recipient receives "ciphertext" and "decodes" the "ciphertext" into the "original message." Id. Thus, a person wishing the verify a digital signature must have received "ciphertext," and thus must "decode" it, because the "message" is not transmitted through the communications "channel." Id.

[17] Other components in the algorithm probably are interchangeable. For example, the encryption exponent (e) and the decryption exponent (d) each meet the definition of the other. The fact that the exponent (d) is the multiplicative inverse of the exponent (e) mod (p-1)*(q-1) proves the converse, that (e) is the multiplicative inverse of (d), and that (e) and (d) are both relatively prime to (p-1)*(q-1).

[18] See Stephen C. Pohlig and Martin E. Hellman, "An Improved Algorithm for Computing Logarithms over GF(p) and its Cryptographic Significance," IEEE TRANSACTIONS ON INFORMATION THEORY (Jan. 1978) (article submitted on June 17, 1976).

[19] The application for a patent on the Pohlig-Hellman system was pending during the period the RSA patent was being prosecuted, and the Patent Office declared an "interference" in which both sides were allowed to compete for a claim which would have covered the generic process of encryption and decryption using exponentiation and modular arithmetic. Stanford University and MIT abandoned the interference in the early 1980's, however, so neither side was awarded this generic claim.

[20] 35 U.S.C. section 271(c).

[21] E.g., Joy Technologies, Inc. v. Flakt, Inc., 6 F.3d 770, 774 (Fed. Cir. 1993); Met-Coil Systems Corp. v. Korners Unlimited, Inc., 803 F.2d 684, 687 (Fed. Cir. 1986). Inducing infringement also requires an intent element not present in a claim for contributory infringement. Hewlett Packard Co. v. Bausch & Lomb, Inc., 909 F.2d 1464, 1468 (Fed. Cir. 1990).

[22] One cannot contribute to the infringement if the "direct" infringer is licensed, expressly or impliedly. See, e.g., Universal Electronics, Inc. v. Zenith Electronics Corp., 846 F. Supp. 641 (N.D. Ill.) (no contributory infringement or inducement to infringe by manufacturer of "universal" remote control for television where the purchaser of the replacement remote has an implied license to practice the invention arising out of purchase of the original television-remote combination), aff'd w/o op., 41 F.3d 1520 (Fed. Cir. 1994).

[23] E.g., Hodosh v. Block Drug Co., 833 F.2d 1575, 1579 (Fed. Cir. 1987), cert. denied, 485 U.S. 1007 (1988).

[24] See C.R. Bard, Inc. v. Advanced Cardiovascular Sys., Inc., 911 F.2d 670, 674 (Fed. Cir. 1990); Universal Electronics, 846 F. Supp. at 651.

[25] Other non-RSA public key variants, such as Diffie-Hellman and El-Gamal, all use exponentiation and modular reduction. See, e.g., Schneier at 476-478; 513-516. While Pohlig-Hellman is the closest system to RSA, it is certainly true that the mathematical steps involved in RSA encryption and decryption are the same steps used in many other non-infringing cryptographic systems.

[26] The details of the SSL protocol may be found at http://home.netscape.com/eng/ssl3/ssl-toc.html.

[27] Netscape Navigator, for example, installs a file names "cert.db" with the other program files.

[28] Indeed, RSA Data itself operates a certificate authority business, and RSA certificate keys are supplied with the Netscape Navigator Browser.

[29] The basic patent statute, 35 U.S.C. section 101, provides, "[w]hoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor . . . ."

[30] Gottschalk v. Benson, 409 U.S. 63, 65 (1972).

[31] Parker v. Flook, 437 U.S. 584, 586 (1978).

[32] 450 U.S. 175 (1981).

[33] 573 F.2d 1237 (C.C.P.A. 1978).

[34] 618 F.2d 758 (C.C.P.A. 1980).

[35] 684 F.2d 902 (C.C.P.A. 1982).

[36] 958 F.2d 1053, 1058 (Fed. Cir. 1992).

[37] RSA Patent at Col. 14, Line 38 - Col. 15, Line 5.

[38] Id. at Col. 25, Lines 47-67.

[39] 33 F.3d 1526 (Fed. Cir. 1994).

[40] Id. at 1544.

[41] 33 F.3d 1354 (Fed. Cir. 1994).

[42] Id. at 1360-1.

[43] 22 F.3d 290 (Fed. Cir. 1994).

[44] Id. at 294 (emphasis in original). In Warmerdam (subsequent to Schrader), the input data was information about the physical objects the robot might encounter, and thus would also satisfy the "physical activity or object" test.

[45] In re Schrader, 22 F.3d at 294.

[46] Id. at 293-94.

[47] See RSA Patent claims 2, 4, 9, 14, 19, and 34.

[48] The United States Patent & Trademark Office will consider claims reciting generic computer hardware as process claims which themselves must be independently patentable. See United States Patent & Trademark Office, Examination Guidelines for Computer-Related Inventions, 61 Fed. Reg. 7478 (1996) (hereinafter, "Guidelines"). These Guidelines have been called "persuasive authority" by the Federal Circuit. In re Trovato, 60 F.3d 807 (Fed. Cir. 1995).

[49] These claims are stated in so-called "means-plus-function" terms, which is permissible under the last paragraph of 35 U.S.C. section 112. When claims are written in these terms, however, they are limited to covering "the corresponding structure . . . described in the specification and equivalents thereof." We have not analyzed whether the specific computational hardware disclosed in the specification of the patent differs in any material way from the processors used in modern computers, and it may well be that these claims are limited to 1977 era computational equipment. This article assumes, however, that a modern computer CPU would be considered at least the "equivalent" to the "register means" claimed in these dependent claims.

[50] This may be contrasted with the "preponderance-of-evidence" standard typical in other civil litigation.

[51] In re Donaldson Co., 16 F.3d 1189, 1192 (Fed. Cir. 1994).

[52] See generally Guidelines, supra note 45.

[53] 35 U.S.C. section 112.

[54] Amgen, Inc. v. Chugai Pharmaceutical Co., 927 F.2d 1200, 1209-10 (Fed. Cir.), cert. denied, 502 U.S. 856 (1991).

[55] Amgen, 927 F.2d at 1209; Engel Industries, Inc. v. Lockformer Co., 946 F.2d 1528, 1531 (Fed. Cir. 1991).

[56] Ironically, it turns out that Dr. Rivest was wrong in his belief that these (and other) limitations on the selections of (p) and (q) made a significant difference in the security of the system. Subsequent research showed that, even with careful selection of (p) and (q), one could not avoid the sort of weakness in the modulus Dr. Rivest was hoping to avoid. See Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, HANDBOOK OF APPLIED CRYPTOGRAPHY, section 3.2.4, p. 94 (CRC Press 1997). Users were told that a "careful" selection of primes allowed a given level of security to be achieved with a smaller modulus than would otherwise be required. In fact, this is an unsafe improvement, and the larger modulus is needed to achieve that level of security. Any impact of this fact on the validity of the patent is beyond the scope of this article.

[57] Ronald L. Rivest, Adi Shamir, Len Adelman, "A Method for Obtaining Digital Signatures and Public Key Cryptosystems," MIT LABORATORY FOR COMPUTER SCIENCE TECHNICAL MEMORANDUM 82 (Revised August 1977) at 10.

[58] Ronald L. Rivest, "Remarks on a Proposed Cryptanalytic Attack on the M.I.T. Public-Key Cryptosystem," CRYPTOLOGIA (January 1978).

[59] Id. at 2.

[60] Id. at 4-5.

[61] See Dana Corp. V. IPC Limited Partnership, 860 F.2d 415, 418-419 (Fed. Cir. 1988), cert. denied, 490 U.S. 1067 (1989); Advanced Semiconductor Materials America, Inc. v. Applied Materials, Inc. 1994 W.L. 715634 (N.D. Cal. Dec. 16, 1994) (denying motion for summary judgment on best mode defense, ruling that the PTO Manual of Patent Examining Procedure, which specifically disallows incorporation by reference to "non patent publications" to comply with the best mode requirement, established the legal rule for incorporation by reference).

[62] Graham v. John Deere Co., 383 U.S. 1, 14-15 (1966).

[63] See note 18 above.

[64] In 1870, a book by William S. Jevons described the relationship of one-way functions to cryptography and went on to discuss specifically the factorization problem used to create the "trap-door" in the RSA system. In July, 1996, one observer commented on the Jevons book in this way:

In his book The Principles of Science: A Treatise on Logic and Scientific Method, written and published in the 1890's, William S. Jevons observed that there are many situations where the 'direct' operation is relatively easy, but the 'inverse' operation is significantly more difficult, One example mentioned briefly is that enciphering (encryption) is easy while deciphering (decryption) is not. In the same section of Chapter 7: Introduction titled 'Induction an Inverse Operation', much more attention is devoted to the principle that multiplication of integers is easy, but finding the (prime) factors of the product is much harder. Thus, Jevons anticipated a key feature of the RSA Algorithm for public key cryptography, though he certainly did not invent the concept of public key cryptography.

Solomon W. Golomb, On Factoring Jevons' Number, CRYPTOLOGIA 243 (July 1996) (emphasis added).