Wie funktioniert die RSA-Verschlüsselung?

Die Frage “Wie funktioniert die RSA-Verschlüsselung?” kann auf zwei Weisen verstanden werden:

1. Welche Berechnungen sind für die RSA-Ver- und Entschlüsselung notwendig?
2. Warum funktionieren die entsprechenden Formeln?

Im Folgenden werde ich erst die für die RSA-Ver- und Entschlüsselung notwendigen Berechnungen kurz erklären und anschließend darlegen, warum diese Formeln funktionieren.

1 Berechnungen zur Ver- und Entschlüsselung

Bevor man ver- und entschlüsseln kann, muss zunächst ein entsprechendes Schlüsselpaar erzeugt werden (Abschnitt 1.1). Im darauf folgenden Abschnitt 1.2 wird das Schlüsselpaar verwendet, um Klartext zu verschlüsseln und anschließend wieder zu entschlüsseln.

1.1 Erzeugung eines Schlüsselpaares

Um ein Schlüsselpaar zu erzeugen, werden zwei große Primzahlen benötigt, nennen wir sie p und q. Diese Primzahlen werden nur zur Erzeugung des Schlüsselpaares benötigt, genauer, um aus dem öffentlichen Schlüssel den privaten zu berechnen. Wenn dies geschehen ist, werden die Primzahlen nicht mehr gebraucht.

Aus den beiden Primzahlen wird das Produkt m berechnet, das anschließend als Restklasse (modulo) verwendet wird:

(1) m=p*q

Anschließend wählt man eine zufällige Zahl e (enkodieren), die (zusammen mit m) als öffentlicher Schlüssel verwendet wird. Sie muss teilerfremd zu und kleiner als phi(m) sein. Im nächsten Schritt muss aus diesem Schlüssel der Schlüssel zum Entschlüsseln d (dechiffrieren) berechnet werden. Dazu wird ein d gesucht, so dass die folgende Formel erfüllt wird:

(2) e*d mod phi(m) = 1

phi() bezeichnet die Euler-Funktion. Sie ist für große Zahlen so aufwändig zu bestimmen, dass selbst moderne Computer dafür Jahrzehnte brauchen würden. Es gibt allerdings eine Ausnahme: Wenn die Primzahl-Zerlegung von m bekannt ist. Da wir m als Produkt aus zwei Primzahlen berechnet haben, kennen wir die Primzahlzerlegung: p und q. Für diesen Fall berechnet sich phi(m) zu:

(3) phi(m)=(p-1)*(q-1)

Nun wird (2) mit Hilfe des erweiterten euklidischen Algorithmus gelöst.

Dann haben wir:

(e,m) als öffentlichen Schlüssel und

(d,m) als privaten Schlüssel.

Alle anderen Werte werden nicht mehr benötigt.

1.2 Ver- und entschlüsseln

Eine Zahl K (Klartext) kann dann mit dem öffentlichen Schlüssel wie folgt verschlüsselt werden:

(4)

V ist der verschlüsselte Klartext. Diese Zahl kann mit Hilfe der folgenden Formel wieder entschlüsselt werden:

(5) V^d mod m = K

2 Warum funktionieren die Formeln zur Ver- und Entschlüsselung?

Es soll gezeigt werden, dass nach Anwendung der Verschlüsselungsformel (4) auf K und anschließend der Entschlüsselungsformel (5) wieder die ursprüngliche Zahl K heraus kommt.

Zunächst muss dies leicht eingeschränkt werden: Die Ver- und Entschlüsselung funktioniert nur für den Klartext K, wenn er zum Modulo m teilerfremd ist.

Das RSA-System funktioniert, weil

1. alle zu m teilerfremden Zahlen Modulo m eine Gruppe bilden (Behauptung 1) und
2. in einer Gruppe immer gilt, dass eine Zahl aus der Gruppe potenziert mit der Anzahl der Elemente in der Gruppe immer die Zahl eins ergibt (Behauptung 2: Satz von Euler-Fermat).

Zunächst zeige ich, dass, wenn diese beiden Bedingungen erfüllt sind, tatsächlich das RSA-Verfahren funktioniert. Anschließend zeige ich, dass beide Bedingungen erfüllt werden.

Ver- und Entschlüsselung hintereinander angewandt ergibt:

(6) (K^e)^d mod m = K

Es soll hier gezeigt werden, dass dabei K wieder heraus kommt. In (6) können die Klammern aufgelöst werden:

(7) K^e*d mod m = K

Wenn man mit a die Anzahl der Elemente (d.h. die Anzahl der zu m teilerfremden Zahlen) bezeichnet, dann gilt:

(8) K^a *K mod m = K,

denn gemäß Behauptung 2 gilt: K^a mod m = 1. Formel (8) kann umgeformt werden zu

(9) K^a+1 mod m = K

Da eine Zahl potenziert mit der Anzahl der Elemente a die Zahl 1 ergibt, tut es das auch für 2*a, 3*a, 4*a…, allgemein f*a:

(10) K^a*f+1 mod m = K

D.h. Gleichung (7) ist erfüllt, wenn gilt:

(11) a*f+1=d*e

Dies entspricht der Berechnung von d nach Formel (2), denn phi(m) gibt die Zahl der zu m teilerfremden Zahlen a an (dies ist die Definition der Euler-Funktion):

(12) a=phi(m)

In (11) eingesetzt erhalten wir:

(11) phi(m)*f + 1=d*e

Wenn man in (2) das Modulo phi(m) entfernt, indem man einen passenden Faktor f wählt, erhält man genau (11).

Damit ist gezeigt, dass – wenn die Behauptungen 1 und 2 zutreffen – durch Einsetzen einer Zahl K in Formel (4) eine verschlüsselte Zahl V berechnet werden kann, so dass durch Einsetzen dieser Zahl in Formel (5) wieder die ursprüngliche Zahl K herauskommt. In den folgenden Kapiteln werden dementsprechend die Behauptungen 1 und 2 bewiesen.