Sht2 ecm3726 solns - SOLUTIONS PDF

Preview

Summary

SOLUTIONS...

Description

ECM3726 — Solutions to Example Sheet 2, 2017/18 1.

Compute the least non-negative residues of (a)

7501 (mod 1319),

(b)

5231 (mod 887),

(c)

10467 (mod 907).

You should read the imperative fast modular exponentiation method described in the lecture note appendix and adapt the algorithm for computation via hand (or calculator). Each solution should consist of a table with one column each for the quantities r, s, and e . Solution 1. See Table 1 for a complete solution to the first part of the question. To reduce the size of numbers involved, I consider residues with the least absolute value. It is equally acceptable to consider the least non-negative residues. The answers are: (a)

63 (mod 1319),

(b)

587 (mod 887), e 501 250 125 62 31 15 7 3 1

s 7 49 −237 −548 −428 −157 −412 −407 −545

(c)

413 (mod 907).

r 1 7 7 −340 −340 430 −241 367 −322 63

Table 1: Computation of 7501 (mod 1319). 2.

Using the Chinese remainder theorem and Fermat’s little theorem, compute the least nonnegative residue of 61023 (mod 143).

Solution 2. Here’s one approach: note first that 143 = 11 × 13. We use the Chinese remainder theorem to find x such that x ≡ 61023 (mod 11) and x ≡ 61023 (mod 13). By Fermat’s little theorem, 610 ≡ 1 (mod 11), so 61023 = 63 × (610 )102 ≡ 63 ≡ 6 × 3 ≡ 7 (mod 11). Likewise, 612 ≡ 1 (mod 13), so 61023 = 63 × 61 2

85

≡ 63 ≡ 6 × (−3) ≡ −5 (mod 13).

We want x ≡ 7 (mod 11) and x ≡ −5 (mod 13). Following the proof of the Chinese remainder theorem, we seek a1 (mod 11) and a2 (mod 13) such that x = 13a1 + 11a2 . Then 7 ≡ x ≡ 13a1 ≡ 2a1 (mod 11), whence a1 ≡ 7 × 2−1 ≡ 7 × 6 ≡ −2 (mod 11). Also −5 ≡ x ≡ 11a2 ≡ −2a2 (mod 13). Thus a2 = 5 × 2−1 ≡ 5 × 7 ≡ −4 (mod 13). We have x = −2 × 13 − 4 × 11 = −70 ≡ 73 (mod 143). 3.

You want to share a Diffie–Hellman secret key with your friend Bob. You have both received, from a trusted authority, the group G = (Z/1319Z )× , with generator g = 13. Bob sends you 1234. You choose an integer y = 3. What is the shared secret key?

Solution 3. The shared secret is 12343 (mod 1319). This is (−85)3 ≡ −85 × (7225) ≡ −85 × 630 ≡ 529 (mod 1319).

ECM3726

4.

C RYPTOGRAPHY

Bob wants to send you a secret message using the ElGamal public-key cryptosystem. Trent gives you a group G = (Z/1319Z )× , with generator g = 13. You choose a secret x = 10 and publish g x . Having received g x , Bob publishes the pair (96, 948). What was Bob’s message?

Solution 4. You publish g x = 1310 ≡ 360 (mod 1319) (this can be found by fast modular exponentiation). Bob uses his (unknown to us) ephemeral key to produce c1 = 96 = gk (mod 1319) and c2 = 948 = ( g x )k m. We recover m as m = c2 (( g x )k )−1 = c2 (( gk ) x )−1 = c2 ( c x1 )−1 . Now c1x = 9610 ≡ 706 (mod 1319). We use Euclid’s algorithm to find 706−1 (mod 1319). It is unnecessary to compute the si column in the table below. si ti 1 0 0 1 1319 = 1 × 706 + 613 1 −1 706 = 1 × 613 + 93 −1 2 613 = 6 × 93 + 55 7 −13 93 = 1 × 55 + 38 −8 15 55 = 1 × 38 + 17 15 −28 38 = 2 × 17 + 4 −38 71 17 = 4 × 4 + 1 167 −312 4 = 4×1+0 The gcd is 1, s = 167, and t = −312 in the equation 1 = 1319s + 706t. Thus −312 = 706−1 (mod 1319). We find m = −312c2 = −312 × 948 ≡ 999 5.

