PLATFORM17

RSA

CIPHER

WHEN

FROM

STATUS

Diffie and Hellman had imagined a lock with two different keys: one to close it, which you could hand out to the whole world, and one to open it, which you kept. A few months later three researchers at MIT built one out of prime numbers. Multiplying two primes together is easy; splitting the result back into its two primes is, as far as anyone knows, very hard. RSA hangs everything on that difference.

The machine

A padlock and its key

Choose two primes p and q. Their product n, together with a small number e, is the padlock: you can give it to anyone, and anyone can use it to lock a message to you. The key d is worked out from p and q, and without them nobody can find it. Type a word, snap the lock shut, then open it with the key. Real keys use primes of about 300 digits each; these are small enough to follow by hand.

Break it yourself

A telegram in numbers

A message has been locked with someone's public key, and the key is printed right on it: n and e. To read it you need d, and to get d you need the two primes inside n. With a four-digit n that is a job for an afternoon with a pencil. Find a divisor on the sieve, rebuild the private key, and type it in: the board decrypts itself.

ARRIVED · CIPHER CRACKED

The story

Ron Rivest, Adi Shamir and Leonard Adleman were young researchers at MIT's Laboratory for Computer Science when they read the Diffie-Hellman paper. For months Rivest and Shamir proposed ways to build a public-key lock and Adleman, a number theorist, found ways to break them. According to the usual telling, the idea that worked came to Rivest one night in April 1977, and he had it written up by morning. The initials of the three gave it its name.

Martin Gardner described it in his "Mathematical Games" column in Scientific American in August 1977. The column printed a challenge: a message locked with a 129-digit n, with a 100-dollar prize for reading it, and Rivest's estimate that factoring a number that size would take some 40 quadrillion years. It took seventeen. In 1994 a team led by Derek Atkins, Michael Graff, Arjen Lenstra and Paul Leyland split up the factoring among about 600 volunteers and their computers over the internet. The message read "THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE" (an ossifrage is a bearded vulture).

Four years too late

In 1997 GCHQ revealed that Clifford Cocks, a young mathematician who had joined it in 1973, had found essentially the same scheme within weeks of starting work, after hearing of James Ellis's idea of "non-secret encryption". Computers of the time were too weak to use it, and it stayed secret.

MIT patented RSA, and the patent ran in the United States until 2000. By then RSA was everywhere: in web browsers, bank cards, software updates and email signatures. Signing is the lock run backwards: you transform a message with your private d, and anyone can check it with your public e. Rivest, Shamir and Adleman received the Turing Award for it in 2002.

How it was broken

Nobody has broken RSA itself, only RSA keys that were too short. The record so far for a number of this kind is 250 digits (829 bits), factored in 2020 with a great deal of computer time. Today's keys are 2048 bits or more, about 617 digits, far out of reach of any known method on ordinary computers.

The weak points have been elsewhere: primes chosen with bad random numbers (in 2012 researchers found many devices on the internet whose keys shared a prime), messages sent without proper padding, and leaks of timing or power use. A large enough quantum computer running Shor's algorithm could factor n quickly, which is why new public-key methods are being brought in.