公钥加密的值可以用别人的私钥解密

Question

今天我只是测试我的代码，发现：

假设 Bob 和 Alice 分别拥有密钥对 (pub1,priv1) 和 (pub2,priv2)。

如果 Bob 使用 pub2（Alice 的公钥）加密消息，然后他再次使用 priv1（鲍勃的私钥）加密该密文，它会返回与消息相同的字节！ IE。 bob 能够解密使用 pub2

加密的密文

但事实证明，当消息被pub2和priv1加密时，它们奇怪地生成了相同的密文，而且priv1和priv2都可以解密它们......

这是我执行的计算：

e = 65537

//Bob's stuff
p = 512 bit prime number
q = 512 bit prime number
n = p * q (where * means multiply)
on = (p-1) * (q-1)
d = modulo inverse of (e, on)

//Alice's stuff
p1 = 512 bit prime number
q1 = 512 bit prime number
n1 = p1 * q1
on1 = (p1-1) * (q1-1)
d1 = modulo inverse of (e, on1)

所以当我说我要加密时

a = 97 (according to utf8)

（让我们忘记使用小数字进行加密的漏洞）

所以我尝试加密：

c1 = mod(97 * e, n1)

，即用爱丽丝的公钥加密。

现在我想让 Alice 验证该消息仅属于 Bob（现在我们不讨论 x509）

所以我用 Bob 的私钥

priv1（或 d）

加密了该密文 c1，如下所示：

c2 = mod(c1 * d, on)

这样Alice就可以解密它两次并确保它只属于Bob：

c3 = mod(c2 * e, n) //as we encrypted c1 with bob's pvt key, now it should be decrypted using his public key.

并解密消息：

c4 = mod(c3 * d1, on1) //should give original message i.e. 97

但是，它并没有按照应有的方式发生，而是

mod(97 * e, n)

，

mod(97 * e, n1)

，

mod(97 * e, on)

，

mod(97 * e, on1)

给出相同的输出..这怎么可能？ (n, on) 和 (n1, on1) 有很大不同。此外，我还能够使用任何人的私钥解密使用上述方法加密的消息，而该人的相应公钥根本没有用于加密。

Answer 1

RSA 加密系统使用模幂作为原始运算，而不是您似乎使用的模乘法。如果 n = p * q 是 RSA 模数，素数 p 和 q 的乘积，e 和 d 分别是加密和解密指数，则加密为 c = x^e mod n，解密为 x = c^d mod n，其中 x 是明文整数。当然，模乘法是模幂的关键组成部分。在Python中，您可以使用内置pow函数的三参数形式来轻松高效地执行模幂运算，如此简单

c = pow(x, e, n)
x = pow(c, d, n)

使用sage来探索RSA（包括RSA教程）也相对容易。在 sage 中，你可以指示算术是在整数模 n 的环中完成，类似于

R = Integers(n)
x = R(97)
c = x ^ e
decrypted = c ^ d
print(decrypted == x)  # prints True

请注意，在 sage 中

^

是求幂运算符，而在 python 中它是异或 (xor) 运算符。

如果以 n 为模的整数环对您来说有点太奇特，那么您可以在 sage 中使用常规整数算术与

mod()

和

power_mod()

函数。