The RSA Algorithm – Eponymy in August

Today’s Eponymy in August continues Nerd Week with the RSA algorithm, named for its inventors Ronald Rivest, Adi Shamir, and Leonard Adleman. Rivest and Shamir were computer scientists at MIT who collaborated on trying to find an effective implementation of the public key encryption system proposed by Diffie and Hellman in 1976. Adleman was a mathematician who found weaknesses and vulnerabilities in the early work of the other two.

The story goes that Rivest was beset with a case of insomnia after a long dinner conversation with his colleagues (and much wine) during Passover in 1977. He cracked open a math text and thought for most of the night about the problem, and had a solution by morning.

The details of the algorithm aren’t particularly complex, but there is math involved which I’ll try to explain with words as best I can.

The most important concept for this algorithm, after basic algebra, is modular arithmetic. Think of it like the hands of a twelve-hour clock; if i start at 10 and add five hours, I go to 3, not to 15. We express that in mathematical terms as $10 + 5 ≡ 3\pmod{12}$ , or “ten plus five is congruent to three, modulo twelve.” This can be applied to all of the basic mathematical operators, including multiplication and division, e.g. $10 \cross 2 ≡ 8\pmod{12}$ .
To generate a pair of keys for encryption and decryption, you first randomly choose two prime numbers, ‘p’ and ‘q’, and multiply them to get their product ‘n’. n will be the modulus for future operations, and is a very large number (somewhere around 10³⁰⁰ for 1024-bit RSA, or 10⁶⁰⁰ for 2048-bit).
Now you must choose two numbers to be your public and private key exponents, call them ‘e’ and ‘d’. e is usually small in comparison to the other numbers, but it must have a special property: e must not share any common factors with “Euler’s totient” of n, which is calculated by the expression $n − (p + q − 1)$ and will hereafter be written $\phi(n)$ . Another way of saying this is that the greatest common divisor of e and $\phi(n)$ is 1.
d is then defined as a number such that $e \dotproduct d ≡ 1\pmod{ϕ(n)}$ . There are well-known algorithms for finding this efficiently, which are not covered here.
Now the cool thing about e and d is that any number less than n, when raised to the power of e and then raised to the power of d, is congruent to itself mod n. Meanwhile, a value raised to the power of e or d, mod n, is completely unrelated to the original value. This function is one-way because computing a ciphertext by converting a message to an integer and then raising it to the e’th power still tells us nothing about d, even if we know e, n, the ciphertext, and the cleartext. The only way to determine d is to know p or q or ϕ(n). We discard what we know about p and q after calculating the keys, and it’s very hard to figure out the prime factors of extremely large numbers like n.
So you can safely and freely send e and n to others as a public key. As long as you keep d private (and hold on to a copy of n) you can easily decrypt a message sent to you; without knowing d it would take astronomical amounts of computing power to recover the original message. That’s public key encryption in a nutshell.

Five years after finalizing the algorithm, Rivest, Shamir, and Adleman went on to form RSA Data Security, which went on to create nifty security devices like two-factor authentication dongles, organize a campaign to defeat stupid cryptography backdoor laws in the ’90s, and also take a bribe to default to some of the NSA’s intentionally weakened cryptography standards. RSA was sold to EMC ten years ago but still operates under its own name and runs the largest conference for the security tech industry.