RSA Verfahren

Zitat von floorball92

Würde das ganze ja mal durchrechnen, aber bin derzeit nur PHP mächtig, das irgendwie mit dem Modulo Operator Probleme macht bei 2 11-Stelligen Zahlen (ich weiß, zu kurz für die Praxis, aber es geht ja ums Prinzip).

Wer hindert dich daran es händisch durchzurechnen? :dd:

Vom Prinzip her ists schon richtig. Da ich zufälligerweise gestern selbst dran rumgerechnet habe, hier mal ein sehr vereinfachtes händisch-durchgerechnetes Beispiel wie es funktioniert - PersonA möchte PersonB eine verschlüsselte Nachricht senden:

Schritt 1 (bei PersonB):
Zwei voneinander verschiedene Primzahlen [tex='p'][/tex]

und [tex='q'][/tex]

werden gewählt (in der Praxis natürlich wesentlich größer). Anschließend wird [tex='n=p\cdot q'][/tex]

und [tex='m = (p-1)(q-1)'][/tex]

berechnet und eine beliebige zu [tex='m'][/tex]

teilerfremde Zahl [tex='a'][/tex]

gewählt.

Beispiel:
Wähle [tex='p=3'][/tex]

und [tex='q=11 \Rightarrow n=33,m=20'][/tex]

.
Als [tex='a'][/tex]

wählen wir eine teilerfremde Zahl zu [tex='m'][/tex]

, z.B. [tex='a=57'][/tex]

.

Schritt 2:
PersonB übermittelt nun das Zahlenpaar [tex='(n,a)'][/tex]

als öffentlichen Schlüssel an PersonA.

Schritt 3 (bei PersonA):
Die Nachricht ist in unserem Fall vereinfacht angenommen eine Zahl, die kleiner als [tex='n'][/tex]

ist (wenn ein Text übermittelt wird, muss wie du richtig sagst zuerst in eine Zahl umgewandelt werden - ist diese Zahl größer als [tex='n'][/tex]

, so wird sie in einzelne Ziffernblöcke aufgeteilt. Die Ziffernblöcke werden dann separat verschlüsselt und nachdem das Gesamtpaket übermittelt wurde wieder blockweise beim Empfänger entschlüsselt. - aber das weißt du ja eh schon alles :))

Wir wählen also z.B. als Nachricht [tex='x=28'][/tex]

.

Verschlüsselung: [tex='y = x^a mod n = 19'][/tex]

Schritt 4:
PersonA sendet die verschlüsselte Nachricht [tex='y=19'][/tex]

an PersonB.

Schritt 5 (bei PersonB):
Nun erfolgt die Berechnung [tex='b=a^{-1} mod m = 13'][/tex]

. Nun, wie kommt man auf diese Zahl 13? Wie du richtig sagst ist eine Möglichkeit der "erweiterte euklidische Algorithmus".
Um das zu veranschaulichen, hier mal der euklidische Algorithmus:

Berechnet wird der ggt von 57 und 20 (muss ja 1 ergeben, da wir ja 57 teilerfremd zu 20 gewählt haben - weiß man zwar auch im Kopf aber man benötigt das Verfahren für das erweiterte euklidische Verfahren):

[tex='57 = 2\cdot 20 + 17'][/tex]

[tex='20 = 1\cdot 17 + 3'][/tex]

[tex='17 = 5\cdot 3 + 2'][/tex]

[tex='3 = 1\cdot 2 + 1'][/tex]

[tex='2 = 2\cdot 1 + 0'][/tex]

Die Zahl 1 in der letzten Zeile ist also richtigerweise ggt(57,20) = 1.

Nun zum erweiterten euklidischen Algorithmus, man fängt von unten mit der Ersetzung an (wichtig dabei, nicht alles ausrechnen bzw. einmultiplizieren):

[tex='1 = 3 - 1\cdot 2'][/tex]

[tex='1 = 3 - 1\cdot(17-5\cdot 3) = 6\cdot 3 - 1\cdot 17'][/tex]

[tex='1 = 6 \cdot (20 - 1\cdot 17) - 1\cdot 17 = 6\cdot 20 - 7\cdot 17'][/tex]

[tex='1 = 6\cdot 20 - 7\cdot(57-2\cdot 20)=20\cdot 20 - 7\cdot 57'][/tex]

