Appendix E Answers and Hints for Selected Odd-Numbered Exercises – Introduction to Cryptography with Coding Theory, 3rd Edition

Appendix E Answers and Hints for Selected Odd-Numbered Exercises

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 21x+9.

  4. 7. The encryption function is therefore 11x+14.

  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 x=1 and x=4 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: 1=(1)101+617.

    2. 6

  2. 3.

    1. d=13

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

  3. 5.

    1. x22 (mod 59), or x22, 81, 140, 199 (mod 236).

    2. No solutions.

  4. 7.

    1. If n=ab with 1<a, b<n, then either an of bn. Otherwise, ab>(n)(n)=n. If 1<a<n, let p be a prime factor of a.

    2. gcd(30030, 257)=1.

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

  5. 9.

    1. The gcd is 257.

    2. 4883=25719 and 4369=25717.

  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. x23 (mod 70).

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

  10. 21.

    1. x43, 56, 87, 100 (mod 143).

    2. x44, 99 (mod 143).

  11. 23. The remainder is 8.

  12. 25. The last two digits are 29.

  13. 27. Use Fermat’s theorem when a0(modp).

  14. 29.

    1. 773 (mod 4).

    2. The last digit is 3.

  15. 39.

    1. 521225.

    2. b0, 2, 4, 6, 8, 10, 12, 16, 18, 20, 22, 24 (mod 26).

  16. 41. 2 and 13

  17. 43.

    1. No solutions.

    2. There are solutions.

    3. No solutions.

Chapter 4

  1. 1.

    1. 0.

    2. P(M=cat|C=mxp)P(M=cat).

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

  3. 5.

    1. 1/2.

    2. m0=HI, m1=BE is a possibility.

  4. 11.

    1. Possible.

    2. Possible.

    3. Impossible.

  5. 13. X

Chapter 5

  1. 1. ] The next four terms of the sequence are 1, 0, 0, 1.

  2. 3. c0=1, c1=0, c2=0, c3=1.

  3. 5. c0=2 and c1=1.

  4. 7. kn+2kn.

  5. 9. c0=4 and c1=4.

Chapter 6

  1. 1. eureka.

  2. 3. 123112.

  3. 5. 72135.

  4. 7.

    1. 1091323.

    2. 10191319.

  5. 9. Use aabaab.

  6. 13.

    1. Alice’s method is more secure.

    2. Compatibility with single encryption.

  7. 19. The jth and the (j+1)st blocks.

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 M0 and therefore M1K, but not M1 or K individually. If you also know the plaintext, you know M1 are therefore can deduce K.

    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 P and K are used, the input to the S-boxes is the same as when P and K are used.

Chapter 8

  1. 1.

    1. We have W(4)=W(0)T(W(0))=T(W(0)). In the notation in Subsection 8.2.5, a=b=c=d=0. The S-box yields e=f=g=h=99(base 10)=01100011(binary). The round constant is r(4)=000000100=00000001. We have er(4)=01100100. Therefore,

      W(4)=T(W(0))=01100100011000110110001101100011.
  2. 3.

    1. Since addition in GF(28) is the same as , we have f(x1)f(x2)=α(x1+x2)=α(x3+x4)=f(x3)f(x4).

Chapter 9

  1. 1. The plaintext is 1415=no.

  2. 3.

    1. d=27.

    2. Imitate the proof that RSA decryption works.

  3. 5. The correct plaintext is 9.

  4. 7. Use d=67.

  5. 9. Solve de1 (mod p1).

  6. 11. Bob computes b1 with bb11 (mod ϕ(n)) and raises e to the power b1.

  7. 13. Divide the decryption by 2.

  8. 15. It does not increase security.

  9. 17. e=1 sends plaintext, and e=2 doesn’t satisfy gcd(e, (p1)(q1))=1.

  10. 21. Compute a gcd.

  11. 23. We have (516107187722)2(27)2 (mod n).

  12. 25. Combine the first three congruences. Ignore the fourth congruence.

  13. 27. Use the Chinese Remainder Theorem to find x with x7 (mod p) and x7 (mod q).

  14. 31. There are integers x and y such that xeA+yeB=1.

  15. 33. HELLO

  16. 41. 12345.

  17. 45. Find d with de1 (mod 12345).

  18. 47.

    1. 1000000 messages.

Chapter 10

  1. 1.

    1. L2(3)=4.

    2. 2711 (mod 13).

  2. 3.

    1. 6510.

    2. x is odd.

  3. 5. x is even.

  4. 7. (a), (b) L2(24)=72.

  5. 9. x=122.

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

  7. 15. Eve computes b1 with bb11 (mod p1).

Chapter 11

  1. 1. It is easy to construct collisions: h(x)=h(x+p1), 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 mod pq is computationally equivalent to factoring.

    2. h(x)h(nx) for all x

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

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

  5. 11. Collision resistance.

