On this page
Diffie and Hellman had shown in 1976 that public-key cryptography could exist, but not how to build a full system for locking and signing messages. Three researchers at MIT did that within a year. This post covers who they were, works through the small example printed in their own paper, and explains why the whole scheme leans on one hard problem: splitting a large number into its prime factors.
Who were Rivest, Shamir and Adleman?
Their ACM Turing Award biographies give the background. Ron Rivest graduated from Yale in 1969 in mathematics and earned a PhD in computer science at Stanford in 1973, then joined MIT. Adi Shamir was born in Tel Aviv in 1952, studied mathematics at Tel Aviv University and earned his PhD at the Weizmann Institute in 1977. Leonard Adleman was born on 31 December 1945 in San Francisco, entered Berkeley planning to be a chemist, graduated in mathematics and completed a PhD in 1976 on number theory and computational complexity. He then joined MIT's mathematics department.
All three biographies say the trio was inspired by the Diffie and Hellman paper, which described ways to avoid a shared secret key but gave no realistic way to implement them. You can read that earlier step in our post on Diffie, Hellman and secret keys.
What did the RSA paper claim?
The paper, A method for obtaining digital signatures and public-key cryptosystems, appeared in Communications of the ACM in February 1978. Its abstract describes the method: represent the message as a number M, raise it to a public power e, and take the remainder on division by n, the product of two large secret primes p and q. Decryption uses a different, secret power d, chosen so that e × d leaves remainder 1 when divided by (p − 1)(q − 1). "The security of the system rests in part on the difficulty of factoring the published divisor, n."
The paper also gives its two users names. It says it will suppose that A and B are "also known as Alice and Bob".
Worked example: the paper's own numbers
Section VIII of the authors' copy of the paper uses small primes so the reader can follow along.
Choose p = 47 and q = 59. Then n = 47 × 59 = 2773.
Compute (p − 1)(q − 1) = 46 × 58 = 2668.
Choose the secret d = 157. The public exponent e must satisfy e × d ≡ 1 (mod 2668). The paper finds e = 17. Check: 17 × 157 = 2669 = 2668 + 1.
Encode letters as two-digit numbers (blank = 00, A = 01, ..., Z = 26). "IT" becomes M = 0920.
Encrypt: M^17 mod 2773, by repeated squaring and reducing each time. 920^2 ≡ 635, 920^4 ≡ 1140, 920^8 ≡ 1836, 920^16 ≡ 1701, and 920^17 ≡ 1701 × 920 ≡ 948. The ciphertext block is 0948.
Decrypt: 948^157 mod 2773 gives back 920, as the paper invites the reader to check.
Anyone can know n = 2773 and e = 17. To find d, you need 2668, and to get that you need p and q. With n = 2773 you can factor it in minutes; with a 200-digit n, the picture changes.
Common mistakes:
Using n instead of (p − 1)(q − 1) to find d. The inverse is taken modulo 2668, not 2773.
Letting M be larger than n. Each block must be smaller than n, which is why the paper encodes two letters at a time.
Multiplying out before reducing. 920^17 has more than 50 digits; reduce after every step.
How hard is factoring?
The paper's Table 1 estimates the time to factor n with the fastest method the authors knew, at one microsecond per operation: about 3.9 hours for a 50-digit number, 74 years for 100 digits and 3.8 × 10^9 years for 200 digits. They recommended n of about 200 digits as "a margin of safety against future developments". Rivest's biography adds a caution of its own: nobody can be sure factoring will stay hard, and a large quantum computer, if one is built, might break the system.
What came of it?
ACM gave the three the 2002 Turing Award "for their ingenious contribution to making public-key cryptography useful in practice." Rivest's biography notes that RSA came to secure most online commercial transactions, and that the three went on to found the company RSA Data Security.
To practise the modular steps above on more examples, the Fermi Problem Library has worked problems with a step-by-step solver that explains the reasoning rather than printing an answer.
What can a student take from how they worked?
Build what someone else only described. Diffie and Hellman gave the concept; RSA supplied the construction.
Show a small example. The paper's 2773 example lets any reader check the whole method with a calculator.
State the weak point honestly. The authors said plainly that security rests on factoring, and estimated how long that would take.
Try it now: with n = 2773 and e = 17, encrypt the block for "AB" (0102), then decrypt it with d = 157.
