RSA und erweiterter Euklidscher Algorithmus

Neue Frage »

04.12.2006, 22:27	timadler	Auf diesen Beitrag antworten »
RSA und erweiterter Euklidscher Algorithmus Hey zusammen, ich habe jetzt schon mehrfach bzgl. RSA gelesen, dass bei Kenntnis von $\begin{eqnarray} \varphi(n) \end{eqnarray}$ sich der private Schlüssel ganz einfach per erweitertem Euklidschen Algorithmus und der Lösung der Gleichung $\begin{eqnarray} ed \equiv_{\varphi(n)} 1 \end{eqnarray}$ bestimmen lässt. Ich weiss auch das sich das umschreiben lässt in die Grundform des EEA mit $\begin{eqnarray} ed+k\varphi(n) = 1 \end{eqnarray}$ . 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
04.12.2006, 22:31	kiste	Auf diesen Beitrag antworten »
http://de.wikipedia.org/wiki/Lemma_von_B%C3%A9zout Das könnte dir weiterhelfen
04.12.2006, 22:38	timadler	Auf diesen Beitrag antworten »
Danke, aber das war mir schon klar. Problem ist nur, dass in diesem Beispiel ja d und $\begin{eqnarray} \varphi(n) \end{eqnarray}$ teilerfremd sind, und man d aber nicht kennt. Wie soll ich da nun den erweiterten euklidschen Algorithmus drauf laufen lassen?
04.12.2006, 22:41	AD	Auf diesen Beitrag antworten »
Bin mir jetzt bei RSA nicht ganz sicher, aber du kennst doch den einen Fakor $\begin{eqnarray} e \end{eqnarray}$ , oder? Und das reicht doch zusammen mit $\begin{eqnarray} \varphi(n) \end{eqnarray}$ , um $\begin{eqnarray} d \end{eqnarray}$ zu bestimmen!
04.12.2006, 23:01	timadler	Auf diesen Beitrag antworten »
Kann man denn einfach $\begin{eqnarray} d \equiv_{\varphi(n)} 1/e \end{eqnarray}$ dividieren ohne die Kongruenz zu verlieren?
04.12.2006, 23:12	AD	Auf diesen Beitrag antworten »
Dazu ist doch gerade der EEA da, um das Inverse $\begin{eqnarray} d \end{eqnarray}$ von $\begin{eqnarray} e \end{eqnarray}$ 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.
Anzeige

05.12.2006, 00:30	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!?
05.12.2006, 07:34	AD	Auf diesen Beitrag antworten »
Das ist es doch auch, die Berechnung des ggT. Deshalb muss man bei RSA auch darauf achten, dass $\begin{eqnarray} e \end{eqnarray}$ zu $\begin{eqnarray} \varphi(n) \end{eqnarray}$ teilerfremd ist. Mit $\begin{eqnarray} e \end{eqnarray}$ und $\begin{eqnarray} \varphi(n) \end{eqnarray}$ geht man dann in den EEA hinein, und der liefert dann eben zwei ganze Zahlen $\begin{eqnarray} d,k \end{eqnarray}$ mit der Eigenschaft $\begin{eqnarray} d\cdot e + k\cdot \varphi(n) = \operatorname{ggT}(e,\varphi(n))\qquad () \end{eqnarray}$ Rechts steht jetzt natürlich eine 1, denn dafür hat man ja bei der Auswahl von e gesorgt. Und jetzt nur noch () modulo $\begin{eqnarray} \varphi(n) \end{eqnarray}$ betrachtet.
30.05.2007, 22:20	Dax	Auf diesen Beitrag antworten »
Kann es sein, dass man nach d umstellen muss und k von 1 bis $\begin{eqnarray} \infty \end{eqnarray}$ wandern lassen muss, bis man für d ein ganzzahliges Ergebniss bekommt? Also $\begin{eqnarray} d = k phi(n) + 1 / e \end{eqnarray*}$ 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.
30.05.2007, 23:21	therisen	Auf diesen Beitrag antworten »
Arthur hat doch schon geschrieben, was zu tun ist. Hat man erst einmal die Gleichung $\begin{eqnarray} d\cdot e + k\cdot\varphi(n) = 1 \end{eqnarray}$ per EEA gefunden, dann folgt doch $\begin{eqnarray} de\equiv 1 \pmod {\varphi(n)} \end{eqnarray}$ d.h. $\begin{eqnarray} d\equiv\frac1e \pmod {\varphi(n)} \end{eqnarray}$ (Vorsicht, das ist nur eine formale Schreibweise) Gruß, therisen
30.05.2007, 23:33	Dax	Auf diesen Beitrag antworten »
omfg ich hatte den tab die ganze Zeit auf und hab nich aktualisiert. sry
30.05.2007, 23:36	therisen	Auf diesen Beitrag antworten »
Du hattest den Tab fast ein halbes Jahr lang auf? Oder wie ist dein Post zu verstehen?

Neue Frage »

Antworten »

RSA und erweiterter Euklidscher Algorithmus

Verwandte Themen