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.

Irreconcilable Differences

When Renuka stepped out of the office bus on that November morning, she was completely overcome by nostalgia. It was her last day at work - the end of her first job. For 13 years, the company had been her home and on that day, after being witness to hundreds of farewells of her colleagues, it was her turn. For the first time in weeks, the sadness that had engulfed her was replaced by a new feeling of nostalgia. She would miss the place very badly. She had spent more time in her workplace than any other place out of home. It was her second home. She had seen it grow from what had been place of thousands to this labyrinthine monster of a hundred thousand people.

How much had she fought to stay in this place? She refused to marry if she had to quit. She had to bear her in-laws' rants. She still stuck to her job after Arjun was born. How many other sacrifices? It was all worth it. She had enjoyed her work so much that she wondered if she'd ever find such a place again. She had never found a place where she belonged to as much. And it was time to throw it all away and leave. As fast as she could.

She walked along with the crowd. She wanted to be lost in the crowd and never come out. It made her feel anonymous. She did not want to get out. She did not want to be spotted again. She did not want to answer questions. She did not want to meet anyone. She hoped they wouldn't delay her with all the formalities. She wanted to get out as soon as she could. Arjun would be waiting...

~~~*~~~

Certificates of Appreciation, coffee mugs, Arjun's drawings, photo-frames, unit newsletters, magazines, certification materials... She was overwhelmed by the amount of stuff her desk and drawer had gathered over the years. Now, she had to take everything back. She started packing her things.

"Morning, Renu!" said Ashok as she was packing them. He seemed to be the only one from the team already in.

"Good Morning, Ashok!" He always reminded her of herself. Early to arrive, early to leave and focused at work.

"What happened?" he asked, ""We were all shocked that you suddenly went on a month's leave and now you're quitting all of a sudden." The question she didn't want to answer, but would keep coming.

"Erm..." she smiled, "You know... family needs."

He sensed she didn't want to answer.

"So," asked Renu herself sensing the awkward silence, "How's Sunil taking over?"

"Not very good actually. He's already very busy with ATLAS. He's finding it hard to manage both the projects. So they're looking for a replacement for you as soon as possible."

"I know." And then there was another silence.

"I'll go have my breakfast then." He said.

"Oh! Sure."

Solitude again! She finally managed to log in to her computer after a lot of recollection. The long break from work made her forget her password.

"Hello Madam! What happened?" pinged Srini immediately. She ignored him. Srini, Manoj and she were the last remaining souls in the company from the July 1997 batch. They hadn't been in touch recently, but still, She owed them an explanation. Not yet... Not now... She told herself.

She took a look at her separation checklist. 21 items. Her head ached already.

~~~*~~~

7. Please surrender your digital security tokens (if any) with the Hardware & Equipment Team at building 13. Contact Rahul Agarwal at 99167...

She stared at the list wondering where in Building 13 the Hardware & Equipment Team was. Meanwhile, there was some commotion in the neighbouring cubes. She turned back to see a few of her team-members assembled outside her cubicle. Others were trickling in. Rahul seemed to be their flag-bearer. Rahul was the usual least productive guy in the team who manages to wriggle out of situations with his social skills. Even then, he was their team's glue that held things together.

"Hi Renu," he broke the ice.

She smiled. They were up to something. "Hi all!"

"Erm..." ermed Rahul, "Sandeep told us that you are quitting because of personal reasons. The way he said it, it sounded more like personal problems. So, erm... we didn't want to trouble you much with a party. But we decided to get you something." And he took a wrapped gift. Sandeep was her manager. She understood he must have tried hard to explain her situation to the team without specific details.

She received the gift amongst cheers, applauses and a muffled whistle. She had the knack of finding out what's inside a gift-wrap. It was definitely a watch.

"Thanks a lot, guys. You really needn't have!"

"Yes, we wouldn't have," said Rahul, "But Guru has already bought a new gold ring. We didn't want the party funds to turn into gold ornaments. So..."

"I got engaged, you moron!" retorted Guru, their party admin.

She did manage to smile. She'd miss her team. "Thank you guys," she said, sadness hindering her speech, "I'm sorry that I cannot take you out for lunch..." It wouldn't take much time, would it? She asked herself. Even if it did, she owed it to her team. "But I'd love to treat you at the coffee shop at... around 3?"

~~~*~~~

