RSA: A Lock Anyone Can Close

in reviewThis lesson is complete and being validated before release - details may still change.

RSA

Loading interactive demo…

The tables are the key as it is built: the public half, n and e, and the private half, p, q, phi, and d, with the attacker's copy of the private half beneath, filled in if the attack succeeds. The plot is the attack: one point per trial divisor, its height the remainder, and a point on the floor is a factor found. The strips are the message letter by letter, the cipher block each becomes, and the letters that come back. Tap a letter to light it across the strips.Take the tour, or press and explore. Legend:

The panel beside the stage is the real RsaCipher class from the published library executing in your browser, with the current line highlighted.

The key part, letter, or trial under way.
The public key, and a cipher block.
A letter that came back intact.
A trial divisor that divides n, and the private key in the attacker's hands.
Key parts, blocks, and trials the run has not reached yet, ghosted.

n is the modulus, d the private exponent, round trip whether decrypting gave the message back, factored whether and after how many trials the attacker found the primes.

The code panel shows bare executable code by default. The bar above it names the file (hover the name for the full published path); options holds the toggles: comments, the tracer instrumentation that produces this visualization, and verbose names for the terse identifiers (display only: the default is the byte-exact published file). The view switch adds plain-English narration: both interleaves it with the code, pseudo shows only the pseudocode. hide code collapses the panel; the rail it leaves behind brings it back.

Keys: Space play/pause · ←/→ step · Home/End jump · R reset · F fullscreen · G guided tour

The key. Choose primes $p \ne q$ and let $n = pq$ and $\varphi(n) = (p-1)(q-1)$ , the count of residues mod $n$ coprime to $n$ . Choose $e$ with $\gcd(e, \varphi) = 1$ and let $d = e^{-1} \bmod \varphi$ , found by the extended Euclidean algorithm. Publish $(n, e)$ ; keep $d$ .

Why it works. Euler's theorem, the generalisation of Fermat's little theorem to any modulus, says $m^{\varphi(n)} \equiv 1 \pmod n$ when $\gcd(m, n) = 1$ . Since $ed = 1 + k\varphi$ ,

(m^e)^d = m^{ed} = m \cdot (m^{\varphi})^k \equiv m \pmod n .

The case $\gcd(m, n) > 1$ also works, by the Chinese remainder theorem applied to $p$ and $q$ separately, though such an $m$ would reveal a factor of $n$ and is vanishingly unlikely at real sizes. Both powers are taken by squaring: $e$ is chosen small with few $1$ bits, so encryption is a couple of multiplications, while $d$ is as large as $\varphi$ and decryption costs about $2 \log_2 n$ .

The trapdoor. Everyone can compute $m^e$ ; only the holder of $d$ can invert it. Computing $d$ needs $\varphi(n)$ , and knowing $\varphi(n)$ is equivalent to knowing $p$ and $q$ : from $n$ and $\varphi$ the primes are the roots of $x^2 - (n - \varphi + 1)x + n$ . So the private key is exactly as safe as $n$ is hard to factor. The stage's attacker divides by every candidate up to $\sqrt{n}$ , which is $O(\sqrt{n})$ and instant for five digits; the number field sieve runs in about $\exp(1.9 (\ln n)^{1/3} (\ln \ln n)^{2/3})$ , which took $2700$ core-years for $829$ bits and is out of reach at $2048$ . Shor's algorithm would do it in polynomial time on a quantum computer, which is why the replacements are being written.

Textbook RSA leaks. With one letter per block and no randomness, equal letters give equal blocks, exactly like codebook mode; and an attacker can encrypt every possible letter with the public key and match. Worse, RSA is multiplicative, $E(m_1) E(m_2) = E(m_1 m_2)$ , which lets an attacker turn one decryption into another. Real use pads each block with random bytes in a structured way, OAEP for encryption, so that no two encryptions of one message agree and the structure can be checked on decryption. The arithmetic is the same.

