Results 1 to 6 of 6

Thread: RSA Verfahren

  1. #1

    Title
    Veteran
    Join Date
    Mar 2009
    Posts
    3
    Thanks Thanks Given 
    0
    Thanks Thanks Received 
    0
    Thanked in
    0 Posts

    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

  2. #2
    markust's Avatar
    Title
    Baccalaureus
    Join Date
    Oct 2006
    Location
    Vienna
    Posts
    525
    Thanks Thanks Given 
    74
    Thanks Thanks Received 
    45
    Thanked in
    9 Posts
    Quote Originally Posted by floorball92 View Post
    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?

    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 This image was created with the kind support of Paulchen und This image was created with the kind support of Paulchen werden gewählt (in der Praxis natürlich wesentlich größer). Anschließend wird This image was created with the kind support of Paulchen und This image was created with the kind support of Paulchen berechnet und eine beliebige zu This image was created with the kind support of Paulchen teilerfremde Zahl This image was created with the kind support of Paulchen gewählt.

    Beispiel:
    Wähle This image was created with the kind support of Paulchen und This image was created with the kind support of Paulchen.
    Als This image was created with the kind support of Paulchen wählen wir eine teilerfremde Zahl zu This image was created with the kind support of Paulchen, z.B. This image was created with the kind support of Paulchen.


    Schritt 2:

    PersonB übermittelt nun das Zahlenpaar This image was created with the kind support of Paulchen als öffentlichen Schlüssel an PersonA.


    Schritt 3 (bei PersonA):
    Die Nachricht ist in unserem Fall vereinfacht angenommen eine Zahl, die kleiner als This image was created with the kind support of Paulchen ist (wenn ein Text übermittelt wird, muss wie du richtig sagst zuerst in eine Zahl umgewandelt werden - ist diese Zahl größer als This image was created with the kind support of Paulchen, 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 This image was created with the kind support of Paulchen.

    Verschlüsselung: This image was created with the kind support of Paulchen


    Schritt 4:
    PersonA sendet die verschlüsselte Nachricht This image was created with the kind support of Paulchen an PersonB.


    Schritt 5 (bei PersonB):
    Nun erfolgt die Berechnung This image was created with the kind support of Paulchen. 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):

    This image was created with the kind support of Paulchen

    This image was created with the kind support of Paulchen

    This image was created with the kind support of Paulchen

    This image was created with the kind support of Paulchen

    This image was created with the kind support of Paulchen

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

    This image was created with the kind support of Paulchen

    This image was created with the kind support of Paulchen

    This image was created with the kind support of Paulchen

    This image was created with the kind support of Paulchen

    This image was created with the kind support of Paulchen

    This image was created with the kind support of Paulchen (im nächsten Schritt wird auf der linken Seite This image was created with the kind support of Paulchen dazuaddiert, da die Inverse positiv und < 20 sein soll - Rest bleibt gleich, das es bei mod ja egal ist)

    This image was created with the kind support of Paulchen

    This image was created with the kind support of Paulchen

    Voila! Wir haben die 13 berechnet.

    Entschlüsselung: This image was created with the kind support of Paulchen


    Vielleicht kannst du es ja für irgendwas gebrauchen, wie das programmiertechnisch umzusetzen ist weiß ich leider auch noch nicht so genau.
    Last edited by markust; 12-03-2009 at 12:27.

  3. #3
    Punkrocker's Avatar
    Title
    Master
    Join Date
    Nov 2004
    Posts
    143
    Thanks Thanks Given 
    1
    Thanks Thanks Received 
    4
    Thanked in
    2 Posts
    [QUOTE=floorball92;572112]
    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;572112]
    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!

  4. #4

    Title
    Veteran
    Join Date
    Mar 2009
    Posts
    3
    Thanks Thanks Given 
    0
    Thanks Thanks Received 
    0
    Thanked in
    0 Posts
    Hallo,

    Habe soweit alles verstanden, nur das einsetzen im erweiterten euklidischen Algorithmus verstehen ich nicht.

    Könntest du mir das noch mal etwas detailierter erklären?

    Wäre super nett!

    Gruß Sebastian

  5. #5
    Punkrocker's Avatar
    Title
    Master
    Join Date
    Nov 2004
    Posts
    143
    Thanks Thanks Given 
    1
    Thanks Thanks Received 
    4
    Thanked in
    2 Posts
    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!

  6. #6

    Title
    Veteran
    Join Date
    Mar 2009
    Posts
    3
    Thanks Thanks Given 
    0
    Thanks Thanks Received 
    0
    Thanked in
    0 Posts
    Vielen Dank,

    dass hab jetzt sogar ich verstanden ;-)

    Gruß Sebastian

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •