RSA-Kryptosystem

RSA (Rivest–Shamir–Adleman) ist ein asymmetrisches kryptographisches Verfahren, das sowohl zum Verschlüsseln als auch zum digitalen Signieren verwendet werden kann.^[1] 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.

Geschichte

Nachdem Whitfield Diffie und Martin Hellman im Jahr 1976 eine Theorie zur Public-Key-Kryptografie veröffentlicht hatten,^[2] versuchten die drei Mathematiker Rivest, Shamir und Adleman am MIT, die Annahmen von Diffie und Hellman 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 1977 RSA, das erste veröffentlichte asymmetrische Verschlüsselungsverfahren. Der Name RSA steht für die Anfangsbuchstaben ihrer Familiennamen. Da Adleman seinen Anteil als gering einschätzte und anfangs gar nicht als Autor genannt werden wollte, kam es zur nicht-alphabetischen Reihenfolge der Autoren und damit zur Abkürzung RSA^[3].

Bereits Anfang der 1970er Jahre war im britischen GCHQ von Ellis, Cocks und Williamson ein ähnliches asymmetrisches Verfahren entwickelt worden, welches aber keine große praktische Bedeutung erlangte und aus Geheimhaltungsgründen nicht wissenschaftlich publiziert wurde.^[4] RSA konnte daher 1983 zum Patent angemeldet werden,^[5] obgleich es nicht das erste Verfahren dieser Art war. Das Patent erlosch am 21. September 2000.

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

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

Der öffentliche Schlüssel (public key) ist ein Zahlenpaar Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (e,N)} und der private Schlüssel (private key) ist ebenfalls ein Zahlenpaar Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (d,N)} , wobei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N} bei beiden Schlüsseln gleich ist. Man nennt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N} den RSA-Modul, Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle e} den Verschlüsselungsexponenten und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d} den Entschlüsselungsexponenten. Diese Zahlen werden durch das folgende Verfahren erzeugt:

Wähle zufällig und stochastisch unabhängig zwei Primzahlen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p \neq q} . Diese sollen die gleiche Größenordnung haben, aber nicht zu dicht beieinander liegen, sodass der folgende Rahmen ungefähr eingehalten wird: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 0{,}1<|\log_2 p -\log_2 q|<30} .^[6] (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.)
Berechne den RSA-Modul
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N = p \cdot q}
Berechne die Eulersche φ-Funktion von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N}
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \varphi(N) = (p-1) \cdot (q-1)}
Wähle eine zu Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \varphi(N)} teilerfremde Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle e} , für die gilt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1 < e < \varphi(N)} .
Berechne den Entschlüsselungsexponenten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d} als multiplikativ Inverses von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle e} bezüglich des Moduls Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \varphi(N)} (kann mit dem erweiterten euklidischen Algorithmus erfolgen). Es soll also die Kongruenz gelten:
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle e \cdot d \equiv 1\pmod{\varphi(N)}}

Die Zahlen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p} , Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle e} , Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N} zu rekonstruieren. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p, q, \varphi(N)} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d} müssen geheim gehalten werden.

Da die Primzahltests inzwischen ausreichend schnell sind, wählt man heutzutage zuerst einen kleinen Exponenten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle e} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2^{16} < e < 2^{64}} und verwirft bei der Erzeugung die Primzahlen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p, q} , für die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p-1, q-1} nicht teilerfremd zu Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle e} sind. Die Wahl eines Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle e} kleiner als die Fermat-Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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.^[7]

Wenn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d} weniger als ein Viertel der Bits des RSA-Moduls hat, kann Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d} – sofern nicht bestimmte Zusatzbedingungen erfüllt sind – mit einem auf Kettenbrüchen aufbauenden Verfahren effizient ermittelt werden.^[8] Bei der Wahl eines Exponenten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle e} kleiner als Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2^{64}} ist diese Möglichkeit jedoch ausgeschlossen.

Beispiel

Wir wählen den Exponenten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle e = 23} .
Wir wählen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p = 11} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q = 13} für die beiden Primzahlen. Die Zahlen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p-1 = 10} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q-1 = 12} sind teilerfremd zum Exponenten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle e = 23} .
Der RSA-Modul ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N = p \cdot q = 143} . Damit bilden Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle e = 23} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N = 143} den öffentlichen Schlüssel.
Die eulersche φ-Funktion hat den Wert Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \varphi(N) = \varphi(143) = (p-1)(q-1) = 120} .
Berechnung der Inversen zu Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle e} modulo Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \varphi(N)} :
Es gilt: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle e \cdot d + k \cdot \varphi(N) = 1 = \operatorname{ggT}(e,\varphi(N))} ,
im konkreten Beispiel: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 23 \cdot d + k \cdot 120 = 1 = \operatorname{ggT}(23,120)} .
Mit dem erweiterten euklidischen Algorithmus berechnet man nun die Faktoren Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d=47} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k=-9} , und somit ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d = 47} der private Schlüssel, während Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} nicht weiter benötigt wird.

