如何确定此 RSA 算法示例中的 d？

Question

作为我大学课程的一部分，我被要求解决一个问题。是关于RSA算法的话题。

我得到了 p = 29，q = 17 和 e = 5。

我必须确定d。

所以我知道 n = 29 x 17 => 493 和 phi(n) = 448

所以我开始深入了解

5 * d mod 448 = 1

然后我按照欧氏算法得到

448 = 89(5) + 3

3 是那里的余数（商）。在前面的例子中，我做了商最终为 1 的情况，很容易解决 d 是什么问题。但是，对于这个例子，我不知道如何做，余数是 3.

有人知道怎么做吗？帮助将不胜感激。

Answer 1

你没有完成扩展欧氏算法。 (https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm)

你应该 (r_i, s_i, t_i):

(448,1,0)    =>  1*448   + 0*5 = 448
(5, 0, 1)    =>  0*448   + 1*5 =   5
(3, 1, -89)  =>  1*448  - 89*5 =   3
(2, -1, 90)  => -1*448  + 90*5 =   2
(1, 2, -179) =>  2*448 - 179*5 =   1

你可以查看 2*448 - 179*5 = 1，所以 -179 * 5 = 1 mod 448，或 269*5 = 1 mod 448，你的答案是 d = 269

如何确定此 RSA 算法示例中的 d？

How to determine d in this RSA Algorithm Example?

algorithm

cryptography

rsa