Public Key Cryptography for Boy Scouts

Let’s imagine that someone (let’s call her Sophie – actually, we can use any desired name, but I would be pleased to use a name of my favorite actress – hope, she would be too :)) is willing to send you something quite sensitive – let it be an old map of the treasure island where captain Flint has hidden his chest full of golden coins. As a true woman, Sophie wishes to ask you – her brave knight – to sail to that island, fight the dragon and bring the treasure to her (I am not sure if there actually was a dragon, but the girls do like that sort of things, so we imagine that the monster is there :)).

However, there’s one problem: a river stands between you and Sophie. The only way for her to send you a map is to use the services of a boat driven by an old one-legged guy with a parrot on his shoulder, and this guy appears not to be that honest. The boat is quite small for two, so neither she nor you can accompany the map in its transfer across the river.

As you are a smart guy, a real knight, you quickly find a solution. Sophie should take a box with a lock, put a map there, close the lock and send the box to you via the boat. Once the box is here, you’ll open the lock and get the map. A great idea, isn’t it? Well, let’s try. Sophie finds the appropriate box, locks it with a key and calls the boat. But… wait a minute. You need the key to open the lock. But the key is on Sophie’s side, and obviously she cannot use the boat to transfer it to you.

You are sitting on the shore and thinking. You understand that Sophie should be able to close the lock and you should be able to open it, but the key should never be transferred across the river. And suddenly you get it! The solution is really simple. You will take a box with a self-closing lock, similar to the one shown on the picture at the left, and send the box to Sophie with an open lock, leaving the key in your pocket. Once Sophie receives the box, she puts the map there and pushes down the shackle. Now she can freely send the box with that strange guy, as she knows that he can’t open the lock without having a key.

An attentive reader may propose the following solution: let Sophie lock the box with a key and send the box with a boat. When the box arrives to the other side, let she call the boat once again and ask the guy to transfer the key. Well, yes, this solution will work (actually, it even suits one of the core principles of cryptography – never store a key along with encrypted data). However, you will not be able to use the same box or lock again, and who knows how many old maps Sophie is going to find? Besides, this solution is not applicable in the digital world, where an old one-legged guy can always do a copy of whatever he transfers and unlock the box once he gets the key.

The above story describes a method that cryptographers call public key (or asymmetric) encryption. In every public key cryptosystem a key consists of two halves called public key and private key. Public key is publicly available, while a private one should be kept in a safe place by its owner. Everyone can encrypt data with a public key, but only the one who possesses the private key will be able to decrypt it. In our case, the open lock is a public key, and the key in the pocket is a private key.

Let’s consider another situation. You and Sophie wish to send letters to each other across the river, and, as you are really a romantic couple, the number of letters is expected to be quite big. Of course, you can use the above scheme with a box with a self-closing lock. However, there will appear two disadvantages of such a scheme applied to our romantic task. First, you will need two boxes (a first one to transfer letters from Sophie to you and a second one – from you to Sophie). Second, a boat will have to do twice more trips across the river than the actual number of letters transferred (there is an extra “dummy” transfer of an empty open box for each letter). This is not critical if the transfers are free of charge, but I am pretty sure that the guy’s parrot eats plenty of corn and that’s why the transfers are performed on a paid basis.

Now that you are not a greenhorn in public key encryption, a reasonable idea comes to your mind quite fast. You will take a box with a lock that can be both opened and closed with the same key (see the picture at the left), and two identical keys that fit it. Then you will ask Sophie to send you an empty box with an open self-closing lock, exactly the same as you used to transfer the map. Once the box is here, you will put one of the two keys inside, close the lock and send it back to your girlfriend. She will open the box using her key and get the key that you’ve put inside. Now – voila - you have a box with a lock and two keys that fit that lock, one on your side and another on Sophie’s side, and you can start exchanging the letters using this box. A box with a self-closing lock is not needed anymore, so Sophie can put it aside.

The second case is a classic key exchange example. A general key exchange method allows two (or more) parties to set up a shared key by communicating over insecure data channel. A lot of key exchange methods are based on public key cryptosystems. The above case is based on public key encryption scheme; however, underlying encryption algorithm is not a requirement though. In modern cryptography key exchange algorithms serve a very important task of sharing a symmetric cipher key between peers using extraordinary strength provided by the asymmetric algorithms.

To be continued...