Game of Life

I am fascinated by the idea of John Conway’s Game of Life. Also fascinating is the term used to describe it – “a zero-player game”. I guess all of us are familiar with zero-player games -  at least those who have built a house with packs of playing cards, stepped back a few feet and have rolled a marble at its foundation to see how it goes crashing down; or those who arranged a long trail of matchboxes and toppled one to set the tumbling in motion (like the dominoes in V for Vendetta). There is some kind of godliness in doing an initial set-up of a system, in kicking it off and in sitting and watching how it pans out.

Conway’s Game of Life is a system with simple rules  -

The universe of the Game of Life is an infinite two-dimensional orthogonal grid of square cells, each of which is in one of two possible states, alive or dead. Every cell interacts with its eight neighbours, which are the cells that are horizontally, vertically, or diagonally adjacent. At each step in time, the following transitions occur:

1. Any live cell with fewer than two live neighbours dies, as if caused by under-population.
2. Any live cell with two or three live neighbours lives on to the next generation.
3. Any live cell with more than three live neighbours dies, as if by overcrowding.
4. Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

The initial pattern constitutes the seed of the system. The first generation is created by applying the above rules simultaneously to every cell in the seed—births and deaths occur simultaneously, and the discrete moment at which this happens is sometimes called a tick (in other words, each generation is a pure function of the preceding one). The rules continue to be applied repeatedly to create further generations. (Extract from the Wikipedia article)

We can understand that, when the above simple rules are applied on a particular seed or inital arrangement, complex patterns start to evolve. Interestingly, on the flip side, a very complex inital arrangement when processed by these rules might destroy itself completely. The Game of Life, initally of academic interest alone became popular after an article on it by Martin Gardner in Scietific American. Numerous complex intial patterns were found by academicians and hobbyists. Some of the examples are - still lifes, oscillators, spaceships, methusalahs, guns, puffer trains, rakes and breeders. (Golly is a tool to see these beautiful patterns in action. It comes with a huge set of complex initial states).

There exist patterns that resemble finite-state machines. This means that the GoL system is Turing-complete, meaning that it is capable of performing any computation that could be performed by a modern computer. (I do not have a clear understanding of finite-state machines or turing machines. Need to delve deeper).

What I find the most facinating with these cellular automata is the amount of time and effort researchers, and more surprisingly, hobbyists put on their research. I sometimes wonder what they get out of it. What beauty do they see in delving deep into such an artifical world and in coming up with patterns? There could possibly be no other explanation than curiosity.

An Interesting Reverse-Analogy

The Game of Life is analogous to life. Generations and civilizations are spawned and after a span of time, destroyed. Though GoL emulates life, I wonder if the reverse is possible? Can human life be lived based on extremely simple rules followed religiously?

I sometimes think that God has to put his head through the skies and scream "STOP!" so that the whole of humanity freezes. He then gives them a command - a simple rule to follow and then snaps them out of the freeze. From then on, humanity functions, robotic it may seem, based on that command and everyone leads a life devoid of the problems before the divine interference.

I wonder what that command would be?

I've always wanted to experiment free will. Suppose we are all told - "You can do anything as long as you cannot prevent others from doing anything they want", and if we all were to follow it religiously, how will the world turn out? Will there be utopia or dystopia?

On first thought, I see this brings more happiness. With the rule firmly etched into all of us, there will be no oppression or tyranny. All such explicit methods of curtailing free-will will be eradicated. What would remain are the implicit modes of curtailing free-will. Most of humanity is bound to one or many of these entities - their community, religion, caste, social class or to their family. Very few have complete individual free-will to make their own decisions. Expectations and demands from family members, and family responsibilites play an important role in everyone's decision-making and at times take people far away from their individual dreams. If all such entities (family, social class, religion etc) advocate free-will, then I guess we'd definitely see happier people around.

(At times, I am skeptic about this experiment. I just wish I could try it out! Note to self: Time to work on the Zombie-iser)

Irreversibility

Once in a while in the passage of time, a man gets so obsessed with numbers that his life is irreversibly changed. On the day Ram walked into my office with his theory, I knew he was obsessed.

~~~*~~~

I met Ram in my Advanced Number Theory class. It is one of our graduate level courses. I have been teaching ANT for the past 12 years, but I don’t remember any student in all these years who had as much passion for numbers as Ram did. It was evident that he was a class apart from his peers after a few classes. He solved the standard textbooks problems with no difficulties, abstracted what he learnt, posed problems for himself and began working on them. He quickly gave up solving my assignments as well. The only reason he was still attending classes was because he said he needed – in his own words – “fresh perspectives”.

