Erweiterter Euklidischer Algorithmus

28.07.2007, 19:46	chriss_2oo4	Auf diesen Beitrag antworten »
Erweiterter Euklidischer Algorithmus Hi, ich hab mir mal die Verschlüsselung durch das RSA-Verfahren angeschaut, bin eigentlich auch ganz gut damit zurecht gekommen. Nur mit der Berechnung der Inversen Elemente mit dem erweiterten Euklidischen Algorithmus komm ich nicht ganz zurecht. Wie mit mit dem Euklidischen Algorithmus den ggT errechnet hab ich schon verstanden, nur mit folgender Vorgehensweise hab ich noch ein kleines Problem: Man wählt zwei möglichst große Primzahlen p und q Man ermittelt das RSA-Modul m = p * q Man errechnet mit der eulerischen Funktion phi(n)=(p-1)*(q-1) Man wählt eine zufällige Zahl e die teilerfremd zu phi(n) ist und 1 < e < phi(n) Daraus ergibt sich der öffentliche Schlüssel: e und m, soweit kein Problem... Nur versteh ich die Berechnung folgender Formel nicht ganz (mit hilfe des erweiterten euklidischen Algorithmus) http://upload.wikimedia.org/math/8/7/1/8719af49b5f9bf03809cd0104ac6933c.png Dabei ergibt d den privaten Schlüssel und k wird nicht mehr benögitg Vielleicht kann mir jemand den Algorithmus erklären? lg chriss
28.07.2007, 20:12	chriss_2oo4	Auf diesen Beitrag antworten »
Sorry hab nen Varablennamen vertrauscht m in der Angabe ist N aus der Formel Mfg
28.07.2007, 20:39	therisen	Auf diesen Beitrag antworten »
Hallo, nach Voraussetzung gilt $\begin{eqnarray} \mathrm{ggT}(e,\varphi(m))=1 \end{eqnarray}$ . Das ist äquivalent zur Existenz von Zahlen $\begin{eqnarray} d,k\in\mathbb Z \end{eqnarray}$ derart, dass $\begin{eqnarray} ed+k\varphi(m)=1 \end{eqnarray}$ erfüllt ist. Die Berechnung dieser Zahlen ermöglicht der erweiterte euklidische Algorithmus. Wie das geht, ist hier beschrieben. Gruß, therisen
29.07.2007, 10:21	__Alex__	Auf diesen Beitrag antworten »
Hi, sagen wir mal e sei gleich 13, dann gilt ggT(13, 24)=1. Um d, den Entschlüsselungsexponenten zu berechnen, benötigen wir das modulare Inverse zu e mod 24. Dies erhalten wir durch Anwendung des erweiterten Euklidischen Algorithmus. Die theoretische Grundlage hierzu ist das sog. Lemma von Bézout oder etwas allg. den Hauptsatz über den ggT. Für unser Bsp. würde das wie folgt aussehen: 24 = 113 + 11, ggT(24, 13)=ggT(13,11) 13 = 111 + 2, ggT(13,11)=ggT(11,2) 11 = 52 + 1, ggT(11,2)=ggT(2,1)= 1 2 = 21 + 0 Bei Rest = 0 bricht der übliche Euklidische Algorithmus ab. Der erweiterte Eukl. Algorithmus stellt obige Gleichungen nun zunächst nach den Resten um: 1 = 13 - 62 2 = 13 - 111 11 = 24 - 113 Durch (Rückwärts-)Substitution erhält man dann 1 = 13 - 6[13 -111] = -513 +611 = -513+6[24-113] = -1113 +624 Liest man diese Gleichung im Restklassen Ring Z/24Z (also mod 24 gelesen), so ergibt sich 1 = -1113 = 1313, d.h. 13 ist zu sich selbst invers und damit auch d=13. Du kannst auch auf mathematik-netz.de dazu etwas finden. LG Alex
29.07.2007, 11:49	chriss_2oo4	Auf diesen Beitrag antworten »
Hi, erstmal Danke für eure Antworten! Ich hab noch eine Frage an Alex: Das mit dem euklidischen Algorithmus hab ich schon verstanden, nur bei der Restbildung 1 = 13 - 6 * 2 versteh ich nicht, wie man darauf kommt. 2 = 13 - 1 * 11 -> 13 = 1 * 11 + 2 11 = 24 - 1 * 13 -> 24 = 113 + 11 Aber bei der o. g. Umstellung komm ich nicht klar: 1 = 13 - 62 -> 11 = 5 * 2 + 1 Lg Chriss
29.07.2007, 14:15	__Alex__	Auf diesen Beitrag antworten »
Hi, stelle die Gleichung aus dem Euklidischen Algorithmus nach den Resten um: 1 = 11-52, 2 = 13-111, 11 = 24-113. Dann setze nacheinander ein, also 1 = 11 -5[13-1*11] = ... und fasse gleich Faktoren zusammen. LG Alex
Anzeige

29.07.2007, 15:30	chriss_2oo4	Auf diesen Beitrag antworten »
Hi, ok, ich hab noch ein kleines Problem bei folgender Rechnung: p=5 q=11 e=7 n=511 = 55 phi(n)=(5-1)(11-1)=40; ggT(40,7): 40 = 5 * 7 + 5 7 = 1 * 5 + 2 5 = 2 * 2 +1 <= ggT 2 = 2 * 1 + 0 Rückwärtzs: 1 = 5 - 2 * 2 2 = 7 - 1 * 5 5 = 40 - 5 * 7 einsezten 1 = 5 - 2 * 2 1 = 5 - 2 * [7 - 1 * 5] ... Wie gehts hier weiter? Lg chriss
29.07.2007, 16:28	__Alex__	Auf diesen Beitrag antworten »
Guck Dir doch bitte mal den Link-Tipp aus meinem vorletzten Post an, dort findest Du komplett durchgerechnete Bsp. So gehts dann weiter (ohne geprüft zu haben was vorher war): 1 = 5 - 2 * 2 1 = 5 - 2 * [7 - 1 * 5] 1 = 5 -27 +25 1 = 35 -27 .. LG Alex

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »