Chapter 2

1. 1. Among the shifts of EVIRE, there are two words: arena and river. Therefore, Anthony cannot determine where to meet Caesar.

2. 3. The decrypted message is ’cat’.

3. 5. The ciphertext is QZNHOBXZD. The decryption function is .

4. 7. The encryption function is therefore .

5. 9. The plaintext is happy.

6. 11. 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.

7. 13. Mod 27, there are 486 keys. Mod 29, there are 812 keys.

8. 15.

1. The possible values for  are 1,7,11,13,17,19,23,29.

2. There are many such possible answers, for example  and  will work. These correspond to the letters ’b’ and ’e’.

9. 19.

1. The key is AB. The original plaintext is BBBBBBABBB.

10. 21. The key is probably AB.

11. 27. EK IO IR NO AN HF YG BZ YB LF GM ZN AG ND OD VC MK

12. 29. AAXFFGDGAFAX

Chapter 3

1. 1.

1. One possibility: .

2. 

2. 3.

1. 

2. Decryption is performed by raising the ciphertext to the 13th power mod 31.

3. 5.

1. , or .

2. No solutions.

4. 7.

1. If  with , then either  of . Otherwise, . If , let  be a prime factor of .

2. .

3. No prime less than or equal to  divides 257 because of the gcd calculation.

5. 9.

1. The gcd is 257.

2.  and .

6. 11.

1. The gcd is 1.

2. The gcd is 1.

3. The gcd is 1.

7. 13.

1. Use the Corollary in Section 3.2.

2. Imitate the proof of the Corollary in Section 3.2.

8. 17. .

9. 19. The smallest number is 58 and the next smallest number is 118.

10. 21.

1. .

2. .

11. 23. The remainder is 8.

12. 25. The last two digits are 29.

13. 27. Use Fermat’s theorem when .

14. 29.

1. .

2. The last digit is 3.

15. 39.

1. .

2. .

16. 41. 2 and 13

17. 43.

1. No solutions.

2. There are solutions.

3. No solutions.

Chapter 4

1. 1.

1. 0.

2. .

2. 3. The conditional probability is 0. Affine ciphers do not have perfect secrecy.

3. 5.

1. 1/2.

2.  is a possibility.

4. 11.

1. Possible.

2. Possible.

3. Impossible.

5. 13. 

Chapter 6

1. 1. eureka.

2. 3. .

3. 5. .

4. 7.

1. .

2. .

5. 9. Use aabaab.

6. 13.

1. Alice’s method is more secure.

2. Compatibility with single encryption.

7. 19. The th and the .

Chapter 7

1. 1.

1. Switch left and right halves and use the same procedure as encryption. Then switch the left and right of the final output.

2. After two rounds, the ciphertext alone lets you determine  and therefore , but not  or  individually. If you also know the plaintext, you know  are therefore can deduce .

3. Three rounds is very insecure.

2. 3. The ciphertext from the second message can be decrypted to yield the password.

3. 5.

1. The keys for each round are all 1s, so using them in reverse order doesn’t change anything.

2. All 0s.

4. 7. Show that when  and  are used, the input to the S-boxes is the same as when  and  are used.

Chapter 8

1. 1.

1. We have . In the notation in Subsection 8.2.5, . The  yields . The round constant is . We have . Therefore,


2. 3.

1. Since addition in  is the same as , we have .

Chapter 10

1. 1.

1. .

2. .

2. 3.

1. .

2.  is odd.

3. 5.  is even.

4. 7. (a), (b) .

5. 9. .

6. 13. Alice sends  to Bob and Bob sends  to Alice. Their shared secret is 6.

7. 15. Eve computes  with .

Chapter 11

1. 1. It is easy to construct collisions: , for example. (However, it is fairly quickly computed (though not fast enough for real use), and it is preimage resistant.)

2. 3.

1. Finding square roots  is computationally equivalent to factoring.

2.  for all 

3. 5. It satisfies (1), but not (2) and (3).

4. 9. (a) and (b) Let  be either of the hash functions. Given  of length , we have .

5. 11. Collision resistance.

Chapter 14

1. 1. Use the Birthday attack. Eve will probably factor some moduli.

2. 3.

1. `0101` and `0110`.

3. 5.

1. Enigma does not encrypt a letter to itself, so `DOG` is impossible.

2. If the first of two long plaintexts is encrypted with Enigma, it is very likely that at least one letter of the second plaintext will match a letter of the ciphertext. More precisely, each individual letter of the second plaintext that doesn’t match the first plaintext has probability around 1/26 of matching, so the probability is  that there is a match between the second plaintext and the ciphertext. Therefore, Enigma does not have ciphertext indistinguishability.

Chapter 16

1. 1.

1. We have . Therefore


2. Since , we have . Therefore,



Multiply by  and raise  to these exponents to obtain



This may be rewritten as


3. Since  and , we have


2. 3.

1. The only place  and  are used in the verification procedure is in checking that .

2. The Spender spends the coin correctly once, using . The Spender then chooses any two random numbers  with  and uses the coin with the Vendor, with  in place of . All the verification equations work.

3. 5.  and  are essentially random numbers (depending on hash values involving the clock), the probability is around  that . Since  is large,  is small.

4. 7. Fred only needs to keep the hash of the file on his own computer.

Chapter 19

1. 3.

1. Nelson computes a square root of  and , then combines them to obtain a square root of .

2. Use the  factorization method.

3. No.

2. 5.

Step 4: Victor randomly chooses  or 2 and asks Peggy for .

Step 5: Victor checks that .

They repeat steps 1 through 5 at least 7 times (since ).

3. 7.

1. One way: Step 4: Victor chooses  at random and asks for  and . Then five repetitions are enough. Another way: Victor asks for only one of the . Then twelve repetitions suffice.

2. Choose . Then solve for .

Chapter 20

1. 1. , and .

2. 3. .

3. 5. .

4. 7.

1. 2.9710

2. 

5. 9.

1. .

2. This system matches up with the one-time pad, and hence .

6. 13.

1. .

2. Use Fermat’s Theorem to obtain .

Chapter 21

1. 3.

1. .

2. .

3. .

2. 5.

1. .

2. She factors 35.

3. 7. One example: .

4. 9.

1. .

5. 15. 

Chapter 22

1. 3. Compute  and .

2. 7.

1. Eve knows . She computes



Eve now computes  and XORs it with  to get .

3. 9. See Claim 2 in Section 9.1.

Chapter 24

1. 1.

1. The original message is 0,1,0,0.

2. The original message is 0,1,0,1.

2. 3.

1.  and .

2. 
3. .

4. .

3. 5.

1. .

4. 13.  is in  and the other two polynomials are not in .

5. 19. The error is in the 3rd position. The corrected vector is (1,0,0,1,0,1,1).

Chapter 25

1. 1.

1. The period is 4.

2. .

3. .