Verschlüsseln von Nachrichten

Verschlüsselung

Um eine Nachricht Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} zu verschlüsseln, verwendet der Absender die Formel

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c \equiv m^e\pmod N}

und erhält so aus der Nachricht Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} den Geheimtext Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c} . Die Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} muss dabei kleiner sein als der RSA-Modul Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N} .

Beispiel

Es soll die Zahl 7 verschlüsselt werden. Der Sender benutzt den veröffentlichten Schlüssel des Empfängers Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N = 143} , Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle e = 23} und rechnet

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2 \equiv 7^{23}\pmod{143}}

Das Chiffrat ist also Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c = 2} .

Entschlüsseln von Nachrichten

Entschlüsselung

Der Geheimtext Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c} kann durch modulare Exponentiation wieder zum Klartext Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} entschlüsselt werden. Der Empfänger benutzt die Formel

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m \equiv c^d\pmod N}

mit dem nur ihm bekannten Wert Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d} sowie Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N} .

Beispiel

Für gegebenes Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c = 2} wird berechnet

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 7 \equiv 2^{47}\pmod{143}}

Der Klartext ist also Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m = 7} .

Signieren von Nachrichten

Um eine Nachricht Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} zu signieren, wird vom Sender auf die Nachricht die RSA-Funktion mit dem eigenen privaten Schlüssel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d} angewendet. Zum Prüfen wendet der Empfänger auf die Signatur Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m^d \bmod\ N} mit Hilfe des öffentlichen Schlüssels des Senders Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle e} die Umkehrfunktion an und vergleicht diese mit der zusätzlich übermittelten unverschlüsselten Nachricht Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m_1^d} , Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m_2^d} vor, so kann ein Angreifer daraus durch Multiplizieren die Signatur der Nachricht Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m_1m_2} berechnen. Sogar aus nur einer Signatur Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m^d} kann ein Angreifer beliebig viele Nachrichten-Signatur-Paare erzeugen: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (m\cdot c^e,m^d\cdot c)} ist ein solches Paar für beliebige Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c} .

Dieses Problem kann umgangen werden, indem nicht die Nachricht selbst signiert wird. Stattdessen wird mit einer zusätzlich zum Signaturverfahren spezifizierten kollisionsresistenten Hashfunktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle H} der Hash-Wert Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle H(m)} der Nachricht Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle h'} . Diesen vergleicht er mit dem von ihm selbst gebildeten Hashwert Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle H(m)} der ihm vorliegenden Nachricht Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} . Wenn beide Werte Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N} gleichzeitig in den zwei kleineren Gruppen der Größe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N} , der RSA-Modul,
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d} , der Entschlüsselungsexponent,
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p} , die erste Primzahl,
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q} , die zweite Primzahl,
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d_p = d \bmod (p-1)} , häufig dmp1 genannt,
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d_q = d \bmod (q-1)} , häufig dmq1 genannt und
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_{Inv} = q^{-1} \bmod p} , häufig iqmp genannt.

Eine Nachricht Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} wird dann wie folgt signiert:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m_1 = m^{d_p} \bmod p}
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m_2 = m^{d_q} \bmod q}
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s = (q_{Inv}(m_1-m_2) \bmod p)q + m_2}

Aus der letzten Gleichung sieht man sofort, dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s \bmod q = m_2} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s \bmod p = q_{Inv}q(m_1-m_2) + m_2 \bmod p = m_1} . Die Signatur Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s} stimmt also sowohl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \bmod p} als auch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \bmod q} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m^d} überein, daher ist nach dem Chinesischen Restsatz Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s = m^d \bmod N} . (Bemerkung: Die Identität Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s = m^d \bmod p} sieht man so: Modulo p gilt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s = m^d \bmod q} .)

RSA ist kein Primzahltest

Wenn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p \neq q} Primzahlen sind, funktioniert das RSA-Verfahren. Umgekehrt kann aber aus dem funktionierenden RSA-Verfahren nicht geschlossen werden, dass der Modul Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N} das Produkt zweier Primzahlen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q} ist, denn mit Carmichael-Zahlen funktioniert das Verfahren auch.

Sicherheit

Public-Key-Verschlüsselungs-Verfahren wie RSA werden in der Praxis immer als hybride Verfahren in Verbindung mit symmetrischen Verfahren verwendet. Bei der Analyse der Sicherheit im praktischen Einsatz müssen die Sicherheit des Public-Key-Verfahrens und die praktische Sicherheit des Gesamtsystems betrachtet werden. Angriffe auf das RSA-Verfahren erfolgen oft über Seitenkanäle. Das Gesamtsystem kann unsicher sein, wenn nur eine Komponente, beispielsweise ein Computer, kompromittiert wurde.

Beziehung zwischen RSA und dem Faktorisierungsproblem

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

