RSA ist ein Verfahren oder Algorithmus zur Verschlüsselung elektronischer Daten, der verschiedene Schlüssel zum Ver- und Entschlüsseln verwendet, wobei der Schlüssel zum Entschlüsseln nicht oder nur mit hohem Aufwand aus dem Schlüssel zum Verschlüsseln berechenbar ist. Der Schlüssel zur Verschlüsselung kann daher veröffentlicht werden. Solche Verfahren werden als asymmetrische oder Public-Key-Verfahren bezeichnet. Er ist nach seinen Erfindern Ronald L. Rivest, Adi Shamir und Leonard Adleman benannt.

Schlüsselverteilung

---

Der Vorteil asymmetrischer Verfahren besteht in der Vereinfachung der Schlüsselverteilung. Bei symmetrischen Verfahren ist der Austausch eines geheimen Schlüssels erforderlich, den Sender und Empfänger gemeinsam nutzen. Der Austausch muss dabei sicher erfolgen. Dies bedeutet, der Austausch muss abhörsicher sein. Es ist jedoch auch sicher zu stellen, dass der Schlüssel tatsächlich von der Person stammt, mit der geheime Nachrichten ausgetauscht werden sollen.

Durch Public-Key-Systeme entfällt die Notwendigkeit, den Schlüsselaustausch gegen Abhören zu härten, da nur der öffentliche Schlüssel ausgetauscht werden muss. Es bleibt aber ein wesentliches Problem, da weiterhin sicherzustellen ist, dass der öffentliche Schlüssel tatsächlich von der Person stammt, mit der geheime Botschaften ausgetauscht werden sollen. In Praxis ist dies oft nur dann möglich, wenn zugleich auch die Geheimhaltung gewährleistet werden kann.

Falls die Kommunikation zwar nicht abhörsicher ist, aber kein Zweifel über die Identität des Partners besteht und die Nachricht nicht von einem Dritten verändert werden kann, ist der Schlüsselaustausch beim Public-Key-Verfahren problemlos. Allerdings ist dies auch mit anderen Verfahren möglich.

Dazu kann der Schlüssel aus vielen Teilschlüsseln zusammengesetzt werden. Eine Hashfunktion wie SHA-1 erlaubt es, aus vielen längeren Teilschlüsseln ein Komprimat zu errechnen, welches als Schlüssel für die symmetrische Verschlüsselung benutzt werden kann. Die Teilschlüssel können zu unterschiedlichen Zeiten und mit höchst unterschiedlichen Methoden ausgetauscht werden.

Geschichte

---

Der Schlüsselaustausch ist eine logistische Schwachstelle und hat bei mehreren zwischenstaatlichen Auseinandersetzungen und Kriegen den Ausgang (mit-)entschieden, so zum Beispiel durch Aktivitäten von Alan Turing und anderen in Bletchley Park im Zweiten Weltkrieg. Daher wurde Anfang der 1970er Jahre im Government Communications Headquarters von Ellis, Cocks und Williamson ein dem späteren Verfahren von Diffie-Hellman ähnliches asymmetrisches Verfahren entwickelt, welches aber keine große praktische Bedeutung hatte und aus Geheimhaltungsgründen nicht (wissenschaftlich) publiziert wurde. RSA konnte daher zum Patent angemeldet werden, obgleich es nicht das erste Verfahren dieser Art war.

Hybride Verfahren

---

RSA ist im Vergleich zu 3DES, AES und SHA-1 um mindestens einen Faktor 1.000 langsamer. Für die Verschlüsselung größerer Datenmengen werden daher symmetrische Verfahren eingesetzt. Es genügt jedoch, RSA zum Austausch eines Schlüssels für die symmetrische Verschlüsselung zu nutzen. Entsprechend genügt es, beim Signaturverfahren einen SHA-1-Wert statt der gesamten Nachricht zu signieren. Es werden daher praktisch immer hybride Verfahren eingesetzt.

Verfahren

---

Nachdem Whitfield Diffie und Martin Hellman eine Theorie zur Public-Key-Kryptografie veröffentlicht hatten, versuchten die drei Mathematiker Rivest, Shamir und Adleman, die Annahmen von Diffie und Hellmann zu widerlegen. Nachdem sie den Beweis bei verschiedenen Verfahren durchführen konnten, stießen sie schließlich auf eines, bei dem sie keinerlei Angriffspunkte fanden. Hieraus entstand dann RSA.