Where this goes. Run the key the other way round, raise a digest to $d$ and let anyone raise the result to $e$ , and the holder of the private key has signed the digest. That is the next lesson, and the certificate chain and the TLS handshake are built from such signatures.

Choices worth reading closely in the implementation (the code panel's comments and tracer checkboxes reveal the full published file):

keygen throws when $\gcd(e, \varphi) \ne 1$ , rather than quietly picking another exponent, so a caller learns that the pair and the exponent do not fit; the lesson's chips offer only primes for which every listed exponent fits.
encrypt and decrypt are one pow each, on the untraced ModularArithmetic the constructor holds, and encryptText and decryptText narrate per letter; the arithmetic is the modular lesson's, nothing more.
factor tries 2 and then only odd divisors up to the square root, within a budget, so the attacker's work is visible in trials and the trace stays short even where the attack fails.
crack reports found: false with null factors when the trials run out, as the handshake lesson's 16-bit primes make it, so the same class shows both the toy's weakness and a key that holds.

Diffie and Hellman had asked in 1976 for a trapdoor: a function anyone could compute but only its owner could invert. Ron Rivest, Adi Shamir, and Leonard Adleman spent a year failing to build one, until Rivest, awake after a Passover seder in April 1977, saw that raising to a power mod a product of two primes would do, since undoing it needs the totient and the totient needs the primes. Martin Gardner's column that August offered a hundred dollars for a message under a 129-digit modulus; it was read seventeen years later, by six hundred volunteers' computers.

1973Clifford Cocks - Finds the same scheme at GCHQ within an afternoon of hearing James Ellis's problem; it stays classified until 1997.source
1977Ron Rivest, Adi Shamir, and Leonard Adleman - Publish the scheme, with the public exponent, the private inverse mod phi, and the argument that breaking it means factoring.source
1994Derek Atkins, Michael Graff, Arjen Lenstra, and Paul Leyland - Factor RSA-129, Gardner's challenge number, with the quadratic sieve across six hundred volunteers' machines, eight months of work.source
1994Peter Shor - Shows a quantum computer would factor in polynomial time, which is why post-quantum schemes are being standardised to replace RSA.source
1998Daniel Bleichenbacher - Breaks the padding then used with RSA in SSL by asking a server a million yes-or-no questions; padding design becomes as important as the arithmetic.source
2020Fabrice Boudot and colleagues - Factor RSA-250, 829 bits, with the number field sieve in about 2700 core-years; 2048-bit keys remain far out of reach.source

Used today

Certificates - Most of the web's certificates still carry RSA public keys; the certificate lesson verifies a chain of them.
SSH and code signing - An SSH key pair and a signed software release are RSA keys used the other way round, which the signatures lesson shows.
Key transport - Older TLS encrypted the session key under the server's RSA key; TLS 1.3 dropped it for the forward secrecy of Diffie-Hellman.

message

n: 12091
d: 9777
round trip: yes
factored: 107 times 113, 54 trials

rsa.ts

import { EuclideanAlgorithm } from "../number-theory/euclidean-algorithm";import { ModularArithmetic } from "../number-theory/modular-arithmetic";import type { Tracer } from "../trace";/** Primes below 2^16, so n stays below 2^32 and every power is exact. */export const MAX_PRIME = 65521;/** The public exponents in use: small, with few 1 bits, so encryption is a couple of multiplications. */export const PUBLIC_EXPONENTS: readonly number[] = [3, 5, 17, 257];/** The factoring attack gives up after this many trial divisors, which covers any n below 2^16. */export const MAX_TRIALS = 128;/** Letters per message on the stage: one block each. */export const MAX_LETTERS = 8;export interface PublicKey {  n: number;  e: number;}export interface PrivateKey {  n: number;  d: number;  privateExponent: number;  p: number;  q: number;  phi: number;  totient: number;}export interface RsaKeyPair {  publicKey: PublicKey;  privateKey: PrivateKey;}export interface Factoring {  n: number;  p: number | null;  q: number | null;  trials: number;  found: boolean;}export interface RsaRun {  keys: RsaKeyPair;  plain: string;  cipher: number[];  decrypted: string;  roundTrip: boolean;  factoring: Factoring;  /** The private key the attacker rebuilt from the public one, or null. */  cracked: PrivateKey | null;}/** * RSA: two primes p and q make a modulus n = pq that anyone may see, * and a public exponent e that is coprime to phi = (p - 1)(q - 1). The * private exponent d is the inverse of e mod phi, which Euclid finds * in a moment for whoever knows phi, and phi needs the factors. A * message m below n is encrypted as m to the e mod n and decrypted * as the result to the d, because ed is 1 plus a multiple of phi and * Euler's theorem makes m to a multiple of phi equal 1. The attacker * who wants d must factor n, and the stage's attacker tries every * divisor, which works below 2^16 and fails at the 2048 bits real * keys use. One letter per block, as here, is textbook RSA and leaks * like codebook mode: real use pads each block with randomness. * * Time: O(log e) multiplications to encrypt, O(log d) to decrypt. Space: O(1). */export class RsaCipher {  constructor(    private readonly tracer?: Tracer,    private readonly modular: ModularArithmetic = new ModularArithmetic(),    private readonly euclid: EuclideanAlgorithm = new EuclideanAlgorithm(),  ) {}  /** The key pair from two distinct primes and a public exponent coprime to phi. */  keygen(p: number, q: number, e: number): RsaKeyPair {    for (const prime of [p, q]) if (!ModularArithmetic.isPrime(prime) || prime > MAX_PRIME) throw new RangeError(`${prime} is not a prime up to ${MAX_PRIME}`);    if (p === q) throw new RangeError("the two primes must differ");    const n = p * q;    // ▸ n = p times q is public; p and q are not    this.tracer?.emit("modulus", { p, q, n });    const phi = (p - 1) * (q - 1);    const totient = (p - 1) * (q - 1);    // ▸ phi counts the residues coprime to n, and needs p and q    this.tracer?.emit("totient", { p, q, phi });    this.tracer?.emit("totient", { p, q, totient });    const gcd = this.euclid.gcd(e, phi);    const gcd = this.euclid.gcd(e, totient);    const coprime = gcd === 1;    // ▸ e must share no factor with phi, or it has no inverse    this.tracer?.emit("exponent", { e, phi, gcd, coprime });    this.tracer?.emit("exponent", { e, totient, gcd, coprime });    if (!coprime) throw new RangeError(`${e} shares the factor ${gcd} with phi = ${phi}`);    const d = this.euclid.inverse(e, phi).inverse!;    const privateExponent = this.euclid.inverse(e, totient).inverse!;    // ▸ d is the inverse of e mod phi: euclid, for whoever knows phi    this.tracer?.emit("private-key", { e, d, phi, check: (e * d) % phi });    this.tracer?.emit("private-key", { e, privateExponent, totient, check: (e * privateExponent) % totient });    return { publicKey: { n, e }, privateKey: { n, d, p, q, phi } };    return { publicKey: { n, e }, privateKey: { n, privateExponent, p, q, totient } };  }  /** m to the e mod n. Untraced: the text methods narrate per letter. */  encrypt(message: number, key: PublicKey): number {    if (!Number.isInteger(message) || message < 0 || message >= key.n) throw new RangeError(`a message is a whole number below n = ${key.n}, got ${message}`);    return this.modular.pow(message, key.e, key.n);  }  /** c to the d mod n. */  decrypt(cipher: number, key: PrivateKey): number {    return this.modular.pow(cipher, key.d, key.n);    return this.modular.pow(cipher, key.privateExponent, key.n);  }  /** Uppercase letters only, one block each. */  static clean(text: string): string {    return text.toUpperCase().replace(/[^A-Z]/g, "").slice(0, MAX_LETTERS);  }  /** Each letter's code raised to e: textbook RSA, one block per letter. */  encryptText(text: string, key: PublicKey): number[] {    return Array.from(text, (letter, index) => {      const message = letter.charCodeAt(0);      const cipher = this.encrypt(message, key);      // ▸ a block to the e, mod n: anyone can do this      this.tracer?.emit("encrypt", { index, letter, message, e: key.e, n: key.n, cipher });      return cipher;    });  }  /** Each block raised to d and read back as a letter. */  decryptText(blocks: readonly number[], key: PrivateKey): string {    return blocks      .map((cipher, index) => {        const message = this.decrypt(cipher, key);        const letter = String.fromCharCode(message);        // ▸ the block to the d, mod n: only the holder of d can        this.tracer?.emit("decrypt", { index, cipher, d: key.d, n: key.n, message, letter });        this.tracer?.emit("decrypt", { index, cipher, privateExponent: key.privateExponent, n: key.n, message, letter });        return letter;      })      .join("");  }  /** Trial division: 2, then every odd number up to the square root, within the trial budget. */  factor(n: number): Factoring {    let trials = 0;    const divisors = [2];    for (let d = 3; d * d <= n && divisors.length < MAX_TRIALS; d += 2) divisors.push(d);    for (let privateExponent = 3; privateExponent * privateExponent <= n && divisors.length < MAX_TRIALS; privateExponent += 2) divisors.push(privateExponent);    for (const divisor of divisors) {      trials += 1;      const remainder = n % divisor;      const hit = remainder === 0;      // ▸ the attacker tries a divisor of n      this.tracer?.emit("trial", { divisor, n, remainder, hit });      if (hit) return { n, p: divisor, q: n / divisor, trials, found: true };    }    return { n, p: null, q: null, trials, found: false };  }  /** The attacker's whole job: factor n, recompute phi, invert e. */  crack(key: PublicKey): { factoring: Factoring; privateKey: PrivateKey | null } {    const factoring = this.factor(key.n);    let privateKey: PrivateKey | null = null;    if (factoring.found && factoring.p !== null && factoring.q !== null) {      const phi = (factoring.p - 1) * (factoring.q - 1);      const totient = (factoring.p - 1) * (factoring.q - 1);      const d = this.euclid.inverse(key.e, phi).inverse;      const privateExponent = this.euclid.inverse(key.e, totient).inverse;      if (d !== null) privateKey = { n: key.n, d, p: factoring.p, q: factoring.q, phi };      if (privateExponent !== null) privateKey = { n: key.n, privateExponent, p: factoring.p, q: factoring.q, totient };    }    // ▸ with p and q, phi and then d follow at once    this.tracer?.emit("cracked", { n: key.n, p: factoring.p, q: factoring.q, phi: privateKey?.phi ?? null, d: privateKey?.d ?? null, trials: factoring.trials, found: privateKey !== null });    this.tracer?.emit("cracked", { n: key.n, p: factoring.p, q: factoring.q, totient: privateKey?.totient ?? null, privateExponent: privateKey?.privateExponent ?? null, trials: factoring.trials, found: privateKey !== null });    return { factoring, privateKey };  }  /** Make the keys, encrypt a short text letter by letter, decrypt it, then attack the public key. */  run(p: number, q: number, e: number, text: string): RsaRun {    const keys = this.keygen(p, q, e);    const plain = RsaCipher.clean(text);    const cipher = this.encryptText(plain, keys.publicKey);    const decrypted = this.decryptText(cipher, keys.privateKey);    const { factoring, privateKey } = this.crack(keys.publicKey);    return { keys, plain, cipher, decrypted, roundTrip: decrypted === plain, factoring, cracked: privateKey };  }}

n =: 12091
roundTrip =: yes
cracked =: yes

n = 12091, d = 9777; the message came back intact, and the attacker rebuilt d after 54 trials.

import { EuclideanAlgorithm } from "../number-theory/euclidean-algorithm";import { ModularArithmetic } from "../number-theory/modular-arithmetic";import type { Tracer } from "../trace";/** Primes below 2^16, so n stays below 2^32 and every power is exact. */export const MAX_PRIME = 65521;/** The public exponents in use: small, with few 1 bits, so encryption is a couple of multiplications. */export const PUBLIC_EXPONENTS: readonly number[] = [3, 5, 17, 257];/** The factoring attack gives up after this many trial divisors, which covers any n below 2^16. */export const MAX_TRIALS = 128;/** Letters per message on the stage: one block each. */export const MAX_LETTERS = 8;export interface PublicKey { n: number; e: number;}export interface PrivateKey { n: number; d: number; privateExponent: number; p: number; q: number; phi: number; totient: number;}export interface RsaKeyPair { publicKey: PublicKey; privateKey: PrivateKey;}export interface Factoring { n: number; p: number | null; q: number | null; trials: number; found: boolean;}export interface RsaRun { keys: RsaKeyPair; plain: string; cipher: number[]; decrypted: string; roundTrip: boolean; factoring: Factoring; /** The private key the attacker rebuilt from the public one, or null. */ cracked: PrivateKey | null;}/** * RSA: two primes p and q make a modulus n = pq that anyone may see, * and a public exponent e that is coprime to phi = (p - 1)(q - 1). The * private exponent d is the inverse of e mod phi, which Euclid finds * in a moment for whoever knows phi, and phi needs the factors. A * message m below n is encrypted as m to the e mod n and decrypted * as the result to the d, because ed is 1 plus a multiple of phi and * Euler's theorem makes m to a multiple of phi equal 1. The attacker * who wants d must factor n, and the stage's attacker tries every * divisor, which works below 2^16 and fails at the 2048 bits real * keys use. One letter per block, as here, is textbook RSA and leaks * like codebook mode: real use pads each block with randomness. * * Time: O(log e) multiplications to encrypt, O(log d) to decrypt. Space: O(1). */export class RsaCipher { constructor( private readonly tracer?: Tracer, private readonly modular: ModularArithmetic = new ModularArithmetic(), private readonly euclid: EuclideanAlgorithm = new EuclideanAlgorithm(), ) {} /** The key pair from two distinct primes and a public exponent coprime to phi. */ keygen(p: number, q: number, e: number): RsaKeyPair { for (const prime of [p, q]) if (!ModularArithmetic.isPrime(prime) || prime > MAX_PRIME) throw new RangeError(`${prime} is not a prime up to ${MAX_PRIME}`); if (p === q) throw new RangeError("the two primes must differ"); const n = p * q; // ▸ n = p times q is public; p and q are not this.tracer?.emit("modulus", { p, q, n }); const phi = (p - 1) * (q - 1); const totient = (p - 1) * (q - 1); // ▸ phi counts the residues coprime to n, and needs p and q this.tracer?.emit("totient", { p, q, phi }); this.tracer?.emit("totient", { p, q, totient }); const gcd = this.euclid.gcd(e, phi); const gcd = this.euclid.gcd(e, totient); const coprime = gcd === 1; // ▸ e must share no factor with phi, or it has no inverse this.tracer?.emit("exponent", { e, phi, gcd, coprime }); this.tracer?.emit("exponent", { e, totient, gcd, coprime }); if (!coprime) throw new RangeError(`${e} shares the factor ${gcd} with phi = ${phi}`); const d = this.euclid.inverse(e, phi).inverse!; const privateExponent = this.euclid.inverse(e, totient).inverse!; // ▸ d is the inverse of e mod phi: euclid, for whoever knows phi this.tracer?.emit("private-key", { e, d, phi, check: (e * d) % phi }); this.tracer?.emit("private-key", { e, privateExponent, totient, check: (e * privateExponent) % totient }); return { publicKey: { n, e }, privateKey: { n, d, p, q, phi } }; return { publicKey: { n, e }, privateKey: { n, privateExponent, p, q, totient } }; } /** m to the e mod n. Untraced: the text methods narrate per letter. */ encrypt(message: number, key: PublicKey): number { if (!Number.isInteger(message) || message < 0 || message >= key.n) throw new RangeError(`a message is a whole number below n = ${key.n}, got ${message}`); return this.modular.pow(message, key.e, key.n); } /** c to the d mod n. */ decrypt(cipher: number, key: PrivateKey): number { return this.modular.pow(cipher, key.d, key.n); return this.modular.pow(cipher, key.privateExponent, key.n); } /** Uppercase letters only, one block each. */ static clean(text: string): string { return text.toUpperCase().replace(/[^A-Z]/g, "").slice(0, MAX_LETTERS); } /** Each letter's code raised to e: textbook RSA, one block per letter. */ encryptText(text: string, key: PublicKey): number[] { return Array.from(text, (letter, index) => { const message = letter.charCodeAt(0); const cipher = this.encrypt(message, key); // ▸ a block to the e, mod n: anyone can do this this.tracer?.emit("encrypt", { index, letter, message, e: key.e, n: key.n, cipher }); return cipher; }); } /** Each block raised to d and read back as a letter. */ decryptText(blocks: readonly number[], key: PrivateKey): string { return blocks .map((cipher, index) => { const message = this.decrypt(cipher, key); const letter = String.fromCharCode(message); // ▸ the block to the d, mod n: only the holder of d can this.tracer?.emit("decrypt", { index, cipher, d: key.d, n: key.n, message, letter }); this.tracer?.emit("decrypt", { index, cipher, privateExponent: key.privateExponent, n: key.n, message, letter }); return letter; }) .join(""); } /** Trial division: 2, then every odd number up to the square root, within the trial budget. */ factor(n: number): Factoring { let trials = 0; const divisors = [2]; for (let d = 3; d * d <= n && divisors.length < MAX_TRIALS; d += 2) divisors.push(d); for (let privateExponent = 3; privateExponent * privateExponent <= n && divisors.length < MAX_TRIALS; privateExponent += 2) divisors.push(privateExponent); for (const divisor of divisors) { trials += 1; const remainder = n % divisor; const hit = remainder === 0; // ▸ the attacker tries a divisor of n this.tracer?.emit("trial", { divisor, n, remainder, hit }); if (hit) return { n, p: divisor, q: n / divisor, trials, found: true }; } return { n, p: null, q: null, trials, found: false }; } /** The attacker's whole job: factor n, recompute phi, invert e. */ crack(key: PublicKey): { factoring: Factoring; privateKey: PrivateKey | null } { const factoring = this.factor(key.n); let privateKey: PrivateKey | null = null; if (factoring.found && factoring.p !== null && factoring.q !== null) { const phi = (factoring.p - 1) * (factoring.q - 1); const totient = (factoring.p - 1) * (factoring.q - 1); const d = this.euclid.inverse(key.e, phi).inverse; const privateExponent = this.euclid.inverse(key.e, totient).inverse; if (d !== null) privateKey = { n: key.n, d, p: factoring.p, q: factoring.q, phi }; if (privateExponent !== null) privateKey = { n: key.n, privateExponent, p: factoring.p, q: factoring.q, totient }; } // ▸ with p and q, phi and then d follow at once this.tracer?.emit("cracked", { n: key.n, p: factoring.p, q: factoring.q, phi: privateKey?.phi ?? null, d: privateKey?.d ?? null, trials: factoring.trials, found: privateKey !== null }); this.tracer?.emit("cracked", { n: key.n, p: factoring.p, q: factoring.q, totient: privateKey?.totient ?? null, privateExponent: privateKey?.privateExponent ?? null, trials: factoring.trials, found: privateKey !== null }); return { factoring, privateKey }; } /** Make the keys, encrypt a short text letter by letter, decrypt it, then attack the public key. */ run(p: number, q: number, e: number, text: string): RsaRun { const keys = this.keygen(p, q, e); const plain = RsaCipher.clean(text); const cipher = this.encryptText(plain, keys.publicKey); const decrypted = this.decryptText(cipher, keys.privateKey); const { factoring, privateKey } = this.crack(keys.publicKey); return { keys, plain, cipher, decrypted, roundTrip: decrypted === plain, factoring, cracked: privateKey }; }}