Hallo zusammen,
ich stecke in der Vorbereitung für eine Kryptologie-Klausur und bin mehrmals das RSA-Verfahren durchgegangen, bekomme aber für d immer andere Werte heraus als Online-Rechner, die ich mit denselben Werten für p, q und e füttere.
Den erweiterten euklidischen Algorithmus mache ich in tabellarischer Form wie von Prof. Spannagel in seinen Videos erklärt. Vielleicht sieht ja jemand, was für einen Fehler ich dabei mache. Bei kleineren p und q komme ich auf das richtige Ergebnis für d (vielleicht Zufall?) aber in u.a. diesem Beispiel haut es einfach nicht hin:
p = 23, q = 1
n = 437
phi(n) = 396
e = 7
Bestimme d mit e * d mod phi(n) = 1 mit dem erweiterten euklidischen Algorithmus.
Euklidischer Algorithmus (a:b = q rest r):
a
| b
| q
| r
|
7
| 396
| 0
| 396
|
396
| 7
| 56
| 4
|
7
| 4
| 1
| 3
|
4
| 3
| 1
| 1
|
3
| 1
| 3
| 0
|
Erweiterter euklidischer Algorithmus
a
| b
| q
| r
| x
| y
|
7
| 396
| 0
| 396
| -113
| 2
|
396
| 7
| 56
| 4
| 2
| -113
|
7
| 4
| 1
| 3
| -1
| 2
|
4
| 3
| 1
| 1
| 1
| -1
|
3
| 1
| 3
| 0
| 0
| 1
|
dabei gehe ich nach der youtube-Anleitung so vor:
in die untere Zeile schreibe ich x*a + y*b = 1
dann immer in jeder Zeile
x(neu) = y(alt) und y(neu) = x(alt) - q(neu) * y(alt) oder auch mit index geschrieben neu = i, alt = i-1
Mein d wäre also 113, der Online-Calculator sagt aber d müsste 283 sein.
Als Probe rechne ich e * x + phi(n) * y = 1 und das kommt sogar hin: 7 * -113 + 396 * 2 = 1
Ich hoffe mir kann jemand sagen, was ich falsch mache. Besten Dank vorab!
