Cipher Pad



Cipher Pad

█ LARRY GILMAN

A cipher pad is a printed list of cipher keys, each intended to be used for the encipherment and decipherment of a single message. Cipher pads (also termed one-time pads) are closely related to one-time tapes and stream ciphers, which are discussed below.

A key is a string of letters or numbers that is needed to correctly encipher or decipher a message. Each distinct key produces a unique ciphertext from a given plaintext (and vice versa). Both sender and receiver must therefore, know the key associated with a specific message if the message is to be successfully enciphered and deciphered. As long as the key remains unknown to an opponent, the enciphered message is secure. If an opponent, however, does manage to steal or guess the key—for example, by systematically trying out all possible keys—then they will have broken the cipher and can decipher the secret message. Another weakness of ordinary key-based ciphering is that the more text is sent using a single key, the easier it is for an opponent to deduce the key by analysis of intercepted messages.

These facts suggest two basic rules of key use: (1) Change keys often. This prevents an opponent from building up a large mass of text, all enciphered by the same key, which can be used to deduce the key. (2) Use long keys. This makes it impractical for an attacker to find the right key by pure guessing. For example, if the key is a 56-bit binary number (as it is for the Data Encryption Standard, a U.S.-government-designed ciphering system widely used since 1977), then there are 2 56 > 7.2 × 10 16 possible keys.

A cipher-pad system takes key changing to a logical extreme by using a different key for every message. The keys used are, furthermore, long enough to keep an opponent from simply guessing at them. These selected keys are printed in a book (the cipher pad), the pad is distributed to all senders and receivers, and the keys in the pad are used up one by one as messages are sent. This has the disadvantage that only a limited number of messages can be sent before a new cipher pad must be printed and distributed. Also, as with codebook systems, there is always the danger that a copy of the book will be captured. For these reasons, printed cipher pads have not often been used.

Principle of ciphering. The cipher-pad principle is important, however, when combined with the following fundamental principle of ciphering: A cipher employing a key that is at least as long as the message itself and is never used for any other message can be made truly unbreakable. This is easy to verify: imagine a message 50 letters long that has been encrypted using a key 50 letters long. To guess the correct key means trying out all possible 50-letter strings. Even if this were practical—and it is not, for there are 26 50 > 10 70 such strings, more than the number of atoms in our galaxy—generating all keys 50 characters long is the same thing as generating all messages 50 characters long. Generating all possible messages is the same as simply guessing at what the message is, which is the same as being unable to break the cipher.

The first mechanized application of this principle was the one-time tape system, invented early in the 20th century by U.S. cryptologist Gilbert Vernam (1890–1960) and perfected by Major Joseph Mauborgne of the U.S. Army in 1918. In this system, a message is encrypted as a series of punched holes on a long paper tape. The holes on the message tape are a function of both the message and a randomly generated key (character string) that is as long as the message itself. The key is stored on one tape and the message on the other, and both tapes are shipped by different routes to the intended recipient. The tapes are read simultaneously by a machine that outputs the deciphered text. There is an obvious disadvantage to this technique: the need to send the key. This rules out any kind of telecommunications, for if an enemy intercepted both the key sequence and the message sequence they could decipher the message. Thus, only a perfectly secure transmission channel can be trusted with such information. If the transmission channel is perfectly secure, then there is no need to cipher. The one-tape system is thus, limited to situations in which physical transport of messages is practical.

This limitation is overcome in modern communications by the use of pseudorandom numbers. A truly random number sequence is one that contains no overall structure or pattern; a pseudorandom number sequence is one that looks like truly random sequence but is in fact produced by a series of arithmetical calculations that can be repeated at will. Pseudorandom number sequences are easy to generate in digital computers using arithmetical procedures termed pseudorandom number generators (PNGs). The bits produced by a PNG can be strung together into a stream that is as long as any desired message. This stream of bits is termed "the cryptographic bit stream" or "key-stream." A message can then be encrypted by performing the EXCLUSIVE OR (XOR) operation pairwise on bits from the message-stream and the key-stream. The XOR operation for two bits is defined as follows:

Cipher Pad

The following is a message-stream, a key-stream, and the encrypted bitstream produced by XORing the message-stream and the key-stream together:

Message-stream:     1 0 1 1 0 0 0 1

Key-stream:      0 1 0 1 0 0 1 1

Encrypted bitstream:   1 1 1 0 0 0 1 0

It is easy to verify that each bit in the encrypted bitstream is the XOR of the two bits above it.

The XOR function is used for encipherment because it has the following useful property: the XOR of the encrypted bitstream and of the key-stream recovers the message-stream.

Encrypted bitstream:   1 1 1 0 0 0 1 0

Key-stream:       0 1 0 1 0 0 1 1

Recovered message:   1 0 1 1 0 0 0 1

In the example above, it is easy to verify that each bit in the recovered message is the XOR of the two bits above it. Because cipher systems of this type work on streams of bits, they are termed stream ciphers.

The discussion so far assumed that the receiver of the encrypted message has access to the same key-stream as the sender. In a cipher-pad or one-time-tape system, agreement on the key sequence is assured by sending the key (on paper or some other medium) to both ends of the link. In a stream cipher, it is assured by generating the key-stream at both ends of the link. Because the pseudorandom bits of the key-stream are generated by a PNG, both ends of the cipher link need only start their PNGs at the same point in its series of operations to generate the same key-stream. This can be accomplished by transmission to the receiver of a group of numbers termed a "seed" or "initializing vector."

Quantum cryptography. Weak points exist even in this system. For example, all PNGs start to repeat themselves eventually, and so do not produce truly random numbers. Also, the initializing vector must be known somehow at both ends of the cipher link. The answer to these difficulties may be resolved using quantum cryptography. In quantum cryptography, stream ciphering returns to the old idea of sending a key-stream along with the message. However, the key-stream is not sent on a paper tape or even as a conventional digital message. It is generated by the sender as a series of truly random subatomic events and shared by the sender and receiver using pairs of "entangled" photons that cannot, by the most fundamental laws of physics as they are now understood, be intercepted without revealing the presence of the eavesdropper.

Real-world quantum-cryptographic systems are being developed rapidly, and proof-of-concept systems have already been built. Thus, there seems to be no basic obstacle to the development of truly unbreakable quantum-cryptographic systems, the ultimate development of the cipher-pad concept.

█ FURTHER READING:

BOOKS:

Meyer, Carl H., and Stephen M. Matyas. Cryptography: A New Dimension in Computer Data Security. New York: John Wiley & Sons, 1982.

Mollin, Richard A. An Introduction to Cryptography. New York: Chapman & Hall, 2001.

PERIODICALS:

Bennett, Charles H., and Peter W. Shor. "Privacy in a Quantum World." Science no. 5415 (1999): 747–748.

SEE ALSO

Codes and Ciphers
Quantum Physics: Applications to Espionage, Intelligence, and Security Issues



User Contributions:

Comment about this article, ask questions, or add new information about this topic:


Cipher Pad forum