(mod 1319).

Let p be a prime number and let g be a primitive root modulo p. Let h ∈ F ×p . An integer x is said to be a discrete logarithm of h to base g if g x ≡ h (mod p). (a) Prove that if x and y are discrete logarithms of h to base g, then x ≡ y (mod p − 1). This shows that we can define dlogg ( h) to be the unique residue class modulo p − 1 such that gdlogg (h) = h in the group F × p. (b) Prove that dlogg ( h1 h2 ) = dlogg ( h1 ) + dlogg ( h2 ), for any h1 , h2 ∈ F × p. n (c) Prove that if n ∈ Z and h ∈ F × p , then dlogg ( h ) = n dlogg ( h).

Solution 5. (a) Suppose x and y are discrete logarithms of h to base g. Then g x = h = gy . Thus g x−y = 1. But g has order p − 1 in the cyclic group Fp×. so p − 1 divides x − y. That is, x ≡ y (mod p − 1). x1 x2 = g x1 + x2 . (b) Let h1 , h2 ∈ F × p . x1 = dlogg ( h1 ) and x2 = dlogg ( h2 ). Then h1 h2 = g g Thus dlogg ( h1 h2 ) = x1 + x2 = dlogg ( h1 ) + dlogg ( h2 ). n x n xn (c) Let n ∈ Z and let h ∈ F × p . Write x = dlogg ( h). Then h = ( g ) = g . Thus dlogg ( hn ) = xn = nx = n dlogg ( h).

6.

Let m = 1511 and let the group G be the set Z/mZ with a binary operation ∗ defined by a ∗ b ≡ ( a + b) + 5 (mod m). (a) Show that G with ∗ is an abelian group. 2

ECM3726

C RYPTOGRAPHY

(b) For a ∈ G, the quantity a x is defined as a ∗ ( a x−1 ) for an integer x ≥ 1, and a0 is defined to be e, the identity element of G. Guess and prove a simple formula for a n , given a ∈ G and n a non-negative integer. Use your algorithm to find the least non-negative residue of a n (mod m) with a = 7 and n = 200. (c) Given h ∈ G and a generator g ∈ G, find an algorithm for efficiently computing the least non-negative integer x such that g x = h. Use your algorithm to find the least non-negative integer x such that g x = h, where g = 12 and h = 111. (d) Would G be a good choice of group for use in the generalised Diffie–Hellman key exchange protocol? Justify your answer. Solution 6. All congruences in this solution are modulo m. (a)

• Associativity: a ∗ ( b ∗ c ) ≡ a ∗ (( b + c ) + 5) ≡ ( a + (( b + c ) + 5)) + 5 ≡ a + b + c + 10, by associativity and commutativity of +. Similarly, ( a ∗ b) ∗ c ≡ (( a + b) + 5) ∗ c ≡ ((( a + b) + 5) + c ) + 5 ≡ a + b + c + 10. • Commutativity: a ∗ b ≡ ( a + b) + 5 ≡ ( b + a ) + 5 ≡ b ∗ a. • Identity: take e ≡ −5. For any a ∈ G, we have a ∗ e ≡ ( a + e ) + 5 ≡ ( a − 5) + 5 ≡ a. By commutativity, e ∗ a ≡ a ∗ e ≡ a. • Inverses: let a ∈ G. Let b ≡ − a − 10. Then a ∗ b ≡ ( a + b) + 5 ≡ ( a − a − 10) + 5 ≡ −5 ≡ e. Likewise b ∗ a ≡ −5.

(b) a1 ≡ a ∗ a0 = ( a + (−5)) + 5 = a, a2 ≡ ( a + a ) + 5 ≡ 2a + 5, a3 ≡ a ∗ ( a2 ) ≡ ( a + (2a + 5)) + 5 ≡ 3a + 2 × 5. We guess a n ≡ an + 5( n − 1). This is certainly true if n = 0. Suppose for some integer n ≥ 0 and for any a ∈ G, that a n ≡ an + 5( n − 1). Then a n+1 ≡ a ∗ ( a n ) ≡ ( a + ( an + 5( n − 1))) + 5 ≡ a ( n + 1) + 5n ≡ a ( n + 1) + 5(( n + 1) − 1. The result is true by induction. We find 72 00 ≡ 7 × 200 + 5 × 199 ≡ 884 (mod m). (c) We want x such that gx + 5( x − 1) ≡ h. That is, x (5 + g) ≡ 5 + h. This happens if and only if x ≡ (5 + h)( 5 + g)−1 , where (5 + g)−1 is the inverse of 5 + g modulo m. The algorithm for finding x is: (1) compute (5 + g)−1 (mod m). (2) Multiply this by 5 + h. (3) Reduce modulo m. The result is x. If g = 12 and h = 111, we first compute (5 + 12)−1 via Euclid’s algorithm: si ti 1511 = 88 × 17 + 15 1 −88 17 = 1 × 15 + 2 −1 89 15 = 7 × 2 + 1 8 −711 The inverse is −711. Thus x ≡ (5 + h) ∗ (−711) ≡ −116 × 711 ≡ 629 (mod m). (d) G would be a very bad choice for DH. We’ve shown that the DLP is easy to solve in this group. This means that an eavesdropper could easily recover the shared secret key from the public data. 7.

You intercept a Diffie–Hellman key exchange between Alice and Bob. They use a group H = F ×p for p = 11411, with element g = 6. Alice publishes 3838 and Bob publishes 5549. (a) Using the algorithm given in the lecture note appendix, compute the order of g modulo 11411. (b) What is their shared secret? You should use the baby-step, giant-step algorithm in solving this. 3

ECM3726

C RYPTOGRAPHY

You may use a computer to calculate modular exponentials. Other than this, list all the steps in your computation. Solution 7. (a) By trial division, we find that the order of the group is 11410 = 2 × 5 × 7 × 163. Using the algorithm in the appendix of the lecture notes, we find the order of g. First set f = 11410. We tabulate: i 1

pi 2

f h 5705 11410 11410 1 2 5 2282 1 3 7 326 1 4 163 2 163 326 1 Then ord( g) is final value of f , namely 326. (b) To find the shared secret we find the discrete logarithm either of 3838 or of 5549, modulo 11411. I choose h = 3838. We want x such that g x = h. Note that this calculation occurs in the cyclic subgroup G = h gi of H. By the previous part of this question, |G| = ord( g) = 326. p We set n = ⌈ |G|⌉ = 19 and produce lists gi and h( g−n ) j where 0 ≤ i < n and 0 ≤ j < n, and search for a match. First we use Euclid’s algorithm to compute g−1 . Now 11411 = 1901 × 6 + 5 and 6 = 1 × 5 + 1 so 1 = 6 − 1 × (11411 − 1901 × 6) = 1902 × 6 − 11411. Thus 1902 = 6−1 (mod p). By fast modular exponentiation, ( g−1 )n = 190219 ≡ 1024 (mod p). We now compute the lists. i g i h( g − n ) i 0 1 3838 1 6 788 2 36 1357 3 216 10982 4 1296 6661 5 7776 3318 6 1012 7133 7 6072 192 8 2199 9946 9 1783 4819 10 10698 8458 11 7133 1909 12 8565 2491 13 5746 10531 14 243 1960 15 1458 11195 16 8748 8780 17 6844 7416 18 6831 10454 There is a match: g11 = 7133 = h( g−n )6 . Thus h = g11+6n = g125 . The discrete log of 3838 modulo 11411 is 125. Finally, we compute the shared secret as 5549125 ≡ 7096 (mod p).

4...