encryption - 如何仅在给定私钥 d 和 Phi(n) 的情况下解密 RSA2 加密消息 C？

Question

给定私钥 d 和 Phi(n)，如何解密 RSA 加密消息 C？

众所周知，这是一个教科书 RSA，所以据说 e 很小。

我已经完成了解密 RSA 的所有常用方法，但是，我似乎只能用 Phi(n) 做一些小事情。

Answer 1

对于 RSA 模数（已知形式为 n = p*q，p 和 q 为素数）的 Phi(n) 很简单：

φ(n) = (p-1) * (q-1)

由于 p-1 和 q-1 都是复合的（没有素数，因为它们是偶数），您需要遍历分解的所有组合（假设每个因子属于 p 和随后属于 q），它们满足 p 和q 大小相同。如果增加的产品不是素数，您可以跳过该组合。

您从假定的 p 和 q 重新计算 n，如果解密有效，您就找到了。