Читать книгу Information Security - Mark Stamp - Страница 36

The one‐time pad, which is also known as the Vernam cipher, is a provably secure cryptosystem. Historically it has been used in various times and places, but it's not practical for most situations. However, it does nicely illustrate some important concepts that we'll see again later.

For simplicity, let's consider an alphabet with only eight letters. Our alphabet and the corresponding binary representation of letters appear in Table 2.1. It's important to note that the mapping between letters and bits is not secret. This mapping serves a similar purpose as, say, the ASCII code, which is not much of a secret either.

Table 2.1 Abbreviated alphabet

Letter	e	h	i	k	l	r	s	t
Binary	000	001	010	011	100	101	110	111

Suppose that Trudy, who is working as a Nazi spy in London during World War II, wants to use a one‐time pad to encrypt the plaintext message

She first consults Table 2.1 to convert the plaintext letters to the bit string

The one‐time pad key consists of a randomly selected string of bits that is the same length as the message. The key is then XORed with the plaintext to yield the ciphertext. For the mathematically inclined, a fancier way to say this is that we add the plaintext and key bits modulo 2.

We denote the XOR of bit with bit as . Since , decryption is accomplished by XOR‐ing the same key with the ciphertext. Modern symmetric ciphers utilize this magical property of the XOR in various ways, as we'll see in the next chapter.

Now suppose that Trudy uses the key

which is the correct length to encrypt her message above. Then to encrypt, Trudy computes the ciphertext as

Converting these ciphertext bits back into letters, the ciphertext message to be transmitted is srlhssthsr .

When her fellow Nazi spy, Eve, receives Trudy's message, she decrypts it using the same shared key and thereby recovers the plaintext

Let's consider a couple of scenarios. First, suppose that Trudy has an enemy, Charlie, within the Nazi spy organization. Charlie claims that the actual key used to encrypt Trudy's message is

Eve decrypts the ciphertext using the key given to her by Charlie and obtains

Eve, who doesn't really understand crypto, orders that Trudy be brought in for questioning.

Now let's consider a different scenario. Suppose that the Allies in London intercept Trudy's ciphertext, raising suspicions that she might be spying for the Nazis. The Allies are eager to read the message and Trudy is “encouraged″ to provide the key to her super‐secret message. Trudy claims that she is actually working against the Nazis, and to prove it, she provides the “key″

When the Allies “decrypt″ the ciphertext using this “key,″ they find

The Allies proceed to give Trudy a medal for her work against the Nazis.

While not a proof, these examples serve to illustrate why the one‐time pad is secure in a stronger sense than the ciphers we have previously considered. The bottom line is that if the key is chosen at random, and used only once, then an attacker who obtains the ciphertext has no useful information about the message itself—any “plaintext″ of the same length can be generated by a suitable choice of “key,″ and all possible plaintexts are equally likely. From a cryptographer's point of view, it doesn't get any better than that.

Of course, we are assuming that the one‐time pad cipher is used correctly. The key (or pad) must be chosen at random and used only once. And, since it is a symmetric cipher, the key must be known by both the encryptor and the intended recipient—and nobody else can know the key.

Since we can't do better than provable security, why don't we always use the one‐time pad? Unfortunately, the cipher is impractical for most applications. Why is this the case? The crucial problem is that the pad is the same length as the message and since the pad is the key, it must be securely shared with the intended recipient before the ciphertext can be decrypted. If we can securely transmit the pad, why not simply transmit the plaintext by the same means and do away with the encryption?

Below, we'll see an historical example, where it actually did make sense to use a one‐time pad—in spite of its limitations. However, for modern high data‐rate systems, a one‐time pad cipher would generally be impractical.

Why is it that the one‐time pad can only be used once? Suppose we have two plaintext messages and , and we encrypted these as as and , that is, we have two messages encrypted with the same “one‐time″ pad . In the cryptanalysis business, this is known as a depth. From these two one‐time pad ciphertexts in depth, we can compute

and we see that the key has disappeared from the problem. In this case, the ciphertext does yield some information about the underlying plaintext. Another way to see this is to consider an exhaustive key search. If the pad is only used once, then the attacker has no way to know whether the guessed key is correct or not. But if two messages are in depth, for the correct key, both putative plaintexts must make sense. This provides the attacker with a means to distinguish the correct key from incorrect guesses. The problem only gets worse (or better, from a cryptanalyst's perspective) the more times the key is reused.

Let's consider an example of one‐time pad encryptions that are in depth. Using the same bit encoding as in Table 2.1, suppose we have

and both are encrypted with the same key . Then

and

If Trudy the cryptanalyst knows that the messages are in depth, she immediately sees that the second and fourth letters of and are the same, since the corresponding ciphertext letters are identical. But far more devastating is the fact that Trudy can now guess a putative message and check her results using . Suppose that Trudy, who only knows and , suspects that . Then she can find the corresponding putative key

and she can then use this to “decrypt″ and obtain

Since this does not yield a sensible decryption for , Trudy can safely assume that her guess for was incorrect. When Trudy eventually guesses that she will obtain the correct key and decrypt to also find that , thereby confirming the correctness of the key and, consequently, the correctness of both decryptions.