The treat turned out to be a break from the irksome exit formalities. It was a relaxing experience and Renu was her normal work-self again. She had managed to forget the thoughts that were plaguing her and even caught up on some gossip. Finally, she was asked to give the customary testimonials about everyone. And then testimonials were showered upon her. After a final toast to her successful future (which she was skeptical about), they all began to disperse back to their places.

"Hello Madam!" called a familiar voice. It was Srini's. Srini and Manoj were gleefully walking towards her. Manoj had a gift bag with him. She excused herself from the others and met the two.

"Hi Guys!" she said. It was time she told them herself, "I'm sorry I couldn't tell you - Today's my last working day. I'm sorry if you already know."

"What happened?" they asked at the same time.

She fell silent. The same dreaded question.

"Nothing. 13 years is much too long, don't you think? Arjun needs taking care of, as well."

"But why so suddenly?" asked Srini.

"He's doing poorly in school. And..." Should I go on now? she thought, No! "Shall I get coffee for you guys?"

"Alright, I'll do that" said Srini and went to order at the counter. Manoj and Renu found a table and sat down. Manoj was lost deep in thought. They seemed to have bought her reason. "But," said Manoj, managing to distill the same question again out of all the thought, "Why all of a sudden?"

"It had to happen at sometime. And I decided to do it now. It's actually Arjun. He needs help."

"Five minutes for the coffee. They're a little held up," said Srini as he sat down along with them. "How's Arjun? You were saying something about him?"

"He's... fine. It's just..." She sighed, "It's a long story, Srini."

They noticed her hesitation. "It's okay," said Srini, "We don't have to talk about it."

"It's not that I don't want to tell you guys. I don't want to keep thinking about it all the time."

They sensed she was seriously concerned. "What happened?" asked Srini, "We might be able to help."

"It's Ravi," she replied, "He's completely out-of-his-mind. I don't seem to be able to make him understand at all. No matter how well I explain to him, he sticks to his own views and we end up shouting at each other. He and his mother keep insisting on using Ayurvedic medicines. I find the idea and the treatment entirely stupid. And in the middle of all this, Arjun's sight is deteriorating and his class teacher tells me that he finds it very hard to follow things in school."

"Deteriorating? What happened to his eye?" asked Srini with concern.

"You know he's been wearing spectacles for a long time, right?. He's had problems in his eyes from his childhood. We did not know it would become so serious. Four months ago, we noticed that he was having regular injuries at school. I also saw that there was something strange about the way he was navigating himself around. We feared something serious and immediately took him for an eye check-up. The doctor told us that it is a case of RP and his vision is deteriorating. He later explained to us that RP is incurable and in most cases progressive. We were both devastated."

"So there's no cure for this problem?" asked Srini. They were devastated too. Arjun was just 9 years old.

"No! The doctors say there's no cure for it as yet. Moreover, they think that Arjun's deterioration is rapid. They're not clear as to how fast, but they say that blindness can be prolonged with proper treatment. They even said that he might not lose complete vision. Ravi was initially hopeful that Arjun will be fine, but when the doctors mentioned that there's every possibility of him eventually going blind in 2 or 3 years and that there's no treatment for it, he began taking annoying decisions."

"You mean the ayurvedic treatment?" asked Srini.

"Yes, that and others. It started with one of his uncles. He came to visit us to check on Arjun and told Ravi that there's a place in Kerala which cures any kind of eye related problems and planted hopes in him. I got so frustrated with this. It was the time when the fact that he was going blind and nothing can be done was sinking in to me. All that we could do was to give Arjun proper treatment to prolong it or to take him to a another hospital for another opinion from the doctors. But Ravi went on to enquire about this place in Kerala and their treatment and to my surprise, decided to carry on with the treatment."

"Why are you against it?" asked Manoj, "If these doctors can't help, what's wrong in getting their help?"

"C'mon Manoj. Do you believe in all this? Do you think Ayurvedic medicines can treat something modern medicine cannot? And different people have different problems. They might not even know what the problem is, but they might give the same medicines. I cannot even remotely think of anything good coming out of this. And he and his mother insist on it instead of normal treatment to prolong blindness."

"Actually," said Manoj, "a friend of mine's cousin is taking ayurvedic medicines and he regularly goes for treatment in person as well. And my friend used to say it's effective."

