Cryptography: Theory and Practice:Classical Cryptography | Modern Cryptography: Theory and Practice

Cryptography: Theory and Practice
by Douglas Stinson
CRC Press, CRC Press LLC
ISBN: 0849385210 Pub Date: 03/17/95

Table of Contents

Example 1.2

Given the ciphertext string

                          JBCRCLQRWCRVNBJENBWRWN,

we successively try the decryption keys d₀, d₁, 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.

1.1.2 The Substitution Cipher

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 × 10²⁶, 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 Cipher

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

Let’s next suppose that gcd(a, 26) = 1. Suppose for some x₁ and x₂ 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(x₁ - x₂) and gcd(a, 26) = 1, we must therefore have that

i.e., x₁ ≡ x₂ (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.)

Let’s now consider the general setting where the modulus is m. We need another definition from number theory.

Table of Contents