Public-key cryptography

Here is a puzzle. You want strangers to be able to send you secret messages, but you have never met them and share no password. How can they lock a message so only you can open it?

The clever answer is to hand out an open padlock. You keep the only key. Anyone can take a copy of your padlock, snap it shut on a box, and send it to you. Even the person who locked it cannot open it again. Only your key can. That is public-key cryptography: the lock is public, the key is private.

In the real thing the padlock and key are numbers, and the lock works because of a lopsided piece of maths. Multiplying two big numbers together is quick. But going backwards, taking the answer and finding which two numbers were multiplied, is fiendishly hard once the numbers are huge. Your public lock is built from a giant product; your private key is the secret of what was multiplied to make it.

This quiet trick is what keeps the internet safe. Every time you see a padlock icon in your browser, some version of this is scrambling your passwords and card numbers so that only the right computer can unscramble them.

The heart of it is a one-way street, what cryptographers call a trapdoor function: easy to walk forwards, practically impossible to walk back, unless you know a secret shortcut. Multiplying two large primes \(p\) and \(q\) to get \(N = pq\) is the forward direction, fast even for numbers hundreds of digits long. Factoring \(N\) back into \(p\) and \(q\) is the hard direction, with no known quick method.

RSA turns this into a working cipher using modular arithmetic, which is just arithmetic that wraps around like a clock. You build a public key from \(N\) and a number \(e\), and a private key \(d\) that only you can compute because you know \(p\) and \(q\). To send you a message number \(m\), the sender computes the ciphertext

\[ c = m^e \bmod N, \]

raising the message to the power \(e\) and keeping the remainder after dividing by \(N\). To read it, you compute

\[ m = c^d \bmod N, \]

and the message reappears. The exponents \(e\) and \(d\) are chosen so that this round trip always lands back on \(m\). The demo above does exactly this with small numbers you can check by hand.

An eavesdropper watching the line sees \(c\), \(N\) and \(e\), all public. To recover \(m\) they would need \(d\), and to get \(d\) they would need to factor \(N\) back into its primes. For a large enough \(N\) that is the wall no one can climb, so the message stays secret in plain sight.

Why the round trip works. Choose primes \(p, q\), set \(N = pq\), and let \(\varphi(N) = (p-1)(q-1)\), Euler's totient, the count of numbers below \(N\) that share no factor with it. Pick a public exponent \(e\) coprime to \(\varphi(N)\), and let \(d\) be its inverse, so \(ed \equiv 1 \pmod{\varphi(N)}\). Then by Euler's theorem \(m^{ed} \equiv m \pmod{N}\) for essentially every message, which is exactly why decrypting an encrypted message returns the original. Computing \(d\) needs \(\varphi(N)\), and computing \(\varphi(N)\) needs the factors of \(N\); that is the trapdoor.

Security rests on an assumption, not a proof. Nobody has proven that factoring is genuinely hard. RSA's safety rests on the empirical fact that, despite centuries of effort, no fast classical factoring algorithm is known. This ties into the broader landscape of computational hardness that also motivates the P versus NP question. If someone found a fast factoring method, or proved unexpected shortcuts exist, much of today's encryption would fall.

More than secrecy. The same machinery does two other essential jobs. Diffie-Hellman key exchange lets two strangers agree on a shared secret over an open channel, using the difficulty of the discrete logarithm rather than factoring. And running RSA in reverse, signing with the private key and verifying with the public one, produces digital signatures, which prove a message really came from the keyholder and was not altered. Secrecy, key agreement and authentication all come from the same asymmetric idea.

The quantum threat. Peter Shor showed in 1994 that a large quantum computer could factor integers and crack discrete logarithms efficiently, which would break RSA and Diffie-Hellman outright. Machines that large do not yet exist, but the risk has driven a shift toward post-quantum cryptography, based on problems like lattices that are believed hard even for quantum computers. The lock you can hand out is not going away; the maths inside it is being replaced.