RSA und erweiterter Euklidscher Algorithmus

Neue Frage »

timadler Auf diesen Beitrag antworten »
RSA und erweiterter Euklidscher Algorithmus
Hey zusammen,

ich habe jetzt schon mehrfach bzgl. RSA gelesen, dass bei Kenntnis von sich der private Schlüssel ganz einfach per erweitertem Euklidschen Algorithmus und der Lösung der Gleichung bestimmen lässt. Ich weiss auch das sich das umschreiben lässt in die Grundform des EEA mit .

Leider ist mir aber schleierhaft, wie ich das mit Euklidschem Algorithmus lösen soll. Muss man dazu nicht d kenne bzw. zumindest k um entsprechend aufzulösen?

Wäre für eine Erklärung dankbar.

Gruß, Tim
kiste Auf diesen Beitrag antworten »

http://de.wikipedia.org/wiki/Lemma_von_B%C3%A9zout
Das könnte dir weiterhelfen
 
 
timadler Auf diesen Beitrag antworten »

Danke, aber das war mir schon klar. Problem ist nur, dass in diesem Beispiel ja d und teilerfremd sind, und man d aber nicht kennt. Wie soll ich da nun den erweiterten euklidschen Algorithmus drauf laufen lassen?
AD Auf diesen Beitrag antworten »

Bin mir jetzt bei RSA nicht ganz sicher, aber du kennst doch den einen Fakor , oder? Und das reicht doch zusammen mit , um zu bestimmen!
timadler Auf diesen Beitrag antworten »

Kann man denn einfach dividieren ohne die Kongruenz zu verlieren?
AD Auf diesen Beitrag antworten »

Dazu ist doch gerade der EEA da, um das Inverse von zu berechnen...

Irgendwie ist das die falsche Reihenfolge: Man sollte schon erst mal die Grundlagen der Modulo-Rechnung studieren, bevor man sich auf RSA stürzt. Hab ich schon oft bei genau diesem Thema beobachtet, dass solchen Grundlagen nicht ausreichend Beachtung geschenkt wird.
timadler Auf diesen Beitrag antworten »

Tja, und wenn man an der Uni ist, da hat man teilweise überhaupt keine Möglichkeit sich die Grundlagen erst ordentlich anzueignen. Da ist der Prof. schneller drüber weg, als Du lernen kannst. Und schwupps muss man schon Aufgabe dazu lösen.

Kannst Du noch erklären, warum der EEA genau das Inverse berechnet von d zu e? Mir war das bisher ja nur als Berechnung einer ggT bekannt!?
AD Auf diesen Beitrag antworten »

Das ist es doch auch, die Berechnung des ggT. Deshalb muss man bei RSA auch darauf achten, dass zu teilerfremd ist. Mit und geht man dann in den EEA hinein, und der liefert dann eben zwei ganze Zahlen mit der Eigenschaft



Rechts steht jetzt natürlich eine 1, denn dafür hat man ja bei der Auswahl von e gesorgt. Und jetzt nur noch (*) modulo betrachtet.
Dax Auf diesen Beitrag antworten »

Kann es sein, dass man nach d umstellen muss und k von 1 bis wandern lassen muss, bis man für d ein ganzzahliges Ergebniss bekommt?

Also

Habe das mal mit dem Beispiel von der Seite hier probiert:
http://www.mathematik.de/mde/information...ik/rsa/rsa.html
Und noch mit nem anderen Beispiel aus meinen Unterlagen und da hat es auch funktioniert.
therisen Auf diesen Beitrag antworten »

Arthur hat doch schon geschrieben, was zu tun ist.

Hat man erst einmal die Gleichung

per EEA gefunden, dann folgt doch



d.h. (Vorsicht, das ist nur eine formale Schreibweise)



Gruß, therisen
Dax Auf diesen Beitrag antworten »

omfg ich hatte den tab die ganze Zeit auf und hab nich aktualisiert. sry
therisen Auf diesen Beitrag antworten »

Du hattest den Tab fast ein halbes Jahr lang auf? Big Laugh Oder wie ist dein Post zu verstehen?
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »