MathePrisma Logo

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=q0.b + r10 < r1 < b
b=q1.r1 + r20 < r2 < r1
r1=q2.r2 + r30 < r3 < r2
 usw  
rn-3=qn-2.rn-2 + rn-10 < rn-1 < rn-2
rn-2=qn-1.rn-1 + rn0 < rn < rn-1
rn-1=qn.rn  

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{ ? } \]