RSA-Kryptosystem

Ein Zahlenbeispiel:

1. Für die beiden Primzahlen p und q nehmen wir p = 11 und q = 13. Damit wird N = 143.
2. Die Eulerfunktion nimmt damit den Wert φ(N) = φ(143) = (p-1)(q-1) = 120 an.
3. Für die zu φ(143) = 120 teilerfremde neue Zahl e wähle man e = 23.
4. Mit diesen Werten erhalten wir die Bedingung: (23·d) mod 120 ≡ 1. Das heißt: Das Produkt soll bei Division durch 120 den Rest 1 lassen. Man kann damit die Kongruenz als Gleichung schreiben: 23·d = k·120 + 1. Dabei ist k eine ganze Zahl. Als eine Lösung dieser diophantischen Gleichung 120·k - 23·d = -1 ergibt sich d = 47 und k = 9. Damit wird d = 47 der geheime Schlüssel, e = 23 und N = 143 der öffentliche Schlüssel.

Verschlüsselung

Es soll die Nachricht K, z.B. die Zahl K = 7 verschlüsselt werden.
Der Nachrichtenabsender benutzt den veröffentlichten Schlüssel N = 143, e = 23 und rechnet

C ≡K^e mod N, im Beispiel also

C ≡7²³ mod 143.

Zur Berechnung von 7²³ mod 143 kann die Kongruenzarithmetik verwendet werden. Mit Hilfe der Modularen Exponentiation berechnet man schnell:

7²³ mod 143= (((7²)²·7)²·7)²·7 mod 143 = 2

Dabei wendet man nach jedem Rechenschritt auf die zu handhabenden Zahlen die Modulo-Operation (kurz: "mod"; Notation in C++, C, Java: a % b) an, um die Ergebnisse möglichst "klein" zu halten.

Aus dem Klartext K = 7 ist somit der Geheimtext C = 2 geworden.

Entschlüsseln von Nachrichten (Decodierung)

thumb|300px|Entschlüsselung

Der Geheimtext C kann durch modulare Exponentiation wieder entschlüsselt werden. Der Nachrichtenempfänger benutzt die Formel:

K ≡C^d mod N

mit den nur ihm bekannten Werten d und N.
Im Zahlenbeispiel ist

K ≡ 2⁴⁷ mod 143 = ((((2²)²·2)²·2)²·2)²·2 mod 143 = 7

Aus C = 2 wird also wieder K = 7.

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, 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.

In der Praxis werden Signaturen meistens mit einem Hashwert H über das zu signierende Dokument gebildet. H besitzt in der Regel eine feste oder maximale Länge, so dass auch große Dokumente signiert werden können. H bildet nun mit codierten Informationen über den Hash-Algorithmus und einer definierten Bytefolge (Padding) die Nachricht K*, die wie oben beschrieben verschlüsselt wird. Beim Prüfen der Signatur erzeugt der Empfänger selbst das K* und vergleicht es mit dem empfangenen.

Sicherheit

Theoretische Sicherheit

Angenommen, der Angreifer kennt lediglich den öffentlichen Schlüssel, also die Werte N und e. Um den Geheimtext zu entschlüsseln benötigt er zusätzlich d, oder einen zu d kongruenten Wert.

Wenn der Angreifer φ(N) kennen würde, könnte er d leicht berechnen. Eine Möglichkeit dazu ist die Zerlegung von N in seine beiden Primfaktoren p und q. 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, der Shor-Algorithmus für Quantencomputer leistet dies in Polynominalzeit. Sollte es also gelingen einen funktionierenden Quantencomputer mit ausreichend Qubits zu konstruieren, wäre RSA nicht mehr sicher. Aber auch mit klassischer Rechentechnik lassen sich mit modernen Algorithmen relativ große Zahlen faktorisieren. So gelang es z. B. Mathematikern der Universität Bonn 2005 eine 200-stellige Dezimalzahl zu faktorisieren. Dies ist aber noch ein gutes Stück von den mindestens 300 Dezimalstellen heute üblicher Schlüssel entfernt. Die wachsende Rechenleistung moderner Computer stellt für die Sicherheit von RSA kein Problem dar. Zumal diese Entwicklung auch vorhersehbar ist und der Nutzer somit bei der Erzeugung seines Schlüsselpaares darauf achten kann, dass die zu zerlegende Zahl so groß ist, dass sie während der Zeit der beabsichtigten Verwendung nicht knackbar ist. Problematisch sind nicht vorhersehbare Entwicklungen wie z. B. die Fertigstellung des Quantencomputers oder die Entdeckung eines genialen Algorithmus' für klassische Hardware. Beides ist zwar sehr unwahrscheinlich, kann aber jederzeit passieren.

