RSA Verschlüsselungsverfahren

Asymmetrische Verschlüsselungsverfahren

Was kann an einem Verfahren zur Verschlüsselung asymmetrisch sein? Und was ist daran so furchtbar aufregend, dass dieses Verfahren seit seinem Auftreten alle symmetrischen Verfahren in der Verbreitung weit hinter sich gelassen hat?

Dazu muss man sich vor Augen halten, dass bei den herkömmlichen (symmetrischen) Verfahren zur Verschlüsselung es zwar möglich ist, einen verschlüsselten Text sehr sicher von einem Absender A zu einer Empfängerin E zu senden, ohne dass zum Beispiel die Briefträgerin oder der Systemadministrator des Webmail - Anbieters diesen Text lesen kann. Allerdings müssen A und E sich auf ein Verfahren zur Verschlüsselung sowie einen Schlüssel einigen, und zumindest dieser Schlüssel darf nicht in die Hände der Briefträgerin oder des Admins fallen, sonst ist alle Verschlüsselung vergebens. Also muss statt des Textes nun ein Schlüssel geheim übertragen werden, und damit haben A und E ihr Problem nur auf eine andere Ebene gehoben.

Asymmetrische Verfahren lösen dieses Problem nun mit einem mathematischen Trick: Sie verwenden eine so genannte Falltürfunktion zum Verschlüsseln, eine Funktion, die relativ einfach zu berechnen ist, deren Umkehrfunktion aber mit vertretbarem Aufwand nicht zu berechnen ist (offensichtlich deuten sich hier in den Formulierungen "relativ einfach" und "vertretbarer Aufwand" Probleme in der Umsetzung an, deren Diskussion wir aber auf später verschieben wollen). Diese Falltürfunktion verwendet nun E, um ein Schlüsselpaar zu generieren: Den geheimen oder privaten Schlüssel behält E für sich, den öffentlichen Schlüssel sendet sie offen an A. A kann nun mit dem öffentlichen Schlüssel von E einen Text verschlüsseln, der nur mit Kenntnis des privaten Schlüssels von E (also in der Regel nur von E selbst) entschlüsselt werden kann. Auf diese Weise ist es möglich, chiffrierte Nachrichten zwischen Personen auszutauschen, ohne dass diese sich jemals begegnen. Praktische Umsetzungen dieser asymmetrischen Verschlüsselungsverfahren finden sich zum Beispiel beim Onlinebanking oder der Absicherung von geschützten Bereichen im Internet (Intranet, WebMail).

Als Beispiel für die Umsetzung eines solchen asymmetrischen Verschlüsselungsverfahrens wird im Folgenden RSA vorgestellt und diskutiert. Die Beschreibung soll sowohl für Interessierte einen Einblick ermöglichen, als auch für mathematisch Interessierte die Details vorstellen.

RSA

Die Sicherheit von RSA liegt in der Schwierigkeit begründet, (sehr) große Zahlen zu faktorisieren. Diese großen Zahlen n sind Produkte zweier Primzahlen p und q, d. h. n = pq. Man geht davon aus, dass es schwer ist, aus gegebenem n die Ursprungswerte p und q zu berechnen.

Schlüsselerzeugung

Zunächst muss ein öffentlicher und privater Schlüssel (Schlüsselpaar) erzeugt werden. Dies kann z. B. durch eine Schlüsselvergabestelle erfolgen. Diese wählt zufällig zwei große Primzahlen p und q:

n = pq

Dann wird Phi(n) (Symbol: Φ) berechnet. Dies dient der Berechnung der Anzahl der teilerfremden Zahlen zu n; z. B. ist Φ(15) = 8, da 1, 2, 4, 7, 8, 11, 13 und 14 keine gemeinsamen Teiler mit 15 haben (die 1 zählt man auch dazu). Da eine Primzahl nur durch 1 und sich selbst teilbar ist, sind alle Zahlen, die unterhalb von ihr liegen, zu ihr teilerfremd. D. h.: Φ(p) = p − 1 bzw. Φ(q) = q − 1. Folglich gilt für Φ(n):

Φ(n) = (p − 1)(q − 1)

Schließlich bestimmen wir zwei Zahlen e und d so, dass

ed mod Φ(n) = 1

gilt. Das bedeutet, e und d heben sich auf, genauso wie 4 und 1/4 bezüglich Multiplikation (4 · 1/4 = 1). Man sagt auch, d ist der Kehrwert von e modulo Φ(n).

