RSA-Verschlüsselung - Mit großen Zahlen rechnen?

18.02.2015, 17:41	Lena95	Auf diesen Beitrag antworten »
RSA-Verschlüsselung - Mit großen Zahlen rechnen? Hey, ich übe grade die RSA-Verschlüsselung. Möchte also ein Wort mit dem öffentlichen Schlüssel: (97, 3713) verschlüsseln. Wenn ich jetzt also den Buchstaben "D" verschlüsseln möchte und die Buchstaben als Zahlen festgelegt mit dem Muster: A = 1, B= 2, ... , Z = 26, dann müsste ich ja: 4^97 mod 3713 rechnen. Die Zahl 4^97 ist natürlich viel zu groß um sinnvoll damit zu rechnen. Gibt es irgendeine halbwegs einfache Variante um an die Lösung von solch einer Rechnung zu kommen? In der Klausur steht mir ja leider auch kein Taschenrechner zur Verfügung Grüße
18.02.2015, 18:12	Elvis	Auf diesen Beitrag antworten »
$\begin{eqnarray} 4^6=2^{12}=4096\equiv 383 (mod \; 3713) \end{eqnarray}$ ohne Taschenrechner berechnet.
18.02.2015, 19:05	Lena95	Auf diesen Beitrag antworten »
Hey, danke schonmal, nur bin ich mir nicht sicher, inwiefern das meine Rechnung vereinfacht. Wenn ich das auf die Rechnung übertrage wäre das: $\begin{eqnarray} 4^{97} = 2^{194} = ??? \equiv ??? (mod\ 3713) \end{eqnarray}$ Diese riesigen Zahlen kann man wahrscheinlich irgendwie "runterbrechen", aber ich weiß leider nicht wie
19.02.2015, 11:12	Elvis	Auf diesen Beitrag antworten »
Du musst nicht $\begin{eqnarray} 4^{97} \end{eqnarray}$ berechnen, das geht auch mit einem Taschenrechner nicht, und dann durch $\begin{eqnarray} 3713 \end{eqnarray}$ teilen ist viel zu aufwendig. Es genügt, klein anzufangen, z.B. $\begin{eqnarray} 4^{12}=4096\cdot 4096\equiv 383\cdot 383 (mod\; 3713) \end{eqnarray}$ . Nun teilst du $\begin{eqnarray} 383\cdot 383 \end{eqnarray}$ durch $\begin{eqnarray} 3713 \end{eqnarray}$ und rechnest mit dem Rest der Division weiter.
19.02.2015, 14:14	Dopap	Auf diesen Beitrag antworten »
du kannst auch bei $\begin{eqnarray} Y=a^x \mod p \end{eqnarray}$ das Prinzip des fortgesetzten Quadrierens und Multiplizierens verwenden: Beispiel: $\begin{eqnarray} Y=a^{25} \mod p \end{eqnarray}$ $\begin{eqnarray} (25)_{10}= (1 1 0 0 1)_{2} \end{eqnarray}$ ( Euklid ) und jetzt: $\begin{eqnarray} a^{25} \mod p = (((a^2a)^2)^2)^2a \end{eqnarray}$ Dabei wird nach jeder Quadratur bzw. Multiplikation eine Reduktion Modulo p durchgeführt. Ist wohl dasselbe Prinzip wie oben, aber vielleicht offensichtlicher.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »