Modern Cryptography: Theory and Practice

Chapter 1Classical Cryptography

1.1 Introduction: Some Simple Cryptosystems

The fundamental objective of cryptography is to enable two people, usually referred to as Alice and Bob, to communicate over an insecure channel in such a way that an opponent, Oscar, cannot understand what is being said. This channel could be a telephone line or computer network, for example. The information that Alice wants to send to Bob, which we call “plaintext,” can be English text, numerical data, or anything at all — its structure is completely arbitrary. Alice encrypts the plaintext, using a predetermined key, and sends the resulting ciphertext over the channel. Oscar, upon seeing the ciphertext in the channel by eavesdropping, cannot determine what the plaintext was; but Bob, who knows the encryption key, can decrypt the ciphertext and reconstruct the plaintext.

This concept is described more formally using the following mathematical notation.

DEFINITION 1.1  A cryptosystem is a five-tuple , where the following conditions are satisfied:

1.   is a finite set of possible plaintexts

2.   is a finite set of possible ciphertexts

3.   , the keyspace, is a finite set of possible keys

4.  For each , there is an encryption rule e_K and a corresponding decryption rule . Each and are functions such that d_K(e_K(x)) = x for every plaintext

The main property is property 4. It says that if a plaintext x is encrypted using e_K, and the resulting ciphertext is subsequently decrypted using d_K, then the original plaintext x results.

Alice and Bob will employ the following protocol to use a specific cryptosystem. First, they choose a random key This is done when they are in the same place and are not being observed by Oscar, or, alternatively, when they do have access to a secure channel, in which case they can be in different places. At a later time, suppose Alice wants to communicate a message to Bob over an insecure channel. We suppose that this message is a string

for some integer n ≥ 1, where each plaintext symbol , 1 ≤ i ≤ n. Each x_i is encrypted using the encryption rule e_K specified by the predetermined key K. Hence, Alice computes y_i = e_K(x_i), 1 ≤ i ≤ n, and the resulting ciphertext string

is sent over the channel. When Bob receives y₁y₂ . . . y_n, he decrypts it using the decryption function d_K, obtaining the original plaintext string, x₁x₂. . .x_n. See Figure 1.1 for an illustration of the communication channel.

Figure 1.1  The Communication Channel

Clearly, it must be the case that each encryption function e_K is an injective function (i.e., one-to-one), otherwise, decryption could not be accomplished in an unambiguous manner. For example, if

where x₁ ≠ x₂, then Bob has no way of knowing whether y should decrypt to x₁ or x₂. Note that if , it follows that each encryption function is a permutation. That is, if the set of plaintexts and ciphertexts are identical, then each encryption function just rearranges (or permutes) the elements of this set.

1.1.1 The Shift Cipher

In this section, we will describe the Shift Cipher, which is based on modular arithmetic. But first we review some basic definitions of modular arithmetic.

DEFINITION 1.2  Suppose a and b are integers, and m is a positive integer. Then we write a ≡ b (mod m) if m divides b - a. The phrase a ≡ b (mod m) is read as “a is congruent to b modulo m.” The integer m is called the modulus.

Suppose we divide a and b by m, obtaining integer quotients and remainders, where the remainders are between 0 and m - 1. That is, a = q₁m + r₁ and b = q₂m + r₂, where 0 ≤ r₁ ≤ m - 1 and 0 ≤ r₂ ≤ m - 1. Then it is not difficult to see that a ≡ b (mod m) if and only if r₁ = r₂. We will use the notation a mod m (without parentheses) to denote the remainder when a is divided by m, i.e., the value r₁ above. Thus a ≡ b (mod m) if and only if a mod m = b mod m. If we replace a by a mod m, we say that a is reduced modulo m.

REMARK  Many computer programming languages define a mod m to be the remainder in the range -m + 1, . . . , m - 1 having the same sign as a. For example, -18 mod 7 would be -4, rather than 3 as we defined it above. But for our purposes, it is much more convenient to define a mod m always to be nonnegative.

We can now define arithmetic modulo m: is defined to be the set {0, . . . , m-1}, equipped with two operations, + and ×. Addition and multiplication in work exactly like real addition and multiplication, except that the results are reduced modulo m.

For example, suppose we want to compute 11 × 13 in . As integers, we have 11 × 13 = 143. To reduce 143 modulo 16, we just perform ordinary long division: 143 = 8 × 16 + 15, so 143 mod 16 = 15, and hence 11 × 13 = 15 in .

Copyright © CRC Press LLC