Mathematische Prinzipien von RSA

 

RSA ist ein asymmetrisches Verschlüsselungsverfahren. Daher gibt es zwei Schlüssel: einen öffentlichen zum Chiffrieren und einen geheimen zum Dechiffrieren. Der Besitzer des Schlüsselbundes gibt den öffentlichen seinen Kommunikationspartnern, den privaten hält er streng geheim. Das sollte soweit bekannt sein, Software und Infos findet Ihr bei PGP oder GnuPG.

Das mathematische Grundprinzip ist ganz einfach: öffentlicher und geheimer Schlüssel heben sich gegenseitig auf: Multipliziert man sie, kommt eins heraus. Wie beispielsweise fünf und ein Fünftel:

5 × 1/5 = 1

Fünf ist der öffentliche Schlüssel. Der Kehrwert 1/5 der geheime. Ein Beispiel: Wir wählen als Nachricht, die wir verschlüsseln wollen, die Zahl zehn und berechnen:

10 5 = 100.000

Als Geheimtext erhalten wir: Einhunderttausend. Wir entschlüsseln mit dem geheimen Schlüssel:

100.000 1/5 = 10

Da sich die Schlüssel gegenseitig aufheben, funktioniert das. Allgemein ausgedrückt gilt also für:

die Nachricht N,
den öffentlichen Schlüssel ,
den geheimen Schlüssel Sg
und den Geheimtext G:

Verschlüsseln: G = N
und Entschlüsseln: N = G Sg .

Wahrscheinlich ist Euch aufgefallen: Wenn man den öffentlichen Schlüssel kennt, kennt man auch den geheimen. Sg ist alles andere als geheim. - Wer fünf kennt, kennt auch den Kehrwert 1/5. Sg lässt sich ganz einfach aus herleiten:

Sö × x = 1 dann ist x = 1/Sö

Kryptographen standen vor der Aufgabe, ein Schlüsselpaar zu entwerfen, in dem sich die Schlüssel zwar gegenseitig aufheben, aber sich dennoch nicht von einander herleiten lassen. Als Grundlage wählten sie eine besondere Rechenart, die der modularen Arithmetik.

 

Modulare Arithmetik

In dieser Rechenart arbeiten Mathematiker mit Divisionsresten. Der Rest der Division 22 durch 3 ist 1. Man schreibt:

22 mod 3 = 1.

(Und man spricht 22 modulo 3, Betonung auf dem ersten o.) Die 3 nennt der Mathematiker Modul und die 1 Residuum. Ein weiteres Beispiel: 11 Uhr und 23 Uhr haben den gleichen Rest, wenn man sie durch 12 teilt, nämlich 11. Beide sind äquivalent modulo 12. Das selbe gilt für 35, 47 ...

11 mod 12 = 11
23 mod 12 = 11
35 mod 12 = 11
usw.

Wandeln wir das oben gezeigte Verschlüsselungsbeispiel mit fünf und ein Fünftel in die modulare Arithmetik, bleibt fünf der öffentliche Schlüssel. Das Chiffrieren sieht so aus:

10 5 mod 17

Allgemein:

G = N mod n

Welche Zahl man als Modul n wählt, in unserem Beispiel die 17, ist nicht ganz willkürlich: Sie muss eine Primzahl sein, alle zu verschlüsselnden Zahlen müssen kleiner sein als sie und (n-1) darf keinen gemeinsamen Teiler mit haben. Diese letzte Bedingung heißt "relativ prim" und spielt eine Rolle bei der Berechnung des Kehrwertes, also des geheimen Schlüssels. Die Berechnung ist aufwendig. Erinnert Ihr Euch an die einfache Formel von oben: Sö × x = 1? In modularer Arithmetik sieht der Kehrwert, der die Verschlüsselung rückgängig macht, so aus:

(Sö × x) mod (n-1) = 1

Den Beweis dieser Formel lasse ich außen vor. In unserem Beispiel:

(5 × x) mod (17-1) = 1

Zur Auflösung von x benötigt man den Euklidischen Algorithmus oder die Eulersche Verallgemeinerung. Bei kleinen Zahlen ist es aber genauso einfach, der Reihe nach alle Möglichkeiten für x auszuprobieren, bis man eine findet, deren Divisionsrest 1 ergibt. Die Lösung für unser Beispiel lautet jedenfalls: x = 13 = Sg. Kehren wir zurück zum Beispiel und verschlüsseln mit 5:

G = N mod n = 10 5 mod 17
= 100000 mod 17 = 6

Mit 13 können wir dechiffrieren:

