RSA-Kryptosystem

Das RSA-Kryptosystem ist ein asymmetrisches Kryptosystem, d. h. es verwendet verschiedene Schlüssel zum Ver- und Entschlüsseln. Es ist nach seinen Erfindern Ronald L. Rivest, Adi Shamir und Leonard Adleman benannt.

Wirtschaftliche und politische Bedeutung, Vorgeschichte

Die immense wirtschaftliche Bedeutung von RSA resultiert aus der Lösung des Schlüsseltransport-Problems. Bis zur Anwendung von RSA und den neueren asymmetrischen Verschlüsselungssystemen mußten aufwendig Schlüssel- und Codebücher zu den entfernten Kommunikationspartnern (z.B. Handelspartnern, Internet-Kommunikationspartnern, Botschaften, exterritoriale Militäreinrichtungen, U-Booten) mit immensen (Sicherheits-)Kosten transportiert werden. Dieser Weg bedeutete darüber hinaus die größte logistische Schwachstelle der konventionellen symmetrischer Verschlüsselungssysteme. Bis in die 1970er Jahre hielt man dieses Problem prinzipiell nicht für lösbar. Die logistische Schwachstelle hat bei mehreren staatlichen Auseinandersetzungen und Kriegen den Ausgang (mit-)entschieden, so durch Aktivitäten z.B. von Alan Turing und anderen in Bletchley Park im Zweiten Weltkrieg. Dort und in Nachfolgeeinrichtungen wurde Anfang der 1970er Jahre von Ellis, Cocks und Williamson ein dem späteren Verfahren von Diffie-Hellman ähnliches assymetrisches Verfahren entwickelt, welches aber in seiner Bedeutung nicht erkannt und aus Geheimhaltungsgründen nicht (wissenschaftlich) publiziert und auch nicht zum Patent angemeldet wurde.

Bis heute werden für die Massenverschlüsselung (z.B. im Internet) weiterhin symmetrische Verfahren, (z.B. DES) eingesetzt, wegen ihrer höheren Geschwindigkeit und anderer Vorteile. RSA und andere asymmetrische Verfahren dienen häufig nur beim Kommunikationsaufbau zum Transport des symmetrischen Schlüssels und der digitalen Unterschrift.

Verfahren

Nachdem Whitfield Diffie und Martin Hellman eine Theorie zur Public-Key-Kryptografie veröffentlicht hatten, versuchten die drei Mathematiker Rivest, Shamir und Adleman, die Annahmen von Diffie und Hellmann zu widerlegen. Nachdem sie den Beweis bei verschiedenen Verfahren durchführen konnten, stießen sie schließlich auf eines, wo sie keinerlei Angriffspunkte fanden. Hieraus entstand dann RSA. Das Verfahren wurde 1977 entwickelt und basiert auf der Idee, dass die Faktorisierung einer großen Zahl, also ihre Zerlegung in (mindestens zwei) Faktoren, eine sehr aufwändige Angelegenheit ist, während das Erzeugen einer Zahl durch Multiplikation zweier Primzahlen trivial ist. Wenn nun eine Nachricht einem Empfänger verschlüsselt zugeleitet werden soll, generiert dieser einen öffentlichen Schlüssel. Der Nachrichtenabsender verwendet diesen öffentlich bekanntgemachten Schlüssel, indem er damit seine Botschaft verschlüsselt. Nur der Empfänger kann diese "dekodieren", da nur er die "Zusammensetzung" des von ihm erzeugten (öffentlichen) Schlüssels kennt.

Einwegfunktionen

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

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

Algorithmus

Wähle zufällig und stochastisch unabhängig zwei Primzahlen p ≠ q, die etwa gleich lang sein sollten und berechne deren Produkt N = p·q.
In der Praxis werden diese Primzahlen durch Raten einer Zahl und darauffolgendes Anwenden eines Primzahltests bestimmt.
Berechne φ(N) = (p-1) · (q-1), wobei φ für die Eulersche φ-Funktion steht.
Wähle eine Zahl e > 1, die teilerfremd zu φ(N) ist.
Berechne die Zahl d so, dass das Produkt e·d kongruent 1 bezüglich des Modulus φ(N) ist, dass also e·d ≡ 1 mod φ(N) gilt.
Die Zahlen N und e werden veröffentlicht (öffentlicher Schlüssel, public key), d, p und q und damit auch φ(N) bilden den geheimen Schlüssel (secret key)

