Papers in Computer Science

Citation: Ron Rivest, Adi Shamir and Len Adleman. “A method for obtaining Digital Signatures and Public Key Cryptosystems.” Communications of the ACM. Feb., 1978 21(2) pages 120-126. (PDF)

Abstract: An encryption method is presented with the novel property that publicly revealing an encryption key does not thereby reveal the corresponding decryption key. This has two important consequences:

1. Couriers or other secure means are not needed to transmit keys, since a message can be enciphered using an encryption key publicly revealed by the intended recipient. Only he can decipher the message, since only he knows the corresponding decryption key.

2. A message can be “signed” using a privately held decryption key. Anyone can verify this signature using the corresponding publicly revealed encryption key. Signatures cannot be forged, and a signer cannot later deny the validity of his signature. This has obvious applications in “electronic mail” and “electronic funds transfer” systems.

A message is encrypted by representing it as a number M, raising M to a publicly specified power e, and then taking the remainder when the result is divided by the publicly specified product, n, of two large secret prime numbers p and q. Decryption is similar; only a different, secret, power d is used, where e ∙ d ≡ 1 (mod (p − 1) ∙ (q − 1)). The security of the system rests in part on the difficulty of factoring the published divisor, n.

Discussion: This seminal 1978 paper describing the original RSA encryption algorithm provided the first practical implementation of a public-key cryptography system, allowing secrets to be transmitted between two parties over an insecure channel. Until this time, setting up a secure channel was an expensive and time-consuming endeavor that required first using an existing secure mechanism, such as a courier, to exchange encryption keys.

Although many people credit the RSA paper with founding public-key cryptography, in fact the conceptual groundwork had already been laid two years earlier by Diffie and Hellman in their “New directions in cryptography.” (IEEE Trans. Inform. Theory IT-22, (Nov. 1976), 644-654. (PDF)) That paper introduced and motivated the idea of having two keys, a public key E for encryption and a key D for decryption, such that it is intractable to compute D from E. They describe how public keys might be distributed and the applications in private communication and authentication; they “propose some techniques for developing public key cryptosystems, but the problem is still largely open.” Their suggestions were based on matrix-vector multiplication, which is easy to break with matrix inversion; and obfuscation of programs, which was never implemented and has since been shown to have poor security properties (see Barak et al’s “On the (Im)possibility of Obfuscating Programs”).

The essential contribution of RSA was to show: 1. that a practical public-key cryptosystem exists; 2. describing such a system in sufficient detail for implementation. Sections I through IV largely rehash Diffie and Helman’s paper and introduce their key terminology.

Section V introduces the system itself, which is very simple: two large prime numbers p and q are generated, and their product n is computed. A large random number d coprime to both p-1 and q-1 is generated, then its inverse modulo (p-1)(q-1) is computed and named e. To encrypt a message M, it is treated as a large integer and then raised to the eth power modulo n. To decrypt, the result is raised to the dth power modulo n. The public key e is widely distributed, while d is kept secret.

Correctness of the system is straightforward: Euler’s theorem states that if a and n are coprime, and x ≡ y (mod φ(n)), then a^x ≡ a^y (mod n). Here φ is Euler’s totient function, which for n with two prime factors p and q is given by (p-1)(q-1). If we substitute M for a, the product ed for x, and 1 for y, we get: if ed ≡ 1 (mod (p-1)(q-1)), then M^ed ≡ M (mod n), which is just what we want, since M^ed = (M^e)^d.

Today the system has been somewhat modified; it is more common for increased efficiency of encryption to choose a small fixed e such as 3 and use it to compute d, rather than choosing a random d and computing e (although this practice has its detractors). PKCS#1 v2.0 requires the use of lcm(p-1, q-1) in place of (p-1)(q-1), and p and q are usually chosen to be of the same size rather than to “differ in length by a few digits.” It’s also common to store additional information as part of the private key, such as p, q, d mod p-1, d mod q-1, and the multiplicatve inverse of q mod p. These all assist in efficient decryption, which using new algorithms can take advantage of the known factorization of n.

The system’s practicality critically depends on the observation that – even in 1978 – all of the necessary operations could be done efficiently: large integers could be multiplied using long multiplication or Toom-Cook (1971), raising an integer to a large power modulo another integer could be done rapidly using exponentiation by squaring (classical), computing e from d could be done with the extended Euclidean algorithm (classical), and testing large random integers for primality could be done using fast primality tests, such as the Solovay and Strassen probabilistic test. This test, discovered in 1977, may well have been the enabling technology for RSA; on computers of the time, it could generate a “100-digit” (330-bit) prime number in “a minute or two.”

