rsa - RSA 求公共指数的倒数

Question

我对 RSA 密钥生成及其用法有一个非常基本的疑问。

在 RSA 密钥生成中，您选择两个非常大的质数。然后你将它们相乘。（eq p * q = N）现在，Euler(N)=(p-1)(q-1)。现在你找到一个数0 < e < Euler(N)，使得 e 和 Euler(N) 互质。{e.Euler(N)}成为你的公钥。现在你计算 d(private key) 使得e * d =1 (mod(Euler(N))).
现在假设你用你的公钥加密了一些东西（m） -c=m^e(mod(N)). 现在在用私钥（d）解密时，你做了c^d(mod(N))。
现在我怀疑你在 mod(Euler(N)) 中找到了 e 的倒数，但是当你解密时，你是在 mod(N) 中做的。这怎么可能？

Answer 1

请参阅此处和此处的维基百科。基本上，您希望解密以“撤消”加密。由于对于某个整数 k，e⋅d = 1 mod φ(N) 等价于 e⋅d = 1 + k⋅φ(N)，因此您有：

c ^d mod N = (m ^e ) ^d mod N = m ^(e⋅d) mod N = m ^{(1 + k⋅φ(N))} = (m ¹ ) ⋅ (m ^φ(N) ) ^k mod N

通过应用您在代数中学到的以下规则：

1) a ^xy = (a ^x ) ^y = (a ^y ) ^x和
2) a ^x+y = a ^x ⋅ a ^y

为了完成这个并简化 (m ¹ ) ⋅ (m ^φ(N) ) ^k mod N，请记住 a ^φ(N) = 1 mod N，所以

(m ^φ(N) ) ^k mod N = 1 ^k = 1 mod N。