Das Verfahren wurde 1977 entwickelt und basiert auf dem aktuellen Wissensstand, dass die Faktorisierung einer großen 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. Wenn nun eine Nachricht einem Empfänger verschlüsselt zugeleitet werden soll, generiert dieser einen öffentlichen Schlüssel. Der Nachrichtenabsender verwendet diesen öffentlich bekanntgemachten Schlüssel, indem er damit seine Botschaft verschlüsselt. Nur der Empfänger kann diese „dekodieren“, da nur er die „Zusammensetzung“ des von ihm erzeugten (öffentlichen) Schlüssels kennt.

Einwegfunktionen

Funktionen wie die Multiplikation/Faktorisierung, bei denen eine Richtung leicht, die andere schwierig zu berechnen ist, bezeichnet man als Einwegfunktionen (engl. one way function). Um allerdings die Entschlüsselung tatsächlich möglich zu machen, muss es sich um Falltürfunktionen (engl. trap door function) handeln, die mit Hilfe einer Zusatzinformation auch rückwärts leicht zu berechnen sind.

Das Verfahren ist mit dem Rabin-Verschlüsselungsverfahren verwandt.

Algorithmus

1. Wähle zufällig und stochastisch unabhängig zwei Primzahlen $p\; \backslash neq\; q$, und berechne das Produkt $N\; =\; p\; \backslash cdot\; q$.
   In der Praxis werden diese Primzahlen durch Raten einer Zahl und darauf folgendes Anwenden eines Primzahltests bestimmt.
2. Berechne $\backslash varphi(N)\; =\; (p-1)\; \backslash cdot\; (q-1)$, wobei $\backslash varphi$ für die Eulersche φ-Funktion steht.
3. Wähle eine Zahl $e$, für die gilt , die teilerfremd zu $\backslash varphi(N)$ ist.
4. Berechne die Zahl $d$ so, dass das Produkt $e\; \backslash cdot\; d$ kongruent 1 bezüglich des Modulus $\backslash varphi(N)$ ist, dass also $e\; \backslash cdot\; d\; \backslash equiv\; 1\; \backslash pmod\{\backslash varphi(N)\}$ gilt.
   
   Der öffentliche Schlüssel (public key) besteht dann aus
   • $N$, dem Primzahlprodukt sowie
   • $e$, dem öffentlichen Exponenten.
   
   Der private Schlüssel (private key) besteht aus
   • $d$, dem privaten Exponenten sowie
   • $N$, welches allerdings bereits durch den öffentlichen Schlüssel bekannt ist.
   
   $p$, $q$ und $\backslash varphi(N)$ werden nicht mehr benötigt und sollten nach der Schlüsselerstellung auf sichere Weise gelöscht werden.

Ein Zahlenbeispiel:

1. Für die beiden Primzahlen $p$ und $q$ wählt man $p\; =\; 11$ und $q\; =\; 13$. Damit wird $N\; =\; 143$.
2. Die eulersche φ-Funktion nimmt damit den Wert $\backslash varphi(N)\; =\; \backslash varphi(143)\; =\; (p-1)(q-1)\; =\; 120$ an.
3. Für die zu $\backslash varphi(143)\; =\; 120$ teilerfremde neue Zahl $e$ wählt man $e\; =\; 23$.
4. Mit dem erweiterten euklidischen Algorithmus berechnet man nun die Zahl $d=47$ mit $e\; \backslash cdot\; d\; \backslash equiv\; 1\; \backslash pmod\{\backslash varphi(N)\}$. Damit wird $d\; =\; 47$ der private Schlüssel, $e\; =\; 23$ und $N\; =\; 143$ der öffentliche Schlüssel.

Verschlüsseln von Nachrichten

Verschlüsselung (asymmetrisches Kryptosystem).png

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

und erhält so aus dem Klartext $K$ den Geheimtext $C$.

Beispiel

Es soll die Zahl 7 verschlüsselt werden.
Der Nachrichtenabsender benutzt den veröffentlichten Schlüssel $N\; =\; 143$, $e\; =\; 23$ und rechnet Zur Berechnung von $7^\{23\}\; \backslash bmod\; 143$ kann die Kongruenzarithmetik verwendet werden. Mit Hilfe der modularen Exponentiation berechnet man schnell:

$7^\{23\}\; \backslash \; \backslash bmod\; \backslash \; 143\; \backslash \; =\; \backslash \; (((\; 7^2\; )^2\backslash cdot\; 7)^2\backslash cdot\; 7)^2\backslash cdot\; 7\; \backslash \; \backslash bmod\; \backslash \; 143\; =\; 2$

Dabei wendet man nach jedem Rechenschritt auf die zu handhabenden Zahlen die Modulo-Operation (kurz: mod) an, um die Ergebnisse möglichst „klein“ zu halten.

Aus dem Klartext 7 ist somit der Geheimtext 2 geworden.

Entschlüsseln von Nachrichten (Decodierung)

Entschlüsselung (symmetrisches und asymmetrisches Kryptosystem).png

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

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

Beispiel

$K\; \backslash equiv\; 2^\{47\}\; \backslash \; \backslash bmod\backslash \; 143\; =\; ((((2^2)^2\; \backslash cdot\; 2)^2\; \backslash cdot\; 2)^2\; \backslash cdot\; 2)^2\; \backslash cdot\; 2\; \backslash \; \backslash bmod\backslash \; 143\; =\; 7$

Aus $C\; =\; 2$ wird also wieder $K\; =\; 7$.

Siehe auch Schnelles Potenzieren

Signieren von Nachrichten

Um eine Nachricht $K$ zu signieren, wird diese mit dem eigenen privaten Schlüssel verschlüsselt. Zum Prüfen der Signatur entschlüsselt der Empfänger die Nachricht mit dem öffentlichen Schlüssel des Senders und vergleicht diese mit dem empfangenen $K$. Wenn sie nicht übereinstimmen, ist die Signatur ungültig. Ist die Signatur gültig, dann kann sich der Empfänger 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.

Da asymmetrische Verfahren nicht geeignet sind, um größere Datenmengen zu verschlüsseln, wird in der Praxis nicht die Nachricht selbst mit dem privaten Schlüssel verschlüsselt. Stattdessen wird der Hashwert $H$ der Nachricht berechnet. Dieser bildet, meist zusammen mit einigen technisch notwendigen Informationen, wie zum Beispiel das verwendete Hashverfahren, die Eingabe $K^*$ der Verschlüsselung mit dem privaten Schlüssel. Diese liefert die eigentliche Signatur. Der Empfänger kann nun mit dem öffentlichen Schlüssel und der Signatur $K^*$ bestimmen. Anschließend kann er selber den Hashwert der Nachricht bestimmen und mit dem in $K^*$ gespeicherten vergleichen. Wenn die beiden Werte übereinstimmen, kann mit hoher Sicherheit davon ausgegangen werden, dass die Nachricht fehlerfrei übertragen wurde und nicht gefälscht ist.

Siehe auch Elektronische Unterschrift

Sicherheit

Public-Key-Verfahren wie RSA werden in der Praxis immer als hybride Verfahren in Verbindung mit symmetrischen Verfahren verwendet. Bei der Analyse der Sicherheit muss die Sicherheit des Public-Key-Verfahrens und die praktische Sicherheit des Gesamtsystems betrachtet werden.

Sicherheit von RSA

Bei der Kryptanalyse des RSA-Verfahrens unterscheidet man zwischen zwei Problemen:

• RSA-Problem ($\backslash mathrm\{RSAP\}$): Gegeben den öffentlichen Schlüssel $(N,\; e)$ und einen Geheimtext $C$, ist ein Klartext $K$ mit $K^e\backslash equiv\; C\backslash pmod\{N\}$ gesucht.
• RSA-Schlüsselproblem ($\backslash mathrm\{RSAP^*\}$): Gegeben den öffentlichen Schlüssel $(N,\; e)$, ist der private Schlüssel $d$ mit $ed\backslash equiv\; 1\backslash pmod\{\backslash varphi(N)\}$ gesucht.

Folgende Beziehungen zwischen den RSA-Problemen und $\backslash mathrm\{FACTORING\}$, dem Faktorisierungsproblem, sind bekannt:

$\backslash mathrm\{RSAP\}\; \backslash leq\_p\; \backslash mathrm\{RSAP^*\}\; =\_p\; \backslash mathrm\{FACTORING\}$

Die Beziehung $\backslash mathrm\{RSAP\}\; \backslash leq\_p\; \backslash mathrm\{RSAP^*\}$ ist trivial, denn wenn man den privaten Schlüssel hat, kann man damit wie oben jeden beliebigen Geheimtext entschlüsseln. Ob die Umkehrung gilt, ist zur Zeit unbekannt.

