我最近对 RSA 产生了兴趣并尝试实现它。 这是我的代码的简化版本:
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, x, y = egcd(b % a, a)
return (g, y - (b // a) * x, x)
def modinv(b, n):
g, x, _ = egcd(b, n)
if g == 1:
return x % n
p = 89
q = 107
n = p * q
phi = (p - 1) * (q - 1)
e = 3
d = modinv(e, phi)
message = 74
encrypted = (message**e) % n
decrypted = (encrypted**d) % n
print(message)
print(encrypted)
print(decrypted)
对于小消息，本例中使用 74，效果很好。 但是，当设置 message = 120000 或任何其他大值时，结果如下:
120000
147
5724
因此，我在 this website 上将完全相同的值输入到 RSA 计算器中. 这也导致错误解密消息。
这可能是什么问题？数学有问题还是这是python问题？提前致谢。
请您参考如下方法:
RSA 以 n 为模工作。因此，消息不能大于或等于 n。这可以通过增加素数 p 和 q 的大小来解决。生成大素数的一种简单方法是使用 rabin-miller 素数测试。您可以在此处阅读有关该测试的更多信息 Rabin-Miller Primality Test .
另外，在旁注中，您的代码中有
(message ** e) % n
虽然这对于小值来说很快，但使用内置的 pow 函数要快得多
pow(message, e, n)
