Advanced Math - Numbers 4, 5 and 7

Problem Set 5

Due: April 29

1. Stinson, problem 6.9, p.277. Only decrypt the first three ciphertext elements, namely (3781, 14409), (31552, 3930), and (27214, 15442).

2. Find all generators of Z∗11.

3. Let g be a generator of Z∗m. Prove that if g x ≡ gy (mod m), then x ≡ y

(mod ϕ(m)).

4. Let p and q be primes such that p = 2q + 1. Let α be a random element of Z∗p . Prove that if neither α

2 mod p nor αq mod p is equal to 1, then α is a generator of Z∗p .

[Hint: Use without proof the following fact, which is stated in the notes but which I only mentioned in passing in class: the order of any element of Z∗p divides ϕ(p).

Note: Another fact stated in the notes is that the number of generators of Z∗p is ϕ(p− 1). In this case, we have ϕ(p− 1) = ϕ(2q) = ϕ(2)ϕ(q) = q− 1. Therefore, the probability that a randomly selected element of Z∗p is a generator is about .50. So the fact I’m asking you to prove in this problem provides an efficient method for finding a generator of Z∗p , as long as we can find a p and q of the required form. It turns out that there are reasonably efficient techniques for finding pairs of primes of this form. ]

5.

i. Suppose that Alice uses the ElGamal signature scheme to sign two dif- ferent messages, m1 and m2. Her private key is a. As usual, the pub- lic parameters are (p, α, β), where α is a generator for Z∗p , and β ≡ αa (mod p). Suppose further that Alice carelessly (or lazily) uses the same ephemeral key (same value of k) for both signatures. Thus she constructs the signatures (r, s1) and (r, s2) for the two messages. Finally, assume that gcd(s1 − s2, p − 1) = 1. Show how Earl can discover the value of k efficiently in this case, given that he knows both m1 and m2.

ii. Suppose p = 31847, α = 5, β = 25703, and that you intercept

a. The messagem1 = 8990 and coresponding ElGamal signature (23972,31396)

b. The messagem2 = 31415 and coresponding ElGamal signature (23972,20481)

Assume no hash function has been used, so that, for a message x, s = k−1(x− ar) mod (p− 1) . Find the ephemeral key k.

6. Stinson, problem 4.9(a), p.157.

[Hint: Show that we can always find a collision for h1, given a collision for h2. Note that we know collisions exist; what we need to show here is that it’s easy to find a collision]

7. Let H be a Merkle-Damgard hash function, with compression function f . Let (x, x′) be a collision for H:

x ̸= x′, H(x) = H(x′)

Suppose further that |x| = |x′| (i.e., x and x′ are the same length), and that the sequence of chaining variables generated by H is the same for each. (Recall that H generates the sequence of chaining variables h0 = IV, h1, . . . , hk, hk+1 = H(x) for input x, and the sequence h′0 = IV, h

′ 1, . . . , h

′ k+1 = H(x

′) for input x′.) Prove that, in this case, we can easily find a collision for the compression function f .