RSA

RSA (Rivest–Shamir–Adleman) ist ein asymmetrisches kryptographisches Verfahren, das sowohl zum Verschlüsseln als auch zum digitalen Signieren verwendet werden kann. Es verwendet ein Schlüsselpaar, bestehend aus einem privaten Schlüssel, der zum Entschlüsseln oder Signieren von Daten verwendet wird, und einem öffentlichen Schlüssel, mit dem man verschlüsselt oder Signaturen prüft. Der private Schlüssel wird geheim gehalten und kann nicht mit realistischem Aufwand aus dem öffentlichen Schlüssel berechnet werden.

Verfahren

Das Verfahren ist mit dem Rabin-Verschlüsselungsverfahren verwandt. Da es deterministisch arbeitet, ist es unter Umständen für bestimmte Angriffe anfällig. In der Praxis wird RSA daher mit dem Optimal Asymmetric Encryption Padding kombiniert.

Einwegfunktionen

Einwegfunktion Funktionen, bei denen eine Richtung leicht, die andere (Umkehrfunktion) schwierig zu berechnen ist, bezeichnet man als Einwegfunktionen (engl. one-way function). Beispielsweise ist nach aktuellem Wissensstand die Faktorisierung einer großen Zahl, also ihre Zerlegung in ihre Primfaktoren, sehr aufwändig, während das Erzeugen einer Zahl durch Multiplikation von Primzahlen recht einfach und schnell möglich ist. Spezielle Einwegfunktionen sind Falltürfunktionen (engl. trapdoor one-way function), die mit Hilfe einer Zusatzinformation auch rückwärts leicht zu berechnen sind.

Die Verschlüsselung und die Signatur mit RSA basieren auf einer Einwegpermutation mit Falltür (engl. trapdoor one-way permutation, kurz TOWP), einer Falltürfunktion, die gleichzeitig bijektiv, also eine Permutation, ist. Die Einwegeigenschaft begründet, warum die Entschlüsselung (bzw. das Signieren) ohne den geheimen Schlüssel (die Falltür) schwierig ist.

Erzeugung des öffentlichen und privaten Schlüssels

Die Schlüssel bestehen aus den drei Zahlen $e,d$ und $N$. Man nennt $N$ den RSA-Modul, $e$ den Verschlüsselungsexponenten und $d$ den Entschlüsselungsexponenten. Das Zahlenpaar $(e,N)$ bildet den öffentlichen Schlüssel (public key) und das Paar $(d,N)$ den privaten Schlüssel (private key). Diese Zahlen werden durch das folgende Verfahren erzeugt:

1. Wähle zufällig und stochastisch unabhängig zwei Primzahlen $p\neq q$. Diese sollen die gleiche Größenordnung haben, aber nicht zu dicht beieinander liegen, sodass der folgende Rahmen ungefähr eingehalten wird: $0{,}1<|\log _{2}p-\log _{2}q|<30$. (In der Praxis erzeugt man dazu solange Zahlen der gewünschten Länge und führt mit diesen anschließend einen Primzahltest durch, bis man zwei Primzahlen gefunden hat.)
2. Berechne den RSA-Modul

   $N=p\cdot q$

3. Berechne die Eulersche φ-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 (N)-1$.
5. Berechne den Entschlüsselungsexponenten $d$ als multiplikativ Inverses von $e$ bezüglich des Moduls $\varphi (N)$, was mit dem erweiterten euklidischen Algorithmus erfolgen kann. Es soll also die Kongruenz gelten:

   $e\cdot d\equiv 1{\pmod {\varphi (N)}}$

Die Zahlen $p$, $q$ und $\varphi (N)$ werden nicht mehr benötigt und können nach der Schlüsselerstellung gelöscht werden. Es ist jedoch relativ einfach, diese Werte aus $e$, $d$ und $N$ zu rekonstruieren. $p,q,\varphi (N)$ und $d$ müssen geheim gehalten werden.

Da die Primzahltests inzwischen ausreichend schnell sind, wählt man heutzutage zuerst einen kleinen Exponenten $e$ mit $2^{16}<e<2^{64}$ und verwirft bei der Erzeugung die Primzahlen $p,q$, für die $p-1,q-1$ nicht teilerfremd zu $e$ sind. Die Wahl eines $e$ kleiner als die Fermat-Zahl $F_{4}=2^{16}+1=65537$ kann zu Angriffsmöglichkeiten führen, etwa in Form des von Johan Håstad publizierten „Broadcast“-Angriffs, bei dem der Versand einer Nachricht an mehrere Empfänger zu einer Dechiffrierung über den chinesischen Restsatz führen kann.