Though he was my best student, we had never met out of the classroom. He worked on his own, never collaborating with anyone. I was sure he made some discoveries worthy of publication, but he never cared to publish. I realized he was aiming for something else. With the questions he was raising in class, he seemed to be on an abstract and directionless pursuit. Though I was curious and worried about where he was headed, I never took the initiative to talk to him out of the classroom. I thought he was a mad genius and it was best to let him be.

Two months into the course, Prof NRV mentioned that a guy in his class had been skipping all other classes except ANT and that he was at the verge of losing his stipend. It was worried it could be Ram. It was. I decided that it was time I had spoken to him.

In the next class, I went to his desk and asked him to meet me in my office after class for a chat. I waited for him, but he did not turn up. He sent me an email in the evening –

“Dear Prof. Hari,

I am sorry for not turning up. I know why you wanted to meet me. I’m alright. I am working on something far more rewarding than my stipend or my classes. I have delved so deep into solving this problem that I find my classes a waste of time. I now realize that I should have enrolled for a research oriented program. Classes don’t make sense to me anymore. But back then, I didn’t know what to pick… my interests are clearer now!

The next few days are the most crucial for me. I hope to make good progress. What I might discover as the solution could be path-breaking. This makes it all the more exciting. I might be missing ANT classes as well.

I’ll meet you soon with some good news!

Ram.

P.S: One-way functions. ;-)”

~~~*~~~

Five days later, he walked into my office. He did not look like someone bringing good news. He was bearded all the time, but his shabby dressing made him look worse. He looked tired as well.

“Good afternoon, Professor.”

“Oh! Good afternoon, Ram,” I motioned him to take a seat, “It’s quite a surprise to see you these days. So, how’s your research going? When are you getting back to classes?”

“Classes? I have not even thought about them Professor, but my research is on track.”

“What are you working on?” I asked, curious about what was holding him back from attending classes.

He hesitated and then spoke, “I am working on finding a universal reversal function. Umm… For example, like a universal de-hashing function.”

I wasn’t quite clear with his terminology. I wanted to make sure if he really meant what I understood it as. “You mean a function that accepts a hash value and returns the original plain text?”

“Exactly,” he said with excitement, “But hash functions are just a sub-set of one-way functions. I intend to find a generic function that can output the original input value when we input the one-way function used and the output it generated. If we use it in the context of hash functions, it can de-hash a hash value generated by any hashing algorithm.”

“Ram,” I paused trying to figure out the best way to put it, sighed and then told him, “I cannot put this in any other way, but what you’re saying is ridiculous.”

“I knew everyone would say this,” he said clearly losing his excitement, “It’s hard to accept the fact that a hashed value can be de-hashed and a one-way function can be reversed.”

“It’s not hard, Ram. It is impossible to accept it. You are trying to deny the very nature and purpose of hash functions. That’s what they are - Once you hash a piece of text, there is no way you can get the original text back.”

“I know the definitions, Professor. I think that’s what blinds you from seeing beyond. You fail to question the definition. I believe there is no such thing as a hashing function. In fact, there is no such thing as a one-way function as well. An input put through a mathematical function resulting in an output can always be reversed. Everything is two-way. I strongly believe in that.”

“You believe?” I asked in disbelief, “one-way functions have been proved to exist!”

“Then I intend to disprove it,” he said suppressing his anger, “Let me explain, Professor. Suppose I take each computation in a one-way function, I can see it has an input and an output. The output of each computation becomes the input of the next. This becomes a chain of causality. I believe – if you have the final output and all the steps of the function – then you can trace it back to the initial input.”

It was then that I realized I was arguing with someone who always questioned the premises of argument. “And this tracing back is what one-way functions do not allow! There is loss of data!”

He remained silent and said “You are going back to the definitions again. You don’t see what I see.”

I couldn’t understand what he could see. He was incorrigible and he was losing the argument. “Okay, Let’s take an example. You say your de-hashing function can give you the original text if you input the hashed value and the hashing function?”

“Yes.”

“Then let’s take any hashing algorithm – MD5 for example. Whatever be the input, be it a 100 page Shakespearean play or just a single character – say an ‘A’ – MD5 always spits out a 16 byte output! There is no way you could de-hash the output into a 100 page text! Data is lost during hashing. You cannot conjure up the data from nowhere! And it applies to one-way functions as well.”

“Yes,” he sounded offended, “you cannot conjure up data, but you can certainly do it within the boundaries of present-day mathematics.”

