A Primer on Cryptography

Cryptography is nearly as old as written language itself, invented to address the age-old question: How can I communicate with my friend without anyone else knowing what passes between us?

People as diverse and isolated from each other as the Tibetans and the Irish have used cryptography, often independently discovering the same tricks for hiding their words. It must be concluded that cryptography answers some fundamental human need for privacy in the midst of social life.

Let us imagine that Popeye the Sailor Man has an important message for Olive Oyl, which he does not wish his rival, Brutus, to read. Popeyes message is: I LOVESK YA, OLIVE this is called the plaintext. Popeye can encipher his message to Olive in any number of ways. He can write it backwards: EVILO AY KSEVOL I, but this is a simple ciphertext and so is unlikely to fool Brutus.

Popeye can use a Caesar alphabet, used by Julius Caesar to fool his barbarian enemies, in which each letter is represented by a different letter, and no letter represents itself. A typical Caesar alphabet moves each letter three places down the alphabet, so: L ORYHVN BD ROLYH. But Brutus may catch wise to this, too, especially if he recognizes the patterns in the English language and figures that the stand-alone letter is I or A.

Popeye can make Brutus life harder by moving the letters into groups of four or six, so as to disguise the beginnings and endings of words: LORY HVNB DROL YH, harder still by rotating it and beginning with the key letter O : RYHV NBDR OLYH LO or maddeningly difficult by varying the key every four letters: LORY KYQE JXUR HQ and introducing nulls letters that dont mean anything: LORA YKYQ EJAX URHQ. The more randomly Popeye varies the key, the harder it will be for Brutus to analyze the cipher. If Popeye is really smart, he will bury the message to Olive in his grocery list, hence:

YVOT GINV OVKZ UHGI IUJE TGSO ZKOR UBKY QEGU ROBK GYVO XOT

Did you get it? Its only enciphered once and you know some of the words youre looking for (big hint, what does Popeye have on his grocery list?) These techniques were already well known in Europe by the time of the Renaissance, and every prince had a staff of cryptographers who sat racking their brains trying to decipher the other sides messages. More than once, superior cryptography has meant the difference between victory and defeat in war.

In the Second World War, the Germans developed a code-cipher system of such complexity that the British dubbed it ENIGMA, and the efforts to solve it, led by Alan Turing and yes, they eventually did solve it, led to the development of the first computers. With a computer, which expresses letters as a series of ones and zeroes, Popeye can scramble his message to Olive with a long (128-bit) key so that Brutus could never decipher it, even with his own computer.

What weve described in the Popeye scenario is called symmetric cryptography it assumes that Popeye and Olive have been able to agree on a key without Brutuss knowledge. But what if Popeye is on a trip to New Jersey and his friend Wimpy in Brooklyn needs to warn him of Brutuss dastardly plan to corner the world spinach market? Theres no way for them to exchange a secret key, because Brutus has all the phone lines tapped. What are they to do?

The answer to their problem is public-key cryptography, invented in 1976 by Whitfield Diffie and Martin Hellman. Wimpy can use Popeyes public key, usually a series of 310 digits that Popeye can fit on his business card, to encrypt his message so that Brutus can never read it. Only Popeye, who holds the private key, can read the message. By using public key cryptography, Popeye has ensured that his friends can contact him as needed without having to pre-share one key per friend.

In the most commonly used public-key cryptography system, invented by Ron Rivest, Adi Shamir, and Len Adleman in 1977, both the public and the private keys are derived from a pair of large prime numbers according to a relatively simple mathematical formula. In theory, it might be possible to derive the private key from the public key by working the formula backwards. But only the product of the large prime numbers is public, and factoring numbers of that size into primes is so hard that even the most powerful supercomputers in the world cant break an ordinary public key.

So far, that is. The tricky thing about cryptography is that its no one has ever proven that a practical cipher is undecipherable. Any such proof would be a fundamental mathematical breakthrough that would have consequences far beyond cryptography. Someone out there may come up with a way to factor large numbers easily that would allow Brutus to intrude upon the domestic bliss of Popeye and Olive.

Thats why the cryptographers at Microsoft Research are constantly trying to break their own cryptosystems, and to come up with clever new ones. Public key and symmetric cryptography are the underpinnings of the emerging ecommerce infrastructure, as well as an indispensable component in the protection of intellectual property such as software, books and music. Theres a lot more riding on cryptography than the love letters of Popeye and Olive.