242 15. A Glimpse of Complexity and Cryptography
applied in one of the most important areas of theoretical computer science,
namely, cryptography.
15.2 Classical Cryptography
Ever since writing was invented, people have been interested not only in
using it to communicate with their partners, but also in trying to conceal
the content of their messages from their adversaries. This leads to cryptog-
raphy (or cryptology), the science of secret communication.
The basic situation is that one party, say King Arthur, wants to send
a message to King Bela. There is, however, a danger that the evil Caesar
Caligula intercepts the message and learns things that he is not supposed
to know about. The message, understandable even for Caligula, is called
theplain text. To protect its content, King Arthurencryptshis message.
When King Bela receives it, he mustdecryptit in order to be able to read
it. For the kings to be able to encrypt and decrypt the message, they must
know something that Caligula does not know: this information is thekey.
Many cryptosystems have been used in history; most of them, in fact,
turn out to be insecure, especially if the adversary can use powerful com-
puting tools to break it.
Perhaps the simplest method issubstitution code: We replace each letter
of the alphabet by another letter. Thekeyis the table that contains for each
letter the letter to be substituted for it. While a message encrypted this
way looks totally scrambled, substitution codes are, in fact, easy to break.
Solving Exercise 15.2.1 will make it clear how the length and positions
of the words can be used to figure out the original meaning of letters if
the word breaks are preserved (i.e., ”space” is not replaced by another
character). But even if the splitting into words is hidden, an analysis of
the frequency of various letters provides enough information to break the
substitution code.
One-time pads.There is another simple frequently used method that is
much more secure: the use of “one-time pads.” This method is very safe; it
was used during World War II for communication between the American
president and the British prime minister. Its disadvantage is that it requires
a very long key (“pad”), which can only be used once.
A one-time pad is a randomly generated string of 0’s and 1’s. Here is
one:
11000111000010000110010100100100101100110010101100001110110000010
Both Kings Arthur and Bela know this sequence (it was sent well in advance
by a messenger). Now King Arthur wants to send the following message to
King Bela:
ATTACK MONDAY