![]() |
|
|||
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
|
![]() |
[an error occurred while processing this directive]
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.
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. 1.1.2 The Substitution CipherAnother 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 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. 1.1.3 The Affine CipherThe 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
In order that decryption is possible, it is necessary to ask when an affine function is injective. In other words, for any to have a unique solution for x. This congruence is equivalent to Now, as y varies over 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 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 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 Since 26 = 2 × 13, the values of Lets now consider the general setting where the modulus is m. We need another definition from number theory.
Copyright © CRC Press LLC
![]() |
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
![]() |