rsa und modula

14.01.2010, 20:56	wrock	Auf diesen Beitrag antworten »
rsa und modula Hi, Habe als Spezialgebiet RSA genommen, oder will nehmen. Steck mom. beim d ausrechenen fest(also e^(-1)mod m Ganze vorgehensweise: p=11 q=13 pq=143 (p-1)(q-1)=120 e=(nichtteiler 120)= 23 ggT(23,120) also 23^(-1) mod 120 oder? Ergbniss sollte sein: d=47 und k=-9 Komm aber überhaupt nicht dahin.... könnte mir jemand die vorgehensweise erklären? lg lukas
14.01.2010, 21:48	David_pb	Auf diesen Beitrag antworten »
Es gilt $\begin{eqnarray} e\cdot d + k \cdot \varphi(N) = 1 \end{eqnarray}$ . Der Faktor e und $\begin{eqnarray} \varphi(N) \end{eqnarray}$ sind ja bekannt. Um d und k zu bekommen kannst du den erweiterten euklidischen Algorithmus verwenden.
14.01.2010, 21:54	wrock	Auf diesen Beitrag antworten »
genau das ist der teil den ich nicht verstehe, zumindest die erklärung auf wiki... habs mal mit 23 und 120 versucht 120=523+5 23=45+3 5=13+2 3=12+1 2=11+1 1=11+0 ???
14.01.2010, 22:18	David_pb	Auf diesen Beitrag antworten »
Ja, das ist der euklidische Algorithmus. Da du aber e so gewählt hast, das es Teilerfrei zu 120 ist, weißt du ja bereits das ggT(e, 120) = 1 sein muss. Was du wissen willst sind die Faktoren d und k und die bekommst du über den erweiterten euklidischen Algorithmus (siehe Link).
14.01.2010, 22:48	wrock	Auf diesen Beitrag antworten »
120=523+5 23=45+3 5=13+2 3=12+1 2=11+1 1=11+0 ok, der teil bis hier is ja richtig oder? Jetzt gehts ja darum das ganze von hinten wieder aufzurollen: 1=2-11 1=3-12 2=5-13 3=23-45 5=120-5*23 und dann?
14.01.2010, 23:22	David_pb	Auf diesen Beitrag antworten »
Im 2. Schritt werden nicht einfach die einzelnen Gleichungen umgestellt sondern jeweils die Reste ersetzt. Aber eigentlich steht das alles haarklein auf der Seite beschrieben, ggf solltest du dir das einfach mal genau ansehen; oder lass dir hier Beispiele vorrechnen und versuch die Erklärungen nachzuvollziehen. Wenn du die restlichen mathematischen Hintergründe von RSA bisher verstanden hast sollte das ja echt kein Problem sein.
Anzeige

14.01.2010, 23:48	wrock	Auf diesen Beitrag antworten »
dann steh ich auf der leitung, kann mit der rechnung des neueren links so gut wie gar nix anfangen... dü hättest nicht kurz die zeit das bspl für mich fertig zu rechnen? vl. gehts ja dann.... bzw, es gibt n alternatives verfahren? http://www.austromath.at/medienvielfalt/...nt/k_euklid.htm
15.01.2010, 15:59	David_pb	Auf diesen Beitrag antworten »
Ok, mal für 120 und 23: $\begin{eqnarray} <br /> \begin{tabular}{r r r r}<br /> a & q & x & y \\ [0.5ex] \hline<br /> 120 & - & 1 & 0 \\ [-2.5ex]<br /> 23 & 5 & 0 & 1 \\ [-2.5ex]<br /> 5 & 4 & 1 & -5 \\ [-2.5ex]<br /> 3 & 1 & -4 & 21 \\ [-2.5ex]<br /> 2 & 1 & 5 & -26 \\ [-2.5ex]<br /> {\bf 1} & 2 & {\bf -9} & {\bf 47}<br /> \end{tabular}<br /> \end{eqnarray}$ Zur Erklärung: Du startest bei i = 2. $\begin{eqnarray} q_i \end{eqnarray}$ ist immer das Ergebnis der ganzahligen Divison von $\begin{eqnarray} a_{i-1} \end{eqnarray}$ und $\begin{eqnarray} a_i \end{eqnarray}$ . Der Wert für $\begin{eqnarray} a_{i+1}=a_{i-1}\mod a_i \end{eqnarray}$ . Sowie: $\begin{eqnarray} x_1 = 1, y_1 = 0, x_2 = 0, y_2 = 1 \end{eqnarray}$ und $\begin{eqnarray} x_{i+1} = x_{i-1} - q_i \cdot x_i \end{eqnarray}$ , $\begin{eqnarray} y_{i+1} = y_{i-1} - q_i \cdot y_i \end{eqnarray}$ . Dann hast du: $\begin{eqnarray} ggT(120, 23) = 1 = \underbrace{(-9)}_{k} \cdot 120 + \underbrace{47}_{d} \cdot 23 \end{eqnarray}$

1

Verwandte Themen