Whispering in Public

Alice and Bob are at a crowded party. They want to talk in private, but Eve, the eavesdropper and Jon the tabloid journalist are aggressively following them. They may try to whisper, but Jon probably has gadgets that would pick up and record their whispers. They could use an obscure language, but who knows, maybe Eve is clever enough to get an interpreter.

Communicating without Secrets

What can Alice or Bob do? They could use come form of code, be it hand signals, or obfuscated writing. But in order to do that, Alice and Bob needs to decide on what code to use, so that they can decode each other’s messages. Since, Alice and Bob has failed to set it up a-priori, if they try to do it now, Eve and Jon will also get to know the code and they would be able to decipher the messages. Oh, no, is there any hope?

If Alice and Bob could communicate electronically, they could use encryption (see this column, March 19^th). Even if Eve or Jon intercepted all of Alice and Bob’s electronic communication, they would have no idea what they were talking about. But electronic communication would have the same problem. To send an encrypted message, Alice has to encrypt it using a “key”. After Bob gets the message he has to use the same key to decrypt it. How would Alice tell Bob what key she is using? If she tells Bob, Eve will get the key.

What is poor Alice to do? How can she tell Bob the key? This is a problem that baffled many an astute researcher working in the area of secure communication. The problem was termed “non-secret encryption”. That is, how to encrypt something without needing to pass on a secret to the person who will be decrypting it, yet making sure only the recipient can decrypt and the eavesdroppers cannot.

Of course, most of us would have just laughed it off. It is quite clear such a scheme is impossible. If Eve, Jon and Bob hear everything that Alice says, there is no way Bob can get more information than Eve or Jon. Hence, Bob cannot figure out something that the rest of them cannot.

Merkle’s Puzzles

Thankfully, some clever brains did take the problem seriously. There is now evidence that some British researchers working for the intelligence agency figured out some techniques, but they were kept secret. Working independently, Ralph Merkle, a Ph.D. student at Stanford found a method in 1976 that was a first step to solving this puzzle. Merkle’s solution is now known as the “Merkle’s Puzzles”.

Suppose Alice creates a “puzzle”. A puzzle is a difficult problem whose solution is a number. For example, Alice can create the following puzzle: “Find a number that is the largest divisor of 3599”. The answer is 61. Given some time Bob can find the solution. So can Eve and Jon. But Alice can generate hundreds or maybe millions of such puzzles.

And that is what Alice does. She creates a list of a million puzzles, writes then down, numbers each one (from 1 to a million) and sends all of them to Bob. Of course everyone hears (or watches Alice do it). Now Bob picks one of these puzzles at random. Suppose Bob picks puzzle number 29,376. Bob solves that puzzle and finds the answer, which is a number, say K. Bob then uses K to encrypt 29,376 (the puzzle number) and sends the resulting number to Alice. Of course, while Bob was finding the answer to the puzzle, Alice had encrypted all the answers with the corresponding puzzle number and generated a list of all possible responses from Bob. Once Bob responds, Alice looks up the response in her list, and bingo, she realizes which problem Bob picked and what is the value of K.

Now Alice and Bob are in business, they can use K as the secret key to encrypt their communications.

Wait just a minute; since Even and her friends watched this, and know all the puzzles and Bob’s response, they can work it out too? Not so easy. In order to find K, Eve has to solve all the million puzzles and build the list Alice had built. Note that Bob solves only one puzzle and Alice gets to know which puzzle Bob solved. Also note that Alice knows all the answers, and does not have to solve the puzzles (creating the puzzles is a lot easier than solving them). It would take a long time, a million times longer than Bob to find the secret key K. Of course, eventually Eve can break the code, but it would take her a long time, and by then the chat between Alice and Bob may not be useful to Eve any more.

The wonder of Merkle’s puzzles is that it is a clever method by which Alice and Bob cab exchange a secret number, K without Eve or Jon finding K (they find it much later). Merkle’s puzzles does not solve the original problem (non-secret encryption), but points they way to the possibility of a real solution.

Diffie-Hellman Key Exchange:

Later in 1976, Whitfield Diffie and Martin Hellman, (working with Ralph Merkle) found the first published algorithm that really solved the problem is called the Diffie-Hellman key exchange protocol. Today Diffie-Helman is used in many security software systems, especially in VPN and IPSec.

A simple explanation of Diffie-Hellman is as follows. Alice picks two numbers: a rather large prime number N and a random number G (G is less than N). Alice openly tells Bob these two numbers. Then Alice picks yet another random number X and keeps this number secret. Similarly Bob picks a secret number Y. Alice then secretly computes a number A = (G^X mod N). Note that “G^X” is G raised to the power X and “mod N” is the modulus, that is the remainder that is left when a number is divided by N. Similarly Bob computes B = (G^Y mod N).

Alice tells Bob the number A and Bob tells Alice the number B. Of course, Eve gets to know G, N, A and B, but not X or Y. Now Alice computes (B^X mod N) and Bob computes (A^Y mod N). Notice that the value computed by Alice is:

Z = B^X mod N = (G^Y mod N)^X mod N = G^Y^X mod N

The value calculated by Bob is also the same, Z.

Problem is now solved. Alice and Bob now know Z but no one else knows Z. To get Z someone has to know X or Y in addition to G, N, A and B. The others do not have this information. Alice and Bob can now use Z as an encryption key and communicate much to the chagrin of the listeners around them.

Public Key Encryption

Diffie-Helman was a breakthrough, and was the precursor of what is now known as “public-key encryption”. While Diffie-Hellman allows us to exchange keys without the need for secrecy, it cannot do a few other things such as digital signatures. The ultimate invention is the RSA algorithm developed a year later (1977) by Ronald Rivest, Adi Shamir and Leonard Adelman. RSA today is the cornerstone of secure communications and is very widely used. Since the invention of RSA, many other competing algorithms have been found, some are even better than RSA, but nothing has the popularity of RSA.

RSA is a public key algorithm. Public key algorithms have a very strange property. In normal encryption, also called symmetric encryption, if you encrypt a message with a key, you have to use the same key to decrypt it. Not so with public key systems (a better, more intuitive name would be “asymmetric key encryption system”). In these schemes there are two keys, K1 and K2. Anything encrypted with K1 can only be decrypted by K2 (and vice versa, encrypt with K2, decrypt with K1).

Strangely there is no way to derive K1 from K2 or vice versa. Consider this, K1 and K2 are two unique related numbers, that is, for a given K1 there is exactly one K2. However there is no known method to get one from the other. Amazingly such numbers exists, and it is not too hard to find both K1 and K2 in one shot.

Public key (or asymmetric) encryption has amazing applications. I can get two keys, K1 and K2, tell everyone the value of K1 and keep K2 a secret. K1 becomes my “public key”. If you use K1 to encrypt a message, only I can decrypt it. Hence I can get e-mail from you that no one can read (only I can). In addition to communications, public key algorithms are used in digital signatures, secure monetary transactions, digital certificates (ID cards) and a plethora of innovative and highly useful applications.

Endnotes

Showing how RSA works and proving that it really works is rather complex, but quite interesting. One of the simplest proofs I have seen can be found at http://cactus.eas.asu.edu/RSA.htm. Most people, who want to enable others to send them email securely, publish their public keys on a web page. My public key can be found on my home page.

Partha Dasgupta is on the faculty of the Computer Science and Engineering Department at Arizona State University in Tempe. His specializations are in the areas of Operating Systems, Cryptography and Networking. His homepage is at http://cactus.eas.asu.edu/partha