RSA Verfahren

  • Hallo!


    Bin hier mal dem Forum bei gestoßen, weil ich für ein Informatikreferat Hilfe brauche.


    Das Thema ist Kryptologie. Also habe ich mir gedacht, erstmal so ein bissi Hintergrundwissen zu erzählen und dann ein simples Verfahren per Transposition und dann noch RSA zu zeigen und vorzurechnen.


    Nun habe ich mir das RSA Verfahren mal angesehen und oha, dass ist ordentlich schwer. Jedoch denke ich, das halbwegs verstanden zu haben, wollte mich aber jetzt doch noch mal bei den Profis vergewissern:


    zwei Zahlen p und q werden gewählt, möglichst große Primzahlen, so 128bit aufwärts.


    Dann wird n mit p*q errechnet.


    Danach kommt e, eine relativ prime Zahl zu (p-1)(q-1), also (p-1)(q-1) -- müsste gehen.


    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)


    Nun nehme ich meinen String und forme ihn in einige Zahlenblöcke um, sodass die Zahl des Blockes unter n bleibt.


    Diese Blöcke bekommen jeweils den Exponenten e und wird mit dem Modulo Operator mit n zu einer neuen schiefrierten zahl verrechnet.


    Diese Zahl mit dem Exponenten d und wieder Module n entschlüsselt die Nachricht wieder.


    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).


    Deshalb würde ich es gerne einfach mal von euch bestätigt oder korrigiert haben.


    Gruß Sebastian

  • 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

    und

    werden gewählt (in der Praxis natürlich wesentlich größer). Anschließend wird

    und

    berechnet und eine beliebige zu

    teilerfremde Zahl

    gewählt.


    Beispiel:
    Wähle

    und

    .
    Als

    wählen wir eine teilerfremde Zahl zu

    , z.B.

    .


    Schritt 2:
    PersonB übermittelt nun das Zahlenpaar

    als öffentlichen Schlüssel an PersonA.



    Schritt 3 (bei PersonA):
    Die Nachricht ist in unserem Fall vereinfacht angenommen eine Zahl, die kleiner als

    ist (wenn ein Text übermittelt wird, muss wie du richtig sagst zuerst in eine Zahl umgewandelt werden - ist diese Zahl größer als

    , 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

    .


    Verschlüsselung:



    Schritt 4:
    PersonA sendet die verschlüsselte Nachricht

    an PersonB.



    Schritt 5 (bei PersonB):
    Nun erfolgt die Berechnung

    . 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):







    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):







    (im nächsten Schritt wird auf der linken Seite

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




    Voila! Wir haben die 13 berechnet.


    Entschlüsselung:

    :applaus:



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

  • [quote='floorball92','http://www.informatik-forum.at/testing/forum/index.php?thread/&postID=572112#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/index.php?thread/&postID=572112#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

    Und eine Stimme aus dem Chaos sprach zu mir:
    lächle und sei froh, es könnte schlimmer kommen.
    Und ich lächelte und war froh, und es kam schlimmer!

  • 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

    Und eine Stimme aus dem Chaos sprach zu mir:
    lächle und sei froh, es könnte schlimmer kommen.
    Und ich lächelte und war froh, und es kam schlimmer!