Auch die Beziehung $\backslash mathrm\{RSAP^*\}\; \backslash leq\_p\; \backslash mathrm\{FACTORING\}$ ist trivial, denn wenn man $N=pq$ faktorisiert hat, kann man damit leicht $\backslash varphi(N)=(p-1)(q-1)$ berechnen, und dann mit dem euklidischen Algorithmus zu gegebenem öffentlichen Schlüssel den zugehörigen privaten Schlüssel effizient berechnen, wie in der Schlüsselerzeugung.

Für die Beziehung $\backslash mathrm\{FACTORING\}\; \backslash leq\_p\; \backslash mathrm\{RSAP^*\}$ ist schon lange ein probabilistischer Polynomialzeitalgorithmus bekannt. Vor kurzem wurde gezeigt, dass sich diese Reduktion im balancierten RSA (d.h. $p$ und $q$ haben gleiche Bitlänge) auch deterministisch durchführen lässt. Der Beweis verwendet das Coppersmith-Verfahren zur Bestimmung von Nullstellen eines irreduziblen bivariaten Polynoms mit ganzzahligen Koeffizienten, welches sich auf eine Gitterreduktion zurückführen lässt.

Da alle gängigen Implementierungen balanciertes RSA verwenden, ist in der Praxis das Brechen des geheimen Schlüssels nur mit der Kenntnis des öffentlichen Schlüssels genau so schwer wie das Faktorisieren von $N$. Wegen $\backslash mathrm\{RSAP\}\; \backslash leq\_p\; \backslash mathrm\{FACTORING\}$ ist im Fall der zusätzlichen Kenntnis eines Geheimtexts die Schwierigkeit des Faktorisierungsproblems von zentralem Interesse.

Man möchte $N=pq$ für sehr große Primzahlen $p$ und $q$ faktorisieren. Diese Primfaktorzerlegung ist für große Zahlen mit den heute bekannten Verfahren praktisch nicht durchführbar. Es ist aber nicht bewiesen, dass es sich bei der Primfaktorzerlegung um ein prinzipiell schwieriges Problem handelt. Im Gegenteil, mit dem Quadratischen Sieb wurden bereits Zahlen mit über 100 Stellen faktorisiert. Mit der Methode des Zahlkörpersiebs wurde im Jahr 2005 von Wissenschaftlern der Universität Bonn die im Rahmen der RSA Factorization Challenge von RSA Laboratories vorgegebene 200-stellige Dezimalzahl RSA-200 in ihre zwei großen Primfaktoren zerlegt. Die Faktorisierung begann Ende 2003 und dauerte bis Mai 2005. Unter anderem kam ein Rechnerverbund von 80 handelsüblichen Rechnern an der Universität Bonn zum Einsatz. Im November 2005 zahlten RSA Laboratories für die Faktorisierung von RSA-640, einer Zahl mit 640 Bits bzw. 193 Dezimalstellen, eine Prämie von 20.000 US-Dollar. Dies ist noch ein gutes Stück von den mindestens 300 Dezimalstellen heute üblicher RSA-Schlüssel entfernt. Jedoch weisen die dabei verwandten Faktorisierungsverfahren ein deutlich subexponentielles (obwohl superpolynomielles) Laufzeitverhalten auf, so dass in näherer Zukunft möglicherweise auch deutlich größere Zahlen mit diesen Methoden faktorisiert werden könnten.

Für die Faktorisierung von RSA-1024 (309 Dezimalstellen) oder gar RSA-2048 (617 Dezimalstellen) sind 100.000 $ bzw. 200.000 $ ausgelobt. Die wachsende Rechenleistung moderner Computer stellt für die kurzfristige Sicherheit von RSA wesentliches kein Problem dar, zumal diese Entwicklung vorhersehbar ist: Der Nutzer kann bei der Erzeugung seines Schlüssels darauf achten, dass er während der Dauer der beabsichtigten Verwendung nicht faktorisiert werden zu kann. Nicht vorhersehbare Entwicklungen, wie die Entwicklung deutlich schnellerer Algorithmen oder gar eines leistungsfähigen Quantencomputers bergen zumindest für die mittel- und langfristige Sicherheit der verschlüsselten Daten gewisse Risiken.

In einigen Spezialfällen kann man das RSA-Verfahren brechen, ohne das Faktorisierungsproblem gelöst zu haben. Der Angriff von Wiener bei balanciertem RSA löst das RSA-Schlüsselproblem effizient unter der Annahme, dass der private Schlüssel nur eine geringe Bitlänge aufweist, genauer . Wiener verwendete dabei die Tatsache, dass unter der Abschätzung für $d$ der Bruch $\backslash frac\{k\}\{d\}$ (für eine ganze Zahl $k$) in der Kettenbruchentwicklung von $\backslash frac\{e\}\{N\}$ auftaucht. Die Schranke wurde mit Mitteln der Giterreduktion auf

