Saturday, November 1, 2008

Perfect Cryptosystem One-Time Pads

Is there a perfect cryptosystem? Surprisingly, the answer is yes. It is called the onetime pad. The idea of the one-time pad is to have a completely random key that is the same length as the message. The key is never reused, and only the sender and the receiver have copies. To send, for example, a 100-bit message, the message is exclusiveORed' with 100 bits of the key. That portion of the key is crossed off, never to be used again. The receiver reverses the process, exclusive-ORing the ciphertext with her copy of the key to reveal the message. If the one-time pad key contains truly random bits, this scheme is absolutely secure. The attacker does not know what is on the pad and must guess—but there is no way to know when he is right. By changing the guess, the attacker can decode the ciphertext into any message, be it "attack at dawn" or "negotiate surrender."

Internet 2010

The one-time pad offers perfect security and is indeed used when perfect security is needed, but the system has many disadvantages.

  • The pad must be truly random. Any structure at all can be used to break the system. Creating truly random characters is difficult, and creating a vast quantity of them is more difficult.
  • The pad must never be reused. If a sheet is used twice, then the two sections of ciphertext encrypted using the same page can be compared, possibly revealing both.2 Since the pad is consumed as messages are sent, the pad has to be very long or frequently replaced.
  • The pads must be distributed, stored, and used with absolute secrecy. Because the ciphertext cannot be successfully attacked, the obvious point of attack is to copy or substitute a pad.
  • Every pair of correspondents must have a unique pad, leading to immense practical difficulties of distribution.

These practical difficulties effectively restrict the use of one-time pad systems to situations in which cost is no object. For most other situations, cryptosystems are used in which the length of the key is fixed, and the key can be attacked by exhaustive search.

No comments:

Internet Blogosphere