December 22, 2006

My kingdom for that key

Just for fun, the wife once sent me an email message in code. I was intrigued. How had she done it? Meaning, how was I supposed to decipher and read it? I didn't want to wait to ask her, that would be too easy. Could I figure the code out for myself?

I managed it in the end, experimenting with the few clues the coded message offered. Swelling with code-breaking pride, I promptly made up what I thought was a more difficult code and dashed off a reply. The lady cracked it far faster than I had hers. So much for pride.

Of course, codes have long been used for more serious purposes than idle husbands trying unsuccessfully to outwit alert wives. Cryptography, the science of encoding and decoding messages, is a rigorous scientific pursuit by itself. In wartime, much energy goes into two efforts: making sure your communication is secure and trying to decode the enemy's. This is so crucial that the side that does a better job will usually win the war.

Till 1976, coding relied on secret keys. You use such a key to convert the message, usually called "plaintext" by cryptographers, into the "ciphertext" that is transmitted. At the other end, the same key is used to decode the ciphertext back into plaintext. The key can be a mere transposition of letters ("b" for "a", "c" for "b" and so on), variations of which are what my wife and I used; or a mechanism using pages in some agreed book; or any number of other possibilities.

But here's the crux of such a method: for communication to work, both parties have to agree on a key.

This turns out to be the flaw in the whole system. To thwart people intent on breaking the code (cryptographers are known to call them "attackers"), keys must be relatively complex, and must themselves be communicated between sender and receiver. That means they can get stolen or lost, or counterfeited by the enemy to confuse, or they may even arrive after the ciphertext itself. Sender and receiver have to find a communication channel they can trust -- a secure phone line, a reliable courier -- merely to get the key transmitted. How do you get around these problems?

In 1976, Whitfield Diffie and Martin Hellmann of Stanford University answered that question by attacking its root: by doing away with the idea of secrecy itself. They proposed a public key coding system, in which the sender and receiver never have to agree on a secret key. Two years later, three researchers at MIT, Ronald Rivest, Adi Shamir and Leonard Adleman, demonstrated such a public key system; it has become known as the RSA (Rivest-Shamir-Adelman) system.

Without a doubt, the public key system is the most significant and influential advance in modern cryptography. In 2002, Rivest, Shamir and Adleman were awarded the Turing Award -- computer science's greatest prize -- for the RSA system.

Public key systems rely on a simple mathematical idea: some functions are much easier performed in one direction than the other. For example, it's not too difficult to figure out that when you multiply 7, 11 and 13, the answer is 1001. But what if I asked you: "Which three distinct numbers produce 1001 when multiplied?" That harder problem will take you, or even a computer, much longer to solve.

With numbers much larger than 1001, this time difference becomes significant. Eventually, the slower direction of these "one-way functions" takes so long that it is effectively impossible to solve. If you took two prime numbers that are each 100 digits long, a computer could multiply them quite easily to produce another number about 200 digits long. But if you gave it that 200-digit number and ask it to find the two 100-digit factors, how long would it take? Not seconds or minutes, but perhaps years. Centuries. In effect, this is impossible.

So RSA works something like this. Let's say Shabnam wants to receive coded messages. She picks two secret prime numbers, preferably big ones, and multiplies them. She does some further manipulation to come up with two more numbers. She announces that her personal public key is the product of the primes and one of these two additional numbers. The third number remains her private key.

Monideepa, who wants to send Shabnam a coded message, uses Shabnam's public key in a formula to encrypt her plaintext. When Shabnam receives Monideepa's ciphertext, she uses her private key in another formula that restores the plaintext. Of course, Shabnam never reveals the two secret primes to anyone.

In theory, this is not a secure system: given an indefinite amount of time, attacker Pappu could take Shabnam's public key and calculate the two numbers that produced it. But of course, Pappu doesn't have indefinite time. Long before he found Shabnam's primes, he would be dead. So Shabnam's key is safe, Monideepa's message cannot be read; the RSA system is secure.

This was a giant leap: RSA opened up the possibility of cheap, yet completely secure communication available to all.

Which, of course, was a red flag to governments around the globe, many of whom want to listen in on what their citizens, or other governments, say to each other. In the USA, this governmental unease over public key cryptography led to an effort to produce a government-approved coding system, based on a secret encryption algorithm called Skipjack. The US government proposed that Skipjack would be built into communication devices that needed to be secure.

Naturally this met with much outrage and eventually the US government declassified Skipjack.

And I've always thought it a delicious aside to the whole RSA story that within a day -- yes, a day -- two researchers had substantially decoded Skipjack itself, and one of those two researchers was Adi Shamir.

Meanwhile, I have here two 100-digit primes. One of them is 4557898123798712347234898920109927481232347798726198764691200283623897221029374283764823764138973668. ... Hmm, what'd I do with the other one?

18 comments:

Anonymous said...

