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:
POYYAEAAZX
which would decrypt to:
SALMONEGGS
or
BXFGBMTMXM
which would decrypt to:
GREENFLUID
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).
There are many cryptographic algorithms. These are three of the most common:
These are the kinds of stuff this book is about.
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
TABLE 1.1 Large Numbers | |
---|---|
Physical Analogue | Number |
Odds of being killed by lightning (per day) | 1 in 9 billion (2^{33}) |
Odds of winning the top prize in a U.S. state lottery | 1 in 4,000,000 (2^{22}) |
Odds of winning the top prize in a U.S. state lottery and being killed by lightning in the same day | 1 in 2^{55} |
Odds of drowning (in the U.S. per year) | 1 in 59,000 (2^{16}) |
Odds of being killed in an automobile accident(in the U.S. in 1993) | 1 in 6100 (2^{13}) |
Odds of being killed in an automobile accident(in the U.S. per lifetime) | 1 in 88 (2^{7}) |
Time until the next ice age | 14,000 (2^{14}) years |
Time until the sun goes nova | 10^{9} (2^{30}) years |
Age of the planet | 10^{9} (2^{30}) years |
Age of the Universe | 10^{10} (2^{34}) years |
Number of atoms in the planet | 10^{51} (2^{170}) |
Number of atoms in the sun | 10^{57} (2^{190}) |
Number of atoms in the galaxy | 10^{67} (2^{223}) |
Number of atoms in the Universe (dark matter excluded) | 10^{77} (2^{265}) |
Volume of the Universe | 10^{84} (2^{280}) cm^{3} |
If the Universe is Closed: | |
Total lifetime of the Universe | 10^{11} (2^{37}) years 10^{18} (2^{61}) seconds |
If the Universe is Open: | |
Time until low-mass stars cool off | 10^{14} (2^{47}) years |
Time until planets detach from stars | 10^{15} (2^{50}) years |
Time until stars detach from galaxies | 10^{19} (2^{64}) years |
Time until orbits decay by gravitational radiation | 10^{20} (2^{67}) years |
Time until black holes decay by the Hawking process | 10^{64} (2^{213}) years |
Time until all matter is liquid at zero temperature | 10^{65} (2^{216}) years |
Time until all matter decays to iron | 10^{1026} years |
Time until all matter collapses to black holes | 10^{1076} 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 |