Page 325 - Discrete Mathematics and Its Applications

304 4 / Number Theory and Cryptography

Exercises

1. Encrypt the message DO NOT PASS GO by translating 10. Determine whether there is a key for which the encipher-
the letters into numbers, applying the given encryption ing function for the shift cipher is the same as the deci-
function, and then translating the numbers back into let- phering function.
ters.
11. What is the decryption function for an affine cipher if the
a) f(p) = (p + 3) mod 26 (the Caesar cipher) encryption function is c = (15p + 13) mod 26?
b) f(p) = (p + 13) mod 26
∗ 12. Find all pairs of integers keys (a, b) for affine ciphers for
c) f(p) = (3p + 7) mod 26
which the encryption function c = (ap + b) mod 26 is
2. Encrypt the message STOP POLLUTION by translating the same as the corresponding decryption function.
the letters into numbers, applying the given encryption
13. Suppose that the most common letter and the second
function, and then translating the numbers back into let-
most common letter in a long ciphertext produced by
ters.
encrypting a plaintext using an affine cipher f(p) =
a) f(p) = (p + 4) mod 26 (ap + b) mod 26 are Z and J, respectively. What are the
b) f(p) = (p + 21) mod 26 most likely values of a and b?
c) f(p) = (17p + 22) mod 26
14. Encrypt the message GRIZZLY BEARS using blocks
3. Encrypt the message WATCH YOUR STEP by translat- of five letters and the transposition cipher based on the
ing the letters into numbers, applying the given encryp- permutation of {1, 2, 3, 4, 5} with σ(1) = 3, σ(2) = 5,
tion function, and then translating the numbers back into σ(3) = 1, σ(4) = 2, and σ(5) = 4. For this exercise, use
letters. the letter X as many times as necessary to fill out the final
block of fewer then five letters.
a) f(p) = (p + 14) mod 26
b) f(p) = (14p + 21) mod 26 15. Decrypt the message EABW EFRO ATMR ASIN which
c) f(p) = (−7p + 1) mod 26 is the ciphertext produced by encrypting a plaintext mes-
sage using the transposition cipher with blocks of four
4. Decrypt these messages that were encrypted using the letters and the permutation σ of {1, 2, 3, 4} defined by
Caesar cipher. σ(1) = 3, σ(2) = 1, σ(3) = 4, and σ(4) = 2.
a) EOXH MHDQV ∗ 16. Suppose that you know that a ciphertext was produced
b) WHVW WRGDB by encrypting a plaintext message with a transposition
c) HDW GLP VXP cipher. How might you go about breaking it?
5. Decrypt these messages encrypted using the shift cipher 17. Suppose you have intercepted a ciphertext message and
f(p) = (p + 10) mod 26. when you determine the frequencies of letters in this mes-
a) CEBBOXNOB XYG sage, you find the frequencies are similar to the frequency
b) LO WI PBSOXN of letters in English text.Which type of cipher do you sus-
pect was used?
c) DSWO PYB PEX
The Vigenère cipher is a block cipher, with a key that is a
6. Suppose that when a long string of text is encrypted using string of letters with numerical equivalents k 1 k 2 ...k m , where
a shift cipher f(p) = (p + k) mod 26, the most common k i ∈ Z 26 for i = 1, 2,...,m. Suppose that the numerical
letter in the ciphertext is X. What is the most likely value equivalents of the letters of a plaintext block are p 1 p 2 ...p m .
for k assuming that the distribution of letters in the text
The corresponding numerical ciphertext block is (p 1 +
is typical of English text?
k 1 ) mod 26 (p 2 + k 2 ) mod 26 ...(p m + k m ) mod 26. Finally,
7. Suppose that when a string of English text is encrypted us- we translate back to letters. For example, suppose that the
ing a shift cipher f(p) = (p + k) mod 26, the resulting key string is RED, with numerical equivalents 17 4 3.
ciphertext is DY CVOOZ ZOBMRKXMO DY NBOKW. Then, the plaintext ORANGE, with numerical equivalents
What was the original plaintext string? 14 17 00 13 06 04, is encrypted by first splitting it into two
8. Suppose that the ciphertext DVE CFMV KF NFEUVI, blocks 14 17 00 and 13 06 04. Then, in each block we shift
REU KYRK ZJ KYV JVVU FW JTZVETV was pro- the first letter by 17, the second by 4, and the third by 3. We
duced by encrypting a plaintext message using a shift obtain 5 21 03 and 04 10 07. The cipherext is FVDEKH.
cipher. What is the original plaintext?
18. Use the Vigenère cipher with key BLUE to encrypt the
9. Suppose that the ciphertext ERC WYJJMGMIRXPC message SNOWFALL.
EHZERGIH XIGLRSPSKC MW MRHMWXM-
RKYMWLEFPI JVSQ QEKMG was produced by en- 19. The ciphertext OIKYWVHBX was produced by encrypt-
crypting a plaintext message using a shift cipher. What is ing a plaintext message using the Vigenère cipher with
the original plaintext? key HOT. What is the plaintext message?