RSA’s security relied on the informal observation that even though n is needed to encrypt the message, and d is a prime factor of n, factoring a product of two large primes is a computationally difficult problem with no known fast solution. Factoring had been the focus of centuries of mathematical research as well as a great deal of recent computer science research, which they believed “partially “certified”" RSA. Although this remains true today, this was even more true in 1978, when the best known factoring algorithm had a runtime given by:

exp((ln n)^1/2 ∙ (ln ln n)^1/2)

This algorithm was an unpublished algorithm described by Richard Schroeppel, whose primary contribution was an analytical framework that could be used to estimate asymptotic runtimes of a class of factoring algorithms. Carl Pomerance would later describe this unpublished work (Pomerance, C. 1985. The quadratic sieve factoring algorithm. In Proc. of the EUROCRYPT 84 Workshop on Advances in Cryptology, 169-182).

As RSA became more popular, both its underlying technologies for practicality and factoring algorithms received an intense research focus. The authors of RSA originally recommended a “200 digit” (660-bit) key n, and estimated such a key would take “74 years” to factor and so “provides a margin of safety against future developments.” The first general semiprime of this size to be factored was RSA200, successfully factored in 2005 using the fastest modern algorithm, the General Number Field Sieve (GNFS); it required about 75 CPU-years of time to factor, and was completed in 13 months. It remains the largest such integer to be factored to date. The RSA paper didn’t anticipate the massive speedup that would result from a 1000-fold improvement in hardware speed, sophisticated new algorithms like the quadratic sieve and general number field sieve, and massive parallelization. By comparison to Schroeppel’s method, the GNFS has asymptotic time given roughly by:

exp(c (ln n)^1/3 (ln ln n)^2/3)

The most important exponent, that of ln n, has been reduced from 1/2 to 1/3.

However, at the same time work there were improvements in primality testing algorithms: the Miller-Rabin primality test that is dominant today was developed only two years after the RSA paper, and together with hardware speedups has enabled keys to easily scale up to the dominant size of 1024 bits, nearly twice the size recommended by the RSA paper. 2048 bit keys are also feasible and far beyond the reach of modern factoring algorithms.

The RSA paper also made the argument that computing d is not substantially easier than factoring n. Their argument makes informal use of the idea of a reduction: “Once a cryptanalyst knows d he can calculate e ∙ d – 1, which is a multiple of n. Miller has shown that n can be factored using any multiple of n. Therefore if n is large a cryptanalyst should not be able to determine d any easier than he can factor n.” However, they left open the interesting question of whether (M^e)^d (mod n) can be computed efficiently without access to d:

“Although this problem of “computing e-th roots modulo n without factoring n” is not a well-known difficult problem like factoring, we feel reasonably confident that it is computationally intractable. It may be possible to prove that any general method of breaking our scheme yields an efficient factoring algorithm. This would establish that any way of breaking our scheme must be as difficult as factoring. We have not been able to prove this conjecture, however. Our method should be certified by having the above conjecture of intractability withstand a concerted attempt to disprove it. The reader is challenged to find a way to “break” our method.”

The problem of computing square roots mod n is known to be equivalent to the problem of factoring n (it suffices to find two squares with distinct square roots, then you have a congruence of squares), so there seems little hope of computing e-th roots. On the other hand, no one has shown either that breaking RSA would imply a factoring algorithm, or that RSA can be decrypted by some method more efficient than computing d; the paper’s challenge still stands.

The paper gave little attention to concerns of how public-key cryptography would be used in practice. Today, with RSA widely deployed and forming the basis of innumerable commercial systems, public-key encryption is primarily used for encrypting of short keys which are then used to encrypt traffic using more efficient symmetric encryption schemes like AES; this is another reason RSA has been successful, despite its heavy computational burden, because there is no need for it to scale to large messages. For this reason, the paper’s attention to “blocking” (as in section X) turned out to be largely moot.

Another interesting point about RSA is its patent history: MIT was issued a patent in 1983, five years after the RSA paper was published. This patent would expire in 2003, but was released into the public domain early in 2000. In the interim, much of the motivation for studying of alternate bases for public-key cryptography came from the desire to avoid infringement.  Today, bases for public-key cryptography other than factoring are still sought either for the sake of improved efficiency or for improved theoretical guarantees on the security of the system. A prominent example is elliptic curve cryptography.

The author releases all rights to all content herein and grants this work into the public domain, with the exception of works owned by others such as abstracts, quotations, and WordPress theme content.