在过去的几天里,我一直在尝试用Python实现RSA算法。我的代码适用于较小的质数(至少直到前一百万个质数)。但是,在尝试使用第49到第50百万次时,我的代码崩溃并给出了错误的结果。
例如,当使用素数11和17作为开始素数时,我得到以下密钥: public:(3,187)和private:(107,187)。使用它加密数字50,密文是84,然后解密回50。
然而,当使用质数961752619和961752931对数字50进行加密时,我得到781250000000,解密后得到482883073917854018。
我尝试了前50000个数字,使用后一对素数,没有一个返回正确的值。显然,这里出了点问题,但我不知道是什么原因。我已经将a pastebin link包含到我的代码中,并且我还将代码粘贴到了帖子下面。
def gcd(a, b):
if b > a:
if b % a == 0:
return a
else:
return gcd(b % a, a)
else:
if a % b == 0:
return b
else:
return gcd(b, a % b)
def find_d(phi_n,e):
k = 1
mod0 = False
while not mod0:
d = (k*phi_n+1)/e
if(d % 1 == 0):
return d
k+=1
def find_e(phi_n):
e = 3
while True:
if not gcd(e,phi_n) == 1:
e+=2
else:
return e
def generate_keys(p1,p2):
n = p1*p2
phi_n = (p1-1)*(p2-1)
e = find_e(phi_n)
d = int(find_d(phi_n,e))
return ((e,n),(d,n))
def endecrypt(key,m):
return pow(m,key[0],key[1])
发布于 2018-06-26 04:29:32
假设你使用的是Python3,在Python3中,除法总是返回一个浮点数,那么问题出在find_d()
上。表达式(k*phi_n+1)/e
将任意精度的整数转换为有限精度的浮点数,这就是不准确的地方。如果你想测试k*phi_n+1
是否能被e
整除并返回商,你应该这样写:
if (k*phi_n+1) % e == 0:
return (k*phi_n+1) // e # Note use of integer division
或者,使用divmod()
会稍微高效一些
d, rem = divmd(k*phi_n+1, e)
if rem == 0:
return d
https://stackoverflow.com/questions/51030384
复制相似问题