10.6 Exercises – Introduction to Cryptography with Coding Theory, 3rd Edition

10.6 Exercises

    1. Let p=13. Compute L2(3).

    2. Show that L2(11)=7.

    1. Let p=17. Compute L3(2).

    2. Show that L3(15)=6.

    1. Compute 65 (mod 11).

    2. Let p=11. Then 2 is a primitive root. Suppose 2x6 (mod 11). Without finding the value of x, determine whether x is even or odd.

  1. Let p=19. Then 2 is a primitive root. Use the Pohlig-Hellman method to compute L2(14).

  2. It can be shown that 5 is a primitive root for the prime 1223. You want to solve the discrete logarithm problem 5x3 (mod 1223). Given that 36111 (mod 1223), determine whether x is even or odd.

    1. Let α be a primitive root mod p. Show that

      Lα(β1β2)Lα(β1)+Lα(β2)(mod p1).

      (Hint: You need the proposition in Section 3.7.)

    2. More generally, let α be arbitrary. Show that

      Lα(β1β2)Lα(β1)+Lα(β2)(mod ordp(α)), 

      where ordp(α) is defined in Exercise 53 in Chapter 3.

  3. Let p=101, so 2 is a primitive root. It can be shown that L2(3)=69 and L2(5)=24.

    1. Using the fact that 24=233, evaluate L2(24).

    2. Using the fact that 5324 (mod 101), evaluate L2(24).

  4. The number 12347 is prime. Suppose Eve discovers that 2100007925431 (mod 12347). Find an integer k with 0<k<12347 such that 2k79 (mod 12347).

  5. Suppose you know that

    3644(mod 137), 3102(mod 137).

    Find a value of x with 0x135 such that 3x11 (mod 137).

  6. Let p be a large prime and suppose α10181 (mod p). Suppose βαk (mod p) for some integer k.

    1. Explain why we may assume that 0k<1018.

    2. Describe a BabyStep, Giant Step method to find k. (Hint: One list can contain numbers of the form βα109j.)

    1. Suppose you have a random 500-digit prime p. Suppose some people want to store passwords, written as numbers. If x is the password, then the number 2x (mod p) is stored in a file. When y is given as a password, the number 2y (mod p) is compared with the entry for the user in the file. Suppose someone gains access to the file. Why is it hard to deduce the passwords?

    2. Suppose p is instead chosen to be a five-digit prime. Why would the system in part (a) not be secure?

  7. Let’s reconsider Exercise 55 in Chapter 3 from the point of view of the Pohlig-Hellman algorithm. The only prime q is 2. For k as in that exercise, write k=x0+2x1++215x15.

    1. Show that the Pohlig-Hellman algorithm yields

      x0=x1==x10=0

      and

      2=β=β1==β11.
    2. Use the Pohlig-Hellman algorithm to compute k.

  8. In the Diffie-Hellman Key Exchange protocol, suppose the prime is p=17 and the primitive root is α=3. Alice’s secret is a=3 and Bob’s secret is b=5. Describe what Alice and Bob send each other and determine the shared secret that they obtain.

  9. In the Diffie-Hellman Key Exchange protocol, Alice thinks she can trick Eve by choosing her secret to be a=0. How will Eve recognize that Alice made this choice?

  10. In the Diffie-Hellman key exchange protocol, Alice and Bob choose a primitive root α for a large prime p. Alice sends x1αa (mod p) to Bob, and Bob sends x2αb (mod p) to Alice. Suppose Eve bribes Bob to tell her the values of b and x2. However, he neglects to tell her the value of α. Suppose gcd(b, p1)=1. Show how Eve can determine α from the knowledge of p, x2, and b.

  11. In the ElGamal cryptosystem, Alice and Bob use p=17 and α=3. Bob chooses his secret to be a=6, so β=15. Alice sends the ciphertext (r, t)=(7, 6). Determine the plaintext m.

  12. Consider the following Baby Step, Giant Step attack on RSA, with public modulus n. Eve knows a plaintext m and a ciphertext c with gcd(c, n)=1. She chooses N2n and makes two lists: The first is cj (mod n) for 0j<N. The second is mcNk (mod n) for 0k<N.

    1. Why is there always a match between the two lists, and how does a match allow Eve to find the decryption exponent d?

    2. Your answer to (a) is probably partly false. What you have really found is an exponent d such that cdm (mod n). Give an example of a plaintext–ciphertext pair where the d you find is not the encryption exponent. (However, usually d is very close to being the correct decryption exponent.)

    3. Why is this not a useful attack on RSA? (Hint: How long are the lists compared to the time needed to factor n by trial division?)

  13. Alice and Bob are using the ElGamal public key cryptosystem, but have set it up so that only Alice, Bob, and a few close associates (not Eve) know Bob’s public key. Suppose Alice is sending the message dismiss Eve to Bob, but Eve intercepts the message and prevents Bob from receiving it. How can Eve change the message to promote Eve before sending it to Bob?