YALE UNIVERSITY
DEPARTMENT OF COMPUTER SCIENCE

	CPSC 467a: Cryptography and Computer Security	Handout #12
Yinghua Wu		November 6, 2006

Solutions to Problem Set 4

Problem 17: Diffie-Hellman Key Exchange

Recall Lucas test: g is a primitive root of p if and only if $g(p-1)∕q ⁄≡ 1 (mod p)$
for all q > 1 such that q∣(p - 1). So here for p = 29 and g = 2, we check all the possible q = {2,4,7,14,28} as the following:
$228∕2 ≡ 28 (mod 29) 28∕4 2 ≡ 12 (mod 29) 228∕7 ≡ 16 (mod 29) 28∕14 2 ≡ 4 (mod 29) 228∕28 ≡ 2 (mod 29)$
Therefore, g has passed Lucas test and is a primitive root of p.
According to Diffie-Hellman Key Exchange Protocol, Alice computes a ≡ g^x ≡ 2⁵ ≡ 3 (mod p), and Bob computes b ≡ g^y ≡ 2³ ≡ 8 (mod p). So the shared secret key is k ≡ a^y ≡ b^x ≡ 27 (mod p).

Problem 18: ElGamal Cryptosystem

According to ElGamal Protocol, Bob’s public key is (p,g,b) = (29,2,8) and private key is (p,g,y) = (29,2,3).

Problem 19: Square Roots with Composite Moduli

∣Z*₁₀₅∣ = φ(105) = φ(3) * φ(5) * φ(7) = 48.
Because 105 = 3 × 5 × 7 and 1 Z*₁₀₅, then if b² ≡ 1 (mod 105), we have
$b2 ≡ 1 (mod 3) b2 ≡ 1 (mod 5) 2 b ≡ 1 (mod 7)$
And we can easily see that the squre roots of 1 in Z*₃, Z*₅ and Z*₃ are all ±1. Conversely, if there is b satisfying the following equations:
$b ≡ ±1 (mod 3) b ≡ ±1 (mod 5) b ≡ ±1 (mod 7)$
Then b² ≡ 1 (mod 105). According to Chinese Remainder theorem, we solve the above set of equations and get all square roots of 1 modulo 105, {1,29,34,41,64,71,76,104}.
From (b) and some extension of Claim 1 in Section 62, we could know that the mapping cu : Z*_n → QR_n defined by bb² (mod n) is a 8-to-1 function, in which n = pqr for p,q,r distinct odd primes. The brief explanation is if a QR_n, then a has two square roots S_p = {±b_p} mod p, two square roots S_q = {±b_q} mod q and two square roots S_r = {±b_r} mod r. Any triple combination {b₁,b₂,b₃}, in which b₁ S_p, b₂ S_q and b₃ S_r, uniquely determines the number b Z*_n such that b² ≡ a (mod n). So cu is a 8-to-1 function and ∣QR₁₀₅∣ = ∣Z*₁₀₅∣ = 6.
From the above description, we can know that if a QR_n, then a is also a quadratic residue modulo p,q,r, and vice versa. So in order to find out all quadratic residues of n = 105, we need to find out quadratic residues of p = 3,q = 5,r = 7 first. That’s QR₃ = {1}, QR₅ = {1,4}, and QR₇ = {1,2,4}. We solve the following set of equations by Chinese Remainder theorem:
$a ≡ a1 (mod 3),a1 ∈ QR3 a ≡ a2 (mod 5),a2 ∈ QR5 a ≡ a3 (mod 7),a3 ∈ QR7,$
and we can get all the quadratic residues module 105, {1,4,16,46,64,79}.

Problem 20: Computing Square Roots Modulo a Prime

According to Euler Criterion, since 103 is a prime and 2^(103-1)∕2 ≡ 2⁵¹ ≡ (2¹⁰)⁵ * 2 ≡ (-6)⁵ * 2 ≡ 1 (mod 103), 2 is a quadratic residue modulo 103.
According to Claim 3 in Section 64, since 103 ≡ 3 (mod 4) and 2 QR₁₀₃, then b ≡ 2^(103+1)∕4 ≡ 2²⁶ ≡ 38 (mod 103) is a square root of 2 modulo 103.

Problem 21: Quadratic Residues

You can use Legendre Symbol to directly show the result or make advantage of a prime’s primitive roots as the following:

Since p is an odd prime, there must be some primitive root of p, denoted as g. Assume a ≡ g^u (mod p) and b ≡ g^v (mod p). Since a,b QNR_p, u and v must be odd integers. Then ab ≡ g^u+v (mod p). Because u + v is even, g^(u+v)∕2 is exactly a square root of ab. So ab is a quadratic residue modulo p.