Chapter 12

  1. 1. 165288.573

  2. 5. 1e7.3×10470.

  3. 7. It is very likely that two choose the same prime.

  4. 9. The probability is approximately 1e5000 (or 1e4500 if you take numbers of exactly 15 digits).

Chapter 13

  1. 1. Use the congruence defining s to solve for a.

  2. 3. See Section 13.4.

  3. 7.

    1. Let m1mr1r1 (mod p1).

  4. 9. Imitate the proof for the usual ElGamal signatures.

  5. 13. Eve notices that β=r.

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 1(25/26)900.97 that there is a match between the second plaintext and the ciphertext. Therefore, Enigma does not have ciphertext indistinguishability.

Chapter 15

  1. 1. KAB=gA(rB)=21, KAC=gA(rC)=7 and KBC=gB(rC)=29.

  2. 3. a=8, b=8, c=23.

Chapter 16

  1. 1.

    1. We have rα1(cx+w)+α2Hx+α1w+α2 (mod q). Therefore

      grgwα1gα2gxHgwα1gα2gxHahH(mod p).
    2. Since c1w+xc (mod q), we have α1c1wα1+xH (mod q). Therefore,

      rα1c1+α2xH+wα1+α2(mod q).

      Multiply by s and raise Ig2 to these exponents to obtain

      (Ig2)rs(Ig2)xsH(Ig2)wsα1(Ig2)sα2(mod p).

      This may be rewritten as

      ArzHb(mod p).
    3. Since r1usd+x1 and r2sd+x2 (mod q), we have

      g1r1g2r2(g1ug2)sdg1x1g2x2(Ig2sdg1x1g2x2≡≡AdB(mod p).
  2. 3.

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

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

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

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

Chapter 17

  1. 1. One possibility is to take p=7 and choose the polynomial s(x)=5+x (mod 7) (where 5 is chosen randomly). Then the secret value is s(0)=5, and we may choose the shares (1,6), (2,0), (3,1), and (4,2).

  2. 3. *=63

  3. 5. The polynomial is

    8(x3)(x5)(13)(15)+10(x1)(x5)(31)(35)+11(x1)(x3)(51)(53).

    The secret is 13 (mod 17).

  4. 7. M=77, 57, 37, 17.

  5. 9. Take a (10, 30) scheme and give the general 10 shares, the colonels five shares each, and the clerks two each.

  6. 11. Start by splitting the launch code into three equal components using a three-party secret splitting scheme.

Chapter 19

  1. 3.

    1. Nelson computes a square root of y mod p and mod q, then combines them to obtain a square root of y mod n.

    2. Use the x2y2 factorization method.

    3. No.

  2. 5.

    Step 4: Victor randomly chooses i=1 or 2 and asks Peggy for ri.

    Step 5: Victor checks that xirie (mod n).

    They repeat steps 1 through 5 at least 7 times (since (1/2)7<.01).

  3. 7.

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

    2. Choose r1, r2. Then solve for r3.

Chapter 20

  1. 1. H(X1)=H(X2)=1, and H(X1, X2)=2.

  2. 3. H(X)=2.

  3. 5. H(Y)H(X).

  4. 7.

    1. 2.9710

    2. 2.9517

  5. 9.

    1. H(P)=13log213+23log223.

    2. This system matches up with the one-time pad, and hence H(P|C)=H(P).

  6. 13.

    1. H(X)=log236.

    2. Use Fermat’s Theorem to obtain H(Y)=0.

Chapter 21

  1. 3.

    1. (3, 2), (3, 5), (5, 2), (5, 5), (6, 2), (6, 5), .

    2. (3, 5).

    3. (5, 2).

  2. 5.

    1. (2, 2).

    2. She factors 35.

  3. 7. One example: y2x3+17.

  4. 9.

    1. 3Q=(1, 0).

  5. 15. y±4, ±11 (mod 35)

Chapter 22

  1. 3. Compute e˜(aA, B) and e˜(A, bB).

  2. 7.

    1. Eve knows rP0, P1, k. She computes

      e˜(rP0, P1)k=(˜kP0, P1)r=e˜(H1(bob@computer.com), P1)r=gr.

      Eve now computes H2(gr) and XORs it with t to get m.

  3. 9. See Claim 2 in Section 9.1.

Chapter 23

  1. 1. The basis (0, 1), (2, 0) is reduced. The vector (0, 1) is a shortest vector.

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. n=5 and k=2.

    2. G=1101010101.
    3. (0, 0, 0, 0, 0), (1, 1, 0, 1, 0), (1, 0, 1, 0, 1), (0, 1, 1, 1, 1).

    4. R=log2(4)5=0.4.

  3. 5.

    1. d(C)=2.

  4. 13. 1+X+X2+X3 is in C and the other two polynomials are not in C.

  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. m=8.

    3. r=4.