Beschreibung des Verfahrens
Das Verfahren besteht aus drei Teilen:
A) | Erstellung eines öffentlichen Schlüssels (durch den Empfänger) |
B) | Verschlüsseln einer Nachricht (durch den Sender) |
C) | Entschlüsseln einer Nachricht (durch den Empfänger) |
Wir besprechen die einzelnen Schritte der Reihe nach, wobei wir die Rolle des Empfängers einnehmen.
Erstellung eines öffentlichen Schlüssels durch den Empfänger
(1) | Wir wählen zwei sehr große Primzahlen p1 ≠ p2 und setzen m = p1 p2. |
(2) | Wir berechnen φ(m) = (p1 − 1)(p2 − 1) und wählen ein zu φ(m) teilerfremdes e ≥ 2, sodass also (φ(m), e) = 1. |
(3) | Nun bestimmen wir ein d ≥ 1 mit ed ≡ 1 (φ(m)). |
(4) | Wir veröffentlichen die Zahlen m und e. Streng geheim bleiben dagegen die Zahlen p1, p2, φ(m) und d. |
(5) | Wenn nicht nur Zahlen, sondern Texte verschlüsselt werden sollen, veröffentlichen wir noch eine Anweisung, wie ein (kurzer) Text oder ein Wort in eine Zahl x mit 0 ≤ x < m zu übersetzen ist (z. B. kann abcdefghijk in 10203040506070809010011 übersetzt werden). |
An dieser Stelle lässt sich bereits die Bedeutung der rechnerischen Komplexität des Verfahrens beschreiben: Theoretisch kann jeder, der m kennt, auch die Primzahlen p1 und p2 bestimmen. Mathematisch würde man einfach schreiben:
„Sei p1 p2 die Primfaktorzerlegung von m.“
Rechnerisch ist die Situation ganz anders: Für sehr große Primzahlen p1 und p2 ist es leicht, das Produkt m = p1 p2 auszurechnen, umgekehrt aber sehr schwer bis aus praktischer Sicht unmöglich, aus dem Produkt m wieder die Primzahlen p1 und p2 zu erhalten. Gleiches gilt für die Zahlen φ(m) und d.
Die Bezeichnungen sind durch „e“ für „encryption“ und „d“ für „decryption“ motiviert.
Verschlüsseln einer Nachricht oder Information durch den Sender
(1) | Falls die Nachricht keine Zahl ist, wird die Nachricht zunächst in eine Zahl x ∈ { 0, …, m } übersetzt. |
(2) | Der Sender berechnet nun den Rest y der Division von xe durch m, sodass also xe ≡ y (m), 0 ≤ y < m. |
(3) | Der Sender schickt nun y öffentlich einsehbar an den Empfänger. |
Die Berechnung von y kann (mit Hilfe eines Computers) sehr effektiv geschehen. Wir haben ja bereits gesehen, wie gut sich y für Zahlen wie 3123 und einen Modul m = 10 per Hand berechnen lässt.
Entschlüsseln einer Nachricht durch den Empfänger
(1) | Als Empfänger erhalten wir y und bestimmen nun ein z mit yd ≡ z (m), 0 ≤ z < m. Die mathematische Theorie sichert, dass z = x. |
(2) | Gegebenenfalls ermitteln wir aus der Zahl x noch die ursprüngliche Textnachricht. |
Dem Leser wird vielleicht aufgefallen sein, dass die Eulersche φ-Funktion beim Ver- und Entschlüsseln keine Rolle mehr spielt. Sie wird aber zur Bestimmung der Zahlen e und d wesentlich gebraucht. Für e muss (φ(m), e) = 1 und für d muss ed ≡ 1 (φ(m)) gelten. Dies sichert, dass die Entschlüsselung funktioniert, d. h. dass z = x ist. Entscheidend wird hierzu verwendet:
(+) (xe)d ≡ x (m).
Weiß man dies, so ist
x ≡ (xe)d ≡ yd ≡ z (m),
und damit x = z, da x und z im Intervall von 0 bis m − 1 liegen.
Um (+) einzusehen, nehmen wir zunächst an, dass x und m relativ prim zueinander sind. Wegen
e d ≡ 1 (φ(m))
existiert ein k mit
e d = k φ(m) + 1.
Nach dem Satz von Euler gilt wegen (x, m) = 1, dass
xφ(m) ≡ 1 (m).
Damit erhalten wir nun:
(xe)d ≡ xed ≡ xkφ(m) + 1 ≡ (xφ(m))k · x ≡ 1k · x ≡ x (m)
Für den Fall (x, m) ≠ 1 ist die Kongruenz (+) ebenfalls gültig. Um dies zu beweisen, ist etwas mehr Theorie nötig als wir hier entwickelt haben. Wir verweisen den interessierten Leser auf die Literatur.
Wie sicher ist das Verfahren? Rivest, Shamir und Adleman haben im Jahr 1977 eine Zahl m mit 129 Stellen angegeben und öffentlich dazu aufgerufen, diese Zahl in ihre Primfaktoren p1 und p2 zu zerlegen. Dies gelang 1994 durch eine Berechnung mit über 1000 Computern. Heute werden noch größere Primzahlen mit etwa 100 Stellen verwendet, um die Verschlüsselung praktisch sicher zu machen. Dennoch gilt: (1) Die Programme, die große Primzahlen erzeugen, können Gefahren in sich bergen. (2) Die Primzahlen p1, p2 können dem Empfänger „gestohlen“ werden. (3) Durch die Entwicklung besserer Computer kann eine im Jahr 2017 erfolgte Verschlüsselung im Jahr 2027 möglicherweise durch andere Personen als den Empfänger entschlüsselt werden. Die Verschlüsselung ist also nur kurzzeitig als „sicher“ einzustufen.
Das RSA-Verfahren ist nur zur Kodierung kleiner Zahlen bzw. kurzer Texte geeignet. Umfangreichere Informationen werden mit anderen Methoden verschlüsselt, wobei hierzu ein mit Hilfe des RSA-Verfahrens erzeugter Kode verwendet wird.