+1 Daumen
2,8k Aufrufe

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

Avatar von

Achtung: beim erweiterten euklidischen Algorithmus in Zeile 1 habe ich mich vertippt, für q muss da natürlich 0 stehen.

1 Antwort

+1 Daumen
 
Beste Antwort

Also du machst erstmal nichts falsch. Generell geht man aber von einem d>0 aus.

Ich zeig dir mal kurz, wie ich das immer mache und wie die auf d = 283 kommen:)


Mit Euklidischen Algorithmus:

396 = 56 * 7 + 4

7 = 1 * 4 + 3

4 = 1 * 3 + 1

3 = 3 * 1 + 0

⇒ ggT(396, 7) = 1

Nun berechnen wir mithilfe des erweiterten euklidischem Algorithmus das multiplikative Inverse von 7:

Stelle alle Gleichungen nach dem Rest um:

1 = 4 - 3

= 4 - (7 - 4) //erhalte in dem ich 7 = 1*4 +3 nach 3 umstelle

= 2* 4 - 7

= 2* (396 - 56 * 7) - 7 // erhalte in dem ich 396 = 56* 7 + 4 nach 4 umstelle

= 2*396 -113 * 7


So das ist das, was du bisher alles hattest:)

Um d>0 zu bekommen, machen sie:

2*396 -113 * 7 + 396 * 7 - 7 * 396 // also + 0

= - 5 * 396 + 283 * 7


283 * 7 mod phi(n) = 1981 mod 396 = 1

Also haben wir alles richtig gemacht:)

Hoffe, dass hilft dir weiter:)

Avatar von

Um auf

= - 5 * 396 + 283 * 7

zu kommen, rechnest du 2-7 * 396 und 396 - 113 * 7, aber ich verstehe den Schritt leider nicht. Ist das ein Teil vom euklidischen Algorithmus? Nach welcher Logik, könnte ich das bei anderen Beispielen dann anwenden?

Vielen Dank für die ausführliche Antwort!

Also wie ich darauf gekommen bin, ist einfach das ich + 0 mache:

0 = 396 * 7 - 7 * 396


2*396 -113 * 7 + 0 

= 2*396 -113 * 7 + 396 * 7 - 7 * 396


Da ich ja jetzt die Zahl vor der 7, also -113 positiv machen will, addiere ich dazu 396 * 7 drauf:) Sonst würde ja d immer noch <0 sein. Wir möchten aber d>0.


Nein, es ist nicht Teil des euklidischen Algorithmus, es ist sozusagen ein Trick, um d>0 zu erreichen.


Welche anderen Beispiele meinst du?:)

Generell ist es wie gesagt nur eine Möglichkeit d>0 zu erreichen:)

Ich verstehe nicht, wie man auf 283 kommt, also woher ich weiss, dass ich -5*396 rechnen muss um auf die 283 zu kommen. Woher kommt die -5? Wenn du "2*396 -113 * 7 + 396 * 7 - 7 * 396" machst, ist die Gleichung ja weiterhin 1 aber von dem Schritt zu der 283 fehlt mir etwas.


Ich meine mit anderen Beispielen andere Werte für p,q und e. Nehme ich beispielsweise für e = 5, erhalte ich -79 für d statt wie der Online-Rechner sagt 317:


a
b
q
r
x
y
5
396
0
5
-79
1
396
57911
-79
5
1
5
0
0
1

Also ich komme auf -5 * 396 wegen:

2 * 396 - 7 *396 = -5 * 396

 -113 * 7 + 396 * 7  = 283 * 7


Jetzt klarer?


Könntest du mir vielleicht sagen, was in deinem Beispiel p, q und e sind, weil ich kenne diese Schreibweise nicht:) Dann könnt ich dir es nochmal ausführlich erklären.

Ja ich glaube das hilft, dankeschön! Probiere das jetzt noch ein paar mal durch.


Alles wie im ersten Beispiel, nur das e ist anders. Also:

p = 23  q = 19
n = 437
phi(n) = 396
e = 5

Vielen vielen Dank, das hilft mir sehr weiter!

Mit euklidischem Algorithmus:

396 = 79 * 5 + 1

5 = 5 * 1 + 0

ggT(396, 5) = 1


Wieder umstellen der Gleichungen nach dem Rest:

1 = 396 - 79 * 5


Jetzt wäre es ja d = -79, aber wir wollen ja d>0. Also wieder + 0:

396 - 79 * 5 + 0

= 396 - 79* 5 + 396* 5 - 5 * 396

= -4 * 396 + 317 * 5


Also d = 317. Nun wieder überprüfen:

317 * 5 mod 396 = 1

Also haben wir alles richtig gemacht:)

Melde dich, falls du noch Fragen hast.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community