Auch das RSA-Problem kann unter einigen Annahmen effizient ohne Faktorisieren gelöst werden. Der Angriff von Håstad ermittelt einen Klartext, der mit kleinem Verschlüsselungsexponent (etwa $e=3$) für mehrere Empfänger vor dem Verschlüsseln speziell aufbereitet wurde, etwa wenn die Nummer des Empfängers in den Klartext codiert wurde. Dieser Angriff verwendet die Coppersmith-Methode, um kleine Nullstellen eines Polynoms in einer Unbestimmten zu berechnen, welche wiederum auf Giterreduktion basiert.

Praktische Sicherheit

RSA wird in der Regel in Hybridverfahren mit symmetrischen Verschlüsselungsverfahren kombiniert. Dabei wird zufällig ein Sitzungsschlüssel für eine symmetrische Verschlüsselung generiert, der dann per RSA verschlüsselt und zusammen mit der Nachricht übertragen wird.

Bei der Signatur wird nicht die gesamte Nachricht sondern nur ein Hashwert signiert. Der symmetrische Schlüssel bzw. der Hashwert sind dabei relativ kurz. Für den symmetrischen Schlüssel gilt also

.

Daher kann der symmetrische Schlüssel mit einer einzigen RSA-Verschlüsselung verschlüsselt werden. Für die Sicherheit von RSA sind Primzahlen mit über 100 Stellen erforderlich. Daher könnte ein symmetrischer Schlüssel mit über 200 Stellen verschlüsselt werden.

Als sehr sicher eingestufte Algorithmen zur symmetrischen Verschlüsselung gelten 3DES und AES. Diese verwenden 112, 128 oder maximal 168 Bit oder etwa 40 Dezimalstellen. Damit ist eine Brute-Force-Angriff faktisch auszuschließen. Eine sichere Hashfunktion wie SHA-1 erzeugt Funktionswerte mit lediglich 160 Bit entsprechend etwa 50 Dezimalstellen bzw. 40 Hexadezimalziffern. Damit lassen sich Signaturverfahren mittels RSA realisieren, die nur einen Verschlüsselungsschritt benötigen.

Die Sicherheit und die Performance des Gesamtsystems werden durch die Sicherheit des Public-Key-Verfahrens limitiert, sofern nur als sicher eingestufte Algorithmen verwendet werden und die Wahl des Schlüssel als hinreichend zufällig betrachtet werden kann.

Beweis

Um die Korrektheit des RSA-Verfahrens zu zeigen, muss folgende Kongruenz bewiesen werden:

$a^\{ed\}\; \backslash equiv\; a\; \backslash mod\; N$ für alle $a$ mit

Dabei ist

• $a$ der Klartext, der ver- und danach wieder entschlüsselt wird,
• $N=pq$ das Produkt zweier Primzahlen $p\backslash neq\; q$,
• $e$ der Verschlüsselungsexponent mit $\backslash operatorname\{ggT\}(e,\backslash varphi(N))\; =\; 1$,
• $d$ der eindeutige Entschlüsselungsexponent mit $ed\backslash equiv\; 1\; \backslash mod\{\backslash varphi(N)\}$.

Die Aussage, dass $ed\backslash equiv\; 1\; \backslash mod\{\backslash varphi(N)\}$ gilt, ist gleichbedeutend mit der Existenz einer ganzen Zahl $u$ mit $u\backslash varphi(N)=ed-1$. Außerdem ist $\backslash varphi(N)=(p-1)(q-1)$ wegen der Multiplikativität von $\backslash varphi$.

Nach Wahl von $a$ und $N$ ist nun $\backslash operatorname\{ggT\}(a,N)\backslash in\backslash \{1,\; p,\; q\backslash \}$, denn für $a\; \backslash equiv\; 0\; \backslash mod\; N$ ist nichts zu zeigen.

Im Fall $\backslash operatorname\{ggT\}(a,N)=1$ gilt

$a^\{ed\}\; \backslash equiv\; a^\{u\backslash ,\backslash varphi(N)+1\}\; \backslash equiv\; (a^\{\backslash varphi(N)\})^ua\; \backslash equiv\; a\; \backslash mod\; N$,

