How RSA locks and unlocks a message

RSA lets you publish a key anyone can use to lock a message, while only you hold the key that unlocks it. Both are the same operation — raise a number to a power and keep the remainder — and the trick is in how the two powers are chosen.

Two keys, one operation

A message is a number M smaller than a fixed modulus n. To encrypt, raise M to a public power e and take the remainder mod n; that is the ciphertext C. To decrypt, raise C to a secret power d, mod n again. The public key is (e, n); the private key is (d, n). Same arithmetic both ways — the paper notes one piece of hardware does both jobs.

Why it matters

Every classical cipher the paper lists needed the parties to share a secret key first, by courier or another private channel — the key distribution problem. Here the encryption key can sit in a public directory. Anyone can lock a message to you; only you can open it. And because decrypting an unencrypted message also "makes sense", the same machinery gives a signature: apply your private power to a message, and anyone can check it with your public power.

Why the second power undoes the first

The modulus n is the product of two primes, p and q. Let φ(n) = (p − 1)(q − 1). The identity due to Euler and Fermat says that for any M with no factor in common with n, M^φ(n) leaves remainder 1 when divided by n. So if e·d ≡ 1 (mod φ(n)) — one more than a multiple of φ(n) — then M^e·d = M^kφ(n)+1 = (M^φ(n))^k · M ≡ M. The paper extends the argument to every M from 0 to n − 1 by checking modulo p and q separately, so encryption is a permutation of the messages and decryption its exact inverse.

The paper's own small example: p = 47, q = 59, so n = 2773 and φ(n) = 46 · 58 = 2668. The authors pick d = 157 and run Euclid's algorithm to find its inverse, e = 17; check: 17 · 157 = 2669 = 2668 + 1. Their message block M = 920 encrypts to 920¹⁷ mod 2773 = 948, and 948¹⁵⁷ mod 2773 = 920 again. Large powers are cheap: the paper computes them by repeated squaring, one per bit of the exponent.

What the attacker holds

An eavesdropper has n and e. To find d she needs φ(n), which comes from p and q. With the factors, everything falls out in a few lines — so the scheme rests on keeping them hidden inside n. The paper shows the obvious attacks — computing φ(n), or finding d by another route — are each at least as hard as factoring n, because any of them would let you factor n. It does not prove factoring is hard, and says so: factoring "is not provably difficult", and the security "rests in part" on that difficulty. The authors recommend primes of about 100 digits, so that n has 200, and note that no known algorithm factored numbers of that size in reasonable time.

In short

RSA encrypts by raising a message to a public power modulo n and decrypts with a private power. It works because the powers multiply to one more than a multiple of φ(n), and the identity due to Euler and Fermat returns the original message. Anyone who can factor n can find the private power. Whether that is the only way in is a conjecture the authors state but cannot prove — the paper says outright that factoring large numbers is "not provably difficult" — and they leave breaking the system as a challenge to the reader.