Discrete Algebraic Methods

2.10. Let n = pq for two secret primes p and q of the form p = 2p' +1 and q = 2q' + 1, respectively, where p' and q' are the prime numbers, too. Let a ∈ (ℤ/nℤ)∗ be an element of order 2pq. Define the compression function h : {1, . . . , n2}→ (ℤ/nℤ)∗ by h(x) = ax mod n. We use the values n = 603 241 and a = 11 to fix such a compression function. Use the collision h(1 294 755) = h(80 115 359) to factorize n.

2.11. (ElGamal signatures) Let p be a prime number and α be a generator of (ℤ/pℤ)∗. The plaintext space is defined as T = (ℤ/pℤ)∗ and the signature space as S =(ℤ/pℤ)∗ × ℤ/(p − 1)ℤ. Keys are of the form k = (p, α, β, m, s) ∈ ℕ5 where β = αm mod p and s ∈ (ℤ/(p − 1)ℤ)∗. The signature function uk : J → S is defined by uk(x) = (γ, δ) where γ