Asymmetrische Vorgehensweise:

A wählt zufällig zwei möglichst gleich lange Primzahlen, berechnet daraus N, φ(N) und zwei Zahlen e und d. N und e veröffentlicht er als öffentlichen Schlüssel, d und N sind Bestandteile seines geheimen Schlüssels, und p, q und φ(N) kann A nach belieben vernichten.

Jeder kann A eine verschlüsselte Nachricht senden, aber nur A kann sie entschlüsseln.

Symmetrische Vorgehensweise:

A und B wählen (in konspirativer Umgebung) zwei möglichst gleich lange Primzahlen aus, bestimmen N, φ(N) und zwei Zahlen e und d. Sowohl e als auch d müssen beide geheim bleiben. A verschlüsselt und entschlüsselt mit e und N. B macht dies mit d und N.

Verschlüsseln von Nachrichten

Datei:Verschlüsselung (asymmetrisches Kryptosystem).png

Verschlüsselung

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

C ≡ K^e mod N

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

Ein Zahlenbeispiel:

Für die beiden Primzahlen p und q nehmen wir p = 11 und q = 13. Damit wird N = 143.
Die Eulerfunktion nimmt damit den Wert φ(N) = φ(143) = (p-1)(q-1) = 120 an.
Für die zu φ(143) = 120 teilerfremde neue Zahl e wähle man e = 23.
Mit diesen Werten erhalten wir die Bedingung: 23·d ≡ 1 mod 120. 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 N = 143 und d = 47 der geheime 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, indem 7²³ (bezüglich des Modulus 143) schrittweise durch eine dazu kongruente kleinere Zahl ersetzt wird.

7²³ = 7²⁰⁺³ = 7^{(5·4) +3} = 7^{(5·(2·2)) +3} = 7^5·2·2 · 7³ = (7⁵)^2·2 · 7³

Man kann in jedem Schritt auf die zu handhabenden Zahlen die Modulo-Operation (kurz: "mod"; Notation in C++, C, Java: a % b) anwenden um die Ergebnisse möglichst "klein" zu halten.

7⁵ = 16.807, => 16.807 mod 143 ≡ 76 mod 143

((76)^2·2 · 7³) mod 143

7³ = 343, => 343 mod 143 ≡ 57 mod 143

((76)^2·2 · 57) mod 143

(76²)²

76² = 5.776, => 5.776 mod 143 ≡ 56 mod 143

((56)² · 57) mod 143

(56)² = 3.136, => 3.136 mod 143 ≡ 133 mod 143

(133·57) mod 143, (133·57) = 7.581, => 7.581 mod 143 ≡ 2 mod 143

So kann schrittweise x^y durch die dazu kongruente kleinere Zahl z ersetzt werden.

7²³ mod 143 ≡2 mod 143.

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

Entschlüsseln von Nachrichten (Decodierung)

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 oder

K ≡(2¹⁵)³ ·2² mod 143 oder

K ≡21³ · 4 mod 143 oder

K ≡37044 mod 143 oder

K ≡7 mod 143.

Aus C = 2 wird wieder K = 7.

Signieren von Nachrichten

Um eine Nachricht K zu signieren wird diese mit dem eigenen privaten Schlüssel verschlüsselt. Der Empfänger holt sich den öffentlichen Schlüssel N des Senders und benutzt seinen eigenen e zum Entschlüsseln. Kommt keine vernünftige Nachricht dabei heraus, wird die Signatur abgelehnt.

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 $\phi (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 2003 eine 174-stellige Dezimalzahl zu faktorisiern. 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 $\phi (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.

Beispiel einer Ver- und einer Entschlüsselung

Das verwendete Alphabet

Das verwendete Alphabet besteht aus den vier Buchstaben A,C,G und T: A=0; C=1; G=2; T=3

Die Schlüssel-Erzeugung

Da mit 3er-Gruppen gearbeitet werden soll (Stichwort Block-Chiffrierung), muss das zu wählende N über 64, aber auch möglichst nahe daran liegen. N= 77 mit p= 7 und q= 11 erfüllt die Bedingungen ganz gut. φ(N)= 60

N=77 p=7 q=11 φ(N)=60

Für e und d müssen zwei Zahlen gefunden werden, für die gilt: $e*d\mod 60=1$ Das ist u. a. für die Paare [7;43], [13;37] und [17;53] der Fall. Wir nehmen e=13 und d=37.