Applied Cryptography, Second Edition: Protocols, Algorthms, and Source Code in C (cloth)
(Publisher: John Wiley & Sons, Inc.)
Author(s): Bruce Schneier
ISBN: 0471128457
Publication Date: 01/01/96

Previous Table of Contents Next

Assuming an eavesdropper can’t get access to the one-time pad used to encrypt the message, this scheme is perfectly secure. A given ciphertext message is equally likely to correspond to any possible plaintext message of equal size.

Since every key sequence is equally likely (remember, the key letters are generated randomly), an adversary has no information with which to cryptanalyze the ciphertext. The key sequence could just as likely be:


which would decrypt to:




which would decrypt to:


This point bears repeating: Since every plaintext message is equally possible, there is no way for the cryptanalyst to determine which plaintext message is the correct one. A random key sequence added to a nonrandom plaintext message produces a completely random ciphertext message and no amount of computing power can change that.

The caveat, and this is a big one, is that the key letters have to be generated randomly. Any attacks against this scheme will be against the method used to generate the key letters. Using a pseudo-random number generator doesn’t count; they always have nonrandom properties. If you use a real random source—this is much harder than it might first appear, see Section 17.14—it’s secure.

The other important point is that you can never use the key sequence again, ever. Even if you use a multiple-gigabyte pad, if a cryptanalyst has multiple ciphertexts whose keys overlap, he can reconstruct the plaintext. He slides each pair of ciphertexts against each other and counts the number of matches at each position. If they are aligned right, the proportion of matches jumps suddenly—the exact percentages depend on the plaintext language. From this point cryptanalysis is easy. It’s like the index of coincidence, but with just two “periods” to compare [904]. Don’t do it.

The idea of a one-time pad can be easily extended to binary data. Instead of a one-time pad consisting of letters, use a one-time pad of bits. Instead of adding the plaintext to the one-time pad, use an XOR. To decrypt, XOR the ciphertext with the same one-time pad. Everything else remains the same and the security is just as perfect.

This all sounds good, but there are a few problems. Since the key bits must be random and can never be used again, the length of the key sequence must be equal to the length of the message. A one-time pad might be suitable for a few short messages, but it will never work for a 1.544 Mbps communications channel. You can store 650 megabytes worth of random bits on a CD-ROM, but there are problems. First, you want exactly two copies of the random bits, but CD-ROMs are economical only for large quantities. And second, you want to be able to destroy the bits already used. CD-ROM has no erase facilities except for physically destroying the entire disk. Digital tape is a much better medium for this sort of thing.

Even if you solve the key distribution and storage problem, you have to make sure the sender and receiver are perfectly synchronized. If the receiver is off by a bit (or if some bits are dropped during the transmission), the message won’t make any sense. On the other hand, if some bits are altered during transmission (without any bits being added or removed—something far more likely to happen due to random noise), only those bits will be decrypted incorrectly. But on the other hand, a one-time pad provides no authenticity.

One-time pads have applications in today’s world, primarily for ultra-secure low-bandwidth channels. The hotline between the United States and the former Soviet Union was (is it still active?) rumored to be encrypted with a one-time pad. Many Soviet spy messages to agents were encrypted using one-time pads. These messages are still secure today and will remain that way forever. It doesn’t matter how long the supercomputers work on the problem. Even after the aliens from Andromeda land with their massive spaceships and undreamed-of computing power, they will not be able to read the Soviet spy messages encrypted with one-time pads (unless they can also go back in time and get the one-time pads).

1.6 Computer Algorithms

There are many cryptographic algorithms. These are three of the most common:

— DES (Data Encryption Standard) is the most popular computer encryption algorithm. DES is a U.S. and international standard. It is a symmetric algorithm; the same key is used for encryption and decryption.
— RSA (named for its creators—Rivest, Shamir, and Adleman) is the most popular public-key algorithm. It can be used for both encryption and digital signatures.
— DSA (Digital Signature Algorithm, used as part of the Digital Signature Standard) is another public-key algorithm. It cannot be used for encryption, but only for digital signatures.

These are the kinds of stuff this book is about.

1.7 Large Numbers

Throughout this book, I use various large numbers to describe different things in cryptography. Because it is so easy to lose sight of these numbers and what they signify, Table 1.1 gives physical analogues for some of them.

These numbers are order-of-magnitude estimates, and have been culled from a variety of sources. Many of the astrophysics numbers are explained in Freeman

Large Numbers

Physical Analogue Number

Odds of being killed by lightning (per day) 1 in 9 billion (233)
Odds of winning the top prize in a U.S. state lottery 1 in 4,000,000 (222)
Odds of winning the top prize in a U.S. state lottery and being killed by lightning in the same day 1 in 255
Odds of drowning (in the U.S. per year) 1 in 59,000 (216)
Odds of being killed in an automobile accident(in the U.S. in 1993) 1 in 6100 (213)
Odds of being killed in an automobile accident(in the U.S. per lifetime) 1 in 88 (27)
Time until the next ice age 14,000 (214) years
Time until the sun goes nova 109 (230) years
Age of the planet 109 (230) years
Age of the Universe 1010 (234) years
Number of atoms in the planet 1051 (2170)
Number of atoms in the sun 1057 (2190)
Number of atoms in the galaxy 1067 (2223)
Number of atoms in the Universe (dark matter excluded) 1077 (2265)
Volume of the Universe 1084 (2280) cm3
If the Universe is Closed:
Total lifetime of the Universe 1011 (237) years
1018 (261) seconds
If the Universe is Open:
Time until low-mass stars cool off 1014 (247) years
Time until planets detach from stars 1015 (250) years
Time until stars detach from galaxies 1019 (264) years
Time until orbits decay by gravitational radiation 1020 (267) years
Time until black holes decay by the Hawking process 1064 (2213) years
Time until all matter is liquid at zero temperature 1065 (2216) years
Time until all matter decays to iron 101026 years
Time until all matter collapses to black holes 101076 years

Dyson’s paper, “Time Without End: Physics and Biology in an Open Universe,” in Reviews of Modern Physics, v. 52, n. 3, July 1979, pp. 447–460. Automobile accident deaths are calculated from the Department of Transportation’s statistic of 163 deaths per million people in 1993 and an average lifespan of 69.7 years.

Previous Table of Contents Next
[an error occurred while processing this directive]