N = G Sg mod n = 6 13 mod 17
= 13060694016 mod 17 = 10

Die Berechnungen sehen schwieriger aus, als sie sind, denn es gilt das Distributivgesetz.

Der öffentliche Schlüssel besteht nun aus zwei Komponenten: dem Schlüssel selbst und dem Modul n, da ohne dieses der Kommunikationspartner die Berechnungen nicht durchführen kann. n ist aus dem gleichen Grund auch Teil des geheimen Schlüssels. Der Unterschied zwischen beiden Schlüsseln besteht also nach wie vor allein aus Wert und Kehrwert, die sich - nun wesentlich verkompliziert -gegenseitig aufheben.

 

Faktorisierung

Wenn auch schwierig, so ist es immer noch möglich, aus den beiden Komponenten des öffentlichen Schlüssels ( und n) den geheimen herzuleiten. Es fehlt ein weiterer, letzter Schritt: Die gezeigten modularen Formeln funktionieren auch, wenn man für n statt einer Primzahl das Produkt zweier Primzahlen nimmt: n = p × q. Die Bedingungen für n lauten: Der zu verschlüsselnde Wert muss kleiner als n sein und muss relativ prim zu ((p-1) × (q-1)) sein, d.h. darf keinen gemeinsamen Teiler besitzen.

Zur Berechnung des geheimen Schlüssels benötigen wir dann folgende Formel:

(Sö × x) mod ((p-1) × (q-1)) = 1

Nun sind wir beim Kern der Sache angelangt: Kennt man p und q, ist es nicht so schwer, Sg zu errechnen. Es funktioniert wieder mit Euklidischem Algorithmus oder Eulerscher Verallgemeinerung. Hat das Verschlüsselungsprogramm den privaten Schlüssel erzeugt, wirft es p und q jedoch weg. Will nun ein Angreifer den geheimen Schlüssel aus dem öffentlichen errechnen, muss er selbst n in seine Faktoren p und q zerlegen. 63 in 7 × 9 zu zerlegen, ist noch recht einfach, jedoch 1536251047 in 23279 × 65993 für einen Menschen schon eine schwierigere Aufgabe - für einen Computer noch ein Kinderspiel. Je größer nun n ist, desto länger dauert das Knacken. Die Größe von n wird so gewählt, dass heutige Computer sie theoretisch erst in Jahrmillionen zerlegen können. Zurück zum Beispiel. Wir halten 5 als öffentlichen Schlüssel und wählen p = 7 und q = 9. Damit ist n also 63. Dann berechnen wir den geheimen Schlüssel:

(5 × x) mod ((7-1)(9-1)) = 1

Mit der Eulerschen Verallgemeinerung berechnen wir: x = 29. Wir verschlüsseln:

G = N mod n = 10 5 mod 63 = 19

Nun dechiffrieren wir (mit Hilfe des Distributivgesetzes):

N = G Sg mod n = 1929 mod 63 = 10

Genau so arbeitet RSA. Nur, dass die Zahlen wesentlich größer sind, als die hier vorgestellten. Ein Bit-Länge von 1024 für n wird allgemein empfohlen. Soll der verschlüsselte Text lange Zeit unangreifbar sein, so empfehlen sich 2048 Bits. Das schließt eine Faktorisierung quasi aus. Es sei denn, es fänden sich neue mathematische Methoden zur Primfaktorenzerlegung. Diese Unsicherheit haftet dem RSA-Verfahren an.

 

Zusammenfassung

Ein Verschlüsselungsprogramm, das ein Schlüsselpaar erzeugt, sucht zuerst zwei große Primzahlen p und q, die das Modul n der beiden Schlüssel bilden. Dann sucht es einen öffentlichen Schlüssel der keinen gemeinsamen Teiler zu ((p-1) × (q-1)) hat. Dann berechnet es für den privaten Schlüssel Sg den Kehrwert von . Die Faktoren p und q vernichtet es. Damit ist es nach heutigem Kenntnisstand unmöglich, den geheimen aus dem öffentlichen Schlüssel herzuleiten.

  • n = p × p wobei p und q zwei große Primzahlen sind
  • muss relativ prim zu ((p-1) × (q-1)) sein
  • Sg ist dann das Ergebnis der Gleichung: (Sö × x) mod ((p-1) × (q-1)) = 1
  • G = N mod n
  • N = G Sg mod n

 

Dieser Text ist Wolfi gewidmet, mit dem ich das Thema kurz vor seinem Tod noch intensiv besprochen habe.

 

(c) Autor und Copyright Wolf Hosbach

 

Letzte Änderung: 1. Februar 2006