RSA by hand

Choose two primes, press Build keys and encrypt, and read the steps. The page builds a public key anyone may use to lock a message, and a private key only you can use to unlock it. Every step is ordinary arithmetic with remainders. The only secret is which two primes you started from.

prime p prime q public exponent e (odd) message m (a number below n)

What's going on

Multiply the primes: n = pq. Count the numbers below n that share no factor with n: φ(n) = (p − 1)(q − 1). Pick any e with no common factor with φ(n). Then find d, the number that undoes e: ed leaves remainder 1 when divided by φ(n). The pair (n, e) is public. The number d is private.

To encrypt m, compute c = m^e mod n. To decrypt, compute c^d mod n, and the original m comes back. That works because of Fermat's little theorem, extended to two primes: raising anything to the power ed is the same as raising it to the power 1, as long as you only keep remainders mod n.

The powers look enormous, but nobody computes them in full. Repeated squaring keeps every intermediate result below n, and needs only about twice as many multiplications as the exponent has binary digits. The tables above show every one of them.

Why is it safe? Anyone can see n. To find d they need φ(n), and to find φ(n) they need p and q. With two-digit primes, trial division cracks it in seconds. Real keys use primes with about 300 digits each, so n has about 600 digits, and no known method factors that in the lifetime of the universe. Multiplying is easy. Unmultiplying is not.

Sheets: RSA: a lock anyone can close and Fermat's little theorem.