TEST BANK FOR Introduction to cryptography with coding theory 2nd Ed By Wade Trappe, Lawrence C.

Contents
Exercises
Chapter 2 - Exercises 1
Chapter 3 - Exercises 6
Chapter 4 - Exercises 14
Chapter 5 - Exercises 17
Chapter 6 - Exercises 19
Chapter 7 - Exercises 23
Chapter 8 - Exercises 25
Chapter 9 - Exercises 27
Chapter 10 - Exercises 28
Chapter 11 - Exercises 29
Chapter 12 - Exercises 31
Chapter 13 - Exercises 33
Chapter 14 - Exercises 34
Chapter 15 - Exercises 36
Chapter 16 - Exercises 40
Chapter 17 - Exercises 44
Chapter 18 - Exercises 46
-2
-1
Chapter 19 - Exercises 51
Mathematica problems
Chapter 2 52
Chapter 3 63
Chapter 6 66
Chapter 7 72
Chapter 8 74
Chapter 9 75
Chapter 12 78
Chapter 16 79
Chapter 18 81
Maple problems
Chapter 2 84
Chapter 3 98
Chapter 6 102
Chapter 7 109
Chapter 8 112
Chapter 9 113
Chapter 12 116
Chapter 16 118
Chapter 18 121
0
MATLAB problems
Chapter 2 124
Chapter 3 147
Chapter 6 151
Chapter 7 161
Chapter 8 164
Chapter 9 165
Chapter 12 167
Chapter 16 169
Chapter 18 174
Chapter 2 - Exercises
1. Among the shifts of EVIRE, there are two words: arena and river. Therefore,
Anthony cannot determine where to meet Caesar.
2. The inverse of 9 mod 26 is 3. Therefore, the decryption function is
x = 3(y−2) = 3y−2 (mod 26). Now simply decrypt letter by letter as follows.
U = 20 so decrypt U by calculating 3 ∗ 20 − 6 (mod 26) = 2, and so on. The
decrypted message is ’cat’.
3. Changing the plaintext to numbers yields 7, 14, 22, 0, 17, 4, 24, 14, 20.
Applying 5x+7 to each yields 5·7+7 = 42 ≡ 16 (mod 26), 5·14+7 = 77 ≡ 25,
etc. Changing back to letters yields QZNHOBXZD as the ciphertext.
4. Let mx + n be the encryption function. Since h = 7 and N = 13, we
have m · 7 + n ≡ 13 (mod 26). Using the second letters yields m · 0 + n ≡ 14.
Therefore n = 14. The first congruence now yields 7m ≡ −1 (mod 26). This
yields m = 11. The encryption function is therefore 11x + 14.
5. Let the decryption function be x = ay + b. The first letters tell us that
7 ≡ a · 2+b (mod 26). The second letters tell us that 0 ≡ a · 17+b.Subtracting
yields 7 ≡ a · (−15) ≡ 11a. Since 11−1 ≡ 19 (mod 26), we have a ≡ 19 · 7 ≡ 3
(mod 26). The first congruence now tells us that 7 ≡ 3 · 2 + b, so b = 1. The
decryption function is therefore x ≡ 3y + 1. Applying this to CRWWZ yields
happy for the plaintext.
6. Let mx+n be one affine function and ax+b be another. Applying the first
then the second yields the function a(mx+n)+b = (am)x+(an+b), which is
an affine function. Therefore, successively encrypting with two affine functions
is the same as encrypting with a single affine function. There is therefore no
advantage of doing double encryption in this case. (Technical point: Since
gcd(a, 26) = 1 and gcd(m, 26) = 1, it follows that gcd(am, 26) = 1, so the affine
function we obtained is still of the required form.)
7. For an affine cipher mx + n (mod 27), we must have gcd(27,m) = 1,
and we can always take 1 ≤ m ≤ 27. So we must exclude all multiples of 3,
which leaves 18 possibilities for m. All 27 values of n are possible, so we have
18 · 27 = 486 keys. When we work mod 29, all values 1 ≤ m ≤ 28 are allowed,
so we have 28 · 29 = 812 keys.
8. (a) In order for α to be valid and lead to a decryption algorithm, we need
gcd(α, 30) = 1. The possible values for α are 1, 7, 11, 13, 17, 19, 23, 29.
(b) We need to find two x such that 10x (mod 30) gives the same value.
There are many such possible answers, for example x = 1 and x = 4 will work.
1
2
This corresponds to the letters ’b’ and ’e’.
9. If x1 = x2+(26/d), then αx1+β = αx2+β+(α/d)26. Since d = gcd(α, 26)
divides α, the number α/26 is an integer. Therefore (α/d)26 is a multiple of 26,
which means that αx1 + β ≡ αx2 + β (mod 26). Therefore x1 and x2 encrypt
to the same ciphertext, so unique decryption is impossible.
10. (a) In order to find the most probable key length, we write the ciphertext
down on two strips and shift the second strip by varying amounts. The shift
with the most matches is the most likely key length. As an example, look at
the shift by 1:
B A B A B A A A B A
B A B A B A A A B A
* *
This has a total of 2 matches. A shift by 2 has 6 matches, while a shift by
3 has 2 matches. Thus, the most likely key length is 2.
(b) To decrypt, we use the fact that the key length is 2 and extract off every
odd letter to get BBBAB, and then every even letter to get AAAAA. Using a
frequency count on each of these yields that a shift of 0 is the most likely scenario
for the first character of the Vigenere key, while a shift of 1 is the most likely
case for the second character of the key. Thus, the key is AB. Decrypting each
subsequence yields BBBAB and BBBBB. Combining them gives the original
plaintext BBBBBBABBB.
11. If we look at shifts of 1, 2, and 3 we have 2, 3, and 1 matches. This
certainly rules out 3 as the key length, but the key length may be 1 or 2.
In the ciphertext, there are 3 A’s, 5 B’s, and 2 C’s. If the key length were 1,
this should approximate the frequencies .7, .2, .1 of the plaintext in some order,
which is not the case. So we rule out 1 as the key length.
Let’s consider a key length of 2. The first, third, fifth, ... letters are ACABA.
There are 3 A’s, 1 B, and 1C. These frequencies of .6, .2, .2 is a close match
to .7, .2, .1 shifted by 0 positions. The first element of the key is probably A.
The second, fourth, ... letters of the ciphertext are BBBBC. There are 0 A’s, 4
B’s, and 1 C. These frequencies .0, .8, .2 and match .7, .2, .1 with a shift by 1.
Therefore the second key element is probably B.
Since the results for length 2 match the frequencies most closely, we conclude
that the key is probably AB.
12. Since the entries of Ai are the same as those in A0 ( shifted a few places)
the two vectors have the same length. Therefore
A0 · Ai = |A0||Ai| cos θ = |A0|2 cos θ.
Note that cos θ ≤ 1, and equals 1 exactly when θ = 0. But θ = 0 exactly when
the two vectors are equal. So we see that the largest value of the cosine is when
A0 = Ai. Therefore the largest value of the dot product is when i = 0.
13. Change YIFZMA to pairs of numbers: (24, 8), (5, 25), (12, 0). Invert
the matrix to get N = 3 −13
−2 9 ≡ 3 13
24 9 (mod 26). Calculate
(24, 8)N = (4, 20), (5, 25)N = (17, 4), (12, 0)N = (10, 0). Change back to
letters: eureka.
3
14. Suppose the encryption matrix M is a b
c d . Change the ciphertext
to numbers: (6, 4), (25, 23), (3, 18). Change the plaintext to numbers: (18,
14), (11, 21), (4,3). We know (18, 14)M ≡ (6, 4), etc. We’ll use (11, 21)M ≡ (25, 23) and (4, 3)M ≡ (3, 18) to get equations for a, b, c, d, which are most
easily put in matrix form: 11 21
4 3 a b
c d ≡ 25 23
3 18 . The inverse
of 11 21
4 3 mod 26 is 3 5
22 11 . Multiply by this matrix to obtain
M = a b
c d ≡ 12 3
11 2 .
15. Suppose the matrix has the form
M = α β
γ δ
Then the encryption of a plaintext x = (b, a) = (1, 0) yields (α, β). We know
this corresponds to HC, and hence α = 7 and β = 2. The second piece of
information is that zz encrypts to GT. This corresponds to a plaintext of (25, 25)
or equivalently (−1,−1). Using this yields −α−γ = 6 and −β −δ = 19. Thus,
γ = 13 and δ = 5.
16. (a) The plaintext is (3,14), (13, 19). The ciphertext is (4,11), (13, 8).
We have 3 14
13 19 M ≡ 4 11
13 8 . The inverse of 3 14
13 19 mod 26
is 19 12
13 3 . Multiplying by this inverse yields M ≡ 10 9
13 23 .
(b) We have 3 14
13 19 M ≡ 4 11
13 10 . Proceeding as in part (a), we
find M ≡ 10 19
13 19 .
17. Suppose the plaintext is of the form (x, y), then the ciphertext is of
the form (x + 3y, 2x + 4y) (mod 26). There will be many possible plaintexts
that will map to the same ciphertext. We will try to make plaintexts that
yield a ciphertext of the form (0, ∗). To do so, we will have the relationship
x = −3y (mod 26). Now we need to find two y values that produce the same
2(−3y) + 4y = −2y (mod 26). If we take y = 4 and y = 17 then we get the
same value for −2y (mod 26). Thus, (14, 4) and (1, 17) are two plaintexts that
map to (0, 18).
18. We will need to use three different plaintexts. First, choose (x, y) =
(0, 0). This will produce a ciphertext that is precisely (e, f). Next, try (x, y) =
(1, 0). This will produce a ciphertext that is (a, b) + (e, f). We may subtract
off (e, f) to find (a, b). Finally, use (x, y) = (0, 1) to get (c, d) + (e, f) as the
ciphertext. We may subtract off (e, f) to get (c, d).
4
19. As is Section 2.11, set up the matrix equation