"This is the problem! It is these bloody friends, colleagues and friend of a friend of a friend who bother me! I feel like... strangling them to death. 'My friend's cousin has got his eyes back', 'My friend's brother-in-law's kid doesn't wear glasses anymore', 'My colleague's sister-in-law got married after going there', 'Even the Americans come and take treatment here' Ravi keeps saying these! God! How can he be so dumb! May be, Ayurvedic medicines do help solve small problems, but people generalise it and raise hopes. I never thought Ravi would listen to all this."

"But-"

"There's another problem as well. Ravi fails to accept that his son would one day go blind. I do have some hope that he'll be okay. Who hasn't hope, anyway? But come to think of it, RP has no cure at present. And I accepted it. It was hard for me. But still, I did and he doesn't. And he still thinks Arjun can be and needs to be normal. Arjun finds it hard to read now. He uses a lens to read along with his spectacles. I don't know how long this would last. He's finding it hard to navigate in the evenings. The doctors say night blindness has already set in. Seeing him struggle, I suggested that we can move him to a blind school or atleast stop his education for this year and he got irate. He insists we should not let him think he's blind, but make him think he's normal. And he says going to school will depend on how the ayurvedic treatment plans are made."

"Hmmm." It was hard for Srini and Manoj to come up with anything to say. "When did all this happen?" asked Srini trying to gauge the present situation.

Renuka's eyes had grown watery by then. She was struggling to keep her emotions in control.

"A month ago. And after that, even when I completely refused, he forcefully tried to take Arjun to that place in Kerala. And that was when I went on leave. I was trying to hold Arjun back for treatment here. Then my mom joined them all and asked me to try just once. They somehow managed to convince me and then I said 'Fine. Let's go there, but I will not agree to any treatment.' The place turned out to be as bad as I expected. I felt that it was run entirely on people's faith. Most of the cases were those rejected by scientific medicine and came there as a last resort. We took him for a check-up and they asked us to stay for a week. That was when we had a huge argument. Ravi wanted to stay and I wanted to leave. He refused to take us back from there insisting that we stayed. But I screamed at him and took a cab to bring Arjun back here. From then on, things have been really bad at home."

"And you've been at home the entire month trying to protect him?" asked Srini, "Why don't you try and give Ravi a chance? Or why couldn't you give him both the treatments? "

"No! A 'no' is a 'no'. I am not experimenting anything on my son. 'Both' is not an option and it will not work out." She said stubbornly even as she struggled to hold back tears.

"He's equally worried as you are. He could be thinking that you don't see his views."

"I do see he loves his son. But, what's the point of this treatment? I clearly know it's of no use or might even be harmful. Then how can I support that? And even if I do, what about the treatment here which can at least help prolong complete blindness." She rested her foreheads on her palms and sighed, "It's the same thing over and over again for the last few weeks. And that's when I took the decision."

"To quit working?"

"Yes. And to take Arjun to my mother's place. I had enough. I can at least get him good treatment without people bothering me all the time. I don't see any point in sending him to school as well. He's going to miss the school and his friends. I need to see him get through that as well and probably next year, get him admitted into a blind school. There's one run by The Preetham Trust in association with the NAB. His life would definitely be better at my mother's place."

"But," replied Srini, "Isn't this a drastic measure? Wouldn't he miss his father? You need to first relax and think!"

"Relax? How can I relax? I am married to a man who thinks his promotions are because of his yearly visits to Thirupathi. And my mother-in-law has started re-making her jewelery into gold eyes and crowns to donate to a temple in the hope of a cure. And my mother has joined hands with her for this! They'll never let go of this rant about giving that treatment a try. And I cannot see my son undergoing such nonsense. They'll never change." Tears ran down her cheeks uncontrollably. The guy at the counter told them their coffee was ready.

Srini decided to console her. "Give it sometime, Renu. Don't take drastic measures. Just be patient. May be, your husband would see your point and accept your son's disability."

By this time, her voice had grown feeble because of the sobbing. She stared at the table as she spoke. She spoke incoherently, as if words came out from deep within her.

"Whom should I blame now? I should blame myself for getting into all this. No, I should blame my father. He brought me up to be like this, to think rationally, to think for myself, to read, to be independent and then he passed away happily at the most important time of my life. And my mom panicked and forced me into all this. I don't fit into any of this. I cannot take it anymore. I think there is something fundamentally different between me and the people around me. I've really had enough."

She then looked at both of them with bloodshot eyes and said, "I wish I believed in some God. I could have at least had someone to pray to..."

And then she sobbed silently into her handkerchief.

~~~ THE END ~~~

P.S : A little inspiration from Sweet Nothing in My Ear.

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.