RSA-Problem (Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathrm{RSAP}} ): Gegeben sind der öffentliche Schlüssel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (N, e)} sowie der Geheimtext Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c} . Gesucht wird der Klartext Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} , wobei gilt: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m^e\equiv c\pmod{N}}

Das Problem liegt hier in der Schwierigkeit, Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle e} -te Wurzeln modulo Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N} zu ziehen, was zur Bestimmung der Nachricht Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} notwendig ist.

RSA-Schlüsselproblem (Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathrm{RSAP^*}} ): Gegeben ist der öffentliche Schlüssel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (N, e)} . Gesucht wird der geheime Schlüssel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d} , wobei gilt: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle ed\equiv 1\pmod{\varphi(N)}}

Das Problem liegt hier in der Schwierigkeit, die Eulersche φ-Funktion von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N} ohne Kenntnis der Faktoren p und q zu berechnen.

Folgende Beziehungen zwischen den RSA-Problemen und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathrm{FACTORING}} , dem Faktorisierungsproblem, sind bekannt:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathrm{RSAP} \leq_p \mathrm{RSAP^*} =_p \mathrm{FACTORING}}

Die Beziehung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathrm{RSAP} \leq_p \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 zurzeit unbekannt.

Auch die Beziehung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathrm{RSAP^*} \leq_p \mathrm{FACTORING}} ist trivial, denn wenn man Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N=pq} faktorisiert hat, kann man damit leicht Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathrm{FACTORING} \leq_p \mathrm{RSAP^*}} ist schon lange ein probabilistischer Polynomialzeitalgorithmus bekannt. Vor kurzem wurde gezeigt, dass sich diese Reduktion im balancierten RSA (d. h. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Gitterbasenreduktion 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N} . Wegen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathrm{RSAP} \leq_p \mathrm{FACTORING}} ist im Fall der zusätzlichen Kenntnis eines Geheimtexts die Schwierigkeit des Faktorisierungsproblems von zentralem Interesse.

Schwierigkeit des Faktorisierungsproblems

Man möchte Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N=pq} für sehr große Primzahlen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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.

Mit dem Quadratischen Sieb wurde 1994 die Zahl RSA-129 mit 129 Dezimalstellen in 8 Monaten von ca. 600 Freiwilligen faktorisiert. Mit der Methode des Zahlkörpersiebs wurde im Jahr 2005 von Wissenschaftlern der Friedrich-Wilhelms-Universität Bonn die im Rahmen der RSA Factoring Challenge von RSA Laboratories vorgegebene 200-stellige Dezimalzahl RSA-200 in ihre zwei großen Primfaktoren zerlegt^[9]. Die ersten RSA-Zahlen bis RSA-500 wurden entsprechend der Anzahl der Dezimalstellen benannt, weitere RSA-Zahlen nach der Anzahl der Binärstellen. 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.^[10] Obwohl mittlerweile für das Faktorisieren der RSA-Challenge-Zahlen keine Prämien mehr gezahlt werden, wurde im Dezember 2009 die Zahl RSA-768 faktorisiert.^[11]

Für die Faktorisierung von RSA-1024 (309 Dezimalstellen) oder gar RSA-2048 (617 Dezimalstellen) waren 100.000 $ bzw. 200.000 $ ausgelobt; die RSA Laboratories haben im Mai 2007 die RSA Factoring Challenge beendet, nachdem die o. g. Wissenschaftler der Universität Bonn im selben Monat eine 1039-Bit Mersennezahl (312 Dezimalstellen) faktorisiert hatten.^[12] Aufgrund der ungleichen Stellenzahl der Faktoren war das aber wesentlich leichter, als eine RSA-Zahl gleicher Länge zu faktorisieren. Die wachsende Rechenleistung moderner Computer stellt für die kurzfristige Sicherheit von RSA im Wesentlichen kein Problem dar, zumal diese Entwicklung vorhersehbar ist: Der Nutzer kann bei der Erzeugung seines Schlüssels darauf achten, dass der während der Dauer der beabsichtigten Verwendung nicht faktorisiert werden kann. Nicht vorhersehbare Entwicklungen wie die Entdeckung deutlich schnellerer Algorithmen oder gar Schaffung eines leistungsfähigen Quantencomputers, der die Faktorisierung von Zahlen durch Verwendung des Shor-Algorithmus effizient durchführen könnte, bergen zumindest für die mittel- und langfristige Sicherheit der verschlüsselten Daten gewisse Risiken.

Zum konkreten Sicherheitsniveau bestimmter Schlüssellängen gibt es unterschiedliche Aussagen.^[13] Laut Bundesnetzagentur sind für RSA-basierte Signaturen bis Ende 2020 Schlüssel mit einer Mindestlänge von 1976 Bit geeignet (Empfehlung 2048 Bit). Für Signaturverfahren nach den Anforderungen aus § 17 Abs. 1 bis 3 SigG, „für die die besten bekannten Angriffe auf dem Problem der Faktorisierung großer Zahlen oder auf dem Problem der Berechnung diskreter Logarithmen in endlichen Körpern beruhen (RSA und DSA), werden Schlüssellängen von mindestens 3 000 Bit verpflichtend werden“, um perspektivisch mindestens ein Sicherheitsniveau von 120 Bit zu etablieren.^[6]

