我最近对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
或任何其他大值时,结果如下:
所以,我在this website上的RSA计算器中输入了完全相同的值。 这也导致了一个解密错误的消息。在
有什么问题吗?这是数学问题还是python问题?提前谢谢。在
RSA的工作方式是模n。因此,消息不能大于或等于n。这可以通过增加质数p和q的大小来解决。生成大素数的一个简单方法是使用rabin-miller素性测试。你可以在这里Rabin-Miller Primality Test阅读更多关于这个测试的信息。在
另外,在代码中
虽然这对于小值很快,但是使用内置的
^{pr2}$pow
函数要快得多相关问题 更多 >
编程相关推荐