Exam (elaborations) TEST BANK FOR Introduction to cryptography with coding theory 2nd Edition By Wade Trappe, Lawrence C. Washington(Solution Manual)-Converted

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