Cryptography: Theory and Practice:Shannon s Theory

cryptography: theory and practice 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 ≤ in. 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



Cryptography. Theory and Practice
Modern Cryptography: Theory and Practice
ISBN: 0130669431
EAN: 2147483647
Year: 1995
Pages: 133
Authors: Wenbo Mao

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net