RSA Python & Extended Euclidean алгоритм для генерации закрытого ключа. Variable is None

Question

Проблема с простым алгоритмом шифрования RSA. Extended Euclidean algorithm используется для создания закрытого ключа . Проблема с методом multiplicative_inverse(e, phi). Он используется для нахождения мультипликативной инверсии двух чисел. Функция не возвращает личный ключ правильно. Он возвращает значение None.

---

У меня есть следующий код:

import random 

def gcd(a, b): 
    while b != 0: 
     a, b = b, a % b 
    return a 

#Euclidean extended algorithm for finding the multiplicative inverse of two numbers 
def multiplicative_inverse(e, phi): 
    d = 0 
    x1 = 0 
    x2 = 1 
    y1 = 1 
    temp_phi = phi 

    while e > 0: 
     temp1 = temp_phi/e 
     temp2 = temp_phi - temp1 * e 
     temp_phi = e 
     e = temp2 

     x = x2- temp1* x1 
     y = d - temp1 * y1 

     x2 = x1 
     x1 = x 
     d = y1 
     y1 = y 

    if temp_phi == 1: 
     return d + phi 

def generate_keypair(p, q): 
    n = p * q 

    #Phi is the totient of n 
    phi = (p-1) * (q-1) 

    #An integer e such that e and phi(n) are coprime 
    e = random.randrange(1, phi) 

    #Euclid's Algorithm to verify that e and phi(n) are comprime 
    g = gcd(e, phi) 
    while g != 1: 
     e = random.randrange(1, phi) 
     g = gcd(e, phi) 

    #Extended Euclid's Algorithm to generate the private key 
    d = multiplicative_inverse(e, phi) 

    #Public key is (e, n) and private key is (d, n) 
    return ((e, n), (d, n)) 


if __name__ == '__main__': 
    p = 17 
    q = 23 

    public, private = generate_keypair(p, q) 
    print("Public key is:", public ," and private key is:", private) 

Поскольку в следующей строке d = multiplicative_inverse(e, phi) переменной d содержит None значение, то при шифровании я получаю следующее сообщение об ошибке:

TypeError: unsupported operand type(s) for pow(): 'int', 'NoneType', 'int'

Выход для кода, который я указал в вопросе:

Public key is: (269, 391) and private key is: (None, 391)

---

Вопрос: Почему переменная содержит None значение. Как это исправить?

Answer 1

Ну, я не уверен в самом алгоритме и не могу сказать, если вы ошибаетесь или правы, но вы возвращаете значение только от multiplicative_inverse при if temp_phi == 1. В противном случае результатом будет None. Поэтому я ставлю ваш temp_phi != 1 при запуске функции. Вероятно, в логике функции есть ошибка.

Answer 2

Я думаю, что это проблема:

if temp_phi == 1: 
    return d + phi 

Эта функция возвращает некоторое значение, только при условии, что temp_phi равно 1, в противном случае он не будет возвращать никакого значения.