Cryptography: Theory and Practice by Douglas Stinson CRC Press, CRC Press LLC ISBN: 0849385210 Pub Date: 03/17/95 |
Previous | Table of Contents | Next |
Example 1.2
Given the ciphertext string
JBCRCLQRWCRVNBJENBWRWN,
we successively try the decryption keys d0, d1, etc. The following is obtained:
jbcrclqrwcrvnbjenbwrwn iabqbkpqvbqumaidmavqvm hzapajopuaptlzhclzupul gyzozinotzoskygbkytotk fxynyhmnsynrjxfajxsnsj ewxmxglmrxmqiweziwrmri dvwlwfklqwlphvdyhvqlqh cuvkvejkpvkogucxgupkpg btujudijoujnftbwftojof astitchintimesavesnine
At this point, we have determined the plaintext and we can stop. The key is K = 9.
On average, a plaintext will be computed after trying 26/2 = 13 decryption rules.
Figure 1.3 Substitution Cipher
As the above example indicates, a necessary condition for a cryptosystem to be secure is that an exhaustive key search should be infeasible; i.e., the keyspace should be very large. As might be expected, a large keyspace is not sufficient to guarantee security.
Another well-known cryptosystem is the Substitution Cipher. This cryptosystem has been used for hundreds of years. Puzzle cryptograms in newspapers are examples of Substitution Ciphers. This cipher is defined in Figure 1.3.
Actually, in the case of the Substitution Cipher, we might as well take and both to be the 26-letter English alphabet. We used in the Shift Cipher because encryption and decryption were algebraic operations. But in the Substitution Cipher, it is more convenient to think of encryption and decryption as permutations of alphabetic characters.
Here is an example of a random permutation, π, which could comprise an encryption function. (As before, plaintext characters are written in lower case and ciphertext characters are written in upper case.)
Thus, eπ(a) = X, eπ(b) = N, etc. The decryption function is the inverse permutation. This is formed by writing the second lines first, and then sorting in alphabetical order. The following is obtained:
Hence, dπ(A) = d, dπ(B) = l, etc.
As an exercise, the reader might decrypt the following ciphertext using this decryption function:
MGZVYZLGHCMHJMYXSSFMNHAHYCDLMHA.
A key for the Substitution Cipher just consists of a permutation of the 26 alphabetic characters. The number of these permutations is 26!, which is more than 4.0 × 1026, a very large number. Thus, an exhaustive key search is infeasible, even for a computer. However, we shall see later that a Substitution Cipher can easily be cryptanalyzed by other methods.
The Shift Cipher is a special case of the Substitution Cipher which includes only 26 of the 26! possible permutations of 26 elements. Another special case of the Substitution Cipher is the Affine Cipher, which we describe now. In the Affine Cipher, we restrict the encryption functions to functions of the form
These functions are called affine functions, hence the name Affine Cipher. (Observe that when a = 1, we have a Shift Cipher.)
In order that decryption is possible, it is necessary to ask when an affine function is injective. In other words, for any , we want the congruence
to have a unique solution for x. This congruence is equivalent to
Now, as y varies over , so, too, does y - b vary over . Hence, it suffices to study the congruence ax ≡ y (mod 26) .
We claim that this congruence has a unique solution for every y if and only if gcd(a, 26) = 1 (where the gcd function denotes the greatest common divisor of its arguments). First, suppose that gcd(a, 26) = d > 1. Then the congruence ax ≡ 0 (mod 26) has (at least) two distinct solutions in , namely x = 0 and x = 26/d. In this case e(x) = ax + b mod 26 is not an injective function and hence not a valid encryption function.
For example, since gcd(4, 26) = 2, it follows that 4x + 7 is not a valid encryption function: x and x + 13 will encrypt to the same value, for any
Lets next suppose that gcd(a, 26) = 1. Suppose for some x1 and x2 that
Then
and thus
We now make use of a property of division: if gcd(a, b) = 1 and a | bc, then a | c. Since 26| a(x1 - x2) and gcd(a, 26) = 1, we must therefore have that
i.e., x1 ≡ x2 (mod 26).
At this point we have shown that, if gcd(a, 26) = 1, then a congruence of the form ax ≡ y (mod 26) has, at most, one solution in . Hence, if we let x vary over , then ax mod 26 takes on 26 distinct values modulo. 26. That is, it takes on every value exactly once. It follows that, for any , the congruence ax ≡ y (mod 26) has a unique solution for y.
There is nothing special about the number 26 in this argument. The following result can be proved in an analogous fashion.
THEOREM 1.1
The congruence ax ≡ b (mod m) has a unique solution for every if and only if gcd(a, m) = 1.
Since 26 = 2 × 13, the values of such that gcd(a, 26) = 1 are a = 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, and 25. The parameter b can be any element in . Hence the Affine Cipher has 12 × 26 = 312 possible keys. (Of course, this is much too small to be secure.)
Lets now consider the general setting where the modulus is m. We need another definition from number theory.
Previous | Table of Contents | Next |
Copyright © CRC Press LLC