RSA 求公共(public)指数的倒数

Question

我对 RSA key 生成及其使用有一个非常基本的疑问。

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

Answer 1

参见维基百科here和here 。基本上，您想要解密来“撤消”加密。由于对于某个整数 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 模 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。