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

Question

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

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

我读到我必须这样做： d = e^-1 模数 使用 模反演 和 欧氏方程 但我无法理解上述公式如何映射到 A^-1 χ mod m 模反演维基页面上的公式，或者它如何映射到欧几里德 GCD 方程。

有人可以帮忙吗，欢呼

Answer 1

您可以使用 扩展欧几里得算法 解决 d 在一致性中

de = 1 mod phi(m)

对于 RSA 加密， e 是加密密钥， d 是解密键，并且通过指示模式进行加密和解密 m. 。如果您加密消息 a带钥匙 e, ，然后使用密钥解密 d, ，你计算（a^e)^d = 一个^德 模组 m. 。但是由于 de = 1 mod phi(m), 欧拉整体定理 告诉我们一个^德 是一致的¹ mod m——换句话说，你得到了原来的 a.

没有已知的有效方法来获取解密密钥 d 仅知道加密密钥 e 和模数 m, ，在不知道因式分解的情况下 m = pq, ，因此RSA加密被认为是安全的。