“I’m sorry that I sound discouraging, but I don’t see this going anywhere, Ram. Even if you were to find such a universal de-hashing or a reversal function, there are so many problems. What about hash collisions? There could be infinitely many plain texts leading to the same hash value. If you were to de-hash it, how would you choose the correct input text from the infinite number of possible input texts?”

“It’s hard to explain to you, Professor,” he said and stood up, “I’ll show it you. It’s just a matter of days. I came here to ask you a favour. Now, I don’t need it. Thank you very much.”

He then stormed out of my office with stern determination.

~~~*~~~

I hadn’t heard of him for a week after that. Then, I received an email –

Dear Prof. Hari,

I’ve done it! I’ve managed to come up with the way to reverse a one-way function! (and to “conjure up” data! :-))

Here’s a sneak preview of my algorithm –

6dc48f564c3f21cbde15075932df63494968589b

Oh! I’m sorry I forgot it’s hashed and I’m the only one (except for Prof. Basu) who knows how to unhash it. :-)

Prof. Basu is hosting an inter-departmental seminar at the RCAMR this Friday. Researchers from the center are also invited. Prof. Basu is planning to make my discovery public that day. Please do come.

Ram.

Prof. Basu was the head of our department and the director of the Ramanujan Center for Advanced Mathematical Research. The “center” as we called it, was a privately funded research organization in our campus. I couldn’t believe Prof. Basu would invite researchers of the center for Ram’s seminar. Either it was going to be path-breaking or he would be making a fool out of himself. I thought I’d know in two days’ time.

~~~*~~~

It happened the day before the seminar. I remember that instance very vividly. I was in a class that morning. Prof. NRV walked swiftly into the class and whispered into my ears to step out. I was first confused. He said it was very important. He was sweating profusely and was acting hysterical. Just as I stepped out of the class along with him, he sputtered –

“Prof. Basu passed away in an accident today. He was on his way to the campus. And that boy – Ram – he was found burned to death in his room. It was a fire accident. No one knows how it happened.”

~~~*~~~

For the next few days, our campus was the talk of the country. There were several media reports, investigations, controversy theories and other such cacophony. After it all died away, I was left with what caused it all –

6dc48f564c3f21cbde15075932df63494968589b

It took away two lives.

It had the key to ultimate reversibility.

And it was irreversible.

~~~THE END~~~

The Science of Secrecy - Part III

This blog was posted on my workspace blog on 08-FEB-2008


~~~***~~~

The Science of Secrecy - Part III

Links to the previous parts : Part I and Part II

RSA

At the end of part II, We saw that Diffie, Helman and Merkle key exchange method was used to communicate the secret key among two people. This scheme was workable but imperfect as it lacked spontaneity. Then they proposed the concept of public key cryptography or asymmetric encryption. This remained a theoretical concept as they had not yet found a special one-way function that could satisfy the requirements of an asymmetric encryption system. So their concept remained a perfect but unworkable one.

After 2 years, since the concept of an asymmetric cipher was proposed by D-M-H(in 1975), another trio named Ron Rivest, Leonard Adleman and Adi Shamir discovered a working model of an asymmetric encrytion system.

All three of them were researchers in the MIT Lab for computer science. Rivest and Shamir were computer scientists while Adleman was a mathematician. It was first Rivest's idea to find a solution for this problem. He then approached Adleman to help him and then Shamir joined in. It turned out to be a perfect partnership.

Rivest and Shamir worked hard to find one one-way function after the other, only to let Adleman find flaws in it. This continued till one day in april 1977, when Rivest came home drunk after a pass-over party. He was sleepless and was pondering over the asymmetric cipher problem. And then all of a sudden, he had a 'Eureka!' moment. At daybreak next day, he was ready with a full length scientific paper. Shamir and Adleman tried to find flaws but the efforts were of no use this time.

The Adleman-Rivest-Shamir(as it was first called by them) asymmetric encryption system was perfect! Then Adleman renamed it as RSA as he was the one to put minimal efforts into it. Before going into the mathematics of RSA, let us recollect the requirements of an asymmetric encryption system:

1. Alice must create a public key with which anyone(Bob) can encrypt their messages to her. It should be an one-way function so that no stranger(Eve) can reverse it to get the secret message.

2. Alice must decrypt the encrypted message. She must therefore have a secret private key which allows her(and only her) to reverse the one-way function.

Putting it black-and-white, we need a system with a one-way function which can be reversible under special conditions(which help only Alice to reverse the irreversible one-way funtion). And this was what R-S and A found:

The Mathematics of RSA

Stage 1 : Alice chooses 2 prime numbers p and q, say p=17 and q = 11. These are her secret.

