Monday July 31, 2006
So What Is Public Key Cryptography Anyway
Think you want to send a valuable object to a friend securely. You have a box that is more than large enough to contain the object. You have several locks with keys. The box has a locking ring that is more than large enough to have a lock attached. But your friend does not have the key to any lock that you have. How do you send the object securely?
The answer to this has a direct application in cryptography. Let’s say you want to send a secret message to your friend. Because you don’t trust commercial and freeware encryption methods, you use a secret cipher of your own. Only you know the key to the cipher. Not even your friend knows it. So you send the encrypted message; your friend encrypts it further with his or her favorite secret cipher and sends it back to you. You remove your cipher and send it back to your friend; and he or she removes the second secret cipher and reads the clear text.
So the answer is, put the valuable object into the box, secure it with one of your locks, and send the box to your friend. Your friend should then attach one of his own locks and return it. When you receive it again, remove your lock and send it back. Now your friend unlock his own lock and retrieve the object.
Posted by insidemyhead [Sun] ( July 31, 2006 09:25 PM ) Permalink | Comments[5]
Posted by D Singh on August 01, 2006 at 03:49 AM IST #
Posted by Sai on August 01, 2006 at 03:20 PM IST #
Posted by Sandeep Soni on August 05, 2006 at 11:38 PM IST #
Actually, the box analogy doesn't always hold true. There can be a problem with this method if the cypher isn't smart enough.
Imagine this simple scenario (a particular case of yours): I want to send a message, (say some numbers, between 0 and 255). To cypher my message, I generate a key: the same structure as my message, the same length, but completely random. Then, the addition of my message and my key (modulo 256) will be completely random as well, so it is undecipherable. I send the result to my friend, which will use the same method of encryption, and sends back the result. I decrypt it with my key, sends the result, He decrypts this, read my message, and we're all happy.
Of course, each message in the network, taken independently, is completely random, thanks to the random keys. However, these three messages are correlated. If they were not, the message could not have been passed. So how an attacker could leverage this correlation?
Let M be the message.
Let Ks be the sender's key.
Let Kr be the receiver's key.
If some cracker intercepts all three messages (the classic "man in the middle"), he has access to:
C1=M+Ks
C2=M+Ks+Kr
C3=M+Kr (=M+Ks+kr-Ks)
Then, if the craker knows the encryption method (an he will know), he will also know that:
Kr=C2-C1
Ks=C2-C3
And of course: M=C1+C3-C2
KABOOM! The cypher is cracked in constant time! Even more interesting, it remains true for any additive group. (I mean, if we replace the '+' by another commutative and associative operator, no matter how complicated)
I though this method was foolproof for years. But I'm afraid cryptography will stay difficult for a long time.
Posted by Loup VAILLANT on September 28, 2007 at 09:20 PM IST #
ans is 11
Posted by 122.167.99.64 on March 30, 2009 at 03:12 PM IST #