![]() |
|
|||
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
|
![]() |
[an error occurred while processing this directive]
2.5 Product CryptosystemsAnother 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 A key of the product cryptosystem has the form K = (K1, K2), where and a decryption rule defined by the formula That is, we first encrypt x with Recall also that cryptosystems have probability distributions associated with their keyspaces. Thus we need to define the probability distribution for the keyspace
In other words, choose K1 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. Lets prove these assertions. A key in the Shift Cipher is an element 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 lets 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.
Copyright © CRC Press LLC
![]() |
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
![]() |