RSA-шифрование реализовано в Python - PullRequest
Новая
       27

RSA-шифрование реализовано в Python

0 голосов
/ 25 июня 2018

В последние дни я пытался реализовать алгоритм RSA в Python.Мой код работал нормально для меньших простых чисел (по крайней мере, до первого миллиона простых чисел).Однако, когда я пытался использовать 49–50 миллионов, мой код сломался и дал неверные результаты.

Например, при использовании простых чисел 11 и 17 в качестве начальных простых чисел я получаю следующие ключи: public: (3 187) и private: (107 187).Используя это для шифрования числа 50, зашифрованный текст равен 84, который затем расшифровывается обратно до 50.

Однако при использовании простых чисел 961752619 и 961752931 для шифрования числа 50 я получаю 781250000000, что при расшифровке дает 482883073917854018.

Я попробовал первые 50000 чисел, используя последнюю пару простых чисел, и ни одно из них не вернуло правильное значение.Очевидно, что-то здесь не так, но я понятия не имею, что.Я включил ссылку для вставки в свой код, и также вставил код под сообщением. 

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 Ответ

0 голосов
/ 25 июня 2018

Предполагая, что вы используете Python 3, в котором деление всегда возвращает число с плавающей запятой, проблема заключается в 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
...