Asymmetrische Verschlüsselung - Berechnung der Keys
 

Hallo zusammen,

ich habe die Aufgabe einen Vortrag über asymmetrische Verschlüsselung zu halten, und brech' mir einen bei der Berechnung des private-keys ab. Stundenlanges googlen verwirrt mich nur noch mehr. Ich hoffe, jemand von euch hat einen heißen Tipp für mich...

Berechnung von N:
N = p * q
N = 5 * 17 = 85

Berechnung von E:
z = (p-1) * (q-1)
z = (5-1) * (17-1) = 64
Teiler (z) = 1, 2, 4, 8, 16, 32, 64
E = 5 (teilerfremd)

Berechnung von D:
E * D = 1 (mod z)
5 * D = 1 (mod 64)

Bei der Berechnung von D hört es bei mir auf... :(

Schau dir für d mal den erweiterten euklidschen Algorithmus an.

So ich habs mal rausgesucht und mir folgendes notiert:
RSA
Privater Schlüssel: d
Öffentlicher Schlüssel N, e
N = P*q // p und q Primzahlen welche geheim sind
e teilerfremd zu (p-1) und (q-1)
C = M^e mod(N) // verschlüsseln
M = C^d mod(N) oder auch E = M^d mod(N) // entschlüsseln

Beispiel 1:
p = 11, q = 17 // werden selber gewählt
N = p*q = 11*17 = 187
gewähltes e = 7
Berechne d = e^-1 mod(p-1)(q-1)
d = 23 oder d = 183 // 160+23
M = 42
C = 42^7 mod(187) // 0-186
C = 15
E = 15^23 mod(187) = 42

Mod berechnen:
23 mod 5 = 3
23 / 5 = 4,6
23-5*4 = 3 oder auch 0,6 * 5 = 3

Beispiel 2
Verschlüsseln

M = 8, N = 55 und e = 3
C = 8^3 mod(55)
C = 512 mod (55)
Nebenrechnung
[512 mod 55 = 17]
[512 / 55 = 9,30]
512 - (55*9) = 17]
C = 17

Entschlüsseln
C = 8, N = 55 und d = 3
(Nebenrechnung für M wegelassen, siehe oben wie das geht)
M = 8^3 mod(55)
M = 512 mod (55)
M = 17

Hoffe das hilft dir ein wenig weiter

23 ist richtig für d, da fehlt aber trotzdem die Berechnung von d ;)

d = e^-1 mod(p-1)(q-1) ist alles vorhanden ;) man muss nur noch einsetzen, was ich oben nicht direkt getan habe.
hab auch ein paar mal editiert, kann also sein, dass es zudem zeitpunkt noch nicht drin war.