Geek asks and answers

How to find d given by p, q and e in RSA?

I know that I need to use the advanced Euclidean algorithm , but I'm not sure exactly what calculations I need to do. I have a huge amount. Thanks

+11
source share
3 answers

Well, it dis chosen such that d * e == 1 modulo (p-1)(q-1), therefore, you can use the Euclidean algorithm for this ( finding the modular multiplicative inverse ).

If you are not interested in understanding the algorithm, you can simply call BigInteger # modInverse directly.

 d = e.modInverse(p_1.multiply(q_1))
+13
source

Given that p = 11, q = 7, e = 17, n = 77, φ (n) = 60, and d =?

: -

ed mod φ (n) = 1

17 d mod 60 = 1

: n, 60 , [e] - .

60 = 17

: - , 17 60. 3.5..... 3.

60 = 3 (17)

4: 60 = 3 (17), . ?

60 = 3 (17) + 9 < == 3 17, 51, 9, 60. , .

5: - 17 9 .

17 = 9

6: - , 9 17. 1.8.......

17 = 1 (9)

7: - 4: 17 = 1 (9)

17 = 1 (9) + 8 < == 1 9, 9, 8, 17. , .

8: 9 8 .

9 = 1 (8)

9 = 1 (8) + 1 < == +1, , .

A: - 8, 9 = 1 (8) + 1, : 1. = 9 - 1 (8)

B: - , (8), 8 = 17 - 1 (9) 7. A : -

1 = 9 -1 (17 - 1 (9)) < == , 9 = 1 (9), : -

1 = 1 (9) -1 (17) +1 (9) < == . 1 (9) 1 (9) - 2 (9).

1 = 2 (9) -1 (17)

C: - , (9) 9 = 60 - 3 (17) 4. B : -

1 = 2 (60-3 (17) -1 (17)

1 = 2 (60) -6 (17) -1 (17) < == . 6 (17) 1 (17) - 7 (17).

1 = 2 (60) -7 (17) < == , , , next 17. 7. .

60-7 =

, , d = 53.

+12

Sidudozo .

, Extended Euclidean Algorthim d?

, ed mod φ(n) = 1 cgd(e, φ(n)) = 1.

, Extended Euclidean Algorthim cgd(a,b) = as + bt, cgd(e, φ(n)) = es + φ(n)t = 1, d s + φ(n),

ed mod φ(n) = 1.

So, given e=17and φ(n)=60(taken from Sidudozo's answer ), we substitute the corresponding values ​​in the above formula: cgd(e, φ(n)) = es + φ(n)t = 1⇔ 17s + 60t = 1.

At the end of Sidudozo's answer we get s = -7. Thus, d = s + φ(n)⇔ d = -7 + 60⇒ d = 53.

Check the results. The condition was ed mod φ(n) = 1.

See 17 * 53 mod 60 = 1 . Correctly!

+1
source

More articles:


All Articles