Wenn $d$ weniger als ein Viertel der Bits des RSA-Moduls hat, kann $d$ – sofern nicht bestimmte Zusatzbedingungen erfüllt sind – mit einem auf Kettenbrüchen aufbauenden Verfahren effizient ermittelt werden. Bei der Wahl eines Exponenten $e$ kleiner als $2^{64}$ ist diese Möglichkeit jedoch ausgeschlossen.

Beispiel

1. Wir wählen den Exponenten $e=23$.
2. Wir wählen $p=11$ und $q=13$ für die beiden Primzahlen. Die Zahlen $p-1=10$ und $q-1=12$ sind teilerfremd zum Exponenten $e=23$.
3. Der RSA-Modul ist $N=p\cdot q=143$. Damit bilden $e=23$ und $N=143$ den öffentlichen Schlüssel.
4. Die eulersche φ-Funktion hat den Wert $\varphi (N)=\varphi (143)=(p-1)(q-1)=120$.
5. Berechnung der Inversen zu $e$ modulo $\varphi (N)$:
   Es gilt: $e\cdot d+k\cdot \varphi (N)=1=\operatorname {ggT} (e,\varphi (N))$,
   im konkreten Beispiel: $23\cdot d+k\cdot 120=1=\operatorname {ggT} (23,120)$.
   Mit dem erweiterten euklidischen Algorithmus berechnet man nun die Faktoren $d=47$ und $k=-9$, und somit ist $d=47$ der private Schlüssel, während $k$ nicht weiter benötigt wird.

Verschlüsseln von Nachrichten

Verschlüsselung

Um eine Nachricht $m$ zu verschlüsseln, verwendet der Absender die Formel

$c\equiv m^{e}{\pmod {N}}$

und erhält so aus der Nachricht $m$ den Geheimtext $c$. Die Zahl $m$ muss dabei kleiner sein als der RSA-Modul $N$.

Beispiel

Es soll die Zahl 7 verschlüsselt werden. Der Sender benutzt den veröffentlichten Schlüssel des Empfängers $N=143$, $e=23$ und rechnet

$2\equiv 7^{23}{\pmod {143}}$

Das Chiffrat ist also $c=2$.

Entschlüsseln von Nachrichten

Entschlüsselung

Der Geheimtext $c$ kann durch modulare Exponentiation wieder zum Klartext $m$ entschlüsselt werden. Der Empfänger benutzt die Formel

$m\equiv c^{d}{\pmod {N}}$

mit dem nur ihm bekannten Wert $d$ sowie $N$.

Beispiel

Für gegebenes $c=2$ wird berechnet

$7\equiv 2^{47}{\pmod {143}}$

Der Klartext ist also $m=7$.

Signieren von Nachrichten

Um eine Nachricht $m$ zu signieren, wird vom Sender auf die Nachricht die RSA-Funktion mit dem eigenen privaten Schlüssel $d$ angewandt. Zum Prüfen wendet der Empfänger auf die Signatur $m^{d}{\bmod {\ }}N$ mit Hilfe des öffentlichen Schlüssels des Senders $e$ die Umkehrfunktion an und vergleicht diese mit der zusätzlich übermittelten unverschlüsselten Nachricht $m$. Wenn beide übereinstimmen, ist die Signatur gültig und der Empfänger kann sicher sein, dass derjenige, der das Dokument signiert hat, auch den privaten Schlüssel besitzt und dass niemand seit der Signierung das Dokument geändert hat. Es wird also die Integrität und Authentizität garantiert, vorausgesetzt, der private Schlüssel ist wirklich geheim geblieben. Aufgrund der Homomorphieeigenschaft von RSA ist dieses Signaturverfahren jedoch ungeeignet. Liegen zwei Signaturen $m_{1}^{d}$, $m_{2}^{d}$ vor, so kann ein Angreifer daraus durch Multiplizieren die Signatur der Nachricht $m_{1}m_{2}$ berechnen. Sogar aus nur einer Signatur $m^{d}$ kann ein Angreifer beliebig viele Nachrichten-Signatur-Paare erzeugen: $(m\cdot c^{e},m^{d}\cdot c)$ ist ein solches Paar für beliebige $c$.

