在Python中实现RSA加密
在Python中实现RSA加密
提问于 2018-06-26 03:09:01
在过去的几天里，我一直在尝试用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])回答 1
Stack Overflow用户
回答已采纳
发布于 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页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/51030384
复制相关文章
相似问题