RSA encryption, step by step

RSA is the public-key cipher that showed the world a lock can be snapped shut by anyone and opened by only one person. Ron Rivest, Adi Shamir and Leonard Adleman described it in 1977. Its security rests on a one-way street in arithmetic: multiplying two large primes is easy, and getting them back from the product is, as far as anyone knows, hopeless once the numbers run to a few hundred digits. RSA protected the early web and still signs things today, though new designs are moving to elliptic curves and, looking ahead, to post-quantum schemes.

Try it

Toy sizes, never real. Nothing you type here leaves your browser.

The tool above uses tiny primes so you can see every number, and it has a button that breaks the key by factoring it, which shows why real keys are huge. The RSA toy page walks through each step.

How it works

The recipe has five steps, and you can do all of them with a calculator on small numbers.

1. Pick two primes, p = 61 and q = 53. Their product, n = 3,233, is the modulus.
2. Compute φ(n) = (p − 1)(q − 1) = 60 × 52 = 3,120.
3. Pick a public exponent e that shares no factor with 3,120, such as 17.
4. Find the private exponent d, the number for which e·d leaves remainder 1 when divided by 3,120. Here d = 2,753, since 17 × 2,753 = 46,801 = 15 × 3,120 + 1.
5. The public key is (n, e) = (3,233, 17), and you can publish it. The private key is d = 2,753.

To lock a message m = 65, compute c = 65¹⁷ mod 3,233 = 2,790. To unlock it, compute 2,790^2,753 mod 3,233 = 65. Euler's theorem is why it works: raising to the power e·d brings you back to where you began. Anyone can do the first step with the public key. The second needs d, and getting d from (n, e) needs φ(n), which needs the factorization of n. The standard definition uses λ(n) = lcm(p − 1, q − 1) and gives a smaller d (413 in this example). Both decrypt correctly.

Raising a number to a power with hundreds of digits sounds impossible, but square-and-multiply does it in a few thousand steps: square repeatedly, and multiply in the squares that match the bits of the exponent. The code listing below does it in six lines.

History

In 1976 Whitfield Diffie and Martin Hellman published the idea of public-key cryptography (Diffie-Hellman) without a working encryption scheme. Rivest, Shamir and Adleman, three colleagues at MIT, set out to find one and described RSA publicly in 1977. MIT was granted US patent 4,405,829 on 20 September 1983, and RSA Security released the algorithm into the public domain on 6 September 2000, two weeks before the patent expired.

It later came out that someone had found the idea first, in secret. In 1973 Clifford Cocks, a mathematician at Britain's GCHQ, developed an equivalent system. The work was classified and wasn't made public until 1997. The three-pass protocol and the treasure-chest puzzle on this site show the lock-and-unlock idea in a simpler setting.

How it's attacked

• Factoring. If you can factor n, you can compute d. The best known method, the general number field sieve, is sub-exponential: far better than trial division and far short of polynomial. RSA-129, a 129-digit (426-bit) number published in 1977, fell in 1994, after 17 years. A 768-bit number, RSA-768, was factored in 2009, and RSA-250, at 829 bits, in 2020. Keys of 2,048 bits (617 decimal digits) and up are considered safe against classical computers for now. NIST counts 2,048-bit RSA as about 112 bits of security and 3,072-bit as 128.
• Padding oracles. Raw RSA is deterministic, so the same message always gives the same ciphertext. It's also malleable: multiply a ciphertext by s^e and the plaintext gets multiplied by s. So it needs padding. Daniel Bleichenbacher broke the old PKCS#1 v1.5 padding in 1998, with an attack that recovers messages from a server that reveals whether a decrypted message was well formed. The padding to use is OAEP.
• Timing and fault attacks. Paul Kocher showed in 1995 that the time a private-key operation takes can reveal the key, which led to blinding: multiplying by a random value first. The ROCA flaw, disclosed in October 2017, hit keys generated by one Infineon library, whose primes had a structure that made factoring feasible.
• Quantum computers. Shor's algorithm factors numbers efficiently on a large enough quantum computer and would break RSA at any size. That's the reason for post-quantum cryptography.

How it's used

RSA is slow and can only encrypt messages smaller than its modulus. So it protects a small secret, such as a key for a symmetric cipher like AES-GCM, and it signs things, such as the certificates that prove a website is genuine. Keys usually run from 2,048 to 4,096 bits. The common public exponent is 65,537, which has only two 1 bits, so encryption is fast. cipher.ink doesn't use RSA at all. It uses a passphrase-derived AES-256-GCM key, so there's no private key to lose.

The code

// Textbook RSA with BigInt. Modular exponentiation by repeated squaring: the heart of RSA, Diffie-Hellman and ElGamal.
function modPow(base, exp, mod) {
  var result = 1n;
  base %= mod;
  while (exp > 0n) {
    if (exp & 1n) result = result * base % mod;       // this bit of the exponent is set: multiply it in
    base = base * base % mod;                          // square for the next bit
    exp >>= 1n;
  }
  return result;
}

// The inverse of a modulo n (extended Euclid): the number x with a * x = 1 (mod n).
function modInverse(a, n) {
  var r0 = n, r1 = a % n, t0 = 0n, t1 = 1n;
  while (r1 !== 0n) { var q = r0 / r1; [r0, r1] = [r1, r0 - q * r1]; [t0, t1] = [t1, t0 - q * t1]; }
  return (t0 % n + n) % n;                             // r0 is now gcd(a, n): it must be 1
}

function rsaKey(p, q, e) {                             // p and q are primes
  var n = p * q, phi = (p - 1n) * (q - 1n);
  return { n: n, e: e, d: modInverse(e, phi) };        // public key (n, e), private exponent d
}
function rsaEncrypt(m, key) { return modPow(m, key.e, key.n); }   // m must be smaller than n
function rsaDecrypt(c, key) { return modPow(c, key.d, key.n); }

Common questions