MathePrisma: RSA


		RSA (RSA⁴)

Schritt 1

Den größten gemeinsamen Teiler zweier Zahlen $a$ und $b$ bestimmt man mit dem euklidischen Algorithmus. Man nennt diesen auch Wechselwegnahme.

Euklidischer Algorithmus

gegeben: $a, b \in \mathbb{Z}$ $a \ge b$
gesucht: $ggT(a,b)$

a	=	q₀^.b + r₁	0 < r₁ < b
b	=	q₁^.r₁ + r₂	0 < r₂ < r₁
r₁	=	q₂^.r₂ + r₃	0 < r₃ < r₂
	usw
r_n-3	=	q_n-2^.r_n-2 + r_n-1	0 < r_n-1 < r_n-2
r_n-2	=	q_n-1^.r_n-1 + r_n	0 < r_n < r_n-1
r_n-1	=	q_n^.r_n

Der letzte von 0 verschiedene Rest $r_n$ ist der größte gemeinsame Teiler von $a$ und $b$ : $r_n = \mathrm{ggT}(a,b)$ .
Interessiert dich die Pseudocode-Version? Oder möchtest du ein Beispiel rechnen?

Schritt 2

Aus den obigen Gleichungen folgt

$\begin{eqnarray*} r_n & = & r_{n-2} + (-q_{n-1}) \cdot r_{n-1}\\ & = & r_{n-2} + (-q_{n-1})(r_{n-3} + (-q_{n-2} \cdot r_{n-2}))\\ & = & r_{n-4} + (-q_{n-3}) \cdot r_{n-3} + (-q_{n-1}) \cdot (r_{n-3} + (-q_{n-2}) \cdot (r_{n-4} + (-q_{n-3})\cdot r_{n-3}))\\ & = & ... \end{eqnarray*}$

Schließlich erhält man eine Darstellung der Form $r_n = x \cdot a + y \cdot b$ . Da $r_n = ggT(a,b)$ , ist damit direkt folgender Satz bewiesen.

Vielfachensumme

Zu zwei Zahlen $a, b \in \mathbb{Z}$ gibt es immer Zahlen $x, y \in \mathbb{Z}$ mit der Eigenschaft, dass

$ggT(a,b) = x \cdot a + y \cdot b.$

Schritt 3

Nun geht der Beweis des

Satzes über die modulare Inverse ganz einfach:
Nach Voraussetzung ist $ggT(a,b) = 1$ und nach dem eben bewiesenen Satz gibt es Zahlen $x$ und $y$ , so dass

$1 = ggT(a,b) = x\cdot a + y\cdot b.$

Das gilt natürlich auch noch modulo $a$ und da $x \cdot a \bmod a = 0$ , gilt:

$x\cdot a + y\cdot b \bmod a = y\cdot b \bmod a = 1.$

Es gibt also tatsächlich eine Zahl $c = y$ , die modulo $a$ zu $b$ invers ist. Und sie lässt sich mit dem euklidischen Algorithmus berechnen.

Aber ist diese Zahl auch positiv? -- Nicht unbedingt! Aber wenn

$b\cdot c \bmod a = 1,$

so ist auch für jede natürliche Zahl $k$

$b \cdot (c + k\cdot a) \bmod a = b \cdot c + b \cdot k \cdot a \bmod a = b \cdot c \bmod a = 1 .$

private key

Hat man die Vielfachensummendarstellung $1 = ggT( (p-1)(q-1), e ) = x \cdot (p-1)(q-1) + y \cdot e$ bestimmt, so ist die kleinste positive Zahl der Form $y + k\cdot (p-1)(q-1)$ der private key $d$ .

Uff! Ganz schön kompliziert!

Wenn es dir genügt, zu wissen, dass man den private key $d$ mit dem euklidischen Algorithmus berechnen kann, lies einfach weiter. Ansonsten kannst du

dir ein Beispiel ansehen um die Berechnung von $d$ nachzuvollziehen
oder
einen Algorithmus kennenlernen, mit dem die Vielfachensummen-Darstellung und damit $d$ berechnet wird .

Alles klar?

Zurück zum RSA-Verfahren. Mit Hilfe des euklidischen Algorithmus' kann man also den private key $d$ bestimmen.
Kennt man die beiden Primzahlen $p$ und $q$ , so ist es also einfach, $d$ zu berechnen und damit dann die mit $N$ und $e$ verschlüsselten Nachrichten zu entschlüsseln. Allerdings ist es nahezu unmöglich, $d$ zu berechnen, ohne $p$ und $q$ zu kennen.

Aber warum funktioniert das Verfahren denn nun überhaupt? Warum kommt wirklich wieder der Klartext heraus, mit anderen Worten: warum gilt

$C^d \bmod N = M \text{ ? }$

Seite 8/12