Python 中实施的 RSA 加密

Question

过去几天我一直在尝试在 Python 中实现 RSA 算法。我的代码适用于较小的质数（至少达到前百万个质数）。但是，当尝试使用百万分之 49 到百万分之 50 时，我的代码出现故障并给出了错误的结果。

例如，当使用素数 11 和 17 作为起始素数时，我得到以下键：public: (3,187) 和 private: (107,187)。用这个加密数字50，密文是84，再解密回50

然而，当使用质数 961752619 和 961752931 加密数字 50 时，我得到 781250000000，解密后得到 482883073917854018。

我已经使用后一对素数尝试了前 50000 个数字，none 返回了正确的值。显然这里出了点问题，但我不知道是什么。我已将 a pastebin link 添加到我的代码中，并将代码也粘贴到 post 下方。

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])

Answer 1

假设您正在使用 Python 3，其中除法总是 return 是一个浮点数，问题出在 find_d()。表达式 (k*phi_n+1)/e 将任意精度整数转换为有限精度浮点数，这就是不准确的地方。如果你想测试 k*phi_n+1 是否可以被 e 和 [= 整除23=] 如果是商，你应该改为：

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

Python 中实施的 RSA 加密

RSA encryption implemented in Python

python

encryption

primes

rsa