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


2.5 Product Cryptosystems

Another innovation introduced by Shannon in his 1949 paper was the idea of combining cryptosystems by forming their “product.” This idea has been of fundamental importance in the design of present-day cryptosystems such as the Data Encryption Standard, which we study in the next chapter.

For simplicity, we will confine our attention in this section to cryptosystems in which : cryptosystems of this type are called endomorphic. Suppose and are two endomorphic cryptosystems which have the same plaintext (and ciphertext) spaces. Then the product of S1 and S2, denoted by S1 × S2, is defined to be the cryptosystem

A key of the product cryptosystem has the form K = (K1, K2), where and . The encryption and decryption rules of the product cryptosystem are defined as follows: For each K = (K1, K2), we have an encryption rule eK defined by the formula

and a decryption rule defined by the formula

That is, we first encrypt x with , and then “re-encrypt” the resulting ciphertext with . Decrypting is similar, but it must be done in the reverse order:

Recall also that cryptosystems have probability distributions associated with their keyspaces. Thus we need to define the probability distribution for the keyspace of the product cryptosystem. We do this in a very natural way:


Figure 2.2  Multiplicative Cipher

In other words, choose K1 using the distribution , and then independently choose K2 using the distribution .

Here is a simple example to illustrate the definition of a product cryptosystem. Suppose we define the Multiplicative Cipher as in Figure 2.2.

Suppose M is the Multiplicative Cipher (with keys chosen equiprobably) and S is the Shift Cipher (with keys chosen equiprobably). Then it is very easy to see that M × S is nothing more than the Affine Cipher (again, with keys chosen equiprobably). It is slightly more difficult to show that S × M is also the Affine Cipher with equiprobable keys.

Let’s prove these assertions. A key in the Shift Cipher is an element , and the corresponding encryption rule is eK(x) = x + K mod 26. A key in the Multiplicative Cipher is an element such that gcd(a, 26) = 1; the corresponding encryption rule is ea(x) = ax mod 26. Hence, a key in the product cipher M × S has the form (a, K), where

But this is precisely the definition of a key in the Affine Cipher. Further, the probability of a key in the Affine Cipher is 1/312 = 1/12 × 1/26, which is the product of the probabilities of the keys a and K, respectively. Thus M × S is the Affine Cipher.

Now let’s consider S × M. A key in this cipher has the form (K, a), where

Thus the key (K, a) of the product cipher S × M is identical to the key (a, aK) of the Affine Cipher. It remains to show that each key of the Affine Cipher arises with the same probability 1/312 in the product cipher S × M. Observe that aK = K1 if and only if K = a-1K1 (recall that gcd(a, 26) = 1, so a has a multiplicative inverse). In other words, the key (a, K1) of the Affine Cipher is equivalent to the key (a-1K1, a) of the product cipher S × M. We thus have a bijection between the two key spaces. Since each key is equiprobable, we conclude that S × M is indeed the Affine Cipher.

We have shown that M × S = S × M. Thus we would say that the two cryptosystems commute. But not all pairs of cryptosystems commute; it is easy to find counterexamples. On the other hand, the product operation is always associative: (S1 × S2) × S3 = S1 × (S2 × S3).

If we take the product of an (endomorphic) cryptosystem S with itself, we obtain the cryptosystem S × S, which we denote by S2. If we take the n-fold product, the resulting cryptosystem is denoted by Sn. We call Sn an iterated cryptosystem.

A cryptosystem S is defined to be idempotent if S2 = S. Many of the cryptosystems we studied in Chapter 1 are idempotent. For example, the Shift, Substitution, Affine, Hill, Vigenere and Permutation Ciphers are all idempotent. Of course, if a cryptosystem S is idempotent, then there is no point in using the product system S2, as it requires an extra key but provides no more security.

If a cryptosystem is not idempotent, then there is a potential increase in security by iterating several times. This idea is used in the Data Encryption Standard, which consists of 16 iterations. But, of course, this approach requires a non-idempotent cryptosystem to start with. One way in which simple non-idempotent cryptosystems can sometimes be constructed is to take the product of two different (simple) cryptosystems.

REMARK  It is not hard to show that if S1 and S2 are both idempotent and they commute, then S1 × S2 will also be idempotent. This follows from the following algebraic manipulations:

(Note the use of the associative property in this proof.)

So, if S1 and S2 are both idempotent, and we want S1 × S2 to be non-idempotent, then it is necessary that S1 and S2 not commute.

Fortunately, many simple cryptosystems are suitable building blocks in this type of approach. Taking the product of substitution-type ciphers with permutation-type ciphers is a commonly used technique. We will see a realization of this in the next chapter.


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