da $a^\{\backslash varphi(N)\}\; \backslash equiv\; 1\; \backslash mod\; N$ nach dem Satz von Euler.

Im Fall $\backslash operatorname\{ggT\}(a,N)\backslash neq\; 1$ dürfen wir ohne Einschränkung annehmen, dass $\backslash operatorname\{ggT\}(a,N)=p$. Wir erhalten folgende zwei Kongruenzen:

• $a^\{ed\}\; \backslash equiv\; a\; \backslash mod\; p$, da $a\; \backslash equiv\; 0\; \backslash mod\; p$ wegen $p|a$
• $a^\{ed\}\; \backslash equiv\; a^\{u\backslash ,\backslash varphi(N)+1\}\; \backslash equiv\; a^\{u(p-1)(q-1)+1\}\; \backslash equiv\; (a^\{q-1\})^\{u(p-1)\}a\; \backslash equiv\; a\; \backslash mod\; q$, da $a^\{q-1\}\; \backslash equiv\; 1\; \backslash mod\; q$ nach dem kleinen Satz von Fermat

Mit dem chinesischem Restsatz folgt nun $a^\{ed\}\; \backslash equiv\; a\; \backslash mod\; N$.

Optimierung

Es ist nicht notwendig $e$ derart zu bestimmen, dass die Kongruenz $\backslash operatorname\{ggT\}(e,\backslash varphi(n))\; =\; 1$ erfüllt wird.

Vielmehr reicht es aus $e$ derart zu bestimmen, dass die Kongruenz $\backslash operatorname\{ggT\}(e,\; \backslash operatorname\{kgV\}(p-1,\; q-1))\; =\; 1$ erfüllt wird. Der Vorteil bei diesem Verfahren liegt in der Größe des Modulus für die Berechnung von $d$, weil dieser nun kleiner geworden ist und dadurch die Berechnung von $d$ schneller durchgeführt werden kann.

Für die Zahlen $p=11$ und $q=13$ ergibt $\backslash varphi(p\; \backslash cdot\; q)$ 120. Das kleinste gemeinsame Vielfache von $p-1$ und $q-1$ ist lediglich 60 (es muss ja ein Teiler von 120 sein) und somit maximal halb so groß wie das Ergebnis der φ-Funktion, da $p-1$ und $q-1$ zumindest den Faktor 2 gemeinsam haben. In Binärdarstellung ist somit das kgV zumindest um ein Bit kürzer.

Beweis

Der Beweis läuft großteils analog zum Beweis für das originale RSA-System. Es existiert lediglich folgender Unterschied.

Da das kgV ein Vielfaches von $p-1$ und $q-1$ ist, gelten folgende zwei Regeln:

• $\backslash operatorname\{kgV\}(p-1,q-1)=\; r\; \backslash cdot\; (p-1)$
• $\backslash operatorname\{kgV\}(p-1,q-1)=\; s\; \backslash cdot\; (q-1)$

Wir unterscheiden drei Fälle.

Fall 1: $\backslash operatorname\{ggT\}(a,n)=1$

Hierbei erhalten wir zwei Kongruenzen:

• $a^\{e\; \backslash cdot\; d\}\; \backslash equiv\; a^\{u\backslash cdot\; \backslash operatorname\{kgV\}(p-1,q-1)+1\}\; \backslash equiv\; a^\{u\backslash cdot\; \backslash operatorname\{kgV\}(p-1,q-1)\}\; \backslash cdot\; a\; \backslash equiv\; a^\{u\backslash cdot\; (p-1)\backslash cdot\; r\}\; \backslash cdot\; a\; \backslash equiv\; a\; \backslash mod\; p$, nach dem kleinen Satz von Fermat
• $a^\{e\; \backslash cdot\; d\}\; \backslash equiv\; a^\{u\backslash cdot\; \backslash operatorname\{kgV\}(p-1,q-1)+1\}\; \backslash equiv\; a^\{u\backslash cdot\; \backslash operatorname\{kgV\}(p-1,q-1)\}\; \backslash cdot\; a\; \backslash equiv\; a^\{u\backslash cdot\; s\backslash cdot\; (q-1)\}\; \backslash cdot\; a\; \backslash equiv\; a\; \backslash mod\; q$, nach dem kleinen Satz von Fermat

Nach dem chinesischem Restsatz folgt nun $a^\{e\; \backslash cdot\; d\}\; \backslash equiv\; a\; \backslash mod\; n$.

