RSA Rechnen Problem

thefiloe

Ich habe versucht den RSA Algorithmus nachzuvollziehen. Doch bei Wikipedia scheitere ich immer an einer Bechrechnung. Und zwar Hier: http://de.wikipedia.org/wiki/RSA-Kryptosystem#Schl.C3.BCsselerzeugung

Hier noch ein Screenshot von dem Problem.
http://s7.directupload.net/images/110720/o4vagyki.png

Ich habe keine Ahnung wie das Funktionieren soll auf die Zahl 1373 bei d zu kommen. Könnte mir da vll. jemand weiterhelfen.

Und noch eine Frage wird eh einfach so mir nix dir nix zufällig gewählt?

Danke schon im Voraus
Wäre echt sehr dankbar wenn mir jemand helfen könnte.

SG1

Du berechnest mit dem erw. euklidischen Algorithmus ggt(e, phi(N)). e ist teilerfremd zu phi(N), also muss da immer 1 rauskommen. Der erweiterte Algorithmus liefert uns aber auch noch 2 Zahlen s und t, so dass

1 = ggt(e, phi(N)) = s*e + t*phi(N)

Da wir modulo phi(N) rechnen, ist der hintere Summand 0:

1 = s*e

s ist also unser gesuchtes Inverses.

Ne Frage vorweg, bevor ich das ein bisschen weiter erklaere. Hast du das spezielle Wissen in Zahlentheorie, das du für RSA brauchst?
Wenn nein, dann willst du vermutlich selbst nur herausfinden wie was etwas erstellt wird, aber nicht unbedingt die Theorie, also das Was dahinter.

Jenachdem werde ich dir naemlich dann antworten

thefiloe

Ich sags mal so. Ganz zu tiefgreifend sollte es nicht gehen aber da mir das aufrufen in einer dll, Header usw. zu einfach ist wollte ich selber versuchen den Algorithmus nachzufollziehen und anschließend zu proggen. Auch als Übung. Jedoch weiß ich nicht wie man das rechnet als den erweiterte Algorithmus.

Also wäre ich sehr sehr sehr dankbar wenn mir jemand einen Lösungsweg zeigen könnte wie ich das oben genannte Beispiel berechnen kann. Also nur den erweiterte Algorithmus und nicht den ganzen RSA-Algo.

SG1

Okay, rechnen wir das mal durch. Erstmal den normalen euklidischen Algorithmus:

262548 = 152 * 1721 + 956
  1721 =   1 *  956 + 765
   956 =   1 *  765 + 191
   765 =   4 *  191 +   1

Es kommt wie erwartet 1 als ggt raus, das ist schonmal gut. Die 4 Zeilen werden jetzt alle etwas umgestellt:

956 = 262548 - 152 * 1721
765 =   1721 - 956
191 =    956 - 765
  1 =    765 - 4 * 191

Und jetzt immer abwechselnd eine der Zeilen einsetzen und Distributivgesetz anwenden. Wir fangen damit an, die vorletzte in die letzte Zeile einzusetzen:

1 = 765 - 4 * 191
  = 765 - 4 * (956 - 765)
  = -4 * 956 + 5 * 765
  = -4 * 956 + 5 * (1721 - 956)
  = 5 * 1721 -9 * 956
  = 5 * 1721 -9 * (262548 - 152 * 1721)
  = -9 * 262548 + 1373 * 1721

Whow, gleich im ersten Anlauf ohne verrechnen - da hast Du Deine 1373

Ok, dann fangen wir mal an.

Um den erweiterte euklidische Algorithmus zu verstehen, musst du zuerst den einfachen euklidische Algorithmus verstehen.
Dieser gibt dir den größten gemeinsamen Teiler zwischen zwei Zahlen A und B, auch geschrieben als ggt(A,B).

Ein paar Beispiele:
ggT(10,5) = 5, denn es gibt keine größere Zahl außer die 5, die beide Zahlen teilen kann.
ggT(18,24) = 6
ggT(3,5) = 1

Was bei RSA interessant ist, ist ggT(A,B) = 1. Dies passiert immer, wenn A oder B Primzahlen sind. Denn die Primzahlen erfüllen die Eigenschaft, das sie keine Teile außer sich selbst und die Zahl 1 haben. Wieso das bei RSA und der Verschlüsselung interessant ist, wollen wir hier nicht weiter erklaeren

Jetzt zum euklidischen Algorithmus, nehmen wir das Beispiel von http://de.wikipedia.org/wiki/Erweiterter_euklidischer_Algorithmus:
Sagen wir, du suchst ggT(99,78). Anders gesucht, du suchst die größte Zahl, mit der du beide Zahlen glatt Teilen kannst. Dann gehst du folgendermaßen vor:

Wie oft passt die kleinere Zahl (78) in die Größere (99)?
In Programmiersprache waere dies: (int)99/78
Das Ergebnis ist 1 und 1 * 78 ist 78, also bleiben 21 übrig. Also schreibst du
99 = 1 * 78 + 21 (Achtung! Behalte immer diese Reihenfolge: GroßeZahl = C*KleineZahl + Rest
Dann ist die kleine Zahl nun der Rest (21) und die großeZahl die kleineZahl von eben (78). Dann machst du das selbe nochmal:
Wie oft passt die kleinere Zahl (21) in die Größere (78)?
In Programmiersprache waere dies: (int)78/21
Das Ergebnis ist 3 und 3 * 21 ist 63, also bleiben 15 übrig. Also schreibst du
78 = 3 * 21 + 15
Das machst du nun solange weiter bis der Rest 0 ist. Am Ende sieht das dann komplett so aus:
99 = 1 * 78 + 21
78 = 3 * 21 + 15
21 = 1 * 15 + 6
15 = 2 * 5 + 3
6 = 2 * 3 + 0

In der letzten Zeile war kleineZahl = 3. Da dort auch die 0 auftaucht, ist der größte gemeinsame Teile von 99 und 78 = 3. Das wars.

Wenn du das verstanden hast und diesen Algorithmus in eine Funktion packen kannst, geht es weiter mit dem erweiterten euklidischen Algorithmus

thefiloe

Okay danke vielmals. Ich werd mir das nochmal ganz genau durchlesen und dann haut das sicher hin. Also danke nochmal euch beiden.

snOOfy

Ansonsten siehe auch:

http://me-lrt.de/groster-gemeinsamer-teiler-euklidischer-algorithmus

snOOfy schrieb:

http://me-lrt.de

I like