RSA explained

Every time a browser shows a padlock, a message is signed or software checks an update, public-key cryptography is at work, and RSA is its best-known form. Its idea is that the key that locks a message can be published while the key that opens it stays private. Remarkably, the whole system rests on arithmetic taught at school: prime numbers, multiplication and remainders.

Secret primes 61 and 53 multiply to the public modulus 3233. The letters of HELLO become 3000, 28, 2726, 2726 and 1307 with the public exponent 17, and the private exponent 2753 turns 3000 back into 72
Secret primes 61 and 53 multiply to the public modulus 3233. The letters of HELLO become 3000, 28, 2726, 2726 and 1307 with the public exponent 17, and the private exponent 2753 turns 3000 back into 72

The problem RSA solves

Older ciphers, from Caesar's shift to modern AES, use the same key to lock and unlock, so the two sides must first share a secret key in private. Public-key cryptography removes that step. Each person has two keys: a public key that anyone may use to encrypt a message to them, and a private key that only they hold and that alone can decrypt it. Whitfield Diffie and Martin Hellman described the idea in 1976, and a year later Ron Rivest, Adi Shamir and Leonard Adleman at MIT found a way to do it, named RSA after their initials.

Martin Hellman (left) and Whitfield Diffie (right), 1977
Martin Hellman (left) and Whitfield Diffie (right), 1977

Making the keys

Choose two large primes, p and q, and multiply them: n = p × q. Compute φ(n) = (p − 1)(q − 1), Euler's totient, which counts the numbers below n that share no factor with it. Pick a public exponent e that shares no factor with φ(n); 65537 is the usual choice. Then find the private exponent d such that e × d leaves remainder 1 when divided by φ(n). The extended Euclidean algorithm does this quickly. The public key is the pair (e, n); the private key is d. With p = 61 and q = 53 this gives n = 3233, φ(n) = 3120, e = 17 and d = 2753.

Encrypting and decrypting

A message is first turned into a number m smaller than n. To encrypt it, compute c = mᵉ mod n, the remainder of mᵉ after dividing by n. To decrypt, compute cᵈ mod n. Euler's theorem guarantees that this gives back m, because e × d is one more than a multiple of φ(n). With the keys above the letter A, code 65, becomes 65¹⁷ mod 3233 = 2790, and 2790²⁷⁵³ mod 3233 = 65 again. Powers this large are never written out: repeated squaring computes them with one squaring per bit of the exponent, taking the remainder at every step.

Digital signatures

RSA also works in reverse. Raising a message to the private exponent, s = mᵈ mod n, produces a signature that only the key's owner can make. Anyone can check it with the public key: if sᵉ mod n gives back m, the message came from the holder of d and was not changed on the way. In practice what is signed is a short hash of the message rather than the message itself. Signatures like this protect software updates, secure websites and electronic documents.

Why it is secure

Everyone can see n and e. To find d, an attacker needs φ(n), and to find φ(n) they need p and q, so breaking RSA comes down to factoring n. Multiplying two primes takes a computer a fraction of a microsecond; splitting the product back into them is believed to be extremely hard. The largest RSA challenge number factored so far, RSA-250 in 2020, has 829 bits and took about 2700 years of computer time. Keys in use today have at least 2048 bits, about 617 digits.

A secret discovered twice

In 1973, four years before RSA, the British mathematician Clifford Cocks found the same scheme while working at the intelligence agency GCHQ, building on an idea of his colleague James Ellis. The work was classified and only made public in 1997. RSA itself was patented in the United States in 1983; the patent expired in September 2000, two weeks after the algorithm had been released into the public domain.

Ron Rivest, Adi Shamir and Len Adleman (left to right)
Ron Rivest, Adi Shamir and Len Adleman (left to right)

RSA in practice

Real RSA never encrypts text directly. The message is padded with random bytes, using a scheme such as OAEP, so that the same message encrypts differently every time and patterns cannot leak. Because RSA is slow, it is mostly used to exchange or protect a short key for a fast symmetric cipher such as AES, or to sign. Large enough quantum computers could factor n quickly with Shor's algorithm of 1994, which is why new post-quantum methods are being introduced alongside RSA.

Explore it

Open the RSA encryption demo to build keys from your own primes or random ones from 2 to 8 digits, see the extended Euclidean algorithm find d row by row, encrypt or sign a message character by character, and follow the repeated squaring for any character. Then let Eve factor n and watch how the time she needs grows with the size of the primes.

Frequently asked questions

Why does RSA need prime numbers?

Because φ(n) is easy to compute only when you know how n splits into primes. For n = p × q with p and q prime, φ(n) = (p − 1)(q − 1). Primes also make n as hard as possible to factor for its size, since it has no small factors at all.

Why is e often 65537?

65537 = 2¹⁶ + 1 is prime and has only two 1s in binary, so encrypting with it takes just 16 squarings and one multiplication. It is also large enough to avoid weaknesses of very small exponents such as 3.

What is the difference between RSA and Diffie–Hellman?

Diffie–Hellman lets two people agree on a shared secret key over an open channel; it does not encrypt or sign anything by itself. RSA encrypts and signs directly with a key pair. Both rest on problems that are easy one way and hard the other: factoring for RSA, the discrete logarithm for Diffie–Hellman.

Can the demo's keys be used for real encryption?

No. Its primes have at most a dozen digits, so any key it makes can be factored in seconds or less, and it encrypts each character on its own without padding. It is meant for seeing how RSA works, not for protecting anything.

Ready to try it?

Open PictorX in your browser — no install, no credit card required to start.

Open the RSA encryption demo