e und n bilden nun den öffentlichen Schlüssel und d und n den privaten Schlüssel. Am besten sollten p und q nach der Berechnung von e, d und n vernichtet werden, da sie nicht mehr benötigt werden und nur einen unnötigen Risikofaktor darstellen (denn wer p und q kennt, kennt auch n, und die Sicherheit des Systems wäre dahin).

Wie wählt man d und e? Zunächst sucht man sich eine beliebige Zahl e, die teilerfremd zu Φ(n) ist; das kann z. B. eine Primzahl sein, die kleiner als Φ(n) ist. Die Bestimmung von d (d. h. dem Kehrwert oder modularen Inversen) ist schwieriger; sie erfordert mehr oder weniger komplizierte Verfahren. Ein weniger aufwändiges Verfahren finden Sie im Artikel RSA Verschlüsselung - ggt Berechnung.

Ver- und Entschlüsselung

Um eine beliebige Nachricht m zu verschlüsseln, die kleiner oder gleich n ist, führen wir folgende Berechnung durch:

c = m^e mod n

Das heißt, m (die Nachricht) wird mit e potenziert, und der Rest, der sich bei der Division durch n ergibt, bildet den Chiffretext oder Geheimtext c. Wenn n beispielsweise 512 Bit lang ist, muss m kleiner oder gleich 512 Bit lang sein.

Um den Geheimtext wieder umzuwandeln, berechnet der Empfänger:

m = c^d mod n

Damit das Verfahren reibungslos über die Bühne gehen kann, muss gewährleistet sein, dass sich e und d "aufheben":

e · d mod (p−1)(q−1) = 1

Warum funktioniert RSA auf die beschriebene Weise, also warum ist das Ergebnis von Ver- und Entschlüsselung immer wieder der Ursprungstext? Diese Frage soll später in dem Kapitel RSA Verschlüsselung - Korrektheit wieder aufgegriffen werden, zunächst wollen wir das Verfahren einmal an einem kleinen Beispiel durchspielen:

Ein Beispiel

So, jetzt mal ein kleines Beispiel zur Verschlüsselung mit RSA. Wir wählen zunächst zwei Primzahlen p und q, sagen wir jetzt einfach 7 und 13 (normalerweise sollten diese Zahlen mehrere hundert Stellen haben, aber das ist hier ja schwer möglich; Sie können die Schritte am Taschenrechner mitverfolgen). Das bedeutet für p, q und n:

p = 7
q = 13
n = 7 · 13 = 91
Φ(n) = (7 − 1) · (13 − 1) = 6 · 12 = 72

Jetzt müssen wir noch e und d bestimmen. Für e wählen wir eine zu Φ(n) teilerfremde Zahl < Φ(n), z. B. 5. Mit Hilfe des erweiterten euklidischen Algorithmus berechnen wir d = 29. Das heißt:

e = 5
d = 29

Diese Zahlen genügen der Anforderung

ed mod Φ(n) = 1
(5 · 29) mod 72 = 1

Wir kennen also

n = 91
Φ(n) = 72
e = 5
d = 29

Der öffentliche Schlüssel besteht aus e und n, der private aus d und n.

So, und nun möchten wir gerne die Nachricht m = 10 (m muss kleiner oder gleich n, also 91, sein!) verschlüsseln. Also berechnen wir

c = 10⁵ mod 91
c = 82

Der Geheimtext lautet demzufolge 82. Jetzt lassen Sie uns mal sehen, ob wir auch wieder den ursprünglichen Klartext erhalten:

m' = 82²⁹ mod 91
m' = 10
m' = m

Sehen Sie, es hat geklappt! Allerdings ist Ihnen vielleicht aufgefallen, dass bei der Entschlüsselung der Wert 82²⁹ zu berechnen war. Dies ergibt eine Zahl mit etwa 50 Ziffern; man sieht also leicht, dass bei den wesentlich größeren "echten" Werten die Zwischenergebnisse nicht mehr handhabbar sein werden. Um dennoch die Berechnung effizient durchzuführen, wird ein Trick angewendet, der im Artikel RSA Verschlüsselung - Modulo Berechnung genauer beschrieben wird. Wenn Sie noch ein wenig mit dem Verfahren spielen wollen, bietet Ihnen die Seite RSA Verschlüsselung - zum Ausprobieren die Möglichkeit dazu. So sieht das Ganze in der Praxis natürlich nicht aus. Da geht's etwas komplizierter zu, schon allein wegen der großen Zahlen.

Wie sicher RSA in der Praxis wirklich ist, können wir in dem Exkurs RSA Verschlüsselung - Sicherheit diskutieren.