hey, your number's not a prime!

Anonymous said...

I am no expert but (with slight abuse of some terms) this one's to you Herr TKA-IH-BE:
"NAS-TSAIDI AL-CHA-NIL DA-SHA-JAH!"

Anonymous said...

Here's the thing. Prime numbers seldom end in "8".

Shashikant Kore said...

As per my knowledge, US Govt also tried to change s-boxes the DES (symmetric key) encryption of IBM. Don't know the truth.

And, really, RSA algorithm is just beautiful. When asked to a CS Prof "What will happen if RSA is broken?", he replied, "The world will come to a halt, I guess."

km said...

Dilip, I hope you are buying an Enigma machine for your wife for Christmas :)

Great post.

Dilip D'Souza said...

B, OK, you got me. What are those caps saying?

Shashikant, I haven't seen the RSA algorithm, but I can believe it is beautiful. Like such a lot of other aspects of CS and programming too. Maybe a post about that one day...

km, thanks! I mean, I'm torn between an Enigma machine and an old Victrola. Whaddaya suggest? And how come I didn't see you when you were in Bom recently?

Anonymous said...

Nice post Dilip. You do have a knack for explaining concepts lucidly. The previous post on Black Holes was excellent too.

Reminds me of Isaac Asimov explaining scientific concepts lucidly. Keep going.

Pankaj

Anonymous said...

People who want to read more about cryptography and encryption systems can refer Dan Brown's 'Digital Fortress' novel. Its explained in quite a bit of detail in the book, should be enough for laymen to get an understanding of the field.

Siddharth Adelkar said...

Hey. I want to show you my parody on Megadeth's Anarchy in the UK....which is parodized to "Public Key in RSA"

http://siddharthadelkar.blogspot.com/2006/04/parodies.html

I know, self promotion, ...lame. but i think its pretty cool ..so check it out. It wont quite help understand public key but cover most terms...involved

Anonymous said...

Hey Dilip,

Not at all, presuming that you don't know or anything, but large primes are an intellectual property.

I hope you have checked the legal issues involved in displaying such a large primes with out reference, or even checked the legality of "possessing" them.

Geeky middleclass

Anonymous said...

Obviously we can see it is the encrypted version of the 100-digit prime, very clever Dilip!!!

Sidhusaaheb said...

I suppose the voice communication that our armed forces rely upon so heavily is still based upon the older forms of cryptography, besides switching communication frequencies quite often.

They could surely do with some technique upgrades.

Anonymous said...

Though public key infrastructure (PKI) is a secure way of communication between two parties the trade off is the speed. It takes more mp cycles to encrypt/decrypt it thus making it unfeasible for encrypting large amount of data. For doing that, Symmetric cryptography still holds best. Since the DES is no longer a good option, 3-DES and AES are in wide use for large data encryption.

More on PKI, if you reverse the whole arrangement -- that is, divulge the 'private key' (for encrypting a message) and use the public key for decryption, it goes on to form the basis of a basic digital signature. The encryption is done by the private key and the decryption by the public Key at the receiving end. It is this decryption which ultimately proves the authenticity of the message -- that being the basic idea of a Digital Signature.

Dilip, sorry for hijacking your comment space like that :)

Anonymous said...

What do the caps say? Well, thats kind of the point. Its not the Caesar ciphers for alert husbands but, like you say, very secure, so much so that it helped win the war. You should either be an Indian or use the (now declassified) dictionary to be a code talker.

Anonymous said...

http://www.buzzle.com/articles/medalist-womens-race-asian-games-failed-gender-test.html

Dilip: Can you explain why s/he was subjected to a gender test? Could you please write an article explaining this outrage and gender-fender-bender? Could all those male chauvinists be actually female, since no gender testing was done to validate the gender of the chauvinism? Help us understand.

Dilip D'Souza said...

I came back here actually because I just had a conversation with one of the big honchos involved in the gender bender affair, mentioned just above. All I can say here and now is, things are not quite what they seem, and I don't at all mean the poor woman herself.

Pankaj, meant to say thank you! I need to get back to those lines so you can display that fine talent you have.

And Truman, no need to apologize. Thanks for your interesting comment.

Anonymous said...

The history of perfume goes back to Egypt, although it was prevalent in East Asia as well. Early perfumes were based

on incense, not chemicals, so aromas were passed around through fumes. The Roman and Islamic cultures further

refined the harvesting and manufacturing of perfumery processes to include other aromatic ingredients.

Thus, the ancient Islamic culture marked the history of modern perfumery with the introduction of spices and herbs.

Fragrances and other exotic substances, such as Jasmine and Citruses, were adapted to be harvested in climates

outside of their indigenous Asia.

electronic signature sharepoint said...

It explains both the historical use and working with encryption.Keys and mechanism used in encryption although quite lengthy blog.but surely people can read this much to clear basics