ed=1如何在RSA密码系统中实现？

Question

我完全理解RSA算法是如何工作的，但现在我正在尝试用这个公式进行推理。我想知道：

为什么RSA加密中的公钥e和私钥d必须满足公式ed =1mod (p−1)(q mod 1)？

这是因为标准的模算术规则，其中1modany等于1，或者这个答案还有更多？

Answer 1

假设您有一个名为x的消息，您想用您的公钥(pq，e)对其进行加密。如果你加密x，你会得到x^e mod pq。知道d的人可以得到x^(ed) mod pq。由于ed =1mod (p - 1)(q - 1)，通过费马小定理，我们得到x^(ed) mod pq = x，从而解密消息。如果ed != 1mod (p - 1)(q - 1)，则消息无法解密。

费马小定理的链接：https://en.wikipedia.org/wiki/Fermat%27s_little_theorem