RSA

Das 1977 von den drei Mathematikern Rivest, Shamir und Adleman entwickelte RSA galt damals als erstes asymmetrisches Verschlüsselungs-Verfahren. Es basiert auf dem aktuellen Wissensstand, dass die Faktorisierung einer grossen Zahl, also ihre Zerlegung in ihre Primfaktoren, eine sehr aufwändige Angelegenheit ist, während das Erzeugen einer Zahl durch Multiplikation zweier Primzahlen recht einfach ist.

Die eigentliche Ver- und Entschlüsselungs-Funktion ist sehr einfach. Einzig das Erzeugen der Schlüssel ist etwas komplizierter. Der öffentliche Schlüssel besteht aus zwei Zahlen: dem RSA-Modul \(N\) und dem Verschlüssel­ungsexponent \(e\). Der private Schlüssel besteht ebenfalls aus zwei Zahlen: dem RSA-Modul \(N\) und dem Entschlüsselungsexponent \(d\).

Verschlüsseln

Um eine Nachricht \(K\) zu verschlüsseln, verwendet der Absender die Formel

\[ C = K^e \text{ mod } N\]

und erhält so aus dem Klartext \(K\) den Geheimtext \(C\).

Entschlüsseln

Der Geheimtext \(C\) kann durch modulare Exponentation wieder zum Klartext \(K\) entschlüsselt werden. Der Empfänger benutzt die Formel

\[ K = C^d \text{ mod } N\]

mit dem nur ihm bekannten Wert \(d\) sowie \(N\).

Schlüssel generieren

Das komplette Schlüsselpaar besteht aus den drei Zahlen \(N\), \(e\) und \(d\), wobei \((N, d)\) den privaten und \((N, e)\) den öffentlichen Schlüssel bilden. Diese Zahlen werden durch das folgende Verfahren erzeugt:

  1. Wähle zufällig zwei Primzahlen \(p\) und \(q\) so dass \(p \neq q\).
  2. Berechne den RSA-Modul \(N = p \cdot q\)
  3. Berechne die Eulersche \(\varphi\)-Funktion von \(N\):
    \(\varphi(N) = (p-1) \cdot (q-1)\)
  4. Wähle eine zu \(\varphi(N)\) teilerfremde Zahl \(e\), für die gilt \(1 < e < \varphi(e)\)
  5. Berechne den Entschlüsselungsexponenten \(d\) als Multiplikativ Inverses von \(e\) bezüglich des Modulus \(\varphi(N)\). Es soll also die folgende Kongruenz gelten: \(e \cdot d \cong 1 \text{ }(\text{mod } \varphi(N))\)

Die Zahlen \(p\), \(q\) und \(\varphi(N)\) werden nicht mehr benötigt und sollten nach der Schlüsselerstellung auf sichere Weise gelöscht werden.

  1. Wir wählen \(p = 11\) und \(q = 13\) für die beiden Primzahlen.
  2. Der RSA-Modul ist \(N = p \cdot q = 143\)
  3. Die Eulersche \(\varphi\)-Funktion nimmt damit den Wert \(\varphi(143) = (p-1) \cdot (q-1) = 120\) an.
  4. Die Zahl \(e\) muss zu \(120\) teilerfremd sein. Wir wählen \(e = 23\).
    Damit bilden \(e = 23\) und \(N = 143\) den öffentlichen Schlüssel.
  5. Berechnung der Inversen zu \(e\):
    Es gilt: \(e \cdot d + k \cdot \varphi(N) = 1 = ggT(e, \varphi(N))\)
    bzw. im konkreten Beispiel: \(23 \cdot d + k \cdot 120 = 1 = ggT(23, 120)\)
    Mit dem erweiterten euklidischen Algorithmus berechnet man nun die Faktoren \(d = 47\) und \(k = -9\), so dass die Gleichung aus dem Beispiel wie folgt aussieht: \(23 \cdot 47 + (-9) \cdot 120 = 1\)
    \(d = 47\) bildet zusammen mit dem schon berechneten \(N\) den privaten Schlüssel, während \(k\) nicht weiter benötigt wird.