Stage 2 : She works out N = p x q = pq = 17 x 11 = 187 and then she chooses another number 'e', say e = 11.

Stage 3 : N and e are published in a directory by Alice as her public key or encryption key. It is to be noted that N is unique for every person while 'e' can be common. So these two numbers put together can be used by anyone to encrypt messages to her.

Stage 4 : Now let us say that Bob wants to send her the letter 'X' (its ASCII value is 88). To find the ciphertext C for the plaintext M(which is only the letter 'X'), Bob should use the common one-way function : C = M^e(mod N). Substituting the values, we get:

C = 88⁷(mod 187) = 11. {NOTE : 88⁷ is a very large value. But there are simple techniques to find out 88⁷(mod 187) easily}

Stage 5 : Bob sends the ciphertext C = 11 to Alice. Now Eve can intercept this message. Eventhough he knows the C = 11 value, N , e and the function used, she cannot get the value of M = 88 because the function used is an one-way funtion. (NOTE : It is the same function used D-H-M key exchange method)

Stage 6 : Now Alice can decipher the message back because she has some special information. She knows p and q. She first works out the decryption key or her secret private key named 'd' with the formula :

e x d = 1 {mod[(p-1) x (q-1)]}

so substituting the values:

7 x d = 1 [mod (16 x 10)] = d = 1 (mod 160) / 7 = 23. [Note : finding 'd' is easier thru a technique called Euclid's algorithm]

So, d = 23 is Alice's private key.

Stage 7 : Now, Alice just has to pass her Ciphertext and her private key into a simple formula to get the plaintext M. The formula is M = C^d(mod N) = 11²³(mod 187) = 88! which was Bob's message to Alice. The calculations of this stage are similar to stage 4.

Note : RSA system needs mathematical tools to easily perform calculations for Stages 4, 6 and 7. I feel that understanding the working of this system is itself a great thing from me. My understanding about RSA would be complete only after understanding the proof and how R-S and A created such a method. But I'm worried about the mathematics behind. So if any of you understood the proof, please do a KT to me :-)

Getting bBack, we have already seen the system from Eve's point of view till Stage 5. She cannot get back M = 88 from C = 11 as it is one-way function. But she knows all the values of N, e and the function. So, Instead of trying to reverse this function to get the plaintext, Can't Eve just work out the decryption key 'd' just as Alice did? like in Stage 6? The answer is 'no'! because she doesnot know the value of p and q(which are Alice's secret).

But Eve knows N. And N was calculated from p and q (i.e., N = pq). So will it not be easy for Eve to find p and q from N? The answer is another big 'No' and here lies the beauty of RSA. N is a product of two prime numbers - p and q. It is very difficult and time consuming to factorise N which is a product of 2 primes. In real life the values of p and q chosen are so large, that it is practically impossible to crack an RSA encrypted message.

As of 2005, the largest values of N factored is 200 decimal digits(660 binary digits or bits) long. That means that p and q were each 100 digits long(compare them with our example of p = 17 and q = 11). It is an accepted fact that 128, 256 and even 512 bit keys are vulnerable to attack because of distributed computing. So the choice of keys are either 1024 or 2048 bits as of now. But computing power and resources exponentially increase day-after-day forcing the use of longer keys.

Unless someone finds an algorithm for rapid factoring(the existence of which has not been proved or disproved by mathematicians and it still remains a great puzzle), RSA is impregnable. The increase in computing power may push the limits of the key-length. But computing power is like a double-edged knife as it can also be used to search for larger primes and thus feeding RSA with high-security keys. (NOTE: The largest known prime, as of August 2007, is 2^232,582,657 - 1 . This number is 9,808,358 digits long! If p and q are this long, N would be 19,616,716 decimal digits long!). Anyways, this holds true no matter what! :-) Edit : Intranet Link

But since RSA is ultimately dependent on the factoring of N back to the primes p and q, the final verdict is that a breakthrough in Mathematics and rapid prime factoring can give RSA the run for its money.

For the time being, RSA system has solved the problem of spontaneity. Anyone could use Alice's public key and send her their encrypted emails while her own computer could decrypt it with her private key and have the message waiting for her to be read. This is totally unlike D-H-M key exchange method where it requires few intermediate calculations to be exchanged between Alice and Bob before the actual message is exchanged. One more problem with D-M-H method is that with each person one communicates, the choice of numbers must vary. But in RSA, Alice can use the same set of public and private keys as long as she feels that they are safe.

RSA was patented in August 1977 and RSA Data Security Inc was found by Rivest, Shamir and Adleman. It first sold its data security products to militaries and large corporations. The products were initally designed for the computing power and resources of such organisations and it was the effort of a free-thinker named Philip Zimmermann that brought RSA out to the public.

PGP :

"Pretty Good Privacy" was the name Phil Zimmermann gave to his controversial application that he distributed across the Internet as a freeware in 1991. It was controversial because it used the concept of RSA encryption without receiving a license from RSA Data Security Inc. RSA Inc branded PGP as a Banditware and Zimmermann was sued for copyright infringements.

PGP was responsible for the data security of the common masses. One main drawback of RSA was that it required high computing power to encrypt long texts. But Zimmermann reused the age-old technique of encrypting it with someother encryption system.(Note that encryption algorithms were really strong(ex: DES) even before D-M-H and R-S-A. But it was only the key distribution problem that undermined them). So Zimmermann used an encryption system called IDEA to encrypt the message and RSA only for the initial key exchange! This resulted in using RSA even in PCs and thus the wide spread use!

The PGP application had other great features too. It was very user-friendly. It kept the RSA, IDEA and other technical mumbo-jumbo to itself and helped the user to just type in, choose the PGP option and send the email. Even the choice of public and private key was innovative. A user could move his mouse in random directions and according to the movement, the public and private keys(the 2 large primes) were selected. PGP also listed everyone's public keys in a directory thus avoiding the need to remember other people's public keys.

Now comes the best part about PGP. Imagine this : Alice wants to send Bob a love letter. She knows Bob's public key. She can encrypt it with Bob's public key and send it to him. Bob can decipher it with his private key. But everyone knows Bob's public key, right? So why can't Eve write a love letter and put Alice's sign at the bottom and send it to him? What guarantee is there that the email that you receive is from the person you expect it to be from? PGP solves this in an brilliant yet simple manner!

Imagine this and see if this makes any sense - What if Alice encrypts her message using her private key(note: private) and sends its across to everyone? does that make any sense? Everyone can dechiper it with her public key and read it, right? It doesnt help for security. But it helps for 'Identity'! If Alice encrypts a message with her private key and sends it to someone, And if they can decrypt it with her public key, it surely means that the message is only from Alice and no one else!

So PGP uses a double encryption system for this 'digital signature':

1. Alice encrypts her message using her private key first (This identifies Alice). Then she encrypts this message with Bob's public key. This ensures that only Bob get the message(and Thus the security).

2. Bob decrypts it with his private key first. And then to see if it really was from Alice, he decrypts it with her public key!

This system was the first to implement the concept of 'Digital signatures' and was the forerunner to SSL(Secure Socket Layer).

The Anti-Climax:

In 1997, after nearly 3 decades from the time Diffie thought he could solve the key distribution problem, the British Government declassified information about three cryptographers of Government Communication Head-Quarters(GCHQ) with the claims that they had discovered the solution for the key distribution problem and the working concept of asymmetric encryption or public key cryptography way back in 1975 (2 years before RSA was patented)

The British Government gave the credits to three of its cryptographers namely - James Ellis, Clifford Cocks and Malcolm Willianson for discovering it even before the DMH and RSA's times. Since, it was for invented for the military, it was classified as 'top secret' and it remained so for 20 years till 1997 when the British Government thought that it was no use keeping it secret anymore.

It is another story of remarkable ingenuity, anonymous heroes and a government cover-up that endured for decades. It is indeed a sad story which I do not wish to share here for the fact that you will kill me for sucking your time.

FYI, from Wikipedia : "On June 29, 2006 it was announced that EMC Corporation will acquire RSA Security for $2.1 billion." But Cocks and Williamson remained unrewarded till 1997 looking at their invention taking over the world. And the saddest was that James Ellis who discovered a solution to key distribution problem in 1969(4 years before Diffie) died even before the information was declassified!

Phew... Whatever it is, my e-banking account and transaction passwords are safe! Thanks to Modern Cryptography!

## The End ##

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.

The Science of Secrecy - Part I

I have decided to repost a few of my favorite blogs that I have posted on my workplace blog. This blog was posted on 04-FEB-2008, after I was heavily influenced by Simon Singh's The Codebook.

Warning: It's quite long. You might have to cancel that movie-watching idea and try reading this.

~~~***~~~

The Science of Secrecy - Part I

Dear citizen of the Internet,

I have a few questions for you. A few important questions. The answers for which, you have taken for granted or neglected.

1. How secure is your gmail or yahoomail(or any other) password on the Internet?
2. How secure are your emails on the Net? Do you believe that your mails are NOT being read by complete strangers?
3. Do you think gmail or yahoomail admins CANNOT read your personal mails? Or even worse, some faraway hacker (who is in no way related to gmail or yahoomail) can read your mail?
4. Do you think you are the only one who knows your e-banking password? Or you think someone else cannot transfer your money to their accounts?
5. Or in the most general sense, Do you think the Internet is totally secure beyond doubts? Is your so-called "Privacy" completely guaranteed?

Well, if these set your mind to contemplate, Fear not! The Internet is secure. But we, netizens, have totally failed to appreciate and recognise a 2000 year old field of study that has given us today such freedom and privacy in this world wide jungle called Internet.

No field of study has undergone as many controversies, intellectual breakthroughs, military espionage and a fierce race for superiority internally among 2 groups. This field of study has created and conquered kingdoms, has affected the wealth and army of empires, provoked and stopped wars and finally has opened up a global economy through E-Commerce.

This blog is about the mysterious science of secrecy - Cryptography!

The Science of Secrecy - Part 1

Allow me to take you through this amazing science from the times of Caesar to Commerce on the Internet.

First let's brush up on the basics of cryptography with an example and an analogy. It is important that you understand a few terms now to enable further understanding. The letters in bold are very important.

Alice and Bob are 2 common people(just like us) who want to share a secret message between them. Let us say that Alive wants to pass on the message "I love apples" to Bob. This "I love apples" is called the plaintext. Now a stranger called Eve wants to intercept and understand their message.

Alice and Bob suspect that someone might want to intercept their message. So Alice uses an encryption system to encrypt her plaintext. An encryption system is a techinque used to scramble the plaintext into something that cannot be understood by a third person.

For example, Alice uses this technique:

She takes her message letter by letter and replaces them with some other letter of the alphabet. Her choice is to replace the letters by the next letter in the alphabet i.e, she shifts each letter by one place.

So "I LOVE APPLES" becomes "J MPWF BQQMFT". Now, "J MPWF BQQMFT" becomes the ciphertext. Alice sends the ciphertext to Bob who can reverse the ciphertext back to the plaintext(I LOVE APPLES) provided he knows the encryption technique and the key. Alice's encryption technique was to replace the letters of the plaintext by someother letter of the alphabet. Bob must know this to reverse the ciphertext back to the plaintext.

But is that enough? No! He needs to know which set of letters to replace with. Alice has shifted the alphabet by one letter:

Plain alphabet : A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Cipher alphabet : B C D E F G H I J K L M N O P Q R S T U V W X Y Z A


Alice has used the letter in the bottom row corresponding to the one in the top row. So shifting by one letter is the key. So Bob needs to know two things to reverse the ciphertext back to the plaintext.

1. The Encryption System and
2. The key she has used.

Knowing these, the reversing operation is easy for Bob. So Alice encrypts the plaintext to the ciphertext using an encryption system and a key. And Bob decrypts the ciphertext back to the plaintext using the encryption system and key. So far, We've learned the essence of modern cryptography.

Now lets see Eve's role. Eve wants to know what Alice sent to Bob. Eve can capture the ciphertext - "J MPWF BQQMFT". But she's clueless about what it means. From what we've learned, she needs both the encryption system and the key to know what it means. But, if she can, in some way, know what it means without knowing the encryption system and key, she becomes a codebreaker or cryptanalyst.

So cryptyanalysis or codebreaking is the process of finding out the plaintext from the ciphertext without knowing the encryption system and the key. That method could be bruteforce attack, eaves-dropping, spying and at times by sheer brilliance in the form of frequency analysis.

So Alice's responsibility is to keep both of them secret to have secure communication with Bob. But the choice of the encryption system and key is supreme for strong, secure and unbreakable communication. Let us see why:

The strength of secure communication lies on the choice of
1. Encryption system and
2. Key.

Obviously because, if they are known or found out easily, then the plaintext could be easily found out. So Lets see if Alice's communication is strong enough to withstand attack by codebreakers.

1. Key : Let us assume that Eve(or any codebreaker) knows Alice's encryption system i.e., that she always shifts the alphabet by a few characters to the left. If this is known to Eve, then she could work out the key easily. If you noticed, the shifting can only be done in 25 different ways. So Eve can just try for a maximum of 25 times to get the plaintext. So this encryption system (shifting the alphabet by a few letters) is prone to bruteforce attack as the number of possible keys is very less (just 25).

2. Encryption System : Actually this is what the codebreakers try to find out first. Without knowing the encryption system, the number of possible keys cannot be found. So keeping a secret encryption system is the first step towards a secure communication. Keeping the encryption system as a secret has a few practical difficulties:

First, If the security of communication is solely dependent on the encryption system alone, it becomes a big overhead to keep it secret in the first place. Because imagine that Alice wants to communicate secretly with 100 people. She can use 100 different encryption system. But if she uses the same one, a codebreaker can easily deduce what system she is using.

Or simply the probability of the encryption system being known is very high when the number of persons using it increases. Simply put, a secret encryption system used between 2 people is very secure but not so when many are involved. (Do you know: Kamasutra consists of 64 essential skills and 1 of them is secret writing. A woman who learns the skills of kamasutra must know how to communicate secretly with her partner). (Present Day Edit : Hehe! Why the reference, Siva? Why?)

Coming back, The trust should not be on the system but on the key. And In this world of the internet, billions and billions of emails are sent per day by a billion people. So each one cannot use their own excryption system. So it is best to choose a publicly known encryption system which has a large choice of keys.

This is Kerckchoff's principle : "The security of a crypto-system must not depend on keeping secret the crypto-algorithm. The security depends only on keeping secret the key."

Having learnt all this, let us see a real life analogy. Alice wants to send Bob a confidential message on a sheet of paper by post. She suspects that the postal dept would do anything to read her message. So she decides to put it in a locked box and send it.

So now, putting the message into a locked box is analogous to the process of encryption. Now the immoral postal system can either break down the box or try a brute force method of using various keys till the box opens. From Alice's point of view, the security of this communication through the locked box depends on 2 things:

1. Strength of the box: The box should be strong enough to resist breaking. Alice can choose just a plastic box or an iron box. This is analogous to the choice of encryption system. The more complex, the more harder it is to break.

2. The Key : The key should be complex enough so that the box could not be opened by trying many random keys that the postal system has. This is analogous to the possible number of keys a crypto-system provides. (Ex: only 26 in Alice's system).

So as long as the box is strong and the key is complex, the message stays secure.

Evolution of Ciphers:

Cryptography is ever-evolving. This is because there has been a fierce battle between cryptographers (codemakers) and cryptanalysts (codebreakers) for supremacy. Once the codemakers come up with a strong crypto-system, it lasts for a few decades or centuries only to let the codebreakers come up with an ingenious method to break it. Information security is lost for sometime but yet again, the codemakers come up with another strong cryptosystem. Both groups have had their times of glory till now. And this battle has led cryptography to this present stage where crptographers are leading the race with people enjoying information privacy and codebreakers fighting to regain their place.

Let us see the evolution of ciphers:

1.Name of the cipher : Caesar cipher(circa 100BC)

Type : Monosubstitiutional (one letter in the plain alphabet is always replaced by the same letter in the cipher alphabet. ex: in Alice's "I LOVE APPLES" the 2 "P"s are always replaced by "Q". In a polysubstituional cipher, the second "P" can be replaced by some other letter).
Encryption algorithm : Shifting the alphabet.
Possible No of Keys : 26.
Method of breaking : Brute force.
Credits for breaking it : Unknown.

Till 16th century, monosubstitutional cipher was used in its various forms and symbols. And Arab cryptanalysts found an ingenious technique called frequency analysis to break it. So development in cryptography came to a stand-still until the 16-century. And then came...

2. Name of the cipher : Vigenere cipher (1523).

Type : Polysubstitutional.
Encryption algorithm : uses a table of alphabets (see table in this link).
Possible no of keys : Infinite (sender and receiver can agree upon any word).
Method of breaking : The vigenere cipher was theortically unbreakable if the key used is long and different each time. But it was practically flawed because such types of keys cannot be used in real life. So as repeated and short keys were used, advanced frequency analysis helped to break it.
Credits for breaking it : surprise.. surprise.. Charles Babbage and later by Freidrich Kasiski(1863).

Till 19th century all methods were breakable by codebreakers. But as the 20th century was born, there was a great demand for a secure crypto-system as the Radio was invented by Marconi and it was increasingly used by the military. In World War I, the german ADFGVX cipher was used which was a complex substitution and transposition cipher which was broken in just 5 years time. The codebreakers thus held an upperhand till the german Enigma was invented.

3. Name : Enigma & Lorentz(advanced) machine ciphers. Enigma was used by common military communication and Lorentz by the German High Command for very secure communication. The movie U-571 was based on the efforts to capture an Enigma machine.

Type : Transposition & polysubstitution using mechanical discs.
E.A : see the link on how it works (its amazing!)
Key : 1016(Enigma) and 1.5 x 1020(Lorentz).
Method of cracking : Truly amazing! A work of great genius by Alan Turing, arguably one of the greatest codebreakers ever. His life history and efforts are worth reading(see link below). He constructed a machine called Turing's Bomb which was the forerunner to the not-acclaimed first programmable computer - Colossus. ENIAC was the first to be acclaimed even when the Colossus was built first. (Do you know : Turing proposed a simple test called Turing Test to check for Artificial Intelligence. If a computer or Robot passes this test, it is said to be Intelligent. Link about Turing Test is given below. CAPTCHAs(those disfigured and twisted letters that you fill up in an account creation form on the Net) is actually an abbreviation of Completely Automated Public Turing test to tell Computers and Humans Apart!)

So after World War II, the Computer Era began and it exponentially increased computing power. And so it enabled the creation of complex and unbreakable crptosystems with a vast number of keys. The power of computers enabled the plaintext to be passed onto complex mathematical functions and loops to create a totally confusing ciphertext. As commercial computers spread, everyone was able to create their own complex cryptosystem. But then a new problem was created. A problem of plenty. There were so many good ciphers that a common method was needed for secure communication among everyone. And so in 1973, DES(Data Encryption Standard) was accepted in the US as a standard for secure communication.

DES is still used. It is powerful and unbreakable. It possible number of keys cannot be broken by brute force in a finite time even by a supercomputer. It is like having a box made of the strongest unbreakable element & having infinite number of possible keys. DES is both theroretically and practically unbreakable!

so is that all? Is our information secure when we use DES? Have the codemakers won?

The answer is both 'yes' and 'no'. 'yes' for the fact that an unbreakable cryptosystem has been created after 2000 years. Both the 2 factors (encryption system and possible no of keys) are unapproachable by codebreakers. A definite 'yes' for the greatest lock ever!

And a 'no' because of a problem that was overlooked for 2000 years - The probem of key distribution.

Imagine this - Alice puts a secret message in an unbreakable iron box. She locks it and sends it to Bob. Now how would Bob open it without the key? Alice could send the key to Bob. But what guarantee is there that the key would reach Bob safely? Anyone could take the key if they wish to read the message. So the key is as important as the message. So the only way for Alice is to distribute the key beforehand. That is, Alice should have made 2 keys for the lock and must have given it to Bob before. Now Bob can open the box and read the message. But here lies the biggest problem - If Alice wants to send a 100 messages per day to 100 people, how would she do it? She cant make a 100 similar keys and distribute to everyone? So in the actual cryptographic sense, a chosen key must be communicated between the sender and receiver. But sending this key demands secure communication which again depends on key distribution. So no matter how secure a cipher(like DES) is in theory, in practise it can be undermined by the problem of key distribution.

This problem has been prevailing for 2000 years unsolved. The Germans distributed keybooks everymonth to all Enigma operators. Even to those in the U-boats at Sea. This was a great overhead. And if the keybooks were captured, one month's communication became insecure. And even when DES was established, large business corporations and banks used couriers (people with a padlocked briefcase chained to their hands) to distribute keys to their clients to have a secure communication between them. But as business and number of people to communicate with grew, hiring couriers became a great overhead to these companies. Key distribution was restricting the general public from having secure communication among them. And it seemed imposssible to come over this problem. The world was eagerly waiting for a breakthrough for the key distribution problem. Especially the military and business corporations. Lots of men and money were involved in research to solve the key distribution problem. It was a gloomy time for cryptography at large.

At this time('70s), Information was not yet secure even when DES was invented and Internet had its birth(in the form of ARPAnet in the '60s). When all hope was lost, arose 2 heroes from humble backgrounds(in the form of Diffie anf Hellman) who gave the 2000 year old dying field of cryptography a fresh breath!

## END of Part 1 ##

to be continued..

A Note on "The Code Book": This blog could also be titled - "The Codebook - In a nutshell". I actually started to write about Diffie & Hellman Key Exchange. But then felt that understanding the importance of that would require prior knowledge on cryptography and its evolution. So i have given my best try here to explain the gist of a famous and wonderful book - "The Codebook" by Simon Singh. I struggled really hard and lost interest a lot of times to write this blog. But I took it as a personal tribute to one of the most captivating books i've read. I am eager to finish the remaining 2 parts, which were the actual things i wanted to write on. So for those of you who read this, thank you. For those who did not, please read the next 2 atleast.

~~~***~~~

Present day footnotes

1. In the introductory paragraphs, I have raised questions about the security of email passwords. I was talking about theoretical security. There are practical problems like phishing et al, which I or The Codebook did not focus on.