The Science of Secrecy - Part II

This blog was posted in my workplace blog on 06-FEB-2008

~~~***~~~

Note : Part I is here. You don't have to read it, if you know the basics of cryptography.

Part I was about how different encryption systems evolved and at the end how developments in cryptography came to a stand-still because of the problem of key distribution:

No matter how strong the encryption system is, the unavoidable problem of key distribution weakens it. For 2000 years, this was considered to be an axiom of cryptography - an indisputable truth.

As we saw in part I, if Alice wants to send her secret message in an iron box to Bob, she has to lock it with a key. Now she has to send the key across to Bob. This key, if captured, can help to open the box to get the secret message. So this key has to be secretly sent. How? another box? another key for this new box? so, another problem of sending the new key arises! Key Exchange seems unavoidable! - or is it?

Let me answer it for you. Key Exchange can be avoided! And the secret message can be passed. There is an ingenious solution to it. Can you guess it? Take it as a puzzle & work it out.

## Spoiler : Answer follows ##

Take this new scenario : Alice locks the box containing the secret message with her own lock(with her own key) and sends it to Bob. Now Bob receives it and locks it again with his own lock(with his own key) and sends it back to Alice. Alice opens her lock with her key and sends the box back to Bob. Now Bob opens his lock and takes out the message. TADAAN! No Key Exchange at all. But Bob has got the secret message.

The implications of this small puzzle were enormous. Even though it has a practical flaw when it is applied to actual encryption, this concept of double encryption was an inspiration to avoid key exchange. This was exploited by 2 brilliant mavericks who were living in 2 extremes of America, destined to unite to solve this mighty problem.

Ladies(???) and Gentlemen, presenting...

The Diffie-Hellman Key Exchange

Whitfield Diffie was born in 1944 in NewYork and studied mathematics at MIT [Hey, even I studied in MIT! ;-)] graduating in 1965. He took up a series of jobs related to computer security and grew into a truly independent and freethinking cryptographer. He was particularly interested in the key distribution problem and he knew that the one who solved it would go down in history as on of the all-time greatest cryptographers. He was very fore-sighted to visualise the growth of an information superhighway (Internet) and the number of communications needed and thus the need for privacy. Key distribution was the only problem stopping the concept of totally private e-mails.

Diffie once visited IBM's Thomas J. Watson lab to give a talk on strategies for attacking the key distribution problem. And there he came to know about Martin Hellman who had earlier given a talk on the same topic. Diffie realised that Hellman was the only soul on this planet who seemed to share his passion. So Diffie got in his car and started a 5000 km journey to the west coast to meet Martin Hellman, a professor at Stanford Univ, CA. This alliance would become one of the most dynamic partnerships in cryptogrpahy.

Hellman had been working on the key distribution problem but had failed a lot of times to solve it. He was struggling badly to keep up his interest. And Diffie's association was like a breath of fresh air for him. They were then joined by Ralph Merkle, another researcher whom Simon singh calls an "Intellectual refugee".

