RSA-Verfahren, wie berechne ich d (private key)?

08.06.2011, 22:57	KönigsHaki	Auf diesen Beitrag antworten »
RSA-Verfahren, wie berechne ich d (private key)? Meine Frage: Hi zusammen, ich habe folgende Aufgabe zu lösen Der folgende hexadez. Code enthält eine mit dem RSA-Verfahren verschlüsselte Nachricht 481fab24 d4b06fd8 0ee354b 73dedbe6 öffentlicher Schlüssel ist N = 4 111 577 933, e = 63 139. folgende Faktorisierung in Primzahlen ist bekannt: $\begin{eqnarray} 41115777933 = 62731\cdot 65543 \end{eqnarray}$ Berechnen Sie den privaten Schlüssel und dekodieren Sie die Nachricht Meine Ideen: also im Grunde habe ich das RSA-Verfahren verstanden und bin auch kurz vorm Durchburch der Lösung: p = 62 731 q = 65 543 N = 4 111 577 933 e = 63 139 Es gilt: $\begin{eqnarray} e \cdot d + k\cdot phi(N) = 1 = ggT(e, phi(N)) \end{eqnarray}$ also: $\begin{eqnarray} 63 139 \cdot d + k\cdot 4 111 512 389 = 1 = ggT(63 139, 4 111 512 389) \end{eqnarray}$ und jetzt wird der erw. euklidischer Algorithmus angewendet um d und k zu berechnen aber genau da hackts bei mir. zunächst der einfach eukl. Algorithmus: $\begin{eqnarray} 4111512389 = 65118 \cdot 63189 + 26987<br /> 26987 = 2 \cdot 9165 + 8657<br /> 9165 = 1 \cdot 8657 + 508<br /> 8657 = 17 \cdot 508 + 21<br /> 508 = 24 \cdot + 4<br /> 4 = 4 \cdot 1 + 0 \end{eqnarray}$ also ist der ggT = 1 der erweiterte eukl. Algor. leitet sich ja dadurch ab: $\begin{eqnarray} 4111512389 = 65118 \cdot 63189 + 26987 \end{eqnarray}$ gdw. $\begin{eqnarray} 26987 = 1 \cdot 4111512389 - 65118 \cdot 63189 \end{eqnarray}$ (bis hier gehts noch^^) $\begin{eqnarray} 26987 = 2 \cdot 9165 + 8657 \end{eqnarray}$ gdw. $\begin{eqnarray} 9165 = 1 \cdot 63189 - 2 \cdot 26987 = ??? \end{eqnarray}$ laut Wikipedia (http://de.wikipedia.org/wiki/Erweiterter...her_Algorithmus) wird hier die Gleichung nochmals umgestellt, ich frage mich warum und nach welchen Kriterien? was ist im Endeffekt mein d, welches ich suche? Wäre nett wenn ihr mir weiterhelfen könntet
09.06.2011, 15:07	KönigsHaki	Auf diesen Beitrag antworten »
ok mittlerweile habe ich den erweiterten eukl. algorithmus verstanden der private schlüssel d = -979316030 jetzt muss ich nur noch rausbekommen wie man dekodiert^^
18.06.2011, 12:55	KönigsHaki	Auf diesen Beitrag antworten »
thx 4 help -.- close

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »