RSA Python & Extended Euklidischer Algorithmus zum Generieren des privaten Schlüssels. Variable ist keine

Question

Problem mit einfachen RSA Verschlüsselungsalgorithmus. Extended Euclidean algorithm wird verwendet, um den privaten Schlüssel zu generieren. Das Problem mit multiplicative_inverse(e, phi) Methode. Es wird verwendet, um die multiplikative Umkehrung zweier Zahlen zu finden. Die Funktion gibt den privaten Schlüssel nicht korrekt zurück. Es gibt None Wert zurück.

---

Ich habe den folgenden Code:

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) 

Da die Variable d in der folgenden Zeile d = multiplicative_inverse(e, phi) enthält None Wert, dann während der Verschlüsselung erhalte ich die folgende Fehlermeldung:

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

Ausgang für den Code, den ich in der Frage zur Verfügung gestellt habe:

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

---

Frage: Warum die Variable None Wert enthält. Wie behebt man das?

Answer 1

Nun, ich bin mir nicht sicher über den Algorithmus selbst, und kann nicht sagen, ob Sie falsch oder richtig, aber Sie geben nur einen Wert von multiplicative_inverse Funktion, wenn if temp_phi == 1. Andernfalls ist das Ergebnis Keine. Ich wette also temp_phi != 1, wenn Sie die Funktion ausführen. Es gibt wahrscheinlich einen Fehler in der Logik der Funktion.

Answer 2

denke ich, dass dies ein Problem ist:

if temp_phi == 1: 
    return d + phi 

Diese Funktion einen Wert zurückgeben nur unter der Bedingung, dass temp_phi gleich 1 ist, sonst wird es keinen Wert zurück.