Fall 2: $p|a$

• $a^\{e\; \backslash cdot\; d\}\; \backslash equiv\; 0\; \backslash equiv\; a\; \backslash mod\; p$, da $a$ von $p$ geteilt wird.
• $a^\{e\; \backslash cdot\; d\}\; \backslash equiv\; a^\{u\backslash cdot\; \backslash operatorname\{kgV\}(p-1,q-1)+1\}\; \backslash equiv\; a^\{u\backslash cdot\; \backslash operatorname\{kgV\}(p-1,q-1)\}\; \backslash cdot\; a\; \backslash equiv\; a^\{u\backslash cdot\; s\backslash cdot\; (q-1)\}\; \backslash cdot\; a\; \backslash equiv\; a\; \backslash mod\; q$, nach dem kleinen Satz von Fermat

Nach dem Chinesischen Restsatz folgt wiederum $a^\{e\; \backslash cdot\; d\}\; \backslash equiv\; a\; \backslash mod\; n$.

Fall 3: $q|a$

analog zu Fall 2

$\backslash Rightarrow\; q.e.d$

RSA ist kein Primzahltest

Wenn $p$ und $q$ Primzahlen sind, funktioniert das RSA-Verfahren. Umgekehrt kann aber aus dem funktionierenden RSA-Verfahren nicht geschlossen werden, dass $p$ und $q$ Primzahlen sind, denn bei Carmichael-Zahlen funktioniert das Verfahren, obwohl Carmichael-Zahlen keine Primzahlen sind.

Beweis

Gegeben:

• $n=p\; \backslash cdot\; c$, wobei $c=\backslash prod\; q\_i$ eine Carmichael-Zahl ist
• $q\_i\; -\; 1\; |\; c-1$, Eigenschaft von Carmichael-Zahlen
• $\backslash varphi(n)=(p-1)(c-1)$, fälschliche Annahme, da angenommen wird, dass $c$ eine Primzahl ist
• $(p-1)(c-1)=(q\_i-1)\backslash cdot\; b\_i$, weil $c-1$ von $q\_i-1$ geteilt wird
• $\backslash operatorname\{ggT\}(e,(p-1)(c-1))=1$
• $d\backslash cdot\; e\; \backslash equiv\; 1\; \backslash mod\{(p-1)(c-1)\}$

Zu zeigen:

$a^\{d\backslash cdot\; e\}\; \backslash equiv\; a\; \backslash mod\; n$

Betrachten wir nun den Primteiler $p$

Fall 1: $p\; |\; a$

$a^\{d\backslash cdot\; e\}\; \backslash equiv\; 0\; \backslash equiv\; a\; \backslash mod\; p$

Fall 2: $p\; \backslash nmid\; a$

$a^\{d\backslash cdot\; e\}\; \backslash equiv\; a^\{(p-1)(c-1)\}\; \backslash cdot\; a\; \backslash equiv\; a\; \backslash mod\; p$

Betrachten wir nun die Primteiler $q\_i$ von $c\_i$

Fall 1: $q\_i\; |\; a$

$a^\{d\backslash cdot\; e\}\; \backslash equiv\; 0\; \backslash equiv\; a\; \backslash mod\{q\_i\}$

Fall 2: $q\_i\; \backslash nmid\; a$

$a^\{d\backslash cdot\; e\}\; \backslash equiv\; a^\{(q\_i-1)(b\_i)\}\; \backslash cdot\; a\; \backslash equiv\; a\; \backslash mod\{q\_i\}$

Unabhängig von der Zahl $a$ folgt aus dem dem chinesischem Restsatz, dass $a^\{e\; \backslash cdot\; d\}\; \backslash equiv\; a\; \backslash mod\; n$.

$\backslash Rightarrow\; q.e.d$

Dieser Beweis hält offensichtlich auch dann stand, wenn $n$ das Produkt von zwei Carmichael-Zahlen ist.

Vollständiges Beispiel

---

Vorarbeiten

Die oben genannten Schritte sollen nun an einem vollständigen Beispiel erläutert werden. Um einen Text zu verschlüsseln, müssen zunächst Buchstaben in Zahlen umgewandelt werden. Dazu verwendet man in der Praxis zum Beispiel den ASCII-Code. Hier sei willkürlich die folgende Zuordnung gewählt: A=01 B=02 C=03 usw. (00 = Leerzeichen) Darüberhinaus sei angenommen, dass jeweils drei Zeichen zu einer Zahl zusammengefasst werden. Die Buchstabenfolge AXT wird also zu 012420. Die kleinste zu verschlüsselnde Zahl ist dann 000000 (drei Leerzeichen), die größte 262626 (ZZZ). Der Modulus $N\; =\; p\; \backslash cdot\; q$ muss also größer 262626 sein.

