Das RSA Verfahren

RSA hat den Namen nach den Anfangsbuchstaben der Nachnamen seiner Erfindern RONALD L. RIVEST, ADI SHAMIR und LEONARD ADLEMAN bekommen. RIVEST, SHAMIR und ADLEMAN haben das Verfahren 1977 entwickelt. Es gilt bis heute als sicher. Die RSA-Verschlüsselung nutzt so genannte Einweg-Funktionen. Man kann sich diese Funktionen als mathematische Einbahnstraßen vorstellen. In die eine Richtung (Verschlüsseln) ist die Berechnung ganz einfach. Versucht man den Rechenweg jedoch rückwärts zu beschreiten (Entschlüsseln ohne Schlüssel), wird die Sache schwieriger.

Ein Beispiel für eine Einweg-Funktion ist die Multiplikation von Primzahlen. Zur Wiederholung: Eine Primzahl ist nur durch sich selbst und 1 teilbar. Es ist sehr einfach, zwei Primzahlen miteinander zu multiplizieren. Nehmen wir 3.259 und 5.431, das Ergebnises 17.699.629.

Die mathematische Einbahnstraße wurde hierbei in der einfachen (richtigen) Richtung „befahren“. Wenn die Frage nun aber lauten würde: „Gesucht sind alle Teiler der Zahl 17.699.629“ sieht die Sache sehr viel schwieriger aus. Jetzt müssen wir die Einbahnstraße in die andere Richtung zurück fahren. Das ist in der Mathematik für diese Aufgabe sehr schwierig. 17.699.629 hat nämlich nur vier Teiler: 1 und sich selbst (das gilt immer und für jede Zahl) sowie die beiden Primzahlen, die wir gerade zuvor multipliziert haben.

Das bedeutet, wenn man aus dem Produkt 17.699.629 alle Teiler, außer 1 und der Zahl selbst, findet, hat man die Ausgangswerte ermittelt. Das große Problem dabei ist, dass für das Zerlegen einer Zahl in ihre Primfaktoren auf der ganzen Welt keine wirklich guter (d. h. schneller) Algorithmus bekannt ist.

Dazu ein Beispiel: Ein 39stelliges Produkt aus zwei 20stelligen Primzahlen wird auf einem aktuellen Computer mit Hilfe einer leistungsfähigen (und übrigens teuren) Mathematik- Software in weniger als einer Sekunde in die beiden Primzahl-Faktoren zerlegt.

Für eine 41stellige Zahl dauert das Ganze schon etwas mehr als 8 Minuten. Für ein 43stelliges Produkt aus zwei 22stelligen Primzahlen benötigte der Computer fast 19 Minuten. Bei einem 44stelliges Produkt hat das Programm die Berechnung ohne Ergebnis abgebrochen.

In der Praxis wird mittlerweile mit 2048-Bit-Schlüssellängen (Zahl mit 617 Stellen) gearbeitet. Es wird schnell klar, dass auch der schnellste Rechner das Produkt beider Primzahl-Faktoren nicht in akzeptabeler Zeit ermitteln und damit die Verschlüsselung ohne Schlüssel knacken kann.

Beispiel für N (1024-Bit-Zahl)
p = 0xFFFFFFFF00000001 (eine 512-Bit-Zahl)
q = 0xFFFFFFFF00000003 (eine andere 512-Bit-Zahl)
Beachte, dass diese Zahlen natürlich nur als ein einfaches Beispiel dienen. In der Praxis wären p und q viel größer und zufällig ausgewählt, um sicherzustellen, dass die Primzahlen echte Zufallszahlen sind und nicht leicht zu faktorisieren sind.

Nehmen wir an, dass die oben genannten p und q tatsächlich Primzahlen sind. Dann könnte N durch einfaches Multiplizieren von p und q berechnet werden:
N = p · q = (0xFFFFFFFF00000001) · (0xFFFFFFFF00000003), das würde zu einer Zahl im Bereich von 1024 Bits führen.

RSA Berechnung

(1) Alice erzeugt zuerst Ihren privaten Schlüssel

• Dazu wählt sie zwei Primzahlen, z. B. p = 17 und q = 11.
• Diese beiden Zahlen muss Alice geheim halten!
• Nun wählt Alice noch eine weitere Zahl e. Nehmen wir an sie wählt e = 7. Dabei sollten e zu phi(N) teilerfremd sein, d. h. der größte gemeinsamer Teiler von e und phi(N) ist 1.
• Allgemein gilt das 1 < e < phi(N) gewählt werden muss.

(2) Alice erzeugt nun ihren öffentlichen Schlüssel

• Der öffentliche Schlüssel besteht aus zwei Zahlen. Als erste Zahl verwendet Alice die Zahl e = 7 aus dem ersten Schritt.
• Zur Berechnung der zweiten Zahl wählt sie zwei Primzahlen, z. B. p = 17 und q = 11. Alice multipliziert 17 und 11 und erhält das Produkt N = 187.

Die Zahlen N = 187 und e = 7 sind Alice "öffentlicher Schlüssel (N,e)" - also (187,7).

(3) Als nächstes wird phi(N) bestimmt:

phi(N) = (p-1) · (q-1)
phi(N) = (17-1) · (11-1)
phi(N) = 16 · 10
phi(N) = 160

(4) Alice berechnet nun ihren geheimen Schlüssel d:
Hinweis: Erweiterter Euklidischer Algorithmus, um d zu bestimmen!
Alice wählt d = 23, da die folgende Gleichung erfüllt ist:
e · d mod phi(N) = 1
7 · 23 mod 160 = 1
161 mod 160 = 1
Geheimer Schlüssel (N,d): (187, 23)

(5) Alice verschlüsselt nun eine Nachricht m = 88:
Die Verschlüsselung erfolgt mit:
c = m^e mod N
c = 88⁷ mod 187
c = 40867559636992 mod 187
c = 11

(6) Alice sendet c an Bob:
Bob entschlüsselt die Nachricht c = 11 mit seinem geheimen Schlüssel d = 23.

(7) Bob entschlüsselt die Nachricht:
Die Entschlüsselung erfolgt mit:
m = c^d mod N
m = 11²³ mod 187
m = 895430243255237372246531 mod 187
m = 88