Schwierigkeit des RSA-Problems

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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d<\tfrac13\sqrt[4]{N}} . Wiener verwendete dabei die Tatsache, dass unter der Abschätzung für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d} der Bruch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tfrac{k}{d}} (für eine ganze Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} ) in der Kettenbruchentwicklung von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tfrac{e}{N}} auftaucht. Die Schranke wurde mit Mitteln der Gitterbasenreduktion auf Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d<N^{0{,}292}} verbessert.

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üsselungsexponenten (etwa Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Gitterbasenreduktion beruht.

Angriffe gegen das unmodifizierte RSA-Verfahren („Textbook-RSA“)

RSA ist in der oben beschriebenen Version, die auch als „Textbook-RSA“ bekannt ist, weder als Verschlüsselungs- noch als Signaturverfahren geeignet, da es in beiden Fällen auf gravierende Weise unsicher ist und als Signaturverfahren auch keine langen Nachrichten signieren kann.

Die RSA-Verschlüsselung ist deterministisch. Das erlaubt es einem Angreifer, einen Klartext zu raten, ihn mit dem öffentlichen Schlüssel zu verschlüsseln und dann mit einem Chiffrat zu vergleichen. Dies kann insbesondere bei sehr kurzen Nachrichten wie “Ja” und „Nein“ sehr praktikabel und verheerend sein. Hieraus folgt, dass unmodifiziertes RSA nicht IND-CPA-sicher ist, heute eine absolute Minimalanforderung an Verschlüsselungsverfahren.

Wenn der Klartext Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} und der Verschlüsselungsexponent Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle e} so klein sind, dass sogar Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c = m^e < N} ist, dann kann ein Angreifer die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle e} -te Wurzel aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c} ziehen und das Chiffrat auf diese Weise entschlüsseln. Wurzelziehen ist nur modulo einer großen Zahl schwierig, aber in diesem Fall kann Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c} als ganze Zahl betrachtet werden.

Wenn dieselbe Nachricht Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} zu mehreren Empfängern geschickt wird, die zwar alle unterschiedliche (und teilerfremde) Moduli Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N_i} benutzen, aber als öffentlichen Schlüssel den gleichen Exponenten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle e} , dann kann aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle e} Nachrichten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m^e \bmod N_1, \ldots, m^e \bmod N_l} mit dem Chinesischen Restsatz Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m^e \bmod \prod N_i} berechnet werden. Weil Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m^e < \prod N_i} (nach Voraussetzung ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m < N_i} für alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i} ), kann diese Zahl wieder als in den ganzen Zahlen liegend aufgefasst werden und Wurzelziehen ist dort einfach. Dieser Angriff wird nach seinem Entdecker Johan Håstad als „Håstads Angriff“ bezeichnet.^[14]

Da die RSA-Funktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x \mapsto x^d \bmod N} multiplikativ ist (d. h. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (xy)^d =x^dy^d \bmod N} gilt), kann man aus jedem Chiffrat Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m^e} ein weiteres gültiges Chiffrat Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m^er^e = (mr)^e} erzeugen. Wenn man den Besitzer des zugehörigen geheimen Schlüssels davon überzeugen kann, diese Zahl zu entschlüsseln oder zu signieren, kann man aus dem Ergebnis Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle mr} leicht Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} gewinnen.

Dieselbe Eigenschaft erlaubt auch einen Angriff auf das Signaturverfahren. Aus bekannten Klartext-Signaturpaaren Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s_1 = m_1^d, \ldots, s_k = m_k^d} lassen sich weitere gültige Signaturen

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s=\prod s_i\bmod N} zu Nachrichten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m=\prod m_i\bmod N}

berechnen.

Padding

