Page 317 - Discrete Mathematics and Its Applications

296 4 / Number Theory and Cryptography

Next, we shift each of these numbers by −k =−7 modulo 26 to obtain

423154178413 24 818 0 61740 19 1940 2 7417.

Finally, we translate these numbers back to letters to obtain the plaintext. We obtain
“EXPERIENCE IS A GREAT TEACHER.” ▲

We can generalize shift ciphers further to slightly enhance security by using a function of
the form

f(p) = (ap + b) mod 26,

where a and b are integers, chosen so that f is a bijection. (The function f(p) = (ap +
b) mod 26 is a bijection if and only if gcd(a, 26) = 1.) Such a mapping is called an affine
transformation, and the resulting cipher is called an affine cipher.
EXAMPLE 4 What letter replaces the letter K when the function f(p) = (7p + 3) mod 26 is used for en-
cryption?

Solution: First, note that 10 represents K. Then, using the encryption function specified, it
follows that f(10) = (7 · 10 + 3) mod 26 = 21. Because 21 represents V, K is replaced by V
in the encrypted message. ▲

We will now show how to decrypt messages encrypted using an affine cipher. Suppose that
c = (ap + b) mod 26 with gcd(a, 26) = 1. To decrypt we need to show how to express p in
terms of c. To do this, we apply the encrypting congruence c ≡ ap + b (mod 26), and solve it
for p. To do this, we first subtract b from both sides, to obtain c − b ≡ ap (mod 26). Because
gcd(a, 26) = 1, we know that there is an inverse a of a modulo 26. Multiplying both sides of
the last equation by a gives us a(c − b) ≡ aap (mod 26). Because aa ≡ 1 (mod 26), this tells
us that p ≡ a(c − b) (mod 26). This determines p because p belongs to Z 26 .

CRYPTANALYSIS The process of recovering plaintext from ciphertext without knowledge
of both the encryption method and the key is known as crytanalysis or breaking codes.In
general, cryptanalysis is a difficult process, especially when the encryption method is unknown.
We will not discuss cryptanalysis in general, but we will explain how to break messages that
were encrypted using a shift cipher.
If we know that a ciphertext message was produced by enciphering a message using a shift
cipher, we can try to recover the message by shifting all characters of the ciphertext by each
of the 26 possible shifts (including a shift of zero characters). One of these is guaranteed to be
the plaintext. However, we can use a more intelligent approach, which we can build upon to
cryptanalyze ciphertext resulting from other ciphers.The main tool for cryptanalyzing ciphertext
Mathematicians make the
best code breakers. Their encrypted using a shift cipher is the count of the frequency of letters in the ciphertext. The nine
work in World War II most common letters in English text and their approximate relative frequencies are E 13%, T 9%,
changed the course of the A 8%, O 8%, I 7%, N 7%, S 7%, H 6%, and R 6%. To cryptanalyze ciphertext that we know was
war. produced using a shift cipher, we first find the relative frequencies of letters in the ciphertext.
We list the most common letters in the ciphertext in frequency order; we hypothesize that the
most common letter in the ciphertext is produced by encrypting E. Then, we determine the
value of the shift under this hypothesis, say k. If the message produced by shifting the ciphertext
by −k makes sense, we presume that our hypothesis is correct and that we have the correct
value of k. If it does not make sense, we next consider the hypothesis that the most common
letter in the ciphertext is produced by encrypting T, the second most common letter in English;
we find k under this hypothesis, shift the letters of the message by −k, and see whether the
resulting message makes sense. If it does not, we continue the process working our way through
the letters from most common to least common.