Klartext: W I K I P E D I A Kodierung: 230911 091605 040901

Schlüsselerzeugung

Zunächst werden geheim zwei Primzahlen gewählt, beispielsweise $p=307$ und $q=859$. Damit ergibt sich:

$N\; =\; p\; \backslash cdot\; q\; =\; 263713$

$\backslash varphi(N)\; =\; (p-1)\; \backslash cdot\; (q-1)\; =\; 262548$

$e\; =\; 1721$ (zufällig, teilerfremd zu $\backslash varphi(N)$)

$d\; =\; 1373$ (das multiplikative Inverse zu $e\; \backslash bmod\; \backslash varphi(N)$ mit Hilfe des Erweiterten euklidischen Algorithmus)

Öffentlicher Schlüssel: $e\; =\; 1721$ und $N\; =\; 263713$

Geheimer Schlüssel: $d\; =\; 1373$ und $N\; =\; 263713$

Verschlüsselung

C_n = K_n^e mod N für n=1,2,3(,...) C₁ = 230911¹⁷²¹ mod 263713 C₁ = 001715 C₂ = 091605¹⁷²¹ mod 263713 C₂ = 184304 C₃ = 040901¹⁷²¹ mod 263713 C₃ = 219983

Entschlüsselung

K_n = C_n^d mod N für n=1,2,3(,...) K₁ = 001715¹³⁷³ mod 263713 K₁ = 230911 K₂ = 184304¹³⁷³ mod 263713 K₂ = 091605 K₃ = 219983¹³⁷³ mod 263713 K₃ = 040901

Signatur (Verschlüsselung mit dem geheimen Schlüssel)

C_n = K_n^d mod N C₁ = 230911¹³⁷³ mod 263713 C₁ = 219611 C₂ = 091605¹³⁷³ mod 263713 C₂ = 121243 C₃ = 040901¹³⁷³ mod 263713 C₃ = 138570

Verifikation (Entschlüsselung mit dem öffentlichen Schlüssel)

K_n = C_n^e mod N K₁ = 219611¹⁷²¹ mod 263713 K₁ = 230911 K₂ = 121243¹⁷²¹ mod 263713 K₂ = 091605 K₃ = 138570¹⁷²¹ mod 263713 K₃ = 040901

Anwendungsgebiete

---

• Internet- und Telefonie-Infrastruktur: X.509-Zertifikate
• Übertragungs-Protokolle: IPSec, TLS, SSH, WASTE
• E-Mail-Verschlüsselung: PGP, S/MIME
• Authentifizierung französischer Telefonkarten
• Kartenzahlung: EMV

Siehe auch

---

• Tabelle mathematischer Symbole

Literatur

---

• c't 25/99, Story „Der Dialog der Schwestern“ Liegt auch dem E-Learning-Programm CrypTool bei.
• Alexander May: Computing the RSA Secret Key is Deterministic Polynomial Time Equivalent to Factoring, in Advances in Cryptology (Crypto 2004), Lecture Notes in Computer Science Volume 3152, pages 213-219, Springer Verlag, 2004.
• Dan Boneh: Twenty Years of Attacks on the RSA Cryptosystem, in Notices of the American Mathematical Society (AMS), Vol. 46, No. 2, pp. 203--213, 1999.

Weblinks

---

• Übersicht über erfolgreiche Faktorisierungen im RSA-Wettbewerb
• Erklärung von RSA vom Fachbereich Mathematik der Universität Wuppertal
• Skript zu Zahlentheorie bis RSA
• Bekannte Attacken auf RSA-Verfahren (in englischer Sprache)
• Zahlentheoretische Arbeit über RSA
• Faktorisierung von RSA-200

Verschlüsselungsverfahren

RSA | RSA | RSA | RSA | RSA | RSA | RSA | Rivest Shamir Adleman | RSA | RSA | RSA-eljárás | RSA | RSA | RSA | RSA暗号 | RSA 암호 | RSA | RSA (cryptografie) | RSA (kryptografia) | RSA | RSA | RSA | RSA | RSA | RSA | Açık anahtarlı şifreleme | RSA (mã hóa) | RSA加密演算法