RSA-Kryptosystem

RSA ist ein asymmetrisches Verschlüsselungsverfahren der Kryptologie. Es ist nach seinen Erfindern Ronald L. Rivest, Adi Shamir and 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 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 ( public key ). Der Nachrichtenabsender verwendet diesen öffentlich bekanntgemachten Schlüssel, indem er damit seine Botschaft verschlüsselt. Nur der Empfänger kann diese "decodieren", 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 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

a) 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. b) Berechne φ ( N ) = ( p - 1 ) · ( q - 1 ), wobei φ für die Eulersche φ-Funktion steht.
c) Wähle eine Zahl e > 1, die teilerfremd zu φ ( N ) ist.
d) 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 ), d, p und q und damit auch φ ( N ) bilden den geheimen Schlüssel (secret key)

Verschlüsseln von Nachrichten

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 "Schlüsseltext" ("Cyphertext") 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. Weil 7 ²³ = 7²⁰ · 7³ = (7⁵)⁴ · 7³ ist, und 7⁵ = 16807 + 76 gilt, kann in einem ersten Schritt 7⁵ durch die dazu kongruente kleinere Zahl 76 ersetzt werden, so dass 7²³ mod 143 ≡76⁴ · 7³ mod 143 wird. Weitere entsprechende Schritte führen so auf

7²³ mod 143 ≡2 mod 143.

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

Entschlüsseln von Nachrichten (Decodierung)

Der Schlüsseltext 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 grosse 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 Ciphertext statt. Es ist daher grundsätzlich möglich, den Klartext durch Wahrscheinlichkeitsanalyse und Known-Plaintext-Angriffe zu ermitteln, da ein Klartext immer genau einem Ciphertext 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.