RSA加密和解密与大消息不一致

Question

我最近对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

所以,我在本网站的RSA计算器中输入了完全相同的值.这也导致错误解密的消息.

这可能是什么问题？数学有问题还是这是一个python问题？提前致谢.

Answer 1

RSA以模数方式工作.因此,消息不能大于或等于n.这可以通过增加素数p和q的大小来修复.生成大素数的简单方法是使用rabin-miller素数检验.你可以在这里阅读更多关于该测试的Rabin-Miller Primality Test.

另外,在旁注中,您的代码中也有

(message ** e) % n

虽然这对于小值很快,但使用内置pow函数要快得多

pow(message, e, n)