Der geht bei mir total daneben
Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Erweiterter Euklidischer Algorithmus
Also gut, nachdem ich in den mir von der Uni zur Verfügung gestellten Unterlagen auf die Schnelle nix brauchbares zum EEA gefunden hab, hab ich mir das hier gesucht. Da gibt’s wenigstens klare Anweisungen, wie dieser tolle Algorithmus funktionieren soll, im Idealfall.
Leider ist die Übungsaufgabe ThI-3, 34 kein Idealfall, denn dafür liefert dieser tolle Algorithmus folgendes:
ggT(17, 11) = 5 = 6
Lustig, hm? Ich hab das in ner 8-spaltigen Tabelle ausgerechnet und hatte nach 6 Zeilen die Abbruchbedingung erreicht. Ich nenn das mal nicht “Ergebnis”, das ist es nämlich nicht so ganz…
Kann jemand diesen Algorithmus nachvollziehen oder mir eine einfachere Erklärung geben? So kann ich mir das Ding nämlich nichtmal ansatzweise merken. Und das war es glaub ich, was die Klausur von mir verlangt.
Also ich finde den iterativen ganz ok:
Initialisierung:
Zahl1, 1 ,0
Zahl2. 0, 1
Dann nimmst du immer die letzten 2 Zeilen. Da steht dann z.B.
a,b,c
x,y,z
Dann machste
- Wert: a mod x
- Wert b - y * (a div x)
- Wert c - z * (a div x)
So lange, bis 0 dasteht. Die Zeile drueber ist der ggT und diese Bezout-Zahlen-Dingers.
Den find ich recht einfach zu merken.
Hm.
ggT(17, 11)
[m][color=black]17 1 0
11 0 1
6 1 -1
5 -1 2
1 2 1
0[/color][/m]
ggT = 1. Bézout = 2; 1
Also müsste jetzt 17 * 2 - 11 * 1 = 1 sein oder? Kommt aber 23 raus. (Huh? 23?)
Die Bezout-Koeffizienten sind 2 und -3 (du hast dich in der letzten Zeile verrechnet).
Aha. Dann muss in der Formel aber ein + stehen, kein –.
Dann kommt nämlich 17 * 2 + 11 * (-3) = 1 raus, und das wäre ja korrekt. OK, danke für die Hilfe! 
Jetzt geht’s mit dem chinesischen Restsatz weiter…
Hilfe, der EEA dreht schon wieder durch.
Ich versuch grade, mir eine RSA-Aufgabe auszudenken. Ich konnte die Berechnung von e auf der RSA-Folie, Seite 8, nachvollziehen, aber mit meinen eigenen Zahlen kommt Müll raus.
Primzahlen: p = 11; q = 7
n = p * q = 77
phi(n) = 10 * 6 = 60
d = 31 (ggT(d, phi(n)) = 1)
Und jetzt suche ich das multiplikative Inverse von d = 31 modulo 60.
[m]31 1 0
60 0 1
31 1 0
29 -1 1
2 2 -1
1 -29 15
0[/m]
Die -29 ist also die gesuchte Zahl… Seltsam. Kann das sein? 31[sup]-1[/sup] mod 60 = -29
-2931= -899 ≡ 1mod 60 stimmt doch! (900 = 15 60)
Was hast du denn?
Achja: die -29 solltest du evtl noch zu -29 mod 60 = 31 auflösen.
31*31 = 961 ≡ 1 mod 60.
d=e=31.
Herzlichen Glückwunsch! Das nenn ich eine sichere Wahl von d. Genau eine Einheitswurzel erwischt.
Hm nagut. Is natürlich dumm, wenn der private und der öffentliche Schlüssel gleich sind… Die negative Zahl hat mich nur sehr irritiert.
wie gesagt, die ist so ja auch nicht richtig.
Negative Zahlen mit “mod Phi” ins positive Bringen, da wir in Ringen keine negativen Exponenten brauchen können.
Jo, ich dachte nur, dass die Zahl die da steht, bereits das Ergebnis ist und es nicht erst aufbereitet werden muss.
Naja, so dumm scheint es auch nicht zu sein. Das Beispiel am Ende der RSA-Folien verwendet auch zweimal den selben Schlüssel und es funktioniert.