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.

Nachdem Whitfield Diffie und Martin Hellman eine Theorie zur Public-Key-Kryptografie veröffentlicht hatten, setzten sich die drei Mathematiker hin und versuchten, die Annahmen von Diffie und Hellmann zu widerlegen. Nachdem sie den Beweis bei verschiedenen Verfahren durchführen konnten, stiessen sie schliesslich 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 grossen 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.

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. Solche Einweg- und Falltürfunktionen kann es nur geben, wenn $P\neq NP$ ist.

RSA wird u.a. zur Authentisierung französischer Telefonkarten angewendet.

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

Schlüsselgenerierung

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 Anwenden eines Primzahltests angewendet.
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 "Moduls" φ(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 KlartextK den Geheimtext C.

Ein Zahlenbeispiel:
a) Für die beiden Primzahlen p und q nehmen wir p = 11 und q = 13. Damit wird N = 143.
b) Die Eulerfunktion nimmt damit den Wert φ ( N ) = φ ( 143 ) = (p-1)(q-1) = 120 an..
c) Für die zu φ ( 143 ) teilerfremde neue Zahl e wähle man e = 23.
d) Mit diesen Werten erhalten wir die Bedingung: 23 · d ≡1 mod 120. Das heisst: 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 ) = 120 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 benützt 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 Moduls 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", oder in C/C++/Java/.. Notation: "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³ · 2⁴ mod 143 oder

K ≡18522 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

Die Sicherheit basiert darauf, dass der Angreifer d nicht kennt. Um d zu berechnen benötigt er φ(N). φ(N) ist aber für grosse Zahlen nicht effizient berechenbar. Nur, wer die Primfaktoren p und q kennt, kann wie oben gezeigt φ(N) leicht berechnen. Die Zerlegung von N in die zufällig gewählten Primfaktoren p und q ist ebenfalls nicht effizient lösbar, aber einfacher als die Berechnung der φ-Funktion. Man kann daher sagen, die Sicherheit von RSA (und vielen anderen asymmetrischen Verfahren) beruht auf dem Problem der Primfaktorzerlegung. Inzwischen gelang es Mathematikern der Universität Bonn, eine 174-ziffrige Zahl zu faktorisieren. Damit ist zwar eine 300-ziffrige Schlüsselzahl, wie sie momentan (2004) beim RSA-Algorithmus verwendet wird, noch (lange) nicht erreicht. Falls aber jemals Quantencomputer zum diesbezüglichen Einsatz kommen sollten, bei denen eine sehr große Zahl von Operationen gleichzeitig durchgeführt werden können, rückt das Problem der Faktorisierung immer mehr in Lösungsreichweite und so würde die Sicherheit des RSA immer mehr schwinden.

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), muß 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. phi(N)= 60

N=77 p=7 q=11 phi(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.