My kingdom for that key

Just for fun, the wife once sent me an email message in code. I was intrigued. How had she done it? Meaning, how was I supposed to decipher and read it? I didn't want to wait to ask her, that would be too easy. Could I figure the code out for myself?

I managed it in the end, experimenting with the few clues the coded message offered. Swelling with code-breaking pride, I promptly made up what I thought was a more difficult code and dashed off a reply. The lady cracked it far faster than I had hers. So much for pride.

Of course, codes have long been used for more serious purposes than idle husbands trying unsuccessfully to outwit alert wives. Cryptography, the science of encoding and decoding messages, is a rigorous scientific pursuit by itself. In wartime, much energy goes into two efforts: making sure your communication is secure and trying to decode the enemy's. This is so crucial that the side that does a better job will usually win the war.

Till 1976, coding relied on secret keys. You use such a key to convert the message, usually called "plaintext" by cryptographers, into the "ciphertext" that is transmitted. At the other end, the same key is used to decode the ciphertext back into plaintext. The key can be a mere transposition of letters ("b" for "a", "c" for "b" and so on), variations of which are what my wife and I used; or a mechanism using pages in some agreed book; or any number of other possibilities.

But here's the crux of such a method: for communication to work, both parties have to agree on a key.

This turns out to be the flaw in the whole system. To thwart people intent on breaking the code (cryptographers are known to call them "attackers"), keys must be relatively complex, and must themselves be communicated between sender and receiver. That means they can get stolen or lost, or counterfeited by the enemy to confuse, or they may even arrive after the ciphertext itself. Sender and receiver have to find a communication channel they can trust -- a secure phone line, a reliable courier -- merely to get the key transmitted. How do you get around these problems?

In 1976, Whitfield Diffie and Martin Hellmann of Stanford University answered that question by attacking its root: by doing away with the idea of secrecy itself. They proposed a public key coding system, in which the sender and receiver never have to agree on a secret key. Two years later, three researchers at MIT, Ronald Rivest, Adi Shamir and Leonard Adleman, demonstrated such a public key system; it has become known as the RSA (Rivest-Shamir-Adelman) system.

Without a doubt, the public key system is the most significant and influential advance in modern cryptography. In 2002, Rivest, Shamir and Adleman were awarded the Turing Award -- computer science's greatest prize -- for the RSA system.

Public key systems rely on a simple mathematical idea: some functions are much easier performed in one direction than the other. For example, it's not too difficult to figure out that when you multiply 7, 11 and 13, the answer is 1001. But what if I asked you: "Which three distinct numbers produce 1001 when multiplied?" That harder problem will take you, or even a computer, much longer to solve.

With numbers much larger than 1001, this time difference becomes significant. Eventually, the slower direction of these "one-way functions" takes so long that it is effectively impossible to solve. If you took two prime numbers that are each 100 digits long, a computer could multiply them quite easily to produce another number about 200 digits long. But if you gave it that 200-digit number and ask it to find the two 100-digit factors, how long would it take? Not seconds or minutes, but perhaps years. Centuries. In effect, this is impossible.

So RSA works something like this. Let's say Shabnam wants to receive coded messages. She picks two secret prime numbers, preferably big ones, and multiplies them. She does some further manipulation to come up with two more numbers. She announces that her personal public key is the product of the primes and one of these two additional numbers. The third number remains her private key.

Monideepa, who wants to send Shabnam a coded message, uses Shabnam's public key in a formula to encrypt her plaintext. When Shabnam receives Monideepa's ciphertext, she uses her private key in another formula that restores the plaintext. Of course, Shabnam never reveals the two secret primes to anyone.

In theory, this is not a secure system: given an indefinite amount of time, attacker Pappu could take Shabnam's public key and calculate the two numbers that produced it. But of course, Pappu doesn't have indefinite time. Long before he found Shabnam's primes, he would be dead. So Shabnam's key is safe, Monideepa's message cannot be read; the RSA system is secure.

This was a giant leap: RSA opened up the possibility of cheap, yet completely secure communication available to all.

Which, of course, was a red flag to governments around the globe, many of whom want to listen in on what their citizens, or other governments, say to each other. In the USA, this governmental unease over public key cryptography led to an effort to produce a government-approved coding system, based on a secret encryption algorithm called Skipjack. The US government proposed that Skipjack would be built into communication devices that needed to be secure.

Naturally this met with much outrage and eventually the US government declassified Skipjack.

And I've always thought it a delicious aside to the whole RSA story that within a day -- yes, a day -- two researchers had substantially decoded Skipjack itself, and one of those two researchers was Adi Shamir.

Meanwhile, I have here two 100-digit primes. One of them is 4557898123798712347234898920109927481232347798726198764691200283623897221029374283764823764138973668. ... Hmm, what'd I do with the other one?