Cairn
algorithms · cryptography · O(log n) time to encrypt/decrypt (one modular exponentiation each); recovering the private key from the public one is exactly as hard as factoring n, no known polynomial algorithm

↩ back to Cryptography

RSA Encryption

The site's second Cryptography entry, and the first that four other pages already promised was coming without ever linking to it. Modular Exponentiation computes gx mod n cheaply — the exact operation RSA uses to encrypt and decrypt, and that page names "RSA key generation, Diffie–Hellman" as its own real-world motivation. Extended Euclidean Algorithm says outright that "modular inverses are how RSA key generation … divide." Miller–Rabin Primality Test opens with "RSA key generation needs to know whether a randomly chosen 300-digit odd number is prime." Pollard's Rho Algorithm names the same system from the other side: "RSA key generation needs the first kind of test [primality] on its own huge candidates; an attacker trying to break a small or badly-generated key needs the second [factoring]." RSA, published by Ron Rivest, Adi Shamir, and Leonard Adleman in 1977, is the algorithm all four of those pages were pointing at.

It sits next to Diffie–Hellman Key Exchange as this category's second entry, and the two make a natural pair. Both rest on a direction that's cheap to compute and believed hard to reverse — but on two different hard problems. Diffie–Hellman rests on the discrete logarithm (see Baby-Step Giant-Step); RSA rests on integer factorization (see Pollard's Rho). Nobody has proven either direction is actually hard in either case — both algorithms, and most of the internet's practical security, rest on decades of nobody finding a fast way to do either one.

Try it

Pick a (p, q) pair — the second one is the exact n = 8,051 that Pollard's Rho's own demo already factors in 3 steps. Changing the preset regenerates a fresh public/private key pair. Type a message, click Encrypt, then Decrypt to see the round trip. Then click Eve: crack it — she gets only the public key and the ciphertext, never the private exponent shown below, and factors n herself with the same tortoise-and-hare search Pollard's Rho's own demo runs.

Pick a preset, type a message, and click Encrypt.

Why it works

Key generation picks two primes p, q, sets n = pq and φ(n) = (p−1)(q−1) (Euler's totient of n), then picks a public exponent e coprime to φ(n) and computes the private exponent d as the modular inverse of e mod φ(n) — so by construction, ed ≡ 1 (mod φ(n)), meaning ed = 1 + kφ(n) for some integer k. Encryption is c = me mod n; decryption is cd mod n. Substituting:

cd = (me)d = med = m1 + kφ(n) = m · (mφ(n))k (mod n)

Euler's theorem says mφ(n) ≡ 1 (mod n) whenever gcd(m, n) = 1 — the same idea Modular Inverse via Fermat's Little Theorem uses in the special case where the modulus is a single prime (there, φ(p) = p−1 and the theorem is Fermat's original, narrower statement). That collapses the whole expression to m · 1k = m (mod n) — decryption returns exactly the original message, for any m that shares no factor with n. In practice m fails that condition only if it happens to be a multiple of p or q, vanishingly rare once those primes have hundreds of digits.

Reference implementation

Key generation, using the exact modular-inverse routine Extended Euclidean Algorithm already documents (see Pitfalls for why that page's routine is required here, not Fermat's):

function extgcd(a, b) {                 // returns [gcd, x, y] with a*x + b*y = gcd
  if (b === 0) return [a, 1, 0];
  const [g, x1, y1] = extgcd(b, a % b);
  return [g, y1, x1 - Math.floor(a / b) * y1];
}

function modinv(a, m) {
  const [g, x] = extgcd(a, m);
  if (g !== 1) return null;             // a and m share a factor — no inverse exists
  return ((x % m) + m) % m;
}

function modpow(base, exp, mod) {       // same square-and-multiply as Modular Exponentiation
  base = ((base % mod) + mod) % mod;
  let result = 1;
  while (exp > 0) {
    if (exp & 1) result = (result * base) % mod;
    base = (base * base) % mod;
    exp = Math.floor(exp / 2);
  }
  return result;
}

function keygen(p, q) {
  const n = p * q, phi = (p - 1) * (q - 1);
  let e = 3;
  while (gcd(e, phi) !== 1) e += 2;      // smallest workable public exponent
  const d = modinv(e, phi);
  return { n, e, d };                    // publish (n, e); keep d, p, q secret
}

const encrypt = (m, e, n) => modpow(m, e, n);
const decrypt = (c, d, n) => modpow(c, d, n);

Eve's crack button runs the identical tortoise-and-hare search Pollard's Rho's own reference implementation uses to factor n — she never reads d, or even p and q, off this page. Once she has a factor, keygen's own modinv call above hands her a private exponent that decrypts the real ciphertext just as well as the one actually kept secret.

Pitfalls

A small enough modulus makes factoring cheap — demonstrated, not just asserted. The second preset's n = 8,051 is the exact number Pollard's Rho's own page already factors into 83 × 97 in 3 tortoise-and-hare steps with its first constant — this page's Eve button runs that same search and gets the same result, every time, because it's the same arithmetic on the same number. Real deployments use primes with hundreds of digits specifically so that same heuristically O(n1/4) search, exponential in the digit count, stays computationally infeasible rather than instantaneous — the math doesn't change between the two cases, only the size of n does, exactly the same lesson Diffie–Hellman's own small-modulus pitfall draws from a different hard problem.

Textbook RSA — exactly what this page demonstrates — is deterministic and multiplicative. The same message under the same key always produces the same ciphertext, and the structure leaks further than that: encrypting two messages separately and multiplying the ciphertexts gives exactly the encryption of their product. Checked directly at this page's first preset (n = 3,233, e = 7): encrypting 5 gives 533, encrypting 7 gives 2,361, and 533 × 2,361 mod 3,233 = 776 — exactly modpow(5 × 7, 7, 3233) = 776 too, no decryption required to see it. Real deployments pad the message (OAEP) before encrypting specifically so this multiplicative shortcut, and the determinism it rides on, never applies to real ciphertexts — a missing piece this page's bare arithmetic was never designed to supply, the same way Diffie–Hellman's own arithmetic can't supply authentication.

Fermat's Little Theorem's modular-inverse shortcut can never compute RSA's private exponent — not a rare edge case, a structural impossibility. That page's method needs a prime modulus. Here the modulus for the inverse is φ(n) = (p−1)(q−1), and for any two odd primes p, q, both p−1 and q−1 are even — so φ(n) is always divisible by 4, never prime. This page's own keygen above uses Extended Euclidean's general method for exactly this reason, not by preference: it's the only one of the two that has ever applied here.

Complexity

Time: each encryption or decryption is one modular exponentiation, O(log e) or O(log d) multiplications via the same square-and-multiply technique Modular Exponentiation uses. Key generation's real cost in practice isn't this page's toy arithmetic — it's finding two random primes hundreds of digits long in the first place, the exact repeated-candidate-testing cost Miller–Rabin documents. Multiplying numbers that large is itself nontrivial; Karatsuba Multiplication names "RSA-scale numbers" as exactly the regime where its own subquadratic trick starts to pay off. Space: O(1) beyond the numbers themselves. Security: recovering d from the public (n, e) alone is computationally equivalent to factoring n — the best known general algorithms (the general number field sieve and its relatives) are sub-exponential, far short of polynomial, the same open-problem shape as Diffie–Hellman's discrete-log assumption, resting on a different problem. Real deployments also use the Chinese Remainder Theorem to roughly quadruple decryption speed by working mod p and mod q separately instead of mod the full n — a genuine further optimization, not built here (see Chinese Remainder Theorem's own page, which names this exact shortcut).