Dieses Problem kann umgangen werden, indem nicht die Nachricht selbst signiert wird. Stattdessen wird mit einer zusätzlich zum Signaturverfahren spezifizierten kollisionsresistenten Hashfunktion $H$ der Hash-Wert $H(m)$ der Nachricht $m$ berechnet. Dieser wird mit dem privaten Schlüssel signiert, um die eigentliche Signatur zu erhalten. Der Empfänger kann die so erhaltene Signatur mit dem öffentlichen Schlüssel verifizieren und erhält dabei einen Wert $h'$. Diesen vergleicht er mit dem von ihm selbst gebildeten Hashwert $H(m)$ der ihm vorliegenden Nachricht $m$. Wenn beide Werte $H(m)=h'$ übereinstimmen, kann mit hoher Wahrscheinlichkeit davon ausgegangen werden, dass die Nachricht fehlerfrei übertragen wurde und nicht gefälscht ist. Auch diese Modifikation erfüllt allerdings nicht die modernen Sicherheitsanforderungen, daher werden Verfahren wie RSA-PSS verwendet, um mit RSA zu signieren.

RSA mit dem Chinesischen Restsatz

Mit Hilfe des Chinesischen Restsatzes können Nachrichten effizienter entschlüsselt oder signiert werden. Weil der Modul $N$ sehr groß ist, sind auch die im Rechner verwendeten Bitdarstellungen der Zahlen sehr lang. Der Chinesische Restsatz erlaubt es, die Berechnungen statt in einer Gruppe der Größe $N$ gleichzeitig in den zwei kleineren Gruppen der Größe $p$ und $q$ auszuführen und das Ergebnis danach wieder zusammenzusetzen. Da hier die Zahlen wesentlich kleiner sind, ist diese Berechnung insgesamt schneller. Diese Variante wird nach der englischen Bezeichnung des Chinesischen Restsatzes CRT (Chinese remainder theorem) auch CRT-RSA genannt.

Der private Schlüssel besteht dann im Gegensatz zu dem, was im Rest dieses Artikels angenommen wird, aus folgenden Komponenten:

• $N$, der RSA-Modul,
• $d$, der Entschlüsselungsexponent,
• $p$, die erste Primzahl,
• $q$, die zweite Primzahl (ungleich p),
• $d_{p}=d{\bmod {(}}p-1)$, häufig dmp1 genannt,
• $d_{q}=d{\bmod {(}}q-1)$, häufig dmq1 genannt und
• $q_{Inv}=q^{-1}{\bmod {p}}$, häufig iqmp genannt.

Eine Nachricht $m$ wird dann wie folgt signiert:

• $m_{1}=m^{d_{p}}{\bmod {p}}$
• $m_{2}=m^{d_{q}}{\bmod {q}}$
• $s=(q_{Inv}(m_{1}-m_{2}){\bmod {p}})q+m_{2}$

Aus der letzten Gleichung sieht man sofort, dass $s{\bmod {q}}=m_{2}$ und $s{\bmod {p}}=q_{Inv}q(m_{1}-m_{2})+m_{2}{\bmod {p}}=m_{1}$. Die Signatur $s$ stimmt also sowohl ${\bmod {p}}$ als auch ${\bmod {q}}$ mit $m^{d}$ überein, daher ist nach dem Chinesischen Restsatz $s=m^{d}{\bmod {N}}$. (Bemerkung: Die Identität $s=m^{d}{\bmod {p}}$ sieht man so: Modulo p gilt $s=m^{d_{p}}=m^{d+k(p-1)}=m^{d}(m^{p-1})^{k}=m^{d}$. Die letzte Identität folgt aus dem kleinen fermatschen Satz. Analog erhält man $s=m^{d}{\bmod {q}}$.)

RSA ist kein Primzahltest

Wenn $p\neq q$ Primzahlen sind, funktioniert das RSA-Verfahren. Umgekehrt kann aber aus dem funktionierenden RSA-Verfahren nicht geschlossen werden, dass der Modul $N$ das Produkt zweier Primzahlen $p$ und $q$ ist, denn mit Carmichael-Zahlen funktioniert das Verfahren auch.