Hellman says of Ralph Merkle (I found this inspiring. so I'm putting it here):

"Ralph, like us, was willing to be a fool, and the way to get to the top of the heap in terms of developing original research is to be a fool, because only fools keep trying. You have idea number 1, you get excited and it flops. then you have idea number 2, you get excited and it flops. Then you have idea number 99, you get excited and it flops. Only a fool would be excited by the 100th idea, but it might take 100 ideas before one really pays off. Unless you're foolish enough to be continually excited, you won't have the motivation, you wont have the energy to carry it through. God rewards fools."

Diffie,Helman and Merkle set out to find a solution for this problem. The problem with the solution of the above iron box puzzle is that, the box would open if it is locked and unlocked in any order. That is, If the box is closed and locked with 10 locks, the box will still open if the locks are opened in any order.

But for actual encryption it is not the same. The order is of supreme importance. Any encryption system should obey the "last on, first off" principle. Lets see how order affects encryption and key exchange:

Alice encrypts, Bob encrypts, Bob decrypts, Alice decrypts(Correct order but doesnt avoid key exchange).
Alice encrypts, Bob encrypts, Alice decrypts, Bob decrypts(Incorrect order but avoids key exchange).

But the use of incorrect order is against the "last on, first off" principle. (The fact that "Encryption using an incorrect order is Invalid" can be easily proved. But it will lenghten this already long blog). So Diffie, Hellman and Merkle set out to find another solution.

They had great hope in a particular type of mathematical functions called one-way functions. Most functions in maths are two-way functions or reversible functions. Ex: multiplication (example below). But one-way functions are irreversible. And one field of maths which is rich in these one-way functions is modular arithmetic. It's nothing but the modulus funtion. Let's understand two-way and one-way functions with an example:

Two-way:

consider a function f(x) = 9x (this is a simple multiplication function). if someone says that they passed a certain value 'x' into this function '9x' and if they got the result as 63, can you find out 'x'?

Yes, you can. 9x = 63. x= 63/9 = 7! If the result is provided, you can find the input value. This is the property of Two-way or reversible functions.

One-way:

Consider a function f(x) = 9x (mod 4) . If someone says that they passed a certain value 'x' into this function and if they got the result as 3, can you find out 'x'?

No, you cannot! Because:

9 x 3 (mod 4) = 27 (mod 4) = 3.
9 x 7 (mod 4) = 63 (mod 4) = 3.
9 x 11(mod 4) = 99 (mod 4) = 3.
.
.
And It goes on... The input value could be any of 3,7,11 etc...

Having found such a one-way function, how did they find out a real working solution to the key exchange problem?

Diffie - Hellman - Merkle Method

Note: Please don't runaway on seeing some math. It's very easy to understand the beauty of this method.

They chose a general one way function - Y^x(mod P). Alice and Bob must choose values for Y and P. The function, Y and P could be known to all(even a codebreaker) and their secrecy does not matter to the security of communication. So they have chosen Y = 7 and P = 11. So their function is 7^x(mod 11).

Alice		Bob
Stage 1	Alice chooses a number say 3(named A) & keeps it as a secret	Stage 1	Bob chooses a number say 6(named B) & keeps it as a secret
The secrecy of A and B is the foundation for secure communication b/w Alice and Bob
Stage 2	Now Alice works out: 7A(mod 11) = 73(mod 11) = 343(mod 11) = 2	Stage 2	Now Bob works out: 7B(mod 11) = 76(mod 11) = 117,649(mod 11) = 4
Stage 3	Alice calls her number M, So M = 2. She sends this across to Bob.	Stage 3	Bob calls his number N, So N = 4. He sends this across to Alice.
This swap is the most crucial thing. Eve can intercept M and N as the communication is not secure.
Stage 4	Now Alice works out: NA(mod 11){note: It's N power A} = 43(mod 11) = 64(mod 11) = 9	Stage 4	Now Bob works out: MB(mod 11){note: It's M power B} = 26(mod 11) = 64(mod 11) = 9
The Key! Miraculous! Alice & Bob have the same number 9! The secret key!

Lets look at it from Eve's Point of View: She knows 7^x(mod 11) and then she knows M and N. But to work out the key(in step 4), she needs A & B, which are Alice and Bob's secret. And she cannot find them back in step 2 as it is a one-way funtion! Aah.. the beauty of mathematics! In practise, the values of Y, P, A and B are very large.

In 1976, for the first time ever, to the astonishment of many cryptoexperts, Diffie, Hellman and Merkle demonstrated how they could exchange a secret via public discussion! This completely baffled the world and is considered one of the most counter-intuitive discoveries in the history of science. This discovery rewrote the rules of encryption. It is to be noted that this discovery was made by this trio when the military and big business corporations were funding a lot of money for classified research projects to solve the key distribution problem.

Alas, their solution posed a practical inconvenience. Their key exchange method required both Alice and Bob(sender and receiver) to be present at the time of key exchange. Because they had to select a value of A and B each time and work out the other things. This method lacked spontaneity as Alice could be asleep in one end of the world and Bob could send her an important message from the other end. This could not be used for emails for the lack of spontaneity and thus it was practically unusable.

But the trio did not lose hope. They tried to solve this problem of lack of spontaneity. And, as a stroke of sheer brilliance, Diffie had a Eureka moment. At home, just as he was about to fetch himself a can of coke, he discovered a totally foolproof system. Diffie proposed the concept of Asymmetric key encryption or Public key cryptography.

It was a very simple concept. Alice(or anyone) had a pair of keys - the public key and the private key. She can publish her public key in a directory for people(Bob) to use. And she had her private key as a secret to herself. Now the trick is, Bob (or anyone) can encrypt his message with the public key. Once the encryption is done, the ciphertext can be deciphered one and only with the private key!(which only Alice knows).

For the first time ever, a message is encrypted by one key(public key) and decrypted by another(private key). Note: It's obvious that even the public key CANNOT decrypt the message. Asymmetric key encryption is widely used for today's information security.

Diffie proposed this as a theoretical concept. And the trio worked hard to find a special kind of one-way function that could help them encrypt with one key and decrypt with another! But their efforts ended in vain as they could not find one. But still, they shattered a myth and proposed D-H-M key exchange which was workable but imperfect and Asymmetric key encryption which was perfect and unworkable! {They still remain my heroes! Diffie now works for SUN Microsystems and his disciple works for Infosys Tech Ltd. (..ahem.. that's me.. ;-) }

So the hunt for the special one-way function began and it was another perfect partnership of 3 brilliant researchers named Rivest, Shamir and Adleman, that gave the world its information secrecy!

Get ready to see yet another beauty of mathematics in the next part! :-)

External Links:

http://en.wikipedia.org/wiki/Diffie-Hellman_key_exchange

Disclaimer : I have borrowed a lot of sentences verbatim from "The Code Book". So, credits to Simon Singh too.