Um solche Angriffe zu verhindern, werden bei RSA-Verschlüsselung und RSA-Signatur sogenannte Padding-Verfahren eingesetzt. Standards für Padding-Verfahren für RSA werden z. B. in PKCS#1 oder ISO 9796 definiert. Diese nutzen aus, dass die Länge des Klartextes bzw. Hash-Wertes deutlich kleiner als die Länge von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N} ist, und fügen dem Klartext bzw. dem Hash-Wert vor der Verschlüsselung oder Signatur eine Zeichenfolge R mit vorgegebener Struktur an, die unter mehreren möglichen zufällig gewählt wird und dadurch das Chiffrat randomisiert. Es wird also die RSA-Funktion nicht auf die Nachricht Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M} oder auf den Hash-Wert Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle h(M)} angewendet, sondern auf den Klartext (bzw. seinem Hashwert) mit angehängtem Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R} . In der Regel enthält Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R} eine Angabe über die Länge der Nachricht oder des Hash-Wertes oder eine eindeutige Zeichenfolge, die den Beginn von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R} kennzeichnet. Dies erleichtert nicht nur die Dekodierung, sondern erschwert auch Angriffe. Padding-Verfahren können für die Berechnung von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R} auch Zufallszahlen und Hashfunktionen verwenden. Einige moderne Paddingverfahren – beispielsweise das Optimal Asymmetric Encryption Padding (OAEP) oder das Probabilistic Signature Scheme (PSS) – verwenden kryptographische Hashfunktionen, um den Klartext vor der Verschlüsselung weiter zu randomisieren, und sind unter idealisierenden Annahmen an die verwendete Hashfunktion beweisbar sicher unter der RSA-Annahme.^[15]^[16]

Chosen-Ciphertext-Angriff

Daniel Bleichenbacher stellte 1998 einen Angriff auf die in PKCS#1 v1 spezifizierte RSA-Verschlüsselung vor. Dabei nutzte er aus, dass PKCS#1 v1 ein Nachrichtenformat vorgibt und einige Implementierungen nach dem Entschlüsseln Fehlermeldungen ausgeben, falls dieses Format nicht eingehalten wurde. Um den Angriff gegen ein Chiffrat Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c} durchzuführen, wählt man eine Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s} und berechnet daraus ein neues Chiffrat Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s^e c} . Bei dem Nachrichtenformat sind die ersten zwei Bytes 00 und 02, wenn also keine Fehlermeldung kommt, weiß man, dass sowohl bei der ursprünglichen Nachricht Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} als auch bei der neuen Nachricht Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle sm} die ersten beiden Bytes 00 02 sind. Mehrfache Wiederholung mit geschickt gewählten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s} erlauben es, nach und nach den gesamten Klartext aufzudecken.^[17] RSA nach PKCS#1 ab Version 2 ist immun gegen diesen Angriff.

Sicherheit hybrider Verfahren

RSA wird aus Effizienzgründen in der Regel in Hybridverfahren mit symmetrischen Verfahren kombiniert. Zur hybriden Verschlüsselung wird zufällig ein Sitzungsschlüssel für ein symmetrisches Verschlüsselungsverfahren generiert, der dann per RSA verschlüsselt und zusammen mit der Nachricht übertragen wird. Zum Signieren wird nicht die gesamte Nachricht, sondern nur ein Hash-Wert signiert.

Für die Sicherheit von RSA sind Primzahlen mit mehreren hundert Dezimalstellen (mindestens 2048 Bit) erforderlich. Damit können symmetrische Schlüssel jeder üblichen Länge verschlüsselt werden. Gängige Verfahren zur symmetrischen Verschlüsselung basieren beispielsweise auf der Blockchiffre AES mit einer Schlüssellänge von 128, 192 oder maximal 256 Bit.

Eine sichere Hashfunktion wie SHA-2 erzeugt Hashwerte mit einer Länge von 224 bis 512 Bit. Damit lassen sich Signaturverfahren mittels RSA realisieren, die nur einen Signaturschritt benötigen.

Die Sicherheit des Gesamtsystems hängt sowohl im Fall der Verschlüsselung als auch der Signatur von der Sicherheit beider verwendeter Verfahren ab. Da bei RSA für ein ähnliches Sicherheitsniveau wie beim symmetrischen Verfahren deutlich längere Schlüssel nötig sind, wird die Sicherheit des Hybridverfahrens meistens von der Sicherheit des Public-Key-Verfahrens bestimmt.

Vollständiges Beispiel

Anmerkung

RSA direkt auf Texte anzuwenden, birgt erhebliche Risiken. RSA wird deshalb, anders als im Beispiel, in der Praxis praktisch nur in Kombination mit anderen Verfahren verwendet. (Siehe: Hybride Verschlüsselung und Abschnitt Angriffe gegen das unmodifizierte RSA-Verfahren.)
Um das Beispiel übersichtlich zu halten, wurden relativ kleine Primzahlen verwendet. Zur sicheren Verschlüsselung werden typischerweise mindestens 600-stellige Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N} empfohlen.^[18]

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über hinaus 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 Modul Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N = p \cdot q} muss also größer als 262626 sein.

Klartext:   W  I  K   I  P  E   D  I  A
Kodierung: 23 09 11  09 16 05  04 09 01

Schlüsselerzeugung

Zunächst werden geheim zwei Primzahlen gewählt, beispielsweise Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p=307} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q=859} . Damit ergibt sich:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N = p \cdot q = 263713}

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \varphi(N) = (p-1) \cdot (q-1) = 262548}

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle e = 1721} (zufällig, teilerfremd zu Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \varphi(N)} )

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d = 1373} (das multiplikative Inverse zu Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle e \pmod{\varphi(N)}} mit Hilfe des erweiterten euklidischen Algorithmus)

