Cryptography: Theory and Practice by Douglas Stinson CRC Press, CRC Press LLC ISBN: 0849385210 Pub Date: 03/17/95 |
Previous | Table of Contents | Next |
DEFINITION 2.2 A cryptosystem has perfect secrecy if for all . That is, the a posteriori probability that the plaintext is x, given that the ciphertext y is observed, is identical to the a priori probability that the plaintext is x.
In Example 2.1, the perfect secrecy property is satisfied for the ciphertext 3, but not for the other three ciphertexts.
We next prove that the Shift Cipher provides perfect secrecy. This seems quite obvious intuitively. For, if we are given any ciphertext element , then any plaintext element is a possible decryption of y, depending on the value of the key. The following theorem gives the formal statement and proof using probability distributions.
THEOREM 2.3
Suppose the 26 keys in the Shift Cipher are used with equal probability 1/26. Then for any plaintext probability distribution, the Shift Cipher has perfect secrecy.
PROOF Recall that , and for 0 ≤ K ≤ 25, the encryption rule eK is eK (x) = x + K mod 26 . First, we compute the distribution . Let ; then
Now, for fixed y, the values y - K mod 26 comprise a permutation of , and is a probability distribution. Hence we have that
Consequently,
for any .
Next, we have that
for every x, y, since for every x, y the unique key K such that eK(x) = y is K = y - x mod 26. Now, using Bayes Theorem, it is trivial to compute
so we have perfect secrecy.
So, the Shift Cipher is unbreakable provided that a new random key is used to encrypt every plaintext character.
Let us next investigate perfect secrecy in general. First, we observe that, using Bayes Theorem, the condition that for all is equivalent to for all . Now, let us make the reasonable assumption that for all , then ciphertext y is never used and can be omitted from ). Fix any . For each , we have . Hence, for each , there must be at least one key K such that eK(x) = y. It follows that . In any cryptosystem, we must have since each encoding rule is an injection. In the boundary case , we can give a nice characterization of when perfect secrecy can be obtained. This characterization is originally due to Shannon.
THEOREM 2.4
Suppose is a cryptosystem where . Then the cryptosystem provides perfect secrecy if and only if every key is used with equal probability , every , and every , there is a unique key K such that eK(x) = y.
PROOF Suppose the given cryptosystem provides perfect secrecy. As observed above, for each and there must be at least one key K such that eK(x) = y. So we have the inequalities:
But we are assuming that . Hence, it must be the case that
That is, there do not exist two distinct keys K1 and K2 such that . Hence, we have shown that for any and , there is exactly one key K such that eK(x) = y.
Figure 2.1 One-time Pad
Denote . Let and fix a . We can name the keys K1, K2,..., Kn, in such a way that . Using Bayes theorem, we have
Consider the perfect secrecy condition . From this, it follows that , for 1 ≤ i ≤ n. This says that the keys are used with equal probability (namely, ). But since the number of keys is , we must have that for every .
Conversely, suppose the two hypothesized conditions are satisfied. Then the cryptosystem is easily seen to provide perfect secrecy for any plaintext probability distribution, in a similar manner as the proof of Theorem 2.3. We leave the details for the reader.
One well-known realization of perfect secrecy is the Vernam One-time Pad, which was first described by Gilbert Vernam in 1917 for use in automatic encryption and decryption of telegraph messages. It is interesting that the One-time Pad was thought for many years to be an unbreakable cryptosystem, but there was no proof of this until Shannon developed the concept of perfect secrecy over 30 years later.
The description of the One-time Pad is given in Figure 2.1.
Using Theorem 2.4, it is easily seen that the One-time Pad provides perfect secrecy. The system is also attractive because of the ease of encryption and decryption.
Vernam patented his idea in the hope that it would have widespread commercial use. Unfortunately, there are major disadvantages to unconditionally secure cryptosystems such as the One-time Pad. The fact that means that the amount of key that must be communicated securely is at least as big as the amount of plaintext. For example, in the case of the One-time Pad, we require n bits of key to encrypt n bits of plaintext. This would not be a major problem if the same key could be used to encrypt different messages; however, the security of unconditionally secure cryptosystems depends on the fact that each key is used for only one encryption. (This is the reason for the term one-time in the One-time Pad.)
For example, the One-time Pad is vulnerable to a known-plaintext attack, since K can be computed as the exclusive-or of the bitstrings x and eK(x). Hence, a new key needs to be generated and communicated over a secure channel for every message that is going to be sent. This creates severe key management problems, which has limited the use of the One-time Pad in commercial applications. However, the One-time Pad has seen application in military and diplomatic contexts, where unconditional security may be of great importance.
The historical development of cryptography has been to try to design cryptosystems where one key can be used to encrypt a relatively long string of plaintext (i.e., one key can be used to encrypt many messages) and still maintain (at least) computational security. One such system is the Data Encryption Standard, which we will study in Chapter 3.
Previous | Table of Contents | Next |
Copyright © CRC Press LLC