0 0 1
0 1 1
1 1 1


c0
c1
c2

≡

1
1
0

.
This yields c0 = 1, c1 = 0, c2 = 1, so the recurrence is kn+3 ≡ kn + kn+2. The
next four terms of the sequence are 1, 0, 0, 1.
20. The sequence is 1,0,1,0,1,0,1,... . The matrix equation is 1 0
0 1 c0
c1 ≡
1
0 . This yields c0 = 1, c1 = 0, so kn+2 ≡ kn.
21. Set up the matrix equation
xn xn+1
xn+1 xn+2 c0
c1 = xn+2
xn+3 .
Using the values provided, we obtain
1 1
1 0 c0
c1 = 0
2 .
The inverse of the matrix can be found to be
− 0 −1
−1 1 = 0 1
1 2 (mod 3)
Multiplying both sides of by the inverse matrix, yields c0 = 2 and c1 = 1.
22.Use x1, x2 and x3 to solve for c1 by obtaining c1 +2 ≡ 1 (mod 5). Thus,
c1 = 4. Next, use x2, x3 and x4 to solve for c0. We get c0 +c1 +2 (mod 5) ≡ 0,
and hence c0 = 4.
23. The number of seconds in 120 years is
60 × 60 × 24 × 365 × 120 ≈ 3.8 × 109.
Therefore you need to count 10100/(3.8×109) ≈ 2.6×1090 numbers per second!
24. (a) The ciphertext will consist of one letter repeated. However, there is
no way of deducing what the key is.
(b) The ciphertext will consist of one letter repeated. However, there is no
way of deducing what the key is.
(c) The ciphertext will consist of a continuous stream of the letter A. This
is easy to detect. However, there will be no way to tell what the key is.
25. (a) The ciphertext will correspond to a shifted version of the key word
that is repeated many times. The periodic nature of the resulting ciphertext
will cause Eve to suspect the plaintext is a single letter, while the period of the
repeating ciphertext will correspond to the key length.
(b) Using the fact that no English word of length six is the shift of another
English word, simply treat the Vigenere key as if it were the plaintext and the
5
single character plaintext as if it were the shift in a shift cipher. Decrypting can
be done by trying all possible shifts of the first six characters of the ciphertext.
One of these shifts will be a word that corresponds to the Vigenere key.
(c) If we use the method of displacement, then shifting by six will have the
highest number of matches. In fact, every place will match up. This will be
easy to detect. However, shifting the ciphertext by one place will just yield the
amount of matches that occur when the repeated key is shifted by one place.
In particular, the key word will most likely not have that many matches with
itself when shifted over one place. Similarly for shifts of two, three, four, and
five. As a result, other shifts will have a much smaller amount of matches.
Chapter 3 - Exercises
1. (a) Apply the Euclidean algorithm to 17 and 101:
101 = 5 · 17 + 16
17 = 1 · 16 + 1.
Working back yields 1 = 17 − 16 = 17 − (101 − 5 · 17) = (−1) · 101 + 6 · 17.
(b) Since −101+6·17 = 1, we have 6·17 ≡ 1 (mod 101). Therefore 17−1 ≡ 6
(mod 101).
2. (a) Apply the Euclidean algorithm to 7 and 30:
30 = 4 · 7 + 2
7 = 3 · 2 + 1.
Working backwards yields 1 = 7 − 3 · 2 = 7 − 3 · (30 − 4 · 7) = 13 · 7 + (−3) · 30.
Therefore 13 · 7 ≡ 1 (mod 30), so d = 13.
(b) Let c ≡ m7 (mod 31) be the ciphertext. Claim: c13 ≡ m (mod 31).
Proof: c13 ≡ (m7)13 ≡ m91 ≡ (m30)3m. If m 6≡ 0 (mod 31) then m30 ≡ 1
(mod 31) by Fermat. Then c13 ≡ 13m ≡ m. If m ≡ 0 (mod 31), then c ≡ m7 ≡ 0, so c13 ≡ 013 ≡ 0 ≡ m. Therefore c13 ≡ m for all m. Therefore decryption is
performed by raising the ciphertext to the 13th power mod 31.
3. 3. (a) gcd(12, 236) = 4, so divide both sides by 4 to obtain 3x ≡ 7
(mod 59). The inverse of 3 mod 59 is 20, so multiply both sides by 20 to obtain
x ≡ 140 ≡ 22 (mod 59). This yields x ≡ 22, 81, 140, 199 (mod 236).
(b) 30 is not divisible by 4 = gcd(12, 236), so there are no solutions.
4. (a)
30030 = 116 · 257 + 218
257 = 1 · 218 + 39
218 = 5 · 39 + 23
39 = 1 · 23 + 16
23 = 1 · 16 + 7
16 = 2 · 7 + 2
7 = 3 · 2 + 1
2 = 2 · 1 + 0.
6
7
Therefore, gcd(30030, 257) = 1.
(b) If 257 is composite, it is divisible by a prime p ≤ √257 = 16.03 . . . . The
primes satisfying this are exactly the prime factors of 30030. Since the gcd is 1,
none of them divide 257, so 257 is prime.
5. (a)
4883 = 1 · 4369 + 514
4369 = 8˙514 + 257
514 = 2 · 257 + 0.
Therefore, the gcd is 257.
(b) We know that both numbers have 257 as a factor. This yields 4883 = 257·19
and 4369 = 257 · 17.
6. (a) The first two steps of the Euclidean algorithm are
Fn = 1 · Fn−1 + Fn−2
Fn−1 = 1 · Fn−2 + Fn−3.
It continues in this way until
2 = 2 · 1 + 1
1 = 1 · 1 + 0.
Therefore, the gcd is 1.
(b)
11111111 = 1000 · 11111 + 111
11111 = 100 · 111 + 11
111 = 10 · 11 + 1
11 = 11 · 1 + 0.
Therefore, the gcd is 1.
(c) The first step of the Euclidean algorithm is
a = 10Fn−2 · b + c,
where c consists of Fn−2 repeated 1’s. Continuing in this way, in each step we
divide Fj−1 repeated 1’s into Fj repeated 1’s and get a remainder consisting of
Fj−2 repeated 1’s. Eventually, we get down to the computations of part (b),
and then obtain that the gcd is 1.
7. (a) If ab ≡ 0 (mod p), then p|ab. By the Corollary on page 64, since p is
prime, either p|a or p|b. Therefore, either a ≡ 0 (mod p) or b ≡ 0 (mod p).
(b) We follow the proof of the Corollary on page 64. Since gcd(a, n) = 1,
there are integers x, y such that ax+ny = 1. Multiply by b to obtain abx+bny =
b. Since n|ab, both terms on the left are multiples of n. Therefore n|b.
8. (x+1)(x−1) ≡ 0 (mod p) implies, by 3(a), that either x+1 ≡ 0 (mod p)
or x − 1 ≡ 0 (mod p). Therefore x ≡ ±1 (mod p).
8
9. One solution is to look at the numbers congruent to 3 (mod 10) until
we find one that is 2 (mod 7): 3, 13 ≡ 6, 23 ≡ 2 (mod 7). Therefore x ≡ 23
(mod 70).
10. Suppose there are x people. Then x ≡ 1 (mod 3