Öffentlicher Schlüssel und RSA (Einführung)

Bei allen bisherigen Verfahren haben Absender und Empfänger denselben Schlüssel (symmetrische Verfahren). Wie tauscht man ihn sicher aus, wenn man sich nie getroffen hat? Die Lösung kam in den 1970er Jahren: asymmetrische Verfahren mit zwei Schlüsseln. Der öffentliche Schlüssel zum Verschlüsseln darf jeder kennen, der private Schlüssel zum Entschlüsseln bleibt geheim. Man kann es sich wie einen Briefkasten vorstellen: Jeder kann einen Brief einwerfen, aber nur du hast den Schlüssel zum Öffnen.

Das bekannteste Verfahren ist RSA, benannt nach Ron Rivest, Adi Shamir und Leonard Adleman, die es 1977 entwickelten und 1978 veröffentlichten. Es rechnet mit Resten und Potenzen. So funktioniert es im Kleinen:

1. Wähle zwei Primzahlen, hier p = 3 und q = 11. Ihr Produkt ist n = 33.
2. Berechne (p − 1) · (q − 1) = 2 · 10 = 20.
3. Wähle eine Zahl e, die zu 20 teilerfremd ist, hier e = 3. Der öffentliche Schlüssel ist (n, e) = (33, 3).
4. Bestimme d mit e · d ≡ 1 (mod 20). Wegen 3 · 7 = 21 ist d = 7. Der private Schlüssel ist d = 7.
5. Verschlüsseln: Aus einer Zahl m (kleiner als 33) wird c = m^e mod n.
6. Entschlüsseln: Aus c wird m = c^d mod n.

Dass das immer klappt, folgt aus dem Satz von Euler, einer Verallgemeinerung des kleinen Satzes von Fermat. Wichtig ist die Sicherheit: Aus n = 33 erkennt jeder sofort 3 · 11 und kann d ausrechnen. Echte Schlüssel verwenden Primzahlen mit hunderten Stellen. Das Produkt zweier solcher Zahlen kann ein Computer in Sekundenbruchteilen bilden, es wieder zu zerlegen, dauert nach heutigem Wissen viel zu lange (Primzahlen und Verschlüsselung). Eine ausführlichere Geschichte mit größeren Zahlen erzählt der Beitrag Primzahlen im Handy: wie Verschlüsselung funktioniert.

Weiter im Studium: Warum die Entschlüsselung immer die Nachricht zurückgibt, beweist der Abschnitt RSA und der Satz von Euler mit einem Beispiel für die Primzahlen 5 und 11.