[tex='\Rightarrow'][/tex]

[tex='-7\cdot 57 mod 20 = 1'][/tex]

(im nächsten Schritt wird auf der linken Seite [tex='20\cdot 57'][/tex]

dazuaddiert, da die Inverse positiv und < 20 sein soll - Rest bleibt gleich, das es bei mod ja egal ist)

[tex='13\cdot 57 mod 20 = 1'][/tex]

[tex='57^{-1} mod 20 = 13 = b'][/tex]

Voila! Wir haben die 13 berechnet.

Entschlüsselung: [tex='x = y^b mod n = 28'][/tex]

:applaus:

Vielleicht kannst du es ja für irgendwas gebrauchen, wie das programmiertechnisch umzusetzen ist weiß ich leider auch noch nicht so genau.

[quote='floorball92','http://www.informatik-forum.at/testing/forum/…2112#post572112']
Danach kommt e, eine relativ prime Zahl zu (p-1)(q-1), also (p-1)(q-1) -- müsste gehen.
[\QUOTE]

Ich glaub 1<e<(p-1)(q-1) muß gelten, d.h. e=(p-1)(q-1) darf nicht sein...

[quote='floorball92','http://www.informatik-forum.at/testing/forum/…2112#post572112']
Nun kommt mein erstes hartes Problem: d wird ja mit dem erweiterten euklidischen Algorithmus errechnet, mit dem Probierverfahren durch umstellen der Gleichung kann ich das, aber eine Funktion dazu krieg ich nicht auf die Reihe. (*ganz-vorsichtig-fragend* wird das mit einer rekursiven Funktion gelöst)[\QUOTE]

wikipedia hat da ein ganz einfaches bsp. dazu:
http://de.wikipedia.org/wiki/RSA-Kryptosystem

im prinzip is ja

e * d + k * phi(n) = ggt(e, phi(n)) = 1

phi(n)=(p-1)(q-1) hast du ja schon ausgerechnet, und e hast du auch schon bestimmt.
Wie du richtig gesagt hast kannst du jetzt mit dem erweiterten euklidschen algorithmus d
bestimmen. ich verwend jetzt mal die zahlen von dem wikipedia example:

e=23 und phi(n) = 120

23 * d + k * 120 = ggt (23, 120) =1

jetzt rechnest du den euklidschen algorithmus runter:

120=5*23+5
23=4*5+3
5=1*3+2
3=1*2+1

und mit dem erweiterten euklidschen algorithmus wieder in die andere richtung:

1= 3-1*2 = 3 - 1*(5-1*3) = 2*3 - 1*5 = 2*(23-4*5) -1*5 =
=2*23 -9*5 = 2*23 -9 * (120- 5*23)= 47 * 23 - 9 *120

=> d= 47 und k=-9

ich hoff das hilft ein bißchen weiter (und stimmt...)

andi

im prinzip wird beim erweiterten euklidschen algorithmus genau umgekehrt gerechnet wie beim euklidschen algorithmus... d.h. man rechnete den einmal ganz normal runter bis man bei 1 rest steht und war nimmst du wenn du ggt von 2 zahlen hast die

größere zahl = k1 * kleinere zahl + rest1 (einfach division mit rest...)

120=5*23+5 k1=5

und dann die kleinere zahl = k2* rest1 + rest2

23=4*5+3

rest 1 = k3* rest2 + rest3

5=1*3+2

usw....
3=1*2+1 // jetzt sind wir bei 1 rest angekommen (unserem ggt), d.h.
// in der nächste zeile wäre 0 rest => abbruch

und jetzt kommt der erweiterte euklidsche algorithmus:

du beginnst mit

1= vorletzer rest - k * letzter rest

1= 3-1*2 =

jetzt ersetzt du den letzten rest durch vorvorletzter rest - k * vorletzter rest

3 - 1*(5-1*3) =

hebst den vorvorletzten und den vorletzten rest raus:

2*3 - 1*5 =

und ersetzt den vorletzten rest:

2*(23-4*5) -1*5 =

usw. usf. ich denk jetzt sollts klar sein....

=2*23 -9*5 = 2*23 -9 * (120- 5*23)= 47 * 23 - 9 *120

am schluß hast du wieder e*d - k*phi(n) dort stehen...

andi