math - 对于 RSA，我如何计算秘密指数？

Question

对于 RSA，我如何计算秘密指数？

给定 p 和 q 两个素数，以及 phi=(p-1)(q-1) 和公共指数 (0x10001)，我如何获得秘密指数 'd' ？

我读过我必须做的事情：d = e ^-1 mod phi using modules inversion and the euclidean equation但我无法理解上述公式如何映射到模块化反演维基页面上的a ^-1 ≡ x mod m公式，或者它如何映射到欧几里得 GCD 方程。

有人可以帮忙吗，干杯

Answer 1

您可以使用扩展欧几里得算法d在同余中求解

de = 1 mod phi(m)

对于 RSA 加密，e是加密密钥，d是解密密钥，加密和解密都是通过取幂 mod 进行的m。如果使用 key 加密消息a ，e然后使用 key 解密，则d计算 (a ^e ) ^d = a ^de mod m。但是de = 1 mod phi(m)，因为欧拉的总定理告诉我们^de与¹ mod m 一致——换句话说，你得到了原来的a.

没有已知的有效方法来获得d仅知道加密密钥e和模数m而不知道分解的解密密钥m = pq，因此认为 RSA 加密是安全的。