Hallo zusammen,
ich habe gedacht ich hätte das RSA Verfahren und vor allem die Schlüsselerzeugung gut verstanden und versuche gerade einfach ein paar Beispiele zu machen. Bei den ersten, mit sehr kleinen p und qs hat es noch funktioniert, aber bei unwesentlich größeren bekomme ich immer den falschen privaten Schlüssel heraus, jedenfalls, wenn ich Online-RSA-Kalkulatoren frage und mit denselben Werten füttere.
Ich schreibe mal auf, wie ich vorgegangen bin. Bis 4. stimmt alles mit dem Online-Kalkulator überein, bei 5. wende ich den erweiterten euklidischen Algorithmus an. Ich nutze dafür die tabellarische Form wie es ein Prof. Spannagel auf Youtube (RSA Beispiel Teil 1) auch zeigt.
1. Wähle 2 Primzahlen p und q:
p = 23 q = 19
2. Bilde das RSA-Modul n = p * q:
n = 437
3. Bestimme phi(n) = (p - 1)(q - 1):
phi(n) = 396
4. Wähle e mit ggT(e, phi(n)) = 1 und 1 < e < phi(n):
e = 7
5. Bestimme d mit e * d mod phi(n) = 1:
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
|
dann den erweiterten euklidischen Algorithmus...
a
| b
| q
| r
| x
| y
|
7
| 396
| 2
| 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 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!
illu
