Monday, April 19, 2004

one-time pads

Donald Sensing has an interesting discussion of encryption over at One Hand Clapping. He explains one-time pads which are a perfect encryption technique in the sense that they are impossible to break unless you have the key. I thought I'd add some interesting details for computerized one-time pads.

A one-time pad is a very large random number (possibly with thousands of digits). There is an operation called exclusive-or (xor) that you can use to take a piece of text and a number to produce another large number. If you do the operation again with the same number, it gives you back the original text. For example suppose the one-time pad is 1193046 and the text is the word "cat". Then "cat" xor 1193046 = 1127746, so your encrypted message is 1127746. When someone receives the message they xor it with the pad: 1127746 xor 1193046 = "cat".

If the number you use for the pad is random, then the result of the xor operation will be effectively random also and there is no way to figure out the text without knowing the pad. In fact, you could give someone a fake pad to make the message come out to be anything you want. In the previous example, suppose someone intercepted your encrypted message and you wanted them to think they have deciphered it. You could let slip that the pad is 1391173 and they would decrypt: 1127746 xor 1391173 = "dog". Clearly, since the encrypted message can be decrypted to any message at all (within the length restrictions) given the right pad, you have no way to know which one is the actual message.

The problem with one-time pads is that the pad contains as much information as the message and it requires a fully secure channel because if anyone can intercept the pad, he can easily decrypt the message. If you have a fully secure channel with enough bandwidth for the pad, why not use it to send the message? One-time pads are really only useful when you have two channels, one secure and one insecure, and you don't always have the secure channel available. Usually the non-secure channel is a wide-area network and the secure channel is some guy on a plane carrying a CD. In these cases, you can use the secure channel to send the pads whenever you can and you use the non-secure but faster, more reliable, or more widely available channel to send the messages.

UPDATE: Donald's masterful and detailed account of quantum cryptography demonstrates once again why he's the only blogger to turn to for postings on quantum computation-related subjects. Well, that, and there's no other bloggers who actually blog about that stuff. But his posting is highly technical, so I thought I'd break it down into a less technical level, like I did the information on one-time pads. OK here goes:

There's these little fairies that you can send running down an optical fiber to carry messages. If someone catches one of the fairies half-way and forces them to talk, then lets them go again, they will (with some probability) report that they were captured so you can know that someone is eavesdropping. This means that you can use a semi-secure channel to transmit a one-time pad because if someone intercepts the information you will know about it and you can just throw away that pad. As soon as you get a pad through without it being intercepted, you can send your message by any channel and use the pad to encrypt it.

No comments: