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

Question

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

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

我读过我必须做的: d = e-1 mod phi 使用 modular inversion和 euclidean equation但我无法理解上述公式如何映射到 a-1 ≡ x mod m 模块化反演维基页面上的公式，或者它如何映射到欧几里德 GCD 方程。

有人可以帮忙吗，干杯

Answer 1

您可以使用 extended Euclidean algorithm求解d在一致

de = 1 mod phi(m)

对于 RSA 加密， e是加密 key ， d是解密 key ，加密
和解密都由幂模 m执行.如果您对消息进行加密 a带 key e ，然后使用 key d 对其进行解密, 你计算 (ae)d = ade mod m .但
自从 de = 1 mod phi(m) , Euler's totient theorem告诉我们ade是全等的
到 a1 mod m -- 换句话说，你得到原来的 a .

没有已知的有效方法来获取解密 key d只知道
加密 key e和模数 m , 不知道分解 m = pq ， 所以
RSA 加密被认为是安全的。