Page 318 - Discrete Mathematics and Its Applications

4.6 Cryptography 297

EXAMPLE 5 Suppose that we intercepted the ciphertext message ZNK KGXRE HOXJ MKZY ZNK CUXS
that we know was produced by a shift cipher. What was the original plaintext message?

Solution: Because we know that the intercepted ciphertext message was encrypted using a
shift cipher, we begin by calculating the frequency of letters in the ciphertext. We find that
the most common letter in the ciphertext is K. So, we hypothesize that the shift cipher sent
the plaintext letter E to the ciphertext letter K. If this hypothesis is correct, we know that
10 = 4 + k mod 26, so k = 6. Next, we shift the letters of the message by −6, obtaining
THE EARLY BIRD GETS THE WORM. Because this message makes sense, we assume that
the hypothesis that k = 6 is correct. ▲

BLOCK CIPHERS Shift ciphers and affine ciphers proceed by replacing each letter of the
alphabet by another letter in the alphabet. Because of this, these ciphers are called character
or monoalphabetic ciphers. Encryption methods of this kind are vulnerable to attacks based
on the analysis of letter frequency in the ciphertext, as we just illustrated. We can make it
harder to successfully attack ciphertext by replacing blocks of letters with other blocks of letters
instead of replacing individual characters with individual characters; such ciphers are called
block ciphers.
We will now introduce a simple type of block cipher, called the transposition cipher.As
a key we use a permutation σ of the set {1, 2,...,m} for some positive integer m, that is, a
one-to-one function from {1, 2,...,m} to itself. To encrypt a message we first split its letters
into blocks of size m. (If the number of letters in the message is not divisible by m we add
some random letters at the end to fill out the final block.) We encrypt the block p 1 p 2 ...p m
as c 1 c 2 ...c m = p σ(1) p σ(2) ...,p σ(m) . To decryt a ciphertext block c 1 c 2 ...c m , we transpose
its letters using the permutation σ −1 , the inverse of σ. Example 6 illustrates encryption and
decryption for a transposition cipher.

EXAMPLE 6 Using the transposition cipher based on the permutation σ of the set {1, 2, 3, 4} with σ(1) = 3,
σ(2) = 1, σ(3) = 4, and σ(4) = 2,
(a) Encrypt the plaintext message PIRATE ATTACK.

(b) Decrypt the ciphertext message SWUE TRAE OEHS, which was encrypted using this cipher.

Solution: (a) We first split the letters of the plaintext into blocks of four letters. We obtain PIRA
TEAT TACK. To encrypt each block, we send the first letter to the third position, the second
letter to the first position, the third letter to the fourth position, and the fourth letter to the second
position. We obtain IAPR ETTA AKTC.
(b) We note that σ −1 , the inverse of σ, sends 1 to 2, sends 2 to 4, sends 3 to 1, and sends
4 to 3. Applying σ −1 (m) to each block gives us the plaintext: USEW ATER HOSE. (Grouping
together these letters to form common words, we surmise that the plaintext is USE WATER
HOSE.) ▲

CRYPTOSYSTEMS We have defined two families of ciphers: shift ciphers and affine ciphers.
We now introduce the notion of a cryptosystem, which provides a general structure for defining
new families of ciphers.

DEFINITION 1 A cryptosystem is a five-tuple (P, C, K, E, D), where P is the set of plaintext strings, C is
the set of ciphertext strings, K is the keyspace (the set of all possible keys), E is the set of
encryption functions, and D is the set of decryption functions.We denote by E k the encryption
function in E corresponding to the key k and D k the decryption function in D that decrypts
ciphertext that was encrypted using E k , that is D k (E k (p)) = p, for all plaintext strings p.