Ein weiteres Problem ist, dass es nicht bewiesen ist, dass der Angreifer das Faktorisierungsproblem überhaupt lösen muss, um die Verschlüsselung zu knacken. Möglicherweise gibt es einen viel einfacheren Weg d zu bestimmen, ohne vorher φ(N) zu berechnen. Es könnte also sein, dass RSA nichtmal so schwer ist wie das Faktorisierungsproblem. Das System von Williams ist ein Public-Key-System, für das bewiesen ist, dass es mindestens so schwer ist wie das Faktorisierungsproblem.

Praktische Sicherheit

Bei der RSA-Verschlüsselung findet eine deterministische Substitution des Klartextes durch den Geheimtext statt. Es ist daher grundsätzlich möglich, den Klartext durch Wahrscheinlichkeitsanalyse und Known-Plaintext-Angriffe zu ermitteln, da ein Klartext immer genau einem Geheimtext zugeordnet wird (ECB, Electronic Codebook). Das auf RSA aufbauende Übertragungsprotokoll muss daher für Abhilfe sorgen, zum Beispiel in Form von Pseudozufall, der an im Protokollstandard definierten Stellen eingefügt und vom Empfänger nach Entschlüsselung wieder entfernt wird.

Bei der Implementation der Schlüsselerzeugung muss darauf geachtet werden, dass die benutzten Primzahlen und der Faktor e tatsächlich so erzeugt werden, dass die Auswahl nicht aus einer kleinen Menge von möglichen Kandidaten erraten werden kann. Hierzu reichen einfache Zufallszahlengeneratoren in der Regel nicht aus.

RSA wird in der Regel in Hybridverfahren mit symmetrischen Verschlüsselungsverfahren gemischt. 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. Der symmetrische Schlüssel ist dabei relativ kurz, so dass der oben beschriebene Angriff mit Wahrscheinlichkeitsanalyse oder Known-Plaintext-Analyse erschwert wird. Voraussetzung ist aber auch hier, dass das Verfahren zur Erzeugung des symmetrischen Schlüssels den gesamten Schlüsselraum mit gleicher Wahrscheinlichkeit abdeckt.

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 z.B. 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 3 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 * 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, z.B. p=307 und q=859. Damit ergibt sich:

N = p · q = 263713

φ(N) = (p-1) · (q-1) = 262548

e = 1721 (zufällig, teilerfremd zu φ(N)

d = 1373 (das multiplikative Inverse zu e mod φ(N) mit Hilfe des Erweiterten euklidischen Algorithmus)

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

Geheimer Schlüssel: d = 1373

Verschlüsselung

C1 = K1e mod N
 

C1 = 2309111721 mod 263713
 

C1 = 001715
 

C2 = 0916051721 mod 263713
 

C2 = 184304
 

C3 = 0409011721 mod 263713
 

C3 = 219983
 

Entschlüsselung

K1 = C1d mod N
 K1 = 0017151373 mod 263713
 K1 = 230911
 K2 = 1843041373 mod 263713
 K2 = 091605
 K3 = 0017151373 mod 263713
 K3 = 040901
 

Signatur

C1 = K1d mod N
 C1 = 2309111373 mod 263713
 C1 = 219611
 C2 = 0916051373 mod 263713
 C2 = 121243
 C3 = 0409011373 mod 263713
 C3 = 138570
 

Verifikation

K1 = C1e mod N
 K1 = 2196111721 mod 263713
 K1 = 230911
 K2 = 1212431721 mod 263713
 K2 = 091605
 K3 = 1385701721 mod 263713
 K3 = 040901
 

Anwendungsgebiete

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

Weblinks

• Homepage von Ron Rivest am massachusetts institute of technology
• Homepage von Adi Shamir am Weizmann Institut
• Homepage von Prof. Adleman an der University of Southern California

• Erklärung von RSA vom Fachbereich Mathematik der Universität Wuppertal
• Kryptologie > Asymmetrische Verfahren > RSA
• Skript zu Zahlentheorie bis RSA
• Kurzer Überblick über das RSA-Verfahren mit Verschlüsselungsbeispiel
• Bekannte Attacken auf RSA-Verfahren

See also: RSA-Kryptosystem, 1970er, 1977, 2005, ASCII, Adi Shamir, Alan Turing, Asymmetrisch, Asymmetrisches Kryptosystem, Authentizität