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(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

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

cd mod N = (me)d mod N = m(e⋅d) mod N = m(1 + k⋅φ(N)) = (m1) ⋅ (mφ(N))k mod N

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

1) axy = (ax)y = (ay)x，并且
2) ax+y = ax ⋅ ay

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

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