This problem explores an attack on RSA with small private key d. Preliminaries. Let r be...

Transcribed Image Text:

This problem explores an attack on RSA with small private key d. Preliminaries. Let r be a positive rational number and write r a/b with a, b e N. Let 90,91,...9m € N be the sequence of quotients produced by applying the Euclidean Algorithm to the numerator and denominator of r: a b To Tm-3 = 9m-15m-2 +Tm-1, Tm-2 = 9mm-1 + rm, Recall the familiar sequences T- < = gob + ro, = qiro + r₁, = 92r1 + 12, ⠀ A-2 = 0, A-1 = 1, A B-2 = 1, B-1 = 0, B₁ = B 2B² The quotients A₁/B₁ (0 ≤ i ≤ m) are called the convergents of r because they oscillate around and converge toward r as i increases, with Am = a, Bm = b, and hence Am/Bm = r. In fact, the following theorem (which you may use without proof) asserts that any rational number sufficiently close to r must occur as one of the convergents: 0<ro<b, 0<r₁ <ro, 0<7₂ <71, qiAi-1 + Ai-2 for 0≤ i ≤m, qiBi-1 + Bi-2 for 0≤ i ≤m. a A Theorem. Let r= € with a, b>0, and let EQ be a fraction in lowest terms such that B Then A= A and B = B; for some i € {0, 1,...,m}. Tm-1 = gcd(a, b), Tm = 0. Vn d< Now back to RSA. Let n = pq where p, q are odd primes satisfying q<p < 2q. These inequalities are reasonable as p and q are usually assumed to have the same bit length. Let e, d be integers with 1 <e,d<o(n) and ed = 1 (mod o(n)). Let k = Z satisfy ed = 1+ ko(n) and suppose that d is small compared to n; specifically, 19 a. (5 marks) Prove that 1 ≤ k <d and ged(d, k) = 1. b. (3 marks) Prove that 2 ≤ n - (n) < 3√n. c. (4 marks) Use parts (a) and (b) to prove that 0 < kn - - ed < 3d√n. k d. (4 marks) Conclude from part (c) and the upper bound (3) on d that 0< BIO V $100 (3) 1 √n 2d² This problem explores an attack on RSA with small private key d. Preliminaries. Let r be a positive rational number and write r a/b with a, b e N. Let 90,91,...9m € N be the sequence of quotients produced by applying the Euclidean Algorithm to the numerator and denominator of r: a b To Tm-3 = 9m-15m-2 +Tm-1, Tm-2 = 9mm-1 + rm, Recall the familiar sequences T- < = gob + ro, = qiro + r₁, = 92r1 + 12, ⠀ A-2 = 0, A-1 = 1, A B-2 = 1, B-1 = 0, B₁ = B 2B² The quotients A₁/B₁ (0 ≤ i ≤ m) are called the convergents of r because they oscillate around and converge toward r as i increases, with Am = a, Bm = b, and hence Am/Bm = r. In fact, the following theorem (which you may use without proof) asserts that any rational number sufficiently close to r must occur as one of the convergents: 0<ro<b, 0<r₁ <ro, 0<7₂ <71, qiAi-1 + Ai-2 for 0≤ i ≤m, qiBi-1 + Bi-2 for 0≤ i ≤m. a A Theorem. Let r= € with a, b>0, and let EQ be a fraction in lowest terms such that B Then A= A and B = B; for some i € {0, 1,...,m}. Tm-1 = gcd(a, b), Tm = 0. Vn d< Now back to RSA. Let n = pq where p, q are odd primes satisfying q<p < 2q. These inequalities are reasonable as p and q are usually assumed to have the same bit length. Let e, d be integers with 1 <e,d<o(n) and ed = 1 (mod o(n)). Let k = Z satisfy ed = 1+ ko(n) and suppose that d is small compared to n; specifically, 19 a. (5 marks) Prove that 1 ≤ k <d and ged(d, k) = 1. b. (3 marks) Prove that 2 ≤ n - (n) < 3√n. c. (4 marks) Use parts (a) and (b) to prove that 0 < kn - - ed < 3d√n. k d. (4 marks) Conclude from part (c) and the upper bound (3) on d that 0< BIO V $100 (3) 1 √n 2d²

Answer rating: 100% (QA)

a Since ed 1 mod n we have ed 1 kn for some integer k ... View the full answer