![]() |
|
|||
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
|
![]() |
[an error occurred while processing this directive]
DEFINITION 2.2 A cryptosystem has perfect secrecy if 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 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 Now, for fixed y, the values y - K mod 26 comprise a permutation of 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 THEOREM 2.4 Suppose PROOF Suppose the given cryptosystem provides perfect secrecy. As observed above, for each But we are assuming that That is, there do not exist two distinct keys K1 and K2 such that
Denote Consider the perfect secrecy condition 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 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.
Copyright © CRC Press LLC
![]() |
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
![]() |