Kann jemand erklären, was mit dem letzten Teil dieses RSA-Beispiels passiert?

Question

Der Titel möglicherweise nicht korrekt, ich war mir nicht sicher, wie meine Frage formuliert wird.

ich mit Python3.6 zu programmieren bin versucht, eine asymmetrische Chiffre ähnlich wie, glaube ich, die mit RSA verschlüsselte Kommunikation verwendet

Meine Logik Verständnis hierfür ist wie folgt:

Person1 (p1) picks two prime numbers say 17 and 19 
let p = 17 and q = 19 
the product of these two numbers will be called n (n = p * q) 
n = 323 
p1 will then make public n 
P1 will then make public another prime called e, e = 7 



Person2(p2) wants to send p1 the letter H (72 in Ascii) 
To do this p2 does the following ((72^e) % n) and calls this value M 
M = 13 
p2 sends M to p1  


p1 receives M and now needs to decrypt it 
p1 can do this by calculating D where (e^D) % ((p-1)*(q-1)) = 1 
In this example i know D = 247 
With D p1 can calculate p2 message using M^D % n 
which successfully gives 72 ('H' in ASCII) 

Mit diesen Worten gelten die folgenden Regeln müssen:

GCD(e,m) = 1 

wo m = ((p-1)*(q-1))

sonst (e^D) % ((p-1)*(q-1)) = 1 existiert nicht.

Jetzt kommt durch Problem! :)

Berechnen von D, wo die Zahlen nicht so einfach zu arbeiten sind.

Jetzt sagen Sie mir bitte, wenn es eine einfachere Möglichkeit gibt, um D zu berechnen, aber das ist, wo ich bis zur Verwendung von Online-Hilfe.

(das Beispiel I im online verwendet sah unterschiedliche Werte, so dass sie sich wie folgt dar:

p = 47

q = 71

n = p * q = 3337

(p-1) * (q-1) = 3220

e = 79

Jetzt müssen wir finden D. Wir wissen (e^D)% ((p-1) * (q-1)) = 1

Daher D = 79^-1% 3220

Die Gleichung 79 umgeschrieben wird * d = 1 mod 3220

Dies ist, wo ich verwirrt

regelmäßigen euklidischen Algorithmus GCD Verwendung (79,3220) gleich 1 sein muß oder es nicht tatsächlich kann eine Lösung sein (sind meine Beschreibungen hier richtig?)

3220 = 40*79 + 60 (79 goes into 3220 40 times with remainder 60) 
    79 = 1*60 + 19 (The last remainder 60 goes into 79 once with r 19) 
    60 = 3*19 + 3 (The last remainder 19 goes into 60 three times with r 3) 
    19 = 6*3 + 1 (The last remainder 3 goes into 19 6 times with r 1) 
    3 = 3*1 + 0 (The last remainder 1 goes into 3 three times with r 0) 

Der letzte Rest ungleich Null ist der gcd. So gcd (79,3220) = 1 (wie es sein sollte)

Der letzte Schritt hier weiß ich nicht, was auf der Erde geschieht

ich die gcd schreiben mir gesagt (eins) als lineare Kombination von 19 und 3220, indem man den Baum wieder aufbaut ...

1 = 19-6*3 
    = 19-6*(60-3*19) 
    = 19*19 - 6*60 
    = 19*(79-60) - 6*60 
    = 19*79 - 25*60 
    = 19*79 - 25*(3220-40*79) 
    = 1019*79 - 25*3220 

Danach ich mit 1019*79 - 25*3220 = 1 bin übrig geblieben, und wenn ich 3220 mod auf beiden Seiten erhalten i 1019 * 79 = 1 mod 3220

(der Begriff, der 3220 enthält weggeht, weil 3220 = 0 mod 3220) .

also d = 1019.

Answer 1

So ist das Problem, die folgende Sequenz entspannen:

3220 = 40*79 + 60 
    79 = 1*60 + 19 
    60 = 3*19 + 3 
    19 = 6*3 + 1 
    3 = 3*1 + 0 

Zuerst vergessen, die letzte Reihe und Start von dem einen mit dem letzten Nicht-Null-Rest.

dann Schritt für Schritt weitergeht:

1 = 19 - 6*3            ; now expand 3 
    = 19 - 6*(60 - 3*19)  = 19 - 6*60 + 18*19 
    = 19*19 - 6*60           ; now expand 19 
    = 19*(79 - 1*60) - 6*60  = 19*79 - 19*60 - 6*60 
    = 19*79 - 25*60           ; now expand 60 
    = 19*79 - 25*(3220 - 40*79) = 19*79 - 25*3220 + 1000*79 
    = 1019*79 - 25*3220          ; done 

Hinweis, dass die Idee, bei jedem Schritt zu erweitern ist, der vorherige Rest. Wenn Sie beispielsweise den Rest 19 mit 79 - 1*60 expandieren, transformieren Sie 19*19 - 6*60 in 19*(79 - 1*60) - 6*60. Damit können Sie sich um 79 und 60 gruppieren und weitermachen.