Öffentlicher Schlüssel:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle e = 1721} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N = 263713}

Privater Schlüssel:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d = 1373} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N = 263713}

Verschlüsselung

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

Entschlüsselung

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

Signatur

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

Verifikation

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

Die Berechnung der modularen Exponentiation kann durch binäre Exponentiation (Square-and-multiply) beschleunigt werden.

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 7^{23} \ \bmod \ 143 \ = \ \left(\left(\left( 7^2 \right)^2\cdot 7\right)^2\cdot 7\right)^2\cdot 7 \ \bmod \ 143 = 2}

Dabei wendet man nach jedem Rechenschritt auf die zu handhabenden Zahlen die Modulo-Operation „mod“ an, um die Zwischenergebnisse möglichst klein zu halten. Aus dem Klartext „7“ erhalten wir somit den Geheimtext „2“.

Programmierung

Das folgende Programm in der Programmiersprache C++ zeigt die Implementierung des RSA-Verfahrens für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p=307} , Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q=859} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle e = 1721} mithilfe des erweiterten euklidischen Algorithmus, der den privaten Schlüssel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d = 1373} erzeugt. Bei der Ausführung des Programms wird die Hauptfunktion main verwendet, die den verschlüsselten Text und den entschlüsselten Text (in diesem Beispiel Werde Mitglied bei Wikipedia!) auf der Konsole ausgibt.

#include <iostream>
using namespace std;

// Diese Funktion gibt den privaten Schlüssel d (das multiplikative Inverse von e modulo phi) mithilfe des [[Erweiterter euklidischer Algorithmus|erweiterten euklidischen Algorithmus]] zurück
int getPrivateKey(int e, int phi)
{
    int b = phi; // Deklaration der lokalen Variablen
    int d = 1;
    int u = 0;
    while (b != 0)
    {
        int q = e / b;
        int b1 = b; // Variable zum Zwischenspeichern
        b = e - q * b;
        e = b1;
        int u1 = u; // Variable zum Zwischenspeichern
        u = d - q * u;
        d = u1;
    }
    return d;
}

// Diese Funktion berechnet die Potenz a ^ b modulo n
int modularPower(int a, int b, int n)
{
    int result = 1;
    for (int i = 0; i < b; i++)
    {
        result *= a;
        result %= n;
    }
    return result;
}

// Diese Funktion verschlüsselt den Text mit dem Schlüssel e
string encryptTextWithRSA(string text, int n, int e)
{
    string encryptedText = "";
    for (int i = 0; i < text.length(); i++) // for-Schleife, die die Zeichen des Textes durchläuft
    {
        int c = modularPower(text[i], e, n); // Verschlüsselt ein Zeichen des Texts
        encryptedText += c;
    }
    return encryptedText;
}

// Diese Funktion entschlüsselt den Text mit dem Schlüssel d
string decryptTextWithRSA(string text, int n, int d)
{
    string decryptedText = "";
    for (int i = 0; i < text.length(); i++) // for-Schleife, die die Zeichen des Textes durchläuft
    {
        int m = modularPower(text[i], d, n); // Entschlüsselt ein Zeichen des Texts
        decryptedText += m;
    }
    return decryptedText;
}

// Hauptfunktion die das Programm ausführt
int main()
{
    int p = 307; // Intialsiert die Variablen für die Primzahlen p und q
    int q = 859;
    int n = p * q;
    int e = 1721; // Deklaration der lokalen Variablen für den öffentlichen Schlüssel
    int phi = (p - 1) * (q - 1);
    int d = getPrivateKey(e, phi); // Aufruf der Funktion, die den privaten Schlüssel (d = 1373) erzeugt
    string text = "Werde Mitglied bei Wikipedia!"; // Initialisiert den Klartext
    string ciphertext = encryptTextWithRSA(text, n, e); // Aufruf der Funktion zum Verschlüsseln
    cout << ciphertext << endl; // Ausgabe des verschlüsselten Texts auf der Konsole
    string plaintext = decryptTextWithRSA(ciphertext, n, d); // Aufruf der Funktion zum Entschlüsseln
    cout << plaintext << endl; // Ausgabe des entschlüsselten Texts auf der Konsole
}

Anwendung

Hybride Verfahren

RSA ist im Vergleich zu Verfahren wie 3DES und AES mindestens um den Faktor 100 langsamer. In der Praxis wird RSA daher meist nur zum Austausch eines Schlüssels für die symmetrische Verschlüsselung benutzt. Für die Verschlüsselung der Daten werden dann symmetrische Verfahren eingesetzt. Damit sind die Vorteile beider Systeme vereint: einfacher Schlüsselaustausch und effiziente Verschlüsselung.

Anwendungsgebiete

Internet- und Telefonie-Infrastruktur: X.509-Zertifikate
Übertragungs-Protokolle: IPsec, TLS, SSH, WASTE
E-Mail-Verschlüsselung: OpenPGP, S/MIME
Authentifizierung französischer Telefonkarten
Kartenzahlung: EMV
RFID-Chip auf dem deutschen Reisepass
Electronic Banking: HBCI

Literatur

Johannes Buchmann: Einführung in die Kryptographie. Springer-Verlag, Berlin 1999, ISBN 3-540-66059-3.
Der Dialog der Schwestern. In: c’t. Nr. 25, 1999 (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. Band 3152. Springer Verlag, 2004, S. 213–219.
Dan Boneh: Twenty Years of Attacks on the RSA Cryptosystem. In: Notices of the American Mathematical Society (AMS). Band 46, Nr. 2, 1999, S. 203–213.

Weblinks

Wikibooks: Beweisarchiv: Korrektheit des RSA-Kryptosystems – Lern- und Lehrmaterialien

Erklärung von RSA vom Fachbereich Mathematik der Universität Wuppertal
Einfache Erklärung von RSA mit Online-Beispielen von Hans-G. Mekelburg
Arbeit über RSA mit Schwerpunkt in der Informatik. (Nicht mehr online verfügbar.) Archiviert vom Original am 18. August 2012; abgerufen am 18. August 2012.
RSA-Codebeispiel in Scheme vom Massachusetts Institute of Technology
Beispiel zur RSA-Verschlüsselung vorgerechnet von Joachim Mohr
Interaktive Präsentation des RSA-Verfahrens von CrypTool
Whitfield Diffie and Martin E. Hellman: New Directions in Cryptography, IEEE Transactions on Information Theory, Vol. IT-22, No. 6, November 1976
Video: RSA: Einführung. Christian Spannagel 2012, zur Verfügung gestellt von der Technischen Informationsbibliothek (TIB), doi:10.5446/19815.
Video: RSA: Konstruktion der Schlüssel. Christian Spannagel 2012, zur Verfügung gestellt von der Technischen Informationsbibliothek (TIB), doi:10.5446/19816.
Video: RSA: Ver- und Entschlüsselung. Christian Spannagel 2012, zur Verfügung gestellt von der Technischen Informationsbibliothek (TIB), doi:10.5446/19817.
Video: RSA: Beispiel Teil 1. Christian Spannagel 2012, zur Verfügung gestellt von der Technischen Informationsbibliothek (TIB), doi:10.5446/19813.
Video: RSA: Beispiel Teil 2. Christian Spannagel 2012, zur Verfügung gestellt von der Technischen Informationsbibliothek (TIB), doi:10.5446/19814.

Einzelnachweise

↑ R.L. Rivest, A. Shamir, and L. Adleman: A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. (mit.edu [PDF]).
↑ Whitfield Diffie, Martin E. Hellman: New Directions in Cryptography. (stanford.edu [PDF]).
↑ Gina Kolata: Leonard Adleman; Hitting the High Spots Of Computer Theory. In: The New York Times. 13. Dezember 1994, ISSN 0362-4331 (nytimes.com).
↑ C. C. Cocks: A note on 'non-secret encryption'. 1973 (Memento vom 27. Februar 2008 im Internet Archive)
↑ Patent US4405829: Cryptographic communications system and method. Veröffentlicht am 20. September 1983, Anmelder: Massachusetts Institute of Technology, Erfinder: Ronald L. Rivest, Adi Shamir, Leonard Adleman.‌
↑ ^a ^b Bundesnetzagentur für Elektrizität, Gas, Telekommunikation, Post und Eisenbahnen: Bekanntmachung zur elektronischen Signatur nach dem Signaturgesetz und der Signaturverordnung (Übersicht über geeignete Algorithmen) vom 21. Januar 2014 (BAnz AT 20.02.2014 B4)
↑ D. Boneh: Twenty Years of Attacks on the RSA Cryptosystem. In: Notes of the AMS. Band 46, Nr. 2, Februar 1999, S. 203–213 (PDF).
↑ MJ Wiener: Cryptanalysis of short RSA secret exponents. In: IEEE Transactions on information theory. Band 36, Nr. 3, Mai 1990, S. 553–558, doi:10.1109/18.54902.
↑ RSA Labs: RSA-200 is factored! (Memento vom 18. November 2007 im Internet Archive)
↑ MathWorld: RSA-640 Factored
↑ RSA Labs: RSA-768 is factored!
↑ Archivierte Kopie (Memento vom 22. Februar 2015 im Internet Archive)
↑ http://www.keylength.com/en/compare/
↑ Johan Håstad: Solving Simultaneous Modular Equations of Low Degree. In: SIAM Journal on Computing. Band 17, Nr. 2, 1988, S. 336–341 (Solving Simultaneous Modular Equations of Low Degree).
↑ What is OAEP? (englisch)
↑ What is PSS/PSS-R? (englisch)
↑ Daniel Bleichenbacher: Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standard PKCS #1. In: CRYPTO '98. 1998, S. 1–12.
↑ Kryptographische Verfahren: Empfehlungen und Schlüssellängen. (PDF 1.4 (830kiB)) (Nicht mehr online verfügbar.) In: BSI. Bundesamt für Sicherheit in der Informationstechnik, 10. Februar 2014, S. 15, 28, archiviert vom Original am 22. Februar 2014; abgerufen am 13. Juli 2014 (Tabelle 1.2 und Tabelle 3.1 empfehlen Schlüssellängen von 2000Bit für RSA).

[1] R.L. Rivest, A. Shamir, and L. Adleman: A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. (mit.edu [PDF]).

[2] Whitfield Diffie, Martin E. Hellman: New Directions in Cryptography. (stanford.edu [PDF]).

[3] Gina Kolata: Leonard Adleman; Hitting the High Spots Of Computer Theory. In: The New York Times. 13. Dezember 1994, ISSN 0362-4331 (nytimes.com).

[4] C. C. Cocks: A note on 'non-secret encryption'. 1973 (Memento vom 27. Februar 2008 im Internet Archive)

[USPAT4405829-5] Patent US4405829: Cryptographic communications system and method. Veröffentlicht am 20. September 1983, Anmelder: Massachusetts Institute of Technology, Erfinder: Ronald L. Rivest, Adi Shamir, Leonard Adleman.‌

[banz-6] Bundesnetzagentur für Elektrizität, Gas, Telekommunikation, Post und Eisenbahnen: Bekanntmachung zur elektronischen Signatur nach dem Signaturgesetz und der Signaturverordnung (Übersicht über geeignete Algorithmen) vom 21. Januar 2014 (BAnz AT 20.02.2014 B4)

[boneh1999-7] D. Boneh: Twenty Years of Attacks on the RSA Cryptosystem. In: Notes of the AMS. Band 46, Nr. 2, Februar 1999, S. 203–213 (PDF).

[wiener1990-8] MJ Wiener: Cryptanalysis of short RSA secret exponents. In: IEEE Transactions on information theory. Band 36, Nr. 3, Mai 1990, S. 553–558, doi:10.1109/18.54902.

[9] RSA Labs: RSA-200 is factored! (Memento vom 18. November 2007 im Internet Archive)

[10] MathWorld: RSA-640 Factored

[11] RSA Labs: RSA-768 is factored!

[12] Archivierte Kopie (Memento vom 22. Februar 2015 im Internet Archive)

[13] ttp://www.keylength.com/en/compare/

[14] Johan Håstad: Solving Simultaneous Modular Equations of Low Degree. In: SIAM Journal on Computing. Band 17, Nr. 2, 1988, S. 336–341 (Solving Simultaneous Modular Equations of Low Degree).

[15] What is OAEP? (englisch)

[16] What is PSS/PSS-R? (englisch)

[17] Daniel Bleichenbacher: Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standard PKCS #1. In: CRYPTO '98. 1998, S. 1–12.

[18] Kryptographische Verfahren: Empfehlungen und Schlüssellängen. (PDF 1.4 (830kiB)) (Nicht mehr online verfügbar.) In: BSI. Bundesamt für Sicherheit in der Informationstechnik, 10. Februar 2014, S. 15, 28, archiviert vom Original am 22. Februar 2014; abgerufen am 13. Juli 2014 (Tabelle 1.2 und Tabelle 3.1 empfehlen Schlüssellängen von 2000Bit für RSA).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

Anonym

Suche

RSA-Kryptosystem

Geschichte

Verfahren

Einwegfunktionen

Erzeugung des öffentlichen und privaten Schlüssels

Beispiel

Verschlüsseln von Nachrichten

Beispiel

Entschlüsseln von Nachrichten

Beispiel

Signieren von Nachrichten

RSA mit dem Chinesischen Restsatz

RSA ist kein Primzahltest

Sicherheit

Beziehung zwischen RSA und dem Faktorisierungsproblem

Schwierigkeit des Faktorisierungsproblems

Schwierigkeit des RSA-Problems

Angriffe gegen das unmodifizierte RSA-Verfahren („Textbook-RSA“)

Padding

Chosen-Ciphertext-Angriff

Sicherheit hybrider Verfahren

Vollständiges Beispiel

Anmerkung

Vorarbeiten

Schlüsselerzeugung

Verschlüsselung

Entschlüsselung

Signatur

Verifikation

Programmierung

Anwendung

Hybride Verfahren

Anwendungsgebiete

Literatur

Weblinks

Einzelnachweise

Navigation

Wikiwerkzeuge

Seitenwerkzeuge

Weitere Projekte

Kategorien