Die RSA-Chiffre

RSA ist ein Verschlüsselungsverfahren, das nach den Nachnamen der Mathematiker Ronald Rivest, Adi Shamir und Leonard Adleman benannt ist. Obwohl die Sicherheit dieses Verfahrens nie bestätigt wurde, ist sich jeder sicher, dass es nicht in nächster Zeit geknackt werden kann. Die Sicherheit dieses Verfahrens basiert auf der Schwierigkeit, große Zahlen mit wenig Primfaktoren zu faktorisieren. Gelingt dies für einen RSA-Schlüssel, so ist dieser geknackt und damit wertlos. Doch es verbergen sich noch weitere Tücken, die später behandelt werden.

RSA ist das erste praktisch angewandte Beispiel einer sogenannten Falltürfunktion. Jeder kann durch eine Falltür fallen, doch nur diejenigen, die den geheimen Ausgang kennen, kommen auch wieder heraus. Die erste Idee für solch eine Falltürfunktion kam vom Studenten Ralph Merkle, der mit seiner Idee Merkles Rätsel ein Chiffreverfahren analog zur Falltürfunktion publizierte und damit die Existenz asymmetrischer Chiffren ein Stück glaubhafter machte. Sein Verfahren wurde nie praktisch angewandt, lieferte aber eine Basis für eine völlig neuartige Chiffre, die das Schlüsseltauschproblem lösen sollte. Kurz darauf wurde von Whitfield Diffie und Martin Hellman das Diffie-Hellman-Protokoll bekannt gegeben, das es ermöglicht, einen geheimen Schlüssel über eine unsichere Leitung zu vereinbaren. Dieses Protokoll lieferte die Grundidee für das RSA-Verfahren. Da das Protokoll sehr simpel ist, wird es später kurz vorgestellt. Der aufmerksame Leser dürfte eine gewisse Ähnlichkeit mit dem RSA-Verfahren feststellen.

Hier ist anzumerken, dass das RSA-Verfahren oft fälschlicherweise als RSA-Algorithmus bezeichnet wird. Diese Bezeichnung trifft nicht zu und ist damit nicht korrekt. Die darunterliegenden einzelnen Rechenschritte lassen sich als Algorithmen implementieren, doch RSA selbst ist nur ein mathematischer Satz; daher sollten die Bezeichnungen RSA-Verfahren oder RSA-Chiffre vorgezogen werden. Der Satz wird am Ende des Kapitels Eulersche phi-Funktion - Eulers Theorie aufgezeigt und im Kapitel Das RSA-Verfahren dann angewandt.

Vor 1976 gab es nur die sogenannten symmetrischen Chiffren. Diese arbeiten mit einem einzigen Schlüssel für Ver- und Entschlüsselung. Lautet die Chiffrierfunktion E(m, k), wobei m die Nachricht und k der Schlüssel ist, so lautet die Dechiffrierfunktion D(c, k) mit c als Chiffretext (Rückgabewert von E). Die Funktion D wirkt nur dann invers zu E, wenn für beide Schritte der gleiche Schlüssel k oder ein dazu kongruenter Schlüssel angegeben wird. In dem Fall kann man sagen: m = D(E(m, k), k). Diese Form der Verschlüsselung wird auch heute sehr exzessiv genutzt, da sie, verglichen mit den asymmetrischen Chiffren, durch einen Computer sehr schnell und effizient durchfürbar ist.

Die asymmetrische Chiffre teilt den Schlüssel k in zwei gegenseitig inverse Schlüssel e und d auf. Wird mit dem Schlüssel e chiffriert, kann nur mit dem Schlüssel d wieder dechiffriert werden. Wird hingegen mit dem Schlüssel d chiffriert, so kann nur mit e dechiffriert werden. Einer dieser Schlüssel wird als öffentlicher und der andere als geheimer Schlüssel festgelegt. Jeder kann mit dem öffentlichen Schlüssel verschlüsseln, jedoch kann nur der Eigentümer des dazugehörigen geheimen Schlüssels die Verschlüsselung umkehren. Andersrum kann eine Nachricht mit dem geheimen Schlüssel verschlüsselt werden. Jeder kann sie mit dem öffentlichen Schlüssel dechiffrieren und lesen, aber nur der Eigentümer des geheimen Schlüssels kann solche Nachrichten erstellen (Signaturprinzip). Lautet die Chiffrierfunktion E(m, e) mit m als Nachricht und e als öffentlichen Schlüssel, so lautet die Dechiffrierfunktion D(c, d), mit c als Chiffretext und d als geheimen Schlüssel. Die Funktion D wirkt nur dann invers zu E, wenn beim Dechiffrieren der zum öffentlichen Schlüssel e gehörende geheime Schlüssel d oder ein Schlüssel kongruent zu d angegeben wird, oder andersrum. Man kann also sagen: m = D(E(m, e), d) und m = D(E(m, d), e). Diese Form der Verschlüsselung wird meist nur zur Schlüsselvereinbarung und zur Signatur genutzt, da sie wesentlich langsamer als die symmetrische Chiffre ist. Sie wird mit den symmetrischen Chiffren kombiniert.

Die klassischen symmetrischen Chiffren hatten alle ein Problem gemeinsam: das Schlüsseltauschproblem. Die Sicherheit eines Verfahrens ist wertlos, solange man keine Möglichkeit hat, mit dem anderen Endpunkt der Kommunikation einen geheimen Schlüssel zu vereinbaren. Man stelle sich folgendes Szenario vor: Alice möchte eine geheime Nachricht an Bob senden. Die einzige Kommunikationsmöglichkeit zwischen Alice und Bob ist jedoch eine lange Kupferleitung, die von jedem angezapft werden könnte. Alice und Bob kennen sich nicht und haben noch nie zuvor einen geheimen Schlüssel vereinbart. Genau hier wird das Schlüsseltauschproblem deutlich. Wie kann Alice auf sicherem Wege mit Bob einen Schlüssel vereinbaren?

1976 wurde die erste elegante Lösung dieses Problems vorgestellt: das Diffie-Hellman-Protokoll. Eine wichtige Einschränkung dieses Protokolls ist, dass es eben nur ein Protokoll zur Schlüsselvereinbarung ist und interaktiver Informationsaustausch notwendig ist. Mit diesem Protokoll sind weder Signaturen, noch Authentifizierung möglich. 1977 wurde dann die erste echte Chiffre bekannt gegeben, die das Schlüsseltauschproblem fast (siehe unten das Man in the Middle - Problem) gegenstandlos machte: RSA. Mit dieser kann man Nachrichten nun auch signieren und Benutzer authentifizieren.

Nun möchten wir langsam zum mathematischen Teil übergehen. Hier folgt nun eine kleine Einführung in die Mengenlehre. Wer sich mit dieser bereits auskennt, kann dieses Kapitel überspringen. Ich empfehle dennoch, es zu lesen. Man lernt nie aus.

In der Mathematik arbeiten wir mit einer Einheit, die wir schlichtweg Zahl nennen. Es gibt nun verschiedene Zahlen mit verschiedenen Eigenschaften. Es gibt ganze Zahlen, also Zahlen ohne Nachkommaanteil, es gibt rationale Zahlen, also Zahlen, die sich als Bruch (engl. ratio) mit ganzen Zahlen als Zähler und Nenner darstellen lassen und irrationale Zahlen, also Zahlen, die sich nicht als Bruch darstellen lassen. Es gibt noch weitere Arten von Zahlen wie die komplexen Zahlen. Die Zahl 25 ist beispielsweise eine ganze Zahl. Wir sagen, sie hat keinen Nachkommaanteil, was allerdings nicht ganz der Wahrheit entspricht. Nach dem Komma folgen unendlich viele Nullen. Diese Zahl könnte man also auch als 25.00000 notieren. Die 25 ist gleichzeitig auch eine rationale Zahl, denn sie lässt sich als Bruch 25/1 darstellen. Noch ein Beispiel für eine rationale Zahl wäre 1.25. Diese Zahl ist keine ganze Zahl, lässt sich jedoch als Bruch darstellen: 5/4. Ein weiteres Beispiel wäre die Zahl 1/3. Sie lässt sich nur mit einer Periode eindeutig als Dezimalzahl darstellen. Beispiele für irrationale Zahlen sind die Quadratwurzel aus zwei, die Eulersche Zahl e und die Kreiszahl pi (dargestellt als griechischer Buchstabe PI). Diese Zahlen haben unendlich viele Nachkommastellen ohne eine Periode und lassen sich auch nicht als Bruch darstellen.

Diese Zahlen werden benannten Mengen untergeordnet. Beispielsweise gibt es die Menge der natürlichen Zahlen. Diese Menge enthält alle Ganzzahlen von 1 aufwärts. Die Zahlen 1, 2, 3, 4 usw. gehören zu dieser Menge. Man sagt, sie sind Elemente der Menge der natürlichen Zahlen. Auch werden die Mengen selbst abgekürzt. Die Menge der natürlichen Zahlen heißt N. Man sieht sofort, dass diese Menge unendlich viele Elemente besitzt. Die untere Grenze ist 1, es gibt also keine Zahl kleiner als 1. Eine obere Grenze ist jedoch nicht gesetzt, also gibt es von 1 aufwärts unendlich viele Elemente. Die Menge N mit dem Subskript 0, also die Menge N[0] enthält zusätzlich noch die 0. N ist eine Untergruppe von N[0], denn alle Elemente von N sind gleichzeitig Elemente von N[0]. Eine weitere Menge mit ganzen Zahlen ist die Menge Z. In dieser Menge hat jedes Element ein eindeutiges additives inverses Element. In diesem Fall sind das die negativen Zahlen. Das additive Inverse zu 3 ist -3. In jeder Menge ist das neutrale Element der Addition invers zu sich selbst. In N[0] und Z ist 0 das neutrale Element der Addition (Addition mit 0 hat keine Wirkung). N hat kein solches Element. Z ist die erste Menge, die beidseitig unendlich ist. Sie geht unendlich in die positive und in die negative Richtung. N und N[0] sind Untergruppen von Z.

Die Menge der rationalen Zahlen wird als Q bezeichnet. Alle Zahlen, die sich als Bruch darstellen lassen, sind Elemente von Q. Es wird ersichtlich, dass Z eine Untergruppe von Q ist, denn alle Elemente von Z sind gleichzeitig auch Elemente von Q. Andersherum ist dies nicht der Fall. Auch zeigt sich, dass N und N[0] auch Untergruppen von Q sind, da sie Untergruppen von Z sind und Z eine Untergruppe von Q ist. Auch diese Menge ist unendlich. Interessant ist, dass zwischen jeden zwei Elementen unendlich viele weitere Elemente liegen. Zwischen 3.5261 und 3.5262 liegen unendlich viele Elemente wie z.B. 3.52617.

Wenn wir uns nun den Graphen für die Funktion f(x) = x, wobei x eine rationale Zahl sein muss, ansehen, sehen wir eine diagonale Gerade. Überraschenderweise ist diese Gerade alles andere als dicht. Zwischen zwei Punkten existieren unendlich viele weitere Punkte. Aber auch existieren unendlich viele Löcher, denn zwischen jeden zwei Elementen von Q gibt es unendlich viele Zahlen, die sich nicht als Bruch darstellen lassen. Diese Funktion ist beispielsweise für die Quadratwurzel aus zwei nicht definiert. Also ist an dieser Stelle ein Loch in der Geraden. Aus diesem Grund führen wir eine weitere Menge ein: die Menge der reellen Zahlen. Nicht, dass alle anderen Zahlen unreell sind. Dies ist schlicht der Name für eine Menge, in der die rationalen Zahlen und die irrationalen Zahlen zusammengefasst werden. Die Menge heißt R. Jetzt erst ist der Werte- und Definitionsbereich von f(x) = x dicht.

Es gibt noch weitere Mengen wie die Menge der komplexen Zahlen C, doch dies übersteigt den Rahmen dieser Dokumentation. Die bisher vorgestellten Mengen waren unendlich. Entweder ließen sie sich von einem Punkt unendlich auf eine oder beide Seiten fortführen, oder es existieren allein zwischen zwei noch so nah beieinander liegenden Punkten unendlich viele weitere Punkte. In diesem Text allerdings arbeiten wir mit einer speziellen Menge, der endlichen Menge. Unsere Menge besteht nur aus Ganzzahlen, daher machen wir uns Z zum Vorbild und nennen unsere Menge Z[n], wobei n das Modul ist. Das Modul ist die Anzahl der Zahlen in dieser Form der endlichen Menge. Wir bezeichnen sie als Modul, weil wir die modulare Arithmetik in dieser Menge anwenden können. Es gibt zwar keine negativen Zahlen, wir haben uns aber dennoch für den Namen Z[n] statt N[n] entschieden, denn in der Menge Z geht es nicht um die Einführung der negativen Zahlen, sondern um die Einführung eines additiven Inversen für jedes Element. In N[0] ist 0 das einzige Element mit einem additiven Inversen. Das Element ist invers zu sich selbst. In N gibt es überhaupt keine additiven inversen Elemente. Additionen sind nicht per Addition umkehrbar. In Z[n] gibt es wie in Z auch zu jedem Element ein eindeutiges additives inverses Element, das allerdings nicht negativ ist. Auch in Z[n] ist die 0 invers zu sich selbst. Die endlichen Mengen werden im Kapitel über die modulare Arithmetik eingeführt.

Mengen haben bestimmte Eigenschaften bezüglich den erlaubten Operationen. Beispielsweise hat in N kein einziges Element ein additives inverses Element. In Z lässt sich die Multiplikation nur umkehren, wenn wir mit 1 (dem neutralen Element der Multiplikation) multiplizieren. Eine Menge wird als additive Gruppe bezeichnet, sofern sie folgende Voraussetzungen erfüllt: es existiert für jedes Element ein eindeutiges additives inverses Element und es existiert genau ein neutrales Element der Addition, das invers zu sich selbst ist. Für die Addition gelten das Kommutativgesetz und das Assoziativgesetz. Eine Menge wird als multiplikative Gruppe bezeichnet, sofern sie folgende Voraussetzungen erfüllt: es existiert für jedes Element, außer dem neutralen Element der Addition, ein eindeutiges multiplikatives inverses Element und es existiert genau ein neutrales Element der Multiplikation. Das neutrale Element der Multiplikation ist invers zu sich selbst und eine Multiplikation mit dem neutralen Element der Addition ist nicht umkehrbar. Für die Multiplikation gelten das Kommutativgesetz, das Assoziativgesetz und das Distributivgesetz. Hier wird sichtbar, dass N und N[0] weder eine additive, noch eine multiplikative Gruppe sind. Z ist eine additive Gruppe, denn jedes Element hat ein eindeutiges inverses Element (z.B. ist -5 invers zu 5 und andersherum), es existiert ein neutrales Element der Addition: 0. Z ist jedoch keine multiplikative Gruppe. Q und R sind additive und multiplikative Gruppen. Z[n] ist eine additive Gruppe und unter bestimmten Voraussetzungen auch eine multiplikative Gruppe. Endliche Mengen, die additive und multiplikative Gruppen sind, werden als endliche Körper bezeichnet. Mehr dazu später.

Eine Kongruenz drückt aus, dass zwei Zahlen in einer Menge die gleichen Zahlen sind. Man könnte sie also problemlos untereinander austauschen, ohne Einfluss. Die Kongruenz wird normalerweise mit einem Gleichheitszeichen mit drei Strichen ausgedrückt, aber dieses steht nicht zur Verfügung. Somit arbeiten wir mit den normalen Gleichheitszeichen, was nicht unbedingt korrekt ist. Die Aussage 3 = 7 ist falsch. Soll sie jedoch eine Kongruenz darstellen, hängt es davon ab, in welcher Menge wir arbeiten. In Z[4] wäre diese Aussage nämlich richtig. Wir dürfen sie dennoch nicht als Gleichung darstellen, denn 3 und 7 sind nicht die gleichen Zahlen. Man sagt, 3 ist kongruent zu 7 in der Menge Z[4]. Kongruenzen in der endlichen Menge Z[n] werden folgendermaßen ausgedrückt:

a = b (mod n)

Diese Kongruenz sagt aus, dass a kongruent zu b in der Menge Z[n] ist. Diese Form der Kongruenz lässt sich auch in eine Gleichung umschreiben. Die Kongruenz entspricht der folgenden Gleichung:

a mod n = b mod n

Wir werfen eine Geburtstagsfeier. So wie es sich gehört haben wir auch eine Torte gemacht. Natürlich möchten wir fair sein und teilen diese Torte in genau so viele Teile auf wie die Anzahl der Teilnehmer an der Feier. Sind also 8 Teilnehmer anwesend, teilen wir diese Torte in genau 8 Teile. Was ist aber, wenn wir eine vorgefertigte und bereits in 20 Teile geschnittene Torte kaufen? Jedes Teil hat eine einheitliche Form. Wir möchten die einzelnen Teile nicht zerschneiden, sonst würden wir diese Form zerstören. Hier stehen wir vor einem Problem. 20 lässt sich nicht restlos durch 8 teilen. Wir müssten jedem Teilnehmer zwei Teile übergeben, denn das wäre fair. Was machen wir aber mit den vier verbleibenden Teilen?

Wir sehen, dass 20 nicht restlos durch 8 teilbar ist. Hätten wir eine Torte mit 16 Teilen gekauft, wäre das kein Problem gewesen, denn 16 ist restlos durch 8 teilbar. Die Teilbarkeit von ganzen Zahlen spielt in sehr vielen Bereichen der Mathematik eine Rolle, z.B. beim Kürzen von Brüchen. Zunächst führen wir einige mathematische Operationen ein. Die bekannteste und wichtigste Operation ist die Division. Da wir jedoch nur mit Ganzzahlen arbeiten, arbeiten wir auch nur mit Ganzzahldivisionen. Eine Ganzzahldivision ist nicht anders als die normale Division, mit dem Unterschied, dass vom Ergebnis der Nachkommaanteil abgeschnitten wird. So ist das Ergebnis von 20 / 8 die Zahl 2. Das tatsächliche Ergebnis wäre 2.5, doch wir haben den Nachkommaanteil abgeschnitten. Das ist gleichbedeutend mit Abrunden. Es ist sehr wichtig, anzumerken, dass wir niemals aufrunden. Selbst 2.9999 runden wir zu 2 ab. Als nächste Operation ist die modulo-Operation einzuführen. Die Operation a mod b (sprich: a modulo b) ist nichts anderes als der Rest der Division a / b. Somit ist 17 mod 3 der Rest der Division 17 / 3. Das Ergebnis ist also 2.

Diese beiden Operationen haben einige Eigenschaften, die ebenfalls besprochen werden müssen. 20 / 8 liefert als Ergebnis 2.5. Das heißt, 2.5 * 8 ergibt wieder 20. Wir subtrahieren jedoch den Nachkommaanteil 0.5 vom Ergebnis, somit verbleibt ein Rest von 0.5 * 8, also 4. Wir können den Rest jedoch auch ohne Kommazahlen berechnen. 20 / 8 ergibt 2, aber 2 * 8 ergibt nicht 20, sondern 16. Somit ist ein Wert von 4, oder 20 - 16 verloren gegangen. a mod b können wir also dadurch berechnen, dass wir zuerst a durch b teilen und gleich darauf wieder mit b multiplizieren. Das Ergebnis subtrahieren wir von a. Somit lässt sich a mod b anhand folgender Formel berechnen, sofern kein Rechner mit modulo-Operation zur Verfügung steht:

// Achtung: Ganzzahldivision!
a mod b = a - a / b * b

// Beispiel:
  20 mod 8
= 20 - 20 / 8 * 8
= 20 - 2 * 8
= 20 - 16
= 4

Hier sollen noch einige Eigenschaften der modulo-Operation zusammengefasst werden, welche für die modulare Arithmetik von sehr großer Bedeutung sind:

1. (a + b) mod n = ((a mod n) + (b mod n)) mod n
2. (a * b) mod n = ((a mod n) * (b mod n)) mod n
3. a^b mod n = (a mod n)^(b mod phi(n)) mod n

(aq + bq + ar + br) mod n

  (aq + bq + ar + br) mod n
= (ar + br) mod n
= ((a mod n) + (b mod n)) mod n

  (a * b) mod n
= ((aq + ar) * (bq + br)) mod n

  ((aq + ar) * (bq + br)) mod n
= ((aq * bq) + (aq * br) + (ar * bq) + (ar * br)) mod n

  ((aq * bq) + (aq * br) + (ar * bq) + (ar * br)) mod n
= (ar * br) mod n
= ((a mod n) * (b mod n)) mod n

Wir gehen weiterhin davon aus, dass wir nur mit Ganzzahlen arbeiten, uns also keine Möglichkeit für Kommazahlen zur Verfügung steht. Wir können also testen, ob a durch b teilbar ist, indem wir a durch b teilen und anschließend sofort wieder mit b multiplizieren. Ist das Ergebnis a, so ist a durch b teilbar. Liefert a / b * b als Ergebnis a, dann ist auch der Rest 0, denn in dem Fall gilt a - a / b * b = 0 bzw. a - a = 0. Wir können also sagen, a ist durch b teilbar, wenn a mod b = 0 gilt; oder als Kongruenz ausgedrückt: a = 0 (mod b). Weiters gilt: (k * n) mod n = 0 für jede beliebige Ganzzahl k, denn eine Zahl teilt immer restlos Vielfache von sich selbst.

(k * n) mod n = 0          // Nach der oben genannten Formel:
k * n - k * n / n * n = 0
k * n - k * n = 0

Als Kongruenz ausgedrückt: k * n = 0 (mod n). Wir können also auch sagen: k * n + x = x (mod n). Dies ist ein sehr wichtiger Satz für die modulare Arithmetik. Mehr dazu später.

Es gibt bestimmte Zahlen, die genau zwei Teiler haben. Sie lassen sich nur durch 1 und durch sich selbst teilen. Ein Beispiel ist die 7. Die 7 lässt sich nur durch 1 und durch 7 teilen. Ein anderes Beispiel ist die 47, welche nur durch 1 und 47 teilbar ist. Um dies zu verdeutlichen, greifen wir das obige Beispiel mit der Torte noch einmal auf. Wäre die Anzahl der Tortenstücke eine solche Zahl, so hätten wir auf jeden Fall einen Rest, wenn die Anzahl der Teilnehmer weder 1, noch die Anzahl der Tortenstücke ist. Hätten wir also eine Torte mit 17 Teilen, so müssten entweder einer oder 17 Teilnehmer anwesend sein. Bei jeder beliebigen Zahl zwischen 1 und 17 würde ein Rest verbleiben. Zahlen mit dieser Teilbarkeitseigenschaft nennen wir Primzahlen. Es ist bereits erwiesen, dass es unendlich viele Primzahlen gibt. Die kleinste Primzahl ist 2. Die Zahl 1 ist keine Primzahl, denn sie hat nur einen Teiler: 1. Auch die Zahl 0 ist keine Primzahl, denn sie hat unendlich viele Teiler. Jede Zahl (außer 0 natürlich) teilt die 0 restlos.

0 mod x = 0        // Nach der obigen Formel:
0 - 0 / x * x = 0
0 - 0 = 0

Eine interessante Eigenschaft der Primzahlen ist, dass sich jede beliebige Ganzzahl größer als 1 als Produkt von Primzahlen darstellen lässt. Beispielsweise lässt sich 42 als Produkt der Primzahlen 2, 3 und 7 darstellen: 2 * 3 * 7 = 42. Die einzelnen Faktoren werden dabei Primfaktoren genannt. Noch viel interessanter ist, dass man jeder Zahl größer als 1 einen eindeutigen Satz Primfaktoren zuordnen kann. 2 * 3 * 7 ergibt auf jeden fall 42 und es gibt garantiert keine andere Zahl, die sich als Produkt von 2, 3 und 7 darstellen lässt. Es gibt auch garantiert keinen anderen Weg, die 42 in Primfaktoren zu zerlegen. Man kann also sagen, jede Zahl lässt sich auch eindeutig als Produkt von Primzahlen darstellen.

Oftmals kommen das kleinste gemeinsame Vielfache (kgV) und (vor allem bei RSA) der größte gemeinsame Teiler (ggT) zum Einsatz. Das kgV ist die kleinste Zahl, die sich gleichzeitig als Vielfaches zweier Zahlen a und b darstellen lässt. Das kgV von 15 und 24 ist also 120, denn es gibt keine kleinere Zahl, die gleichzeitig Vielfaches von 15 und 24 ist. Der ggT ist die größte Zahl, die zwei Zahlen a und b restlos teilt. Der ggT von 12 und 15 ist also 3, denn es gibt keine größere Zahl, die 12 und 15 restlos teilt. Das kgV lässt sich berechnen, indem man die Primfaktoren von a und b kombiniert, von den gemeinsamen Faktoren aber nur die höchste Potenz verwendet. Beispiel:

// kgV von 56 und 60:
56 = 2 * 2 * 2 * 7 = 2^3 * 7
60 = 2 * 2 * 3 * 5 = 2^2 * 3 * 5

kgv(56, 60) = 2^3 * 3 * 5 * 7 = 840

Der ggT lässt sich dadurch berechnen, dass man die gemeinsamen Primfaktoren von a und b kombiniert:

// ggT von 350 und 616
350 = 2 * 5^2 * 7  = 2 * 5 * 5 * 7
616 = 2^3 * 7 * 11 = 2 * 2 * 2 * 7 * 11

ggT(350, 616) = 2 * 7 = 14

Sind keine gemeinsamen Primfaktoren aufzufinden, so ist 1 der größte gemeinsame Teiler, denn 1 teilt jede Zahl restlos. Wenn der größte gemeinsame Teiler zweier Zahlen 1 ist, so sagt man, die beiden Zahlen sind teilerfremd oder relativ prim, sie haben also keine Primfaktoren gemeinsam. Zum Thema ggT wird später der Euklidsche Algorithmus vorgestellt, mit dem sich der ggT auf systematischem Wege berechnen lässt, ohne a und b erst faktorisieren zu müssen. Wir verwenden ab jetzt die englische Bezeichnung gcd (engl. greatest common divisor) anstatt ggT für den größten gemeinsamen Teiler.

Um RSA überhaupt verstehen zu können, müssen wir uns erst einmal einer ganz neuen Zahlenmenge zuwenden, der endlichen Menge. Diese Menge ist ungewöhnlich. Interessant wird sie dadurch, dass fast alle normalen Rechenregeln auch in dieser Menge Geltung finden. Wie der Name schon sagt, handelt es sich bei der endlichen Menge um eine Menge, in der es nicht unendlich viele Elemente gibt. Wir arbeiten mit einer Form der endlichen Menge, in der es, von 0 beginnend, nur Ganzzahlen bis zu einem bestimmten Maximalwert gibt. In einer solchen Menge findet die modulare Arithmetik Anwendung. Wir bezeichnen diese Menge als Z[n], wobei n die Anzahl der Zahlen in der Menge (das Modul) darstellt. Ist n = 14, so heißt die Menge Z[14] und gibt es 14 Zahlen in der Menge: 0 bis 13. Modulare Arithmetik ist nicht anders als die normale Arithmetik, mit dem Unterschied, dass wir nur auf Ganzzahlen operieren und alle Rechenoperationen modulo n durchführen.

In diesem Text werden oft modulare Kongruenzen der Form x = y (mod n) dargestellt. Diese Kongruenz drückt aus, dass x und y in der Menge Z[n] gegenseitig ersetzbar sind. Das heißt, dass x und y in Z[n] die gleichen Zahlen sind. Beispiel: 17 = 6 (mod 11). Erinnerung: die Kongruenz lässt sich auch zu einer Gleichung umschreiben: x = y (mod n) entspricht der Gleichung x mod n = y mod n.

Am besten lässt sich die endliche Menge am Beispiel einer Uhr verdeutlichen. Der Stundenzeiger einer Uhr arbeitet in der Menge Z[12]. Es gibt also die Stunden 0 bis 11. Wenn wir gerade 9 Uhr haben, dann ist es nach 5 Stunden 2 Uhr. Das ist das Prinzip des Umklappens. Nach der Stunde 11 klappt der Zeiger wieder um und landet auf der Stunde 0 (meist als 12 gekennzeichnet). Diese Rechnung können wir allerdings auch mathematisch durchführen:

9 + 5 = 14     // Normale Addition,
14 mod 12 = 2  // jedoch modulo 12

Die modulo-Operation a mod b ist nichts anderes als der Rest der Division a / b (siehe Primzahlen und Teilbarkeit). Was haben wir also hier getan? Wir haben normal addiert und das Ergebnis dann durch die modulo-Operation wieder in die Menge Z[12] gebracht. Das garantiert, dass weder ein Operand, noch ein Ergebnis jemals größer oder gleich 12 sind. Wir können dieses Spiel fortsetzen. Wenn es jetzt 7 Uhr ist, wieviel Uhr ist es dann nach 16 * 17 Stunden? Stellen wir also unsere Aufgabe auf:

x = 7 + 16 * 17 (mod 12)

Der eine oder andere Leser dürfte bereits angefangen haben, 16 * 17 auszurechnen, was jedoch völlig unnötig ist. Hier zeigt sich, dass die modulare Arithmetik viele Rechenaufgaben erheblich erleichtert. Wir greifen die oben genannten Regeln der modulo-Operation auf:

(a + b) mod n = ((a mod n) + (b mod n)) mod n
(a * b) mod n = ((a mod n) * (b mod n)) mod n

Das heißt, wir können unseren Term (7 + 16 * 17) mod 12 etwas abändern:

  (    7      +      16 * 17      ) mod 12
= ((7 mod 12) + ((16 * 17) mod 12)) mod 12

Nun haben wir einen Nebenterm (16 * 17) mod 12 geschaffen, den wir ebenfalls abändern können:

  (16 * 17) mod 12
= ((16 mod 12) * (17 mod 12)) mod 12
= (4 * 5) mod 12

Wir können also bei Additionen und Multiplikationen jede beliebige Zahl erst mal durch eine modulo-Operation in die Menge Z[12] bringen. Weder 16, noch 17 sind in der Menge Z[12], also bringen wir sie erst in die Menge:

16 * 17 = (16 mod 12) * (17 mod 12) (mod 12)  // Wir "reduzieren" 16 und 17
16 * 17 = 4 * 5 (mod 12)                      // Normale Multiplikation
16 * 17 = 20 (mod 12)                         // Auch 20 ist nicht in Z[12]
16 * 17 = 8 (mod 12)                          // 20 = 8 (mod 12)

Hier haben wir nun aus allen zu großen Zahlen den Divisionsrest durch 12 gebildet. 16 mod 12 ist 4, 17 mod 12 ist 5, also lautet unsere neue Gleichung:

x = 7 + 4 * 5 (mod 12)

Jetzt berechnen wir noch 4 * 5 und kommen auf 20. Auch die 20 ist außerhalb von Z[12], also wird sie wieder reduziert. 20 mod 12 ist 8. Nun unsere neue, stark simplifizierte Gleichung, die wir jetzt problemlos auflösen können:

x = 7 + 8 (mod 12)  // Normale Addition
x = 15 (mod 12)     // 15 ist außerhalb Z[12], also...
x = 3 (mod 12)      // ... reduzieren wir wieder: 15 mod 12 = 3

Und unsere Antwort: wenn es jetzt 7 Uhr ist, ist es nach 16 * 17 Stunden 3 Uhr.

So einfach? Unmöglich! Also überprüfen wir unser Ergebnis und rechnen das ganze noch einmal auf die harte Tour:

x = 7 + 16 * 17 (mod 12)
x = 7 + 272 (mod 12)
x = 279 (mod 12)
x = 3 (mod 12)            // 279 = 3 (mod 12)

Tatsächlich! Ach, wenn wir doch alles auf der Welt modulo 12 rechnen könnten! Die modulo-Operation lässt sich übrigens auch so beschreiben: wir stellen den Zeiger auf 0 Uhr und drehen ihn einmal rund herum. Damit sind 12 Stunden vergangen und wir sind wieder auf 0 Uhr (das ist analog zu der weiter oben aufgeführten Kongruenz k * n = 0 (mod n)). Also ziehen wir 12 von 279 ab. Das machen wir so oft, bis unsere Zahl unter 12 ist. Gleiches Prinzip: wir stellen ihn auf 7 Uhr und fahren 272 Stunden (16 * 17) weiter. So kann der Skeptiker das an einer echten Uhr überprüfen.

Im Kapitel über Primzahlen und Teilbarkeit wurde erklärt, dass sich a mod b durch die Formel a mod b = a - a / b * b (Ganzzahldivision!) berechnen lässt. Um die modulare Arithmetik besser verstehen zu können, soll hier allerdings noch ein weiterer Weg vorgestellt werden: a mod b lässt sich auch berechnen, indem man wiederholt b von a subtrahiert, bis a kleiner als b ist. Dies kann man optimieren, indem man erst Vielfache von b subtrahiert. Damit lässt sich 632457 mod 412 dadurch berechnen, dass man wiederholt 412000 von 632457 abzieht, bis das Ergebnis kleiner als 412000 ist. Von diesem zieht man dann 41200 ab, bis das Ergebnis kleiner als 41200 ist. Von diesem zieht man dann wiederholt 4120 ab und schließlich 412. So lässt sich die modulo-Operation sehr einfach von Hand durchführen.

Nun zu den trockenen Fakten. Für jedes Element x der Menge Z[n] gilt die Kongruenz x = x + k * n (mod n) für jede beliebige Zahl k (merke: wir arbeiten nur mit Ganzzahlen, somit muss auch k eine solche sein). Verallgemeinert lautet die Kongruenz: k * n = 0 (mod n).

Die Subtraktion a - b ist definiert, solange b kleiner als a ist, da sonst negative Zahlen resultieren, welche weder Elemente der Menge Z[n] sind, noch sich durch die modulo-Operation korrekt in diese überführen lassen. Die Division ist gar nicht definiert. Es gibt jedoch multiplikative Inverse. Mehr dazu weiter unten.

In der Menge Z[n] gelten alle normalen Gesetze für die Addition. Zu jedem Element x ungleich 0 der Menge Z[n] existiert ein additives inverses Element -x und es existiert genau ein neutrales Element der Addition: 0. Hier muss erwähnt werden, dass es sich bei der Darstellung -x nicht um eine negative Zahl handelt. Die Darstellung mit dem negativen Vorzeichen ist reine Formsache. Addition des additiven Inversen eines Elements macht eine Addition mit dem Element selbst rückgängig. Addition des inversen Elements -x zu x resultiert im neutralen Element. Addition des neutralen Elements der Addition hat keine Wirkung. Das neutrale Element ist invers zu sich selbst:

a + x = b (mod n)   // Addition des Elements x
b + -x = a (mod n)  // Addition des additiven Inversen zu x ("Subtraktion")

a + 0 = a (mod n)   // Addition des neutralen Elements der Menge Z[n]
x + -x = 0 (mod n)  // Addition von -x zu x ergibt neutrales Element

// Zusammenfassung (addition des neutralen Elements):
a + (x + -x) = a (mod n)

Das additive Inverse eines Elements x in der Menge Z[n] ist definiert als n - x.

x + -x = 0 (mod n)
-x = 0 - x (mod n)
// bzw.:
-x = n - x (mod n)

// denn:
x + (n - x) = n (mod n)
// und:
n = 0 (mod n)

Somit ist das additive Inverse zu 9 in der Menge Z[12] errechenbar: 12 - 9 = 3. Überprüfung:

7 + 9 = 4 (mod 12)
4 + 3 = 7 (mod 12)

  7 + (9 + 3) (mod 12)
= 7 + 12 (mod 12)
= 7 + 0 (mod 12)
= 7 (mod 12)

Für die Addition gelten das Kommutativgesetz (a + b = b + a (mod n)) und das Assoziativgesetz ((a + b) + c = a + (b + c) (mod n)). Somit ist Z[n] eine additive Gruppe.

In der Menge Z[n] gelten, sofern n prim ist, alle normalen Gesetze der Multiplikation. Zu jedem Element x > 0 in der Menge Z[n] (n prim) gibt es genau ein multiplikatives Inverses 1/x und es existiert genau ein neutrales Element der Multiplikation: 1. Hier ist zu erwähnen, dass die Bruchschreibweise reine Formsache ist. Hierbei handelt es sich nicht um einen echten Bruch, da dies zu Kommazahlen oder falschen Ergebnissen führen würde (die Division ist in Z[n] ohnehin nicht definiert). Multiplikation mit dem multiplikativen Inversen eines Elements macht eine Multiplikation mit dem Element selbst rückgängig. Multiplikation eines Elements x mit seinem multiplikativen Inversen 1/x resultiert im neutralen Element. Multiplikation mit dem neutralen Element hat keinen Einfluss. Das neutrale Element ist invers zu sich selbst. Multiplikation mit 0 resultiert in 0 und ist nicht umkehrbar, daher hat 0 kein multiplikatives Inverses:

a * x = b (mod n)    // Multiplikation mit x
b * 1/x = a (mod n)  // Multiplikation mit dem multiplikativen Inversen von x

a * 0 = 0 (mod n)    // Multiplikation mit 0 ist nicht umkehrbar
a * 1 = a (mod n)    // Multiplikation mit dem neutralen Element
x * 1/x = 1 (mod n)  // Multiplikation von x und 1/x ergibt neutrales Element

// Zusammenfassung (Multiplikation mit neutralem Element):
a * (x * 1/x) = a (mod n)

Das multiplikative Inverse eines Elements x in der Menge Z[n] (n prim!) ist definiert als x^(n - 2) (mod n) (der Beweis folgt im Abschnitt über die Eulersche phi-Funktion). Somit ist das multiplikative Inverse zu 4 in der Menge Z[13] errechenbar: 4^(13 - 2) = 4^11 = 10 (mod 13). Überprüfung:

8 * 4 = 6 (mod 13)
6 * 10 = 8 (mod 13)

  8 * (4 * 10) (mod 13)
= 8 * 40 (mod 13)
= 8 * 1 (mod 13)
= 8 (mod 13)

Für die Multiplikation gelten, auch, wenn n nicht prim ist, das Kommutativgesetz (a * b = b * a (mod n)), das Assoziativgesetz ((a * b) * c = a * (b * c) (mod n)) und das Distributivgesetz (a * (b + c) = a * b + a * c (mod n)). Z[n] ist jedoch nur dann eine multiplikative Gruppe, wenn n prim ist, da sonst nicht jedes Element x > 0 ein eindeutiges multiplikatives Inverses besitzt. Dies kann man sich durch die folgenden Multiplikationsmatrizzen verdeutlichen:

Menge: Z[7] (multiplikative Gruppe, da n prim)

    0  1  2  3  4  5  6
  *---------------------
0 | 0  0  0  0  0  0  0
1 | 0  1  2  3  4  5  6
2 | 0  2  4  6  1  3  5
3 | 0  3  6  2  5  1  4
4 | 0  4  1  5  2  6  3
5 | 0  5  3  1  6  4  2
6 | 0  6  5  4  3  2  1

Menge: Z[9] (keine multiplikative Gruppe, da n nicht prim)

    0  1  2  3  4  5  6  7  8
  *---------------------------
0 | 0  0  0  0  0  0  0  0  0
1 | 0  1  2  3  4  5  6  7  8
2 | 0  2  4  6  8  1  3  5  7
3 | 0  3  6 (0) 3  6 (0) 3  6
4 | 0  4  8  3  7  2  6  1  5
5 | 0  5  1  6  2  7  3  8  4
6 | 0  6  3 (0) 6  3 (0) 6  3
7 | 0  7  5  3  1  8  6  4  2
8 | 0  8  7  6  5  4  3  2  1

Hier zeigt sich deutlich, dass in Z[9] nur Multiplikationen mit Elementen, die relativ prim (teilerfremd) zum Modul (9) sind, auch eindeutig umkehrbar sind. Wer genau hinsieht, dem dürfte auch auffallen, dass die restlichen Elemente auch keine multiplikativen Inversen besitzen (man erinnere sich: x * 1/x = 1). Es gibt in Z[9] keine Zahl, die, mit 3 oder 6 multipliziert, das neutrale Element 1 ergibt. Damit ist Z[9] keine multiplikative Gruppe.

Hier soll jedoch erwähnt werden, dass jedes Element x in der Menge Z[n] ein eindeutiges multiplikatives Inverses besitzt, wenn x und n relativ prim sind. Auch dann, wenn n nicht prim ist. In diesem Fall kann dieses inverse Element jedoch nicht durch die obige Formel x^(n - 2) (mod n) berechnet werden. Wie man dieses Element ermittelt, wird im Abschnitt über den erweiterten Euklidschen Algorithmus erklärt.

Da in Z[n] die normalen Gesetze der Multiplikation gültig sind, sind auch die normalen Gesetze der Exponentiation gültig, auch, wenn n nicht prim ist. Diese lauten:

a^0 = 1 (mod n)  // Null-Exponent: 0
a^1 = a (mod n)  // Neutraler Exponent: 1

(a^b)^c = (a^c)^b (mod n)      // Kommutativgesetz
(a^b)^c = a^(b * c) (mod n)    // Assoziativgesetz
a^b * a^c = a^(b + c) (mod n)  // Distributivgesetz

Die Bezeichnungen Kommutativgesetz, Assoziativgesetz und Distributivgesetz sind in diesem Fall nicht ganz richtig, passen jedoch am ehesten zu den gegebenen Rechengesetzen.

Exponentiation ist ein sehr rechenintensiver Prozess. Allein der sehr simpel aussehende Term 4132^4152 liefert simplifiziert eine Zahl mit 15015 Dezimalstellen. Die Dinge ändern sich jedoch dramatisch, wenn wir in der endlichen Menge rechnen. Dazu sehen wir uns den Term 3^4 (mod 11) genauer an:

3^4 = 3 * 3 * 3 * 3 (mod 11)

Nun greifen wir eine Regel der modulo-Operation (siehe Primzahlen und Teilbarkeit) auf, die wir auf diesen Term anwenden können:

(a * b) mod n = ((a mod n) * (b mod n)) mod n

Das heißt, wir können nach jeder Multiplikation das Ergebnis wieder reduzieren und erhalten damit einen Term, der sehr einfach zu lösen ist:

  3^4 (mod 11)
= 3 * 3 * 3 * 3 (mod 11)
= (((3 mod 11) * 3 mod 11) * 3 mod 11) * 3 (mod 11)
= ((3 * 3 mod 11) * 3 mod 11) * 3 (mod 11)
= (9 * 3 mod 11) * 3 (mod 11)
= 5 * 3 (mod 11)
= 4 (mod 11)

Wir probieren dies anhand des Beispiels 63^165 (mod 285) aus. Die Vereinfachung dieses Prozesses basiert darauf, dass wir ihn in mehrere Teilprozesse unterteilen und an jeder Zwischenstation (dort, wo multipliziert wird) das Ergebnis wieder in die Menge Z[285] bringen. Zunächst teilen wir den Exponenten in eine Summe von Zweierpotenzen (2^x) auf und zerlegen die Exponentiation entsprechend den im letzten Abschnitt genannten Gesetzen:

  63^165 (mod 285)
= 63^(128 + 32 + 4 + 1) (mod 285)
= 63^128 * 63^32 * 63^4 * 63 (mod 285)
= 63^(2^7) * 63^(2^5) * 63^(2^2) * 63 (mod 285)

Auf den ersten Blick sieht unser neuer Term noch schlimmer aus als der alte, doch wir sehen, dass es sich nur noch um wiederholte Quadrierung handelt. Also ziehen wir Schritt für Schritt Quadrate. Zuerst nehmen wir das Quadrat von 63 und erhalten 3969. Dieses Quadrat ist nicht mehr in Z[285], also kürzen wir es:

3969 = 264 (mod 285)

Nun ersetzen wir jedes Vorkommen von 63^2 durch 264:

  63^(2^7) * 63^(2^5) * 63^(2^2) * 63 (mod 285)
= 264^(2^6) * 264^(2^4) * 264^2 * 63 (mod 285)

Dieses Spiel setzen wir fort, bis wir nur noch eine Reihe Multiplikationen haben:

  264^(2^6) * 264^(2^4) * 264^2 * 63 (mod 285)  // 264^2 = 156 (mod 285)
= 156^(2^5) * 156^(2^3) * 156 * 63 (mod 285)    // 156^2 = 111 (mod 285)
= 111^(2^4) * 111^(2^2) * 156 * 63 (mod 285)    // 111^2 = 66 (mod 285)
= 66^(2^3) * 66^2 * 156 * 63 (mod 285)          // 66^2 = 81 (mod 285)
= 81^(2^2) * 81 * 156 * 63 (mod 285)            // 81^2 = 6 (mod 285)
= 6^2 * 81 * 156 * 63 (mod 285)                 // 6^2 = 36 (mod 285)
= 36 * 81 * 156 * 63 (mod 285)

Was haben wir nun getan? Aus unserer gigantischen Exponentation sind nur noch drei simple Multiplikationen übrig geblieben, die wir noch durchführen müssen. Aber auch hier können wir weiter von der Eigenschaft der endlichen Menge Gebrauch machen, indem wir die Ergebnisse der Multiplikation auch reduzieren:

  36 * 81 * 156 * 63 (mod 285)
= 2916    * 9828     (mod 285)
= 66      * 138      (mod 285)
= 9108 (mod 285)
= 273 (mod 285)

Diese Exponentiation hätte man sogar von Hand durchführen können, da man immer allerhöchstens dreistellige Zahlen multipliziert. Auch das scheint zu schön, um wahr zu sein, also probieren wir es auch hier auf die harte Tour und berechnen 63^165:

778378192247619740380721780831222290114610481624105151532375518829875807596
116289582565299183256830709798510100387818773018002979076581023295840489802
219795340758238588944653298749004558556165447877535493042131134313364098586
596859205285801099216441875976059243003292302074746769640034486477031743

// Diese Zahl modulo 285 ergibt:
273

Natürlich kann das nur der nachprüfen, der einen geeigneten Rechner hat. Die Kommandozeilenprogramme bc und dc (enthalten in allen Unix- und in den meisten Linux-Distributionen) eignen sich hervorragend für Berechnungen mit unbegrenzt großen Zahlen. Als kleiner Hinweis: das Programm dc hat sogar einen Operator für die modulare Exponentiation, doch dies übersteigt den Rahmen dieser Dokumentation. Für Windows gibt es diverse Algebraprogramme wie Mathematica und Derive. Diese sind jedoch kostenpflichtig. Für rein numerische Berechnungen oder simplere Algebraprogramme führt eine kurze Suche bei SourceForge vielleicht zum Erfolg. Dort finden sich kostenfreie Programme für diese Zwecke.

Diese Art der Exponentiation lässt sich sehr einfach von einem Computer durchführen. Dazu betrachten wir das, was wir oben getan haben, von einer anderen Perspektive. Bleiben wir bei der Aufgabe 63^165 (mod 285). Wir können nun entweder 165 mal die 63 mit sich selbst multiplizieren, oder wir gehen etwas systematischer vor. Ausgänglich haben wir den Wert m = 63 und e = 165. Wir führen zwei zusätzliche Variablen r und s. In der Variablen r halten wir immer das aktuelle Ergebnis und in der Variablen s führen wir immer eine Exponentiation von 63 mit Zweierpotenzen, so wie wir das oben von Hand gemacht haben. s wird mit m initialisiert und r wird mit 1 initialisiert. Damit lässt sich 63^165 (mod 285) systematisch ausrechnen. Wir sehen, ob e ungerade ist. Wenn ja, multiplizieren wir r mit dem Wert von s und dekrementieren e um 1. Wenn nicht, dann multiplizieren wir s mit sich selbst und halbieren e. Sobald e = 0 ist, erhalten wir in r das gewünschte Ergebnis. Alle Multiplikationen werden modulo n durchgeführt. Das garantiert, dass keines der Multiplikationsergebnisse größer als (n - 1)^2 sein kann.

m = 63
n = 285

  s    r    e
---  ---  ---
 63    1  165  e ungerade, also: r = r * s; e = e - 1
 63   63  164  e gerade, also: s = s * s; e = e / 2
264   63   82  e gerade
156   63   41  e ungerade
156  138   40  e gerade
111  138   20  e gerade
 66  138   10  e gerade
 81  138    5  e ungerade
 81   63    4  e gerade
  6   63    2  e gerade
 36   63    1  e ungerade
 36  273    0  Schleife abgeschlossen, r enthält das Ergebnis

Die folgenden Pseudocodes implementieren die modulare Exponentiation einmal wie eben beschrieben und einmal rekursiv. Meist wird in Dokumentationen die rekursive Form aufgezeigt. Diese ist jedoch langsamer, unsicherer und schwerer zu verstehen. Je mehr Stellen der Exponent hat, desto öfter muss die Funktion sich selbst aufrufen. Genau genommen muss sie sich für jede binäre Stelle im Exponent genau einmal selbst aufrufen. Für jede binäre 1, die dabei angetroffen wird, ruft sie sich zusätzlich noch einmal selbst auf, außer die letzte (höchstwertige) 1. Dies kann bei besonders großen Zahlen oder besonders kleinem Stapelspeicher zu einem Stapelüberlauf und in den meisten Fällen zum Programmabsturz führen. Wer diesen Text liest, dürfte am Thema Sicherheit interessiert sein. Ein Programm, dessen Stapel überläuft, ist nicht sicher! Der Vollständigkeit halber wird die rekursive Version hier dennoch vorgeführt. Die beiden Funktionen rechnen exakt nach dem selben Algorithmus. Die eine arbeitet, wie oben beschrieben, iterativ, und die andere arbeitet rekursiv:

// Iterative Version:
MODEXP(m, e, n) {
  LOCAL s, r

  s = m
  r = 1
  WHILE(e != 0) {
    IF (e MOD 2 == 1) THEN
      r = r * s MOD n
      e = e - 1
    ELSE
      s = s * s MOD n
      e = e / 2
    ENDIF
  }
  RETURN r
}

// Rekursive Version:
MODEXP_RC(m, e, n) {
  IF (e == 1) THEN RETURN m

  IF (e MOD 2 == 1) THEN
    RETURN (m * MODEXP_RC(m, e - 1, n)) MOD n
  ELSE
    RETURN MODEXP_RC((m * m) MOD n, e / 2, n)
  ENDIF
}

Die iterative Version lässt sich übrigens noch weiter optimieren. Wenn e gerade ist, wird es halbiert. Das so oft, bis e ungerade wird. Das können wir in eine eigene innere Schleife einschließen. Solange e gerade ist, führen wir s = s * s (mod n) und e = e / 2 (mod n) durch. Nachdem wir die Schleife verlassen, ist garantiert, dass e ungerade ist. Hier also die optimierte Version:

// Optimierte iterative Version:
MODEXP(m, e, n) {
  LOCAL s, r

  s = m
  r = 1
  WHILE(e != 0) {
    WHILE(e MOD 2 == 0) {
      s = s * s MOD n
      e = e / 2
    }
    r = r * s MOD n
    e = e - 1
  }
  RETURN r
}

In den meisten Programmiersprachen wie C lässt sich die Funktion noch einmal zusätzlich optimieren. Wir können statt s auch einfach m weiterverwenden, da die Variable in den meisten Programmiersprachen ohnehin lokal zur Funktion ist. Das spart eine Zuweisung und je nach Größe der Zahlen eine immense Menge Stapelspeicher. Ob e gerade ist, können wir testen, indem wir das niederwertigste Bit abfragen. Ist dieses 0, so ist e gerade. Die Division durch zwei können wir durch eine Rechtsschiebeoperation optimieren und die Subtraktion können wir, da die Zahl auf jeden Fall ungerade ist, durch eine binäre XOR-Operation durchführen. Also hier noch einmal die stark optimierte Version in einem C-ähnlichen Pseudocode:

// Weiter optimierte iterative Version:
huge_t modexp(huge_t m, huge_t e, huge_t n) {
  huge_t res = 1;

  while(e) {
    while(!(e & 1)) {
      m = m * m % n;
      e >>= 1;
    }
    res = res * m % n;
    e ^= 1;
  }
  return res;
}

Dieser Algorithmus berechnet den größten gemeinsamen Teiler zweier nicht negativer Ganzzahlen. Die Funktion gcd(a, b) (engl. greatest common divisor) hat folgende Eigenschaften:

// a und g sind Elemente von N
// b ist Element von N[0]
gcd(a, b) = g

// u und v sind Elemente von Z. Es gibt unendlich viele Paare (u, v), die die
// folgende Gleichung Erfüllen:
g = u * a + v * b

Der Algorithmus führt gcd(a, b) wiederholt auf gcd(b, a mod b) zurück. Diese Schleife endet, sobald a mod b = 0 ist. Dann ist b der größte gemeinsame Teiler von den ursprünglichen a und b. Ist dieser 1, so sind a und b relativ prim (teilerfremd), haben also keine Primfaktoren gemeinsam.

Somit ist der Euklidsche Algorithmus definiert als:

// Wenn b ungleich 0
gcd(a, b) = gcd(b, a mod b)

// Wenn b gleich 0
gcd(a, b) = a

Als kleines Beispiel ermitteln wir den größten gemeinsamen Teiler von 11 * 13 * 17 * 23 = 55913 und 11^2 * 13^2 = 20449. Der größte gemeinsame Teiler ist übrigens die Kombination der gemeinsamen Primfaktoren. In dem Fall müsste das Ergebnis 11 * 13 = 143 lauten:

    a      b  a mod b
-----  -----  -------
55913  20449    15015  Hier berechnen wir a mob b und...
20449  15015     5434  ... setzen das Ergebnis nach b; das alte b wird zu a.
15015   5434     4147  Das wiederholen wir...
 5434   4147     1287  ... nochmal,
 4147   1287      286  ... nochmal,
 1287    286      143  ... nochmal,
  286    143        0  ... nochmal,
  143      0        -  bis b = 0 ist. Dann ist a der ggT.

Der folgende Pseudo-Code sollte dies veranschaulichen. Hier werden wieder eine iterative und eine rekursive Version aufgezeigt. Die rekursive Funktion wird wieder nur der Vollständigkeit halber aufgeführt. Sie sollte nicht verwendet werden, da sie langsamer und unsicherer ist. Anmerkung: wie oft sich die rekursive Funktion selbst aufruft, hängt allein von den beiden Funktionsparametern ab. Es kann vorkommen, dass sich die Funktion sehr oft selbst aufruft. Im obigen Falle würde sie sich genau 7 mal selbst aufrufen. Das ist purer Zufall. Es kann passieren, dass sich die Funktion bei größeren Zahlen mehrere Millionen mal selbst aufrufen muss. Das passiert nur bei wenigen Zahlenpaaren, kommt aber vor.

// Iterative Version
GCD(a, b) {
  LOCAL x, y, temp
  
  x = a
  y = b
  WHILE(y != 0) {
    temp = x
    x = y
    y = temp MOD y
  }
  RETURN x
}

// Rekursive Version
GCD_RC(a, b) {
  IF (b == 0) THEN
    RETURN a;
  ELSE
    RETURN GCD_RC(b, a MOD b)
  ENDIF
}

In den meisten Programmiersprachen wie C/C++ sind die beiden lokalen Variablen x und y überflüssig. Man kann auch direkt auf a und b operieren. Dies ist jedoch nicht in jeder Programmiersprache der Fall und deswegen legen wir zwei lokale Variable an.

x = a * b
y = a * c
x + y = (a * b) + (a * c) = a * (b + c)

// Beispiel:
18 = 2 * 3^2
60 = 2^2 * 3 * 5
78 = 2 * 3 * 13

a = x + b

Wie oben schon erwähnt, lässt sich anhand des Euklidschen Algorithmus sehr einfach feststellen, ob zwei Zahlen relativ prim (teilerfremd) sind. Ist dies der Fall, so ist der größte gemeinsame Teiler immer 1. Die beiden Eingabewerte haben somit keine Primfaktoren gemeinsam. Dies kann zum Faktorisieren größerer Zahlen eingesetzt werden, indem man einfach wiederholt den größten gemeinsamen Teiler der zu faktorisierenden Zahl und einer Zufallszahl sucht. Das ist jedoch sehr ineffizient.

Die Menge Z[n] hat übrigens eine sehr interessante Eigenschaft. Diese soll wieder am Beispiel einer Uhr verdeutlicht werden. Wir setzen den Stundenzeiger auf 0 Uhr. Jetzt fahren wir wiederholt 3 Stunden fort. Wir kommen also auf 3 Uhr, dann auf 6 Uhr, dann 9 Uhr und schließlich wieder 0 Uhr. Damit beginnt die Sequenz von vorne. Probieren wir das gleiche mit der Zahl 7. Wir setzen den Zeiger auf 0 Uhr und fahren 7 Stunden fort. Dann haben wir erst 7 Uhr, dann 2 Uhr, dann 9 Uhr, dann 4 Uhr usw. Sobald wir wieder bei 0 Uhr angekommen sind, stellen wir fest, dass wir jede Stunde genau einmal angefahren haben, bevor sich die Sequenz wiederholt. Warum ist das mit 7 passiert, mit 3 aber nicht? Wir merken, dass 7 relativ prim (teilerfremd) zu 12 ist, dass 7 also keine Primfaktoren mit 12 gemeinsam hat. Der größte gemeinsame Teiler von 7 und 12 ist also 1. Da 3 nicht relativ prim zu 12 ist, teilt 3 die 12 in genau 4 Teile auf: 0, 3, 6 und 9. Da 12 schon wieder 0 ist, treffen Vielfache von 3 wieder die 0, nachdem sie alle Teile durchlaufen sind. Damit gilt folgender Satz: die Periode von f(x) = x * f (mod n) ist genau n / gcd(n, f). Für relativ prime Zahlen ist sie also n. Damit kommen wir mit f(x) = x * 3 (mod 12) nur auf die Ergebnisse 0, 3, 6 und 9. Die anderen Elemente von Z[12] treffen wir mit dieser Funktion nicht. Mit f(x) = x * 7 (mod 12) treffen wir jedoch jedes Element und können jede beliebige Zahl in Z[12] als Ergebnis erhalten. Das beweist auch, dass x kein multiplikatives inverses Element in Z[n] besitzt, wenn es nicht relativ prim zu n ist. Es gibt dann nämlich kein Element, das mit x multipliziert 1 ergibt. Mit Vielfachen von x können wir die 1 nicht treffen.

Mit Hilfe des Euklidschen Algorithmus lässt sich auch das kleinste gemeinsame Vielfache zweier Zahlen a und b ermitteln. Im Kapitel über Primzahlen und Teilbarkeit haben wir gelernt, dass das kgV die Kombination aller Primfaktoren beider Zahlen ist, wobei von den gemeinsamen Faktoren nur die höchste Potenz verwendet wird. Der größte gemeinsame Teiler ist die Kombination aller gemeinsamen Primfaktoren, wobei immer nur die kleinste Potenz verwendet wird. Somit ist das kgV die Kombination aller Primfaktoren, abzüglich der gemeinsamen Primfaktoren. Wir können das kgV (im Folgenden lcm (least common multiplicate) genannt) dadurch berechnen, dass wir alle Primfaktoren kombinieren, also a mit b multiplizieren und anschließend durch den größten gemeinsamen Teiler teilen:

lcm(a, b) = (a * b) / gcd(a, b)

Hier wird eine weitere interessante Eigenschaft ersichtlich. Sind die beiden Eingabewerte relativ prim, der größte gemeinsame Teiler also 1, so ist das kleinste gemeinsame Vielfache das Produkt beider Zahlen.

Die Eulersche phi-Funktion, die schlichtweg als griechischer Buchstabe phi geschrieben wird, liefert für jede Zahl x in der Menge N die Anzahl der Elemente in Z[x], die relativ prim zu x sind. Für Primzahlen ist sie definiert als phi(x) = x - 1. Da jede Zahl kleiner als x, außer 0, relativ prim zu x ist, wenn x selbst eine Primzahl ist, ist diese Funktion sehr einfach zu überprüfen: phi(7) = 7 - 1 = 6. Die Zahlen 1 bis 6 sind alle relativ prim zu 7. Die 0 hingegen ist nicht relativ prim zu 7, denn 0 lässt sich durch jede Zahl, also auch 7, restlos teilen. Dies kann man ebenfalls leicht überprüfen: gcd(7, 0) = 7. Nur Zahlen, die 7 als Primfaktor haben, sind nicht relativ prim zu 7, also alle Vielfache von 7. Es kann kein Vielfaches von 7 kleiner als 7 geben. Somit sind alle Zahlen kleiner als 7 relativ prim zu 7, außer 0.

Auch für Produkte zweier unterschiedlicher Primzahlen p und q ist diese Funktion simpel definiert: phi(x) = (p - 1) * (q - 1). Um dies zu überprüfen, wählen wir p = 5 und q = 7. Das Produkt ist 35. Wir rechnen:

35 = 5 * 7

  phi(35)
= (5 - 1) * (7 - 1)
= 4 * 6
= 24

24 Zahlen aus Z[35] sind relativ prim zu 35. Das überprüfen wir, indem wir eine Liste aufstellen, die relativ primen Zahlen hervorgehoben:

Z[35] = {
   0,  1,  2,  3,  4,  // 4 Elemente in dieser Zeile
   5,  6,  7,  8,  9,  // 3 Elemente in dieser Zeile
  10, 11, 12, 13, 14,  // 3 Elemente in dieser Zeile
  15, 16, 17, 18, 19,  // 4 Elemente in dieser Zeile
  20, 21, 22, 23, 24,  // 3 Elemente in dieser Zeile
  25, 26, 27, 28, 29,  // 3 Elemente in dieser Zeile
  30, 31, 32, 33, 34   // 4 Elemente in dieser Zeile
}                      // = insgesamt 24 Elemente

Damit ist diese Funktion das Produkt aller Primfaktoren des Eingabewertes minus 1. Dies funktioniert jedoch nur dann, wenn sich alle Primfaktoren voneinander unterscheiden. Für den Eingabewert 5 * 11 * 17 = 935 gilt daher:

  phi(935)
= (5 - 1) * (11 - 1) * (17 - 1)
= 4 * 10 * 16
= 640

Die allgemeine Defintion der Funktion für eine Zahl x mit den Potenzen ihrer Primfaktoren p[1]^e[1] bis p[n]^e[n] lautet:

phi(x) = (p[1] - 1) * p[1]^(e[1] - 1) * ... * (p[n] - 1) * p[n]^(e[n] - 1)

Beispiel:

x = 2^5 * 3 * 7^3 = 32928

  phi(x)
= ((2 - 1) * 2^(5 - 1)) * (3 - 1) * ((7 - 1) * 7^(3 - 1))
= (1 * 2^4) * (2) * (6 * 7^2)
= 16 * 2 * 294
= 9408

  n - phi(n)
= n - (p - 1) * (q - 1)            // Ausmultiplizieren
= n - (p * (q - 1) - 1 * (q - 1))  // Klammern auflösen
= n - (p * q - p - q + 1)          // Klammern auflösen
= n - p * q + p + q - 1            // Weil n = p * q:
= p + q - 1

Es zeigt sich deutlich, dass wir die Primfaktoren von x brauchen, um phi(x) zu berechnen. Genau diese Tatsache macht sich RSA zunutze. Mehr dazu später.

x^e mod n = (x mod n)^(e mod phi(n)) mod n

xr = x mod n
xq = x - xr

  x^e mod n
= (xq + xr)^e mod n

  (xq + xr) * (xq + xr)
= (xq * xq) + (xq * xr) + (xr * xq) + (xr * xr)

  (xq * xq) + (xq * xr) + (xr * xq) + (xr * xr)
= xr * xr

Mathematische Funktionen haben genau eine Aufgabe. Sie geben einen Wert zurück. Für jede umkehrbare Funktion lässt sich eine Umkehrfunktion schreiben. Folgendes Beispiel soll dies verdeutlichen:

// x ist Element von R
f(x) = 13 * x + 7

Um diese Funktion umzukehren, müssen wir nur in der richtigen Reihenfolge alle Operationen rückgängig machen. Also subtrahieren wir erst 7 und teilen dann durch 13. Die resultierende Umkehrfunktion sieht also so aus:

// x ist Element von R
g(x) = (x - 7) / 13

Für jedes x (aus R) gilt dann x = g(f(x)). Die beiden aufgeführten Funktionen sind gegenseitig invers. Somit gilt auch x = f(g(x)). Dies ist jedoch keine Voraussetzung.

Man stelle sich nun vor, man hat eine Funktion vor sich, die auf jeden Fall eindeutig umkehrbar ist. Es ist auch bestätigt, dass es die Umkehrfunktion dazu schon gibt. Aus diesem Wissen soll man nun die Umkehrfunktion schreiben. Das klingt alles problemlos. Aber sobald auch noch die kleine Einschränkung hinzukommt, dass man die Umkehrung dieser Funktion in weniger als 15 Milliarden Jahren fertiggestellt haben muss, ändert sich die Lage dramatisch.

Hierbei handelt es sich um das Falltürprinzip. Es gibt bestimmte Funktionen, die schnell definiert werden können, deren Umkehrung aber so aufwändig ist, dass sich diese nicht lohnt durchzuführen. Hier wird klar, dass solche Funktionen vor allem im kryptographischen Bereich ihre Anwendung finden. Dabei hängt die Umkehrung von einem Geheimnis ab, welches nur der Autor der Funktion kennt. Ohne dieses Geheimnis kann die Funktion nicht umgekehrt werden.

Euler ist damals auf eine sehr interessante Eigenschaft der endlichen Menge gestoßen. Solange x und n teilerfremd sind (gcd(x, n) = 1), gilt:

x^phi(n) = 1 (mod n)

// Wenn n prim ist, gilt:
phi(n) = n - 1

// damit gilt:
x^(n - 1) = 1 (mod n)

// Wir legen fest:
1/x = x^(n - 2) (mod n)

// und wissen:
x * 1/x = 1 (mod n)

// Das kombinieren wir:
x * x^(n - 2) = 1 (mod n)

// denn:
x * x^(n - 2) = x^(n - 1) (mod n)

// und:
x^(n - 1) = 1 (mod n)

// weil:
x^phi(n) = 1 (mod n)

Um diesen Satz zu erklären, entnehmen wir einerseits eine wichtige Regel der Exponentiation: x^0 = 1. Danach sehen wir uns folgende Regel der modulo-Operation an:

a^b mod n = (a mod n)^(b mod phi(n)) mod n

Ist b also kongruent zu 0 in Z[phi(n)], ist das Ergebnis 1. Aber nur, wenn a und n teilerfremd sind. Um verständlich machen zu können, was genau daran so interessant sein soll, müssen wir diesen Satz ein wenig ausbauen:

x^phi(n) * x^phi(n) = 1 * 1 (mod n)

Es stellt sich heraus, dass wir dies beliebig oft wiederholen können, das Ergebnis jedoch immer 1 bleibt. Also verallgemeinern wir diesen Satz:

x^(t * phi(n)) = 1 (mod n)

Dieser Satz kommt der obigen modulo-Regel etwas näher. Natürlich verlassen wir uns nicht blind darauf und überprüfen das:

n = 41 * 67 = 2747
phi(n) = 40 * 66 = 2640

20^2640 = 1 (mod 2747)
21^2640 = 1 (mod 2747)
22^2640 = 1 (mod 2747)
23^2640 = 1 (mod 2747)

// 574 ist nicht relativ prim zu 2747:
574^2640 = 738 (mod 2747)

Tatsächlich. Aber dieser Satz hat in der Form noch überhaupt keinen Nutzen für uns. Also sehen wir doch mal, was wir aus dem Satz machen können:

// Hier wieder unsere Ausgangskongruenz
x^(t * phi(n)) = 1 (mod n)

// Multiplizieren wir diese Kongruenz doch mal mit x:
x^(t * phi(n)) * x = 1 * x (mod n)
x^(t * phi(n) + 1) = x (mod n)

Was haben wir nun? Wir nehmen irgendeinen Wert x, führen eine modulare Exponentiation mit einer bestimmten Zahl durch und als Ergebnis erhalten wir x. Überraschenderweise entfällt plötzlich die Voraussetzung, dass gcd(x, n) = 1 gelten muss, denn der Exponent ist nicht mehr Vielfaches von phi(n). Er ist also nicht mehr kongruent zu 0 in Z[phi(n)]. Falls das noch nicht interessant klingt, sehen wir uns doch mal den Exponenten genauer an:

// Unser Exponent
k = t * phi(n) + 1

// Oder als Kongruenz ausgedrückt (Erinnerung: y * n = 0 (mod n), y beliebig):
k = 1 + t * phi(n) (mod phi(n))
k = 1 + 0 (mod phi(n))
k = 1 (mod phi(n))

// Damit der etwas simplifizierte Satz:
k = 1 (mod phi(n))
x^k = x (mod n)

Was genau tun wir hier? Die Lage hat sich nicht geändert. Wir haben eine Zahl x und führen eine modulare Exponentiation durch. Aber halt! Der Exponent kann jede beliebige Zahl kongruenz zu 1 in Z[phi(n)] sein. Unser Ergebnis bleibt weiterhin x. Das interessante hierbei ist, dass der Exponent kongruent zu 1 in der Menge Z[phi(n)] und nicht Z[n] sein muss. Sehen wir doch mal, ob wir daraus etwas machen können.

Wir erinnern uns, dass 1 das neutrale Element der Multiplikation in Z[n] (n beliebig) ist. Somit auch in Z[phi(n)]. Und weiter erinnern wir uns, dass es zu jeder Zahl e in Z[n], die relativ prim zu n ist, ein eindeutiges multiplikatives Inverses d gibt, für das gilt: e * d = 1 (mod n). Also nehmen wir ein beliebiges e, das relativ prim zu phi(n) ist und berechnen das multiplikative Inverse zu e in Z[phi(n)]. Damit können wir unseren Exponenten ein klein wenig abändern:

e * d = 1 (mod phi(n))
k = 1 (mod phi(n))
// Das heißt:
k = e * d (mod phi(n))

// Das wiederum heißt:
x^k = x (mod n)

// oder:
x^(e * d) = x (mod n)

In diesen Kongruenzen liegt der Schlüssel zum RSA-Verfahren, denn die Kongruenz x^(e * d) = x (mod n) können wir noch einmal zerlegen:

e * d = 1 (mod phi(n))
x^(e * d) = x (mod n)

// Nach den Regeln der Potenzrechnung:
(x^e)^d = x (mod n)

// oder:
x^e = y (mod n)
y^d = x (mod n)

Nach all den Umformungen und Einbeziehungen aller möglichen Sätze haben wir folgenden Satz:

e * d = 1 (mod phi(n))
x^e = y (mod n)
y^d = x (mod n)

Was wir im letzten Kapitel gelernt haben, können wir nun anwenden. Aber zunächst sehen wir uns das nochmal genauer an. Wir haben zwei Werte e und d, die in der Menge Z[phi(n)] multiplikativ invers zueinander sind. Führen wir in Z[n] (!) eine modulare Exponentiation mit Basis x und Exponent e durch, so erhalten wir eine andere Zahl y. Aus der Kenntnis von y lassen sich weder x, noch d, noch phi(n) rekonstruieren, denn y könnte jede beliebige Zahl in Z[n] sein. Nehmen wir nun diese Zahl y und führen in Z[n] eine modulare Exponentiation mit dem Exponenten d durch, so erhalten wir wieder x.

Wie funktioniert RSA nun? Wir wählen eine Zahl n, aus der wir sehr einfach phi(n) berechnen können. Optimal ist das Produkt zweier unterschiedlicher Primzahlen. Wir wählen also zwei unterschiedliche Primzahlen p und q und bilden das Produkt n = p * q. Dann berechnen wir phi(n) = (p - 1) * (q - 1). Die Primzahlen brauchen wir ab jetzt nicht mehr und vergessen sie. Jetzt wählen wir eine Zahl e, die relativ prim zu phi(n) ist, für die also gilt gcd(e, phi(n)) = 1. Das garantiert, dass die Zahl ein eindeutiges multiplikatives Inverses in Z[phi(n)] besitzt. Als letzten Schritt suchen wir ein d, das die Kongruenz e * d = 1 (mod phi(n)) erfüllt. Wir suchen also genau das multiplikative Inverse zu e in der Menge Z[phi(n)]. Ab hier brauchen wir auch phi(n) nicht mehr. Wir legen fest, dass e der öffentliche Exponent und d der private Exponent ist. Wenn m unser Klartext ist, so können wir m folgendermaßen verschlüsseln:

c = m^e (mod n)

c ist dann der Chiffretext. Nur mit der Kenntnis von d können wir den Chiffretext c folgendermaßen wieder in den Klartext überführen:

m = c^d (mod n)

Als kleines Beispiel erstellen wir erst einmal einen RSA-Schlüssel. Wir suchen uns zwei zufällige Primzahlen p und q aus und berechnen n sowie phi(n):

p = 11
q = 17
n = p * q = 187
phi(n) = (p - 1) * (q - 1) = 160

Nun suchen wir uns ein e, das relativ prim zu phi(n) = 160 ist. e = 7 erfüllt diesen Zweck. Zuletzt suchen wir ein d, das die Kongruenz e * d = 1 (mod phi(n)) erfüllt. Wir probieren d = 23 und testen:

e * d = 1 (mod phi(n))
7 * 23 = 161 = 1 (mod 160)

Damit ist unser Schlüssel fertiggestellt. Nun haben wir einen Klartext 52 73 121 173 65. Diesen möchten wir verschlüsseln. Also verschlüsseln wir jede einzelne Komponente:

 52^7 =    1028071702528 =  35 (mod 187)
 73^7 =   11047398519097 =  61 (mod 187)
121^7 =  379749833583241 =  77 (mod 187)
173^7 = 4637914326451397 =  79 (mod 187)
 65^7 =    4902227890625 = 142 (mod 187)

Aus dem Klartext 52 73 121 173 65 haben wir nun den Chiffretext 35 61 77 79 142 gemacht. Diesen können wir nun mit dem Exponenten d wieder in die ursprüngliche Form bringen:

 35^23 =               326260892630588011062145233154296875 =  52 (mod 187)
 61^23 =         115501122579584388592138579457905758648181 =  73 (mod 187)
 77^23 =       24506804088319785713436649354236658982956133 = 121 (mod 187)
 79^23 =       44200084506410989454600861862443675119534639 = 173 (mod 187)
142^23 = 31814999504641997296916177121902819369397243609088 =  65 (mod 187)

Es muss dringend erwähnt werden, dass die komponentenweise Verschlüsselung nur zur Demonstration so durchgeführt wurde. Man sollte unbedingt die Komponenten eines Klartextes kombinieren und daraus die größtmögliche Einheit bilden. Wie und warum wird weiter unten im Kapitel über die Tücken von RSA beschrieben.

Dazu schauen wir uns noch einmal den Schlüssel an. Nachdem wir zwei Primzahlen ausgewählt und n und phi(n) berechnet haben, vergessen wir die Primzahlen. Dann berechnen wir e und d und vergessen danach auch phi(n). Zum Schluss bleiben nur noch die Zahlen n als Modul, e als öffentlicher Exponent und d als privater Exponent übrig. Den öffentlichen Schlüssel bilden damit die Zahlen e und n. Jeder kann mit diesen beiden Werten eine Nachricht verschlüsseln. Ohne das entsprechende d kann sie jedoch nicht entschlüsselt werden.

Schlüpfen wir nun in die Rolle des Angreifers. Der Angreifer wird versuchen, d zu ermitteln. Er weiß:

e * d = 1 (mod phi(n))

Um d also berechnen zu können, muss er aus n einfach nur phi(n) berechnen. Er weiß, dass n aus genau zwei Primzahlen p und q besteht, mit denen er phi(n) berechnen kann:

phi(n) = (p - 1) * (q - 1)

Was muss er also tun? Er muss die Primzahlen p und q ermitteln. Das heißt, er muss n faktorisieren. Setzen wir das Beispiel im letzten Kapitel als Angreifer fort. Wir haben n = 187 und e = 7. 187 faktorisieren wir und erhalten damit die beiden Primfaktoren 11 und 17. Daraus können wir phi(n) berechnen. Sobald wir phi(n) haben, haben wir auch d, indem wir die obige Kongruenz nach d auflösen.

Was macht RSA also nun sicher? Es war sehr einfach, 187 zu faktorisieren. Was aber nun, wenn wir größere Primfaktoren wählen? Beispielsweise:

n = 71030048357343616816591843627
e = 538475231

Also faktorisieren wir ganz einfach n. Ganz einfach? Hier stellt sich bald heraus, dass wir genau vor dem Problem stehen, das RSA sicher macht. Wir können n nur nach einem Rateverfahren faktorisieren. Es bleibt uns nichts anderes übrig, als n durch alle möglichen Primzahlen zu dividieren und zu sehen, ob eine der Probezahlen restlos in n geht. Das erklärt auch, warum wir nicht einfach eine große Primzahl als n genommen haben. Dann hätte der Angreifer phi(n) direkt, denn er müsste nur noch n - 1 berechnen. Durch ein kleines Computerprogramm kann n jedoch immer noch in relativ kurzer Zeit faktorisiert werden. Wir erhalten:

p = 267958487152523
q = 265078554190049
phi(n) = (p - 1) * (q - 1) = 71030048357343083779550501056

Aus dieser Erkenntnis heraus können wir d berechnen. Mit dem erweiterten Euklidschen Algorithmus ermitteln wir:

e = 538475231
d = 61249433402649775486339595551
e * d = 32981302800110953867104851058771297281 = 1 (mod phi(n))

Was ist aber nun, wenn die Primfaktoren mehrere Hundert Dezimalstellen lang sind? Nach mehreren Tausend Jahren Forschung in der Zahlentheorie hat noch niemand ein Verfahren gefunden, mit dem sich jede beliebige Zahl auf direktem Wege faktorisieren lässt. Auch Primzahlen selbst scheinen relativ systemlos verteilt zu sein. Bisher konnte aber auch niemand beweisen, dass so ein Verfahren nicht existiert. Falls jemals jemand ein derartiges Verfahren finden sollte, ist RSA nicht mehr sicher und kann nicht mehr für kryptographische Zwecke eingesetzt werden. Aber eben angesichts der jahrtausendelangen Forschung im Bereich der Zahlentheorie, erscheint ein solches Verfahren sehr unwahrscheinlich.

Hier muss bedacht werden, dass es inzwischen schon sehr ausgeprägte Suchverfahren gibt. Im Moment (Oktober 2004) ist das bisher schnellste Verfahren zur Faktorisierung von großen Zahlen der Zahlkörpersieb (engl. number field sieve). Doch auch dieses Verfahren ist nur ein Annäherungsverfahren. Man kann sich vor einer erfolgreichen Modulfaktorisierung schützen, indem man die Primzahlen groß genug wählt. Dabei muss man mehrere Hundert Stellen in Betracht ziehen. Im Moment liegt die Empfehlung bei 1024 Bits (Zahlen von 0 bis 2^1024 - 1) für das Modul, also durchschnittlich 512 Bits für die beiden Primfaktoren. Man kann sich selbstverständlich größere Schlüssel generieren, doch irgendwann wird die Schlüsselgenerierung selbst unpraktisch, da die Suche nach den beiden Primzahlen mit steigender Anzahl an Bits zunehmend länger dauert. Das liegt daran, dass Primzahlen mit steigendem Wert immer seltener werden und die modulare Arithmetik immer langsamer. Außerdem muss darauf geachtet werden, dass viele Keyserver und CAs (certificate authorities) keine unbegrenzte Schlüssellänge zulassen. Schlüssel mit mehr als 4096 Bits werden nicht empfohlen, falls diese auf einem Keyserver oder ähnlichem abgelegt werden sollen, es sei denn, dem Anwender ist ein Keyserver oder CA bekannt, der die entsprechende Länge zulässt.

Es gibt noch einen zweiten Weg, die Verschlüsselung umzukehren. Wenn wir annehmen, die Chiffre würde nicht in der endlichen Menge durchgeführt werden, so hätten wir folgendes Schema:

c = m^e

Hier hätte der Angreifer ein leichtes Spiel. Er müsste nur die e'te Wurzel aus c ziehen. Dies ist durchführbar. Aber stattdessen haben wir folgendes Schema:

c = m^e (mod n)

Das ändert die Lage dramatisch, denn das Ergebnis könnte jede beliebige Zahl in Z[n] sein. Er kann also nicht einfach die Wurzel ziehen. Doch auch das Wurzelziehen ist in Z[n] möglich. Dieses ist aber mindestens eben so schwer wie Faktorisierung von n. Er kann systematisch m^e (mod n) mit allen möglichen Basen m ausprobieren und sehen, ob das Ergebnis c ist. Hierbei handelt es sich um das Problem der modularen Wurzel.

Es zeigt sich, dass RSA eine Falltürfunktion ist. Der Angreifer kann problemlos c = m^e (mod n) berechnen. Die Umkehrung dieses Terms ist jedoch eine immens schwierige Aufgabe. Weiter oben wurde erwähnt, dass die Umkehrung einer solchen Falltürfunktion von einem Geheimnis abhängt, das nur dem Autor der Funktion bekannt ist. Dieses Geheimnis ist hier der Wert von phi(n). Entweder, der Angreifer faktorisiert n, oder er sucht nach einem d, das c wieder in das ursprüngliche m überführt (dazu benötigt er phi(n)), oder er versucht, die e'te Wurzel aus c zu ziehen (hier kann er nur raten). Die beiden letzten Verfahren wären kein Problem, wenn wir nicht in der endlichen Menge rechnen würden. Die Faktorisierung ist ohnehin ein Problem.

RSA ist ein Verfahren, das widersprüchlicher nicht sein kann. Nicht nur, dass die Sicherheit von RSA unbestätigt ist und wahrscheinlich auch sehr lange so bleiben wird. RSA war lange Zeit ein Verfahren, dass sich auf Schätzungen verlassen musste. Weiters verbergen sich eine Reihe Tücken in diesem Verfahren, die hier besprochen werden sollen. Diese Liste erhebt keinen Anspruch auf Vollständigkeit. Im Grunde ist sie mehr als unvollständig. Der Leser wird hier auf externe Literatur verwiesen, aber die wichtigsten Fehler, die von Programmierern gemacht werden, sollen hier besprochen werden.

1. Kleine Exponenten

Eine früher oft übersehene Sicherheitslücke war die Wahl kleiner öffentlicher Exponenten. Nehmen wir als Beispiel folgenden öffentlichen Schlüssel an:

n = 37762589
e = 7

Wir schlüpfen wieder in die Rolle des Angreifers und sehen, dass jemand folgende Nachricht an den Besitzer des Schlüssels schickt:

c = 35831808

Rein probehalber ziehen wir aus 35831808 die siebte Wurzel. Erstaunt und voller Freude stellen wir fest, dass das Ergebnis eine Ganzzahl ist: 12. Das heißt, 12^7 ergibt 35831808 und 35831808 ist ein gültiges Element von Z[37762589]. Die Originalnachricht muss also 12 sein. Das probieren wir aus:

12^7 = 35831808 (mod 37762589)

Was hat der Absender nun falsch gemacht? Genau genommen gar nichts. Dies ist eine kritische Tücke im RSA-Verfahren. Je kleiner der Exponent e ist, desto größer ist die Wahrscheinlichkeit, dass das Ergebnis von x^e innerhalb von Z[n] ist. Tritt der Fall ein, dass x^e in Z[n] ist, dass also x^e mod n = x^e ist, braucht man nur die e'te Wurzel aus x^e (mod n) zu ziehen und erhält x. Ob das funktioniert hat, erkennt man an der Wurzel. Ist sie eine Ganzzahl, so hält man die Nachricht im Klartext in den Händen.

Wir sollten also keinen zu kleinen öffentlichen Exponenten wählen. Auch sollten wir keinen zu großen wählen, denn sonst herrscht die Gefahr, dass der entsprechende private Schlüssel zu klein wird und dadurch per Bruteforce (ausprobieren) ermittelbar ist. Eine gute Regel ist es, einen Exponenten zu wählen, sodass 2^e außerhalb von Z[n] ist. So garantieren wir, dass jede Zahl mindestens einmal umklappt und dadurch kein Wurzelziehen möglich ist.

2. Trivialer Klartext

Auch wird oft übersehen, dass 0^x immer 0 und 1^x immer 1 sind. Lautet der Chiffretext also c = 0, so lautet garantiert auch der Klartext m = 0, denn m^e = 0^e = 0 (mod n) für jedes beliebige e. Das gleiche gilt für c = 1. Problematisch ist auch, wenn wir zwei Chiffretexte c[1] und c[2] haben, die gleich sind (c[1] = c[2]). Wir als Angreifer wissen dann nämlich, dass die dazugehörigen Klartexte m[1] und m[2] auch gleich sind. Dies ist vor allem dann gefährlich, wenn wir Buchstabe für Buchstabe verschlüsseln, was ohnehin nicht gemacht werden sollte.

Um diese beiden Probleme zu lösen, sollten die untersten paar Bits des Klartextes immer irgendwelche Zufallszahlen über 1 sein. Es sollten also nur die höheren Bits für die eigentliche Nachricht genutzt werden. So verhindert man, dass der Klartext m jemals 0 oder 1 wird. Das erschwert dann auch die Kryptanalyse. Da die untersten paar Bits zufällig gewählt sind, liefert der gleiche Klartext immer einen unterschiedlichen Chiffretext. Je mehr Bits zufällig sind, desto mehr Chiffretextvarianten eines Klartextes gibt es. Sind 8 Bits zufällig, so hat jeder Klartext genau 2^8 = 256 verschiedene Chiffretextdarstellungen. Dies ist garantiert, da x^e (mod n) jedes x unterschiedlich abbildet, solange e relativ prim zu phi(n) ist und das ist Voraussetzung für die korrekte Funktionalität von RSA.

Es sollte auch immer die größtmögliche Einheit zum Verschlüsseln gewählt werden. Nehmen wir folgenden Schlüssel an:

n = 3382087550195091160127
e = 6341
d = 3244478562864920811989

Wir haben nun den Klartext 1 52 73 12 63 12 68, den wir wie im letzten Kapitel beschrieben verschlüsseln:

1.  1^e = 1 (mod n)
2. 52^e = 2111984357415861106407 (mod n)
3. 73^e = 1274135684506913336235 (mod n)
4. 12^e = 2889964449295186937660 (mod n)
5. 63^e = 721727110139700243420 (mod n)
6. 12^e = 2889964449295186937660 (mod n)
7. 68^e = 2130683150637670776795 (mod n)

Hier werden die beiden zuletzt beschriebenen Probleme deutlich. Der erste Klartext 1 liefert auch den Chiffretext 1. Der Angreifer weiß also, dass der Klartext auf jeden Fall 1 sein muss. Das nächste Problem, das deutlich wird, ist, dass wir die 12 doppelt verschlüsseln. Der Angreifer weiß also, dass an 4. und 6. Stelle auf jeden Fall der gleiche Klartext steht.

Wie oben beschrieben setzen wir eine Zufallszahl an die ersten paar Stellen. Weiters bilden wir die größtmögliche Einheit. Wir kombinieren die Komponenten des Klartextes also so, dass wir eine Zahl kleiner als n erhalten. Aus 1 52 73 12 63 12 68 machen wir also eine einzige Zahl: 0152731263126882. Die untersten beiden Stellen der Zahl sind zufällig gewählt. Wir verschlüsseln diese Zahl:

152731263126882^e = 2371099362558603522389 (mod n)

Aus dem Ergebnis kann der Angreifer jetzt keine Informationen mehr über den ursprünglichen Wert ermitteln. Jetzt sieht er weder, dass eine Komponente auf jeden Fall 1 sein muss, noch, dass zwei Komponenten gleich sind. Der Empfänger der Nachricht entschlüsselt:

2371099362558603522389^d = 152731263126882 (mod n)

Diese Zahl 152731263126882 teilt er nun wieder in zweistellige Komponenten auf: 1 52 73 12 63 12 68 82. Die letzte Komponente verwirft er, da sie zufällig ist und nicht zur eigentlichen Nachricht gehört.

3. Schlechte Primfaktoren

Die beiden Primfaktoren, aus denen das Modul n gebildet wird, müssen zwar zufällig sein, aber nur begrenzt. Beispielsweise sollten die Primzahlen p und q nicht zu nah beieinander liegen, denn je kleiner der Betrag | p - q |, desto kleiner auch die Beträge | sqrt(n) - p | und | sqrt(n) - q | (sqrt() ist die Quadratwurzelfunktion). Ab einer gewissen Grenze kann man dann die Primfaktoren dadurch ermitteln, dass man von der Quardratwurzel von n beginnend auf- und/oder abwärts sucht. Die Faktoren sollten sich in mindestens 90% der niederwertigen Ziffern unterscheiden. Am besten ist es, wenn sich die höchstwertigen paar Stellen voneinander unterscheiden. Andererseits sollten die Primzahlen nicht zu weit auseinander liegen, da sonst die Gefahr herrscht, dass eine der Primzahlen zu klein wird. Eine gute Regel ist es, zwei Primzahlen zu finden, die die gleiche Anzahl an Hexadezimalstellen haben, deren höchste Stellen sich aber deutlich voneinander unterscheiden. Hier ein Beispiel schlechter Primzahlen:

// Zu nah beieinander:
p = 102430499
q = 102430519

// Zu weit auseinander:
p = 845613173
q = 521

Und als Kontrast, hier noch einmal ein Beispiel mit guten Primzahlen:

p = 635678137
q = 295298623

Natürlich sind diese Zahlen allgemein zu klein, aber sie zeigen deutlich, worauf geachtet werden muss.

4a. Falsche RSA-Schlüssel

So simpel RSA auch sein mag. All das funktioniert nicht, solange wir keine Möglichkeit haben, die beiden Primzahlen p und q zu finden. Bisher konnte noch niemand ein System in der Verteilung von Primzahlen entdecken. Wir wissen nur, dass jede Primzahl ungleich zwei ungerade ist, denn sonst wäre die Zahl durch 2 teilbar und damit keine Primzahl mehr. Lange Zeit war das ein großes Problem für die Implementierung des RSA-Verfahrens. Man war darauf angewiesen, die Primzahlen nach einem Rate- und Schätzverfahren zu ermitteln. Es gab nämlich nur Primzahltests, die feststellen konnten, ob eine Zahl nicht prim ist. Das Problem ist inzwischen gelöst, aber um zu verdeutlichen, welche Folgen ein falscher RSA-Schlüssel haben kann, müssen wir uns vorübergehend in die Vergangenheit begeben.

Wie schon gesagt, arbeiten wir nach einem Rate- und Schätzverfahren. Wir wählen irgendeine Zahl x und müssen nun überprüfen, ob diese prim ist. Hier sind wir mit einem Jahrtausende alten Problem konfrontiert. Wie können wir ermitteln, ob x prim ist? Wir haben die Möglichkeit einer Garantie, dass x nicht prim ist, aber wir können nicht garantieren, dass x prim ist. Was passiert also nun, wenn unsere Schätzung fehlschlägt? Hier ein Beispiel mit kleinen Zahlen:

// Unsere Schätzung hat ergeben, dass die folgenden Zahlen prim sind:
p = 637243  // Diese Zahl ist prim
q = 387103  // Diese jedoch nicht: 521 * 743

// Also berechnen wir Modul und Anzahl der teilerfremden Zahlen:
n = p * q = 246678677029
phi(n) = (p - 1) * (q - 1) = 246677652684  // Falsch!

// Jetzt wählen wir die Exponenten:
e = 851
d = 123193892351
e * d = 1 (mod phi(n))

Damit ist unser falscher Schlüssel fertiggestellt. Das Problem bei diesem Schlüssel ist, dass phi(n) einen falschen Wert hat und damit die folgende Kongruenz nicht mehr aufgeht:

x^phi(n) = 1 (mod n)

Das können wir testen:

10^246677652684 = 100373419417 (mod 246678677029)
11^246677652684 = 155962675279 (mod 246678677029)
12^246677652684 = 204098099770 (mod 246678677029)
13^246677652684 = 228224756993 (mod 246678677029)
14^246677652684 = 158516107980 (mod 246678677029)
// ...

An diesem Beispiel sehen wir deutlich, dass unsere gewählten Zahlen nicht korrekt waren. Wir können das auch mit Ver- und Entschlüsselung testen, denn sie wird nicht mehr funktionieren:

// Wir verschlüsseln 643:
643^851 = 202623744463 (mod 246678677029)

// Jetzt entschlüsseln wir:
202623744463^123193892351 = 49265256973 (mod 246678677029)

Die Verschlüsselung wurde nicht korrekt umgekehrt. Dieses Problem konnten wir nicht lösen, nur eingrenzen. Für jedes p und q (n = p * q) mussten wir einige Tests durchführen. Zuerst einmal testeten wir, ob die Kongruenz x^((p - 1) * (q - 1)) = 1 (mod n) aufgeht, wenn gcd(x, n) = 1 gilt. Wir führten diese Operation einfach mit verschiedenen Basen x, die relativ prim zu n sind, durch. Sobald das Ergebnis für eine Basis x nicht 1 war, wussten wir mit Sicherheit, dass n auf jeden Fall nicht das Produkt zweier Primzahlen ist. Somit war entweder p oder q faktorisierbar und damit unser Ergebnis falsch. In diesem Fall suchten wir ein neues Paar p und q und testeten noch einmal. Je öfter unser Ergebnis 1 blieb, desto unwahrscheinlicher wurde es, dass p und q nicht prim sind. Dies konnte jedoch nicht versichert werden und wir hatten zwei zusätzliche Probleme. Es gibt bestimmte Zahlen, die für jede Basis 1 als Ergebnis liefern. Diese Zahlen sind extrem selten und werden mit der Größe von n zunehmend seltener, jedoch existieren sie und es gibt unendlich viele davon. Diese Zahlen sind analog zu den Carmichael-Zahlen, welche später besprochen werden. Das zweite Problem ist, dass wir mit riesigen Zahlen arbeiten müssen, damit RSA sicher ist. Das heißt, wir konnten nicht alle möglichen Basen x ausprobieren, denn für jede Probe mussten wir einmal den größten gemeinsamen Teiler gcd(x, n) berechnen, um zu sehen, ob x und n relativ prim sind und einmal eine modulare Exponentiation x^((p - 1) * (q - 1)) (mod n) durchführen, um zu sehen, ob die obige Kongruenz aufgeht. Das erfordert immense Rechenzeit und konnte daher nur auf eine winzige Untergruppe von x aus Z[n] durchgeführt werden. Zuletzt konnte man, um noch einmal sicher zu gehen, mit mehreren Probezahlen die Ver- und Entschlüsselung testen. Schlug dies fehl, so wussten wir auch mit Sicherheit, dass unser Ergebnis falsch war.

Wie bereits gesagt, ist dieses Problem inzwischen gelöst. Es gibt bereits Testverfahren wie das Miller-Rabin-Verfahren, die garantieren können, dass eine Zahl prim ist. Wir bleiben jedoch weiterhin in der Vergangenheit. Durch unvorsichtiges Programmieren können auch in der Gegenwart falsche Schlüssel entstehen. Im nächsten Abschnitt wird gezeigt, welche Gefahren in einem falschen Schlüssel stecken.

4b. Konsequenzen falscher Schlüssel

Damit wir Beispiele mit kleineren Zahlen liefern können, versetzen wir uns zurück in eine Zeit, in der es Jahrehunderte gedauert hat, eine Zahl mit 20 Stellen zu faktorisieren, aber nur wenige Minuten, um eine Zahl mit 10 Stellen zu faktorisieren. Falls dies unrealistisch klingt: die Zeit, die man zum Faktorisieren einer Zahl braucht, steigt exponentiell mit der Größe der Zahl, nicht etwa linear! Daher ist dieses Beispiel durchaus realistisch. Nehmen wir folgenden falschen Schlüssel:

p = 5928463679  // Ist prim.
q = 2168935883  // Ist nicht prim: 34171 * 63473
n = 12858457604445293557
phi(n) = 12858457596347893996  // Falsch!

e = 61
d = 8220981086189637145
e * d = 1 (mod phi(n))

Da n nun Produkt aus drei Primzahlen ist, wobei zwei davon nur fünfstellig sind, lässt sich diese Zahl wie ein zehnstelliges Produkt aus zwei Primzahlen innerhalb weniger Minuten faktorisieren. phi(n) ist für ein n mit drei Primfaktoren n = p * q * r definiert als phi(n) = (p - 1) * (q - 1) * (r - 1). Also faktorisieren wir n erst einmal und erhalten:

p = 5928463679
q = 34171
r = 63473
n = p * q * r = 12858457604445293557

Daraus können wir also nun den tatsächlichen Wert von phi(n) berechnen:

phi(n) = (p - 1) * (q - 1) * (r - 1) = 12857878729297446720

Wir wissen, dass e = 61 ist und können, da wir nun den richtigen Wert für phi(n) kennen, auch den richtigen Wert für d berechnen:

e = 61
d = 2950988560822364821

Aber wenn der Schlüssel so oder so falsch ist, wo ist dann das Problem? Dazu stellen wir uns folgendes Szenario vor. Bob generiert diesen falschen Schlüssel und legt ihn auf einem Keyserver ab. Da Bobs Software den Schlüssel nicht überprüft hat, merkt er nichts davon, dass der Schlüssel falsch ist. Nun holen sich Alice und Eve (die Angreiferin) diesen öffentlichen Schlüssel. Alice schickt nun eine verschlüsselte Nachricht an Bob und Eve hört diese Nachricht ab. Da Eve aus dem falschen Schlüssel problemlos einen richtigen Schlüssel machen konnte, wobei sich die Werte für n und e aber nicht ändern, kann sie die Nachricht problemlos entschlüsseln. Bob hingegen kann dies nicht, denn sein Schlüssel ist falsch. Alice berechnet aus m = 253761356 den Chiffretext:

c = 253761356^61 = 5441719397908522177 (mod n)

Diesen sendet Alice nun an Bob. Eve fängt diese Nachricht ab und entschlüsselt sie mit dem richtigen Wert für d:

m = 5441719397908522177^2950988560822364821 = 253761356 (mod n)

Bob hingegen, der eigentliche Empfänger der Nachricht, wird ein falsches Ergebnis bekommen, da sein d nicht stimmt:

// Falsch:
m = 5441719397908522177^8220981086189637145 = 6461175203459092287 (mod n)

Bob ruft bei Alice an und beschwert sich über den Mist, den Alice ihm geschickt hat. In der Zwischenzeit versendet Eve bereits alle möglichen Nachrichten mit der Signatur von Bob.

Es zeigt sich deutlich, dass falsche Schlüssel zu einer ernsthaften Gefahr werden können. Wer den privaten Schlüssel eines anderen hat, kann problemlos alle verschlüsselten Nachrichten, die an den Besitzer des Schlüssels gerichtet sind, lesen. Noch schlimmer jedoch, kann er Signaturen im Namen des eigentlichen Schlüsselbesitzers erzeugen und damit sogar Verträge abschließen. Dieses Problem kann nur durch vorsichtiges Programmieren und durch korrekte Testverfahren gelöst werden. Wir verlassen an dieser Stelle die Vergangenheit und kehren zur Gegenwart zurück. Man kann den weiter oben erwähnten Miller-Rabin-Primzahltest verwenden, denn dieser kann garantieren, dass eine Zahl prim ist.

Nachdem wir alle wichtigen Bestandteile von RSA kennengelernt haben, möchten wir die Chiffre natürlich auch anwenden. Hier werden einige Anwendungsbeispiele vorgestellt und erklärt.

1. Verschlüsselung

Die Verschlüsselung ist wohl das trivialste Beispiel überhaupt. Wie in einem früheren Kapitel bereits erwähnt wurde, ist die RSA-Chiffre sehr langsam. Aus diesem Grund wird sie fast immer mit einer klassischen symmetrischen Chiffre kombiniert. Zunächst erstellen wir einen RSA-Schlüssel R und veröffentlichen den öffentlichen Teil Rp dieses Schlüssels. Der Absender, der nun einen verschlüsselten Text an uns senden möchte, wählt eine symmetrische Chiffre, z.B. AES oder Blowfish und erstellt für diese Chiffre einen symmetrischen Schlüssel K. Er verschlüsselt seinen Text mit dem symmetrischen Verfahren unter Verwendung des Schlüssels K. Danach verschlüsselt er K mit RSA unter Verwendung des Schlüssel Rp. Die Kombination aus symmetrisch verschlüsseltem Text, asymmetrisch verschlüsseltem Schlüssel und eventuell einer Prüfsumme sendet er an uns.

Wir als Empfänger kennen den privaten Teil Rs von R und können somit den Schlüssel K, der per RSA verschlüsselt in der Nachricht enthalten ist, entschlüsseln. Diesen verwenden wir dann für die Entschlüsselung der eigentlichen Nachricht mit der gewählten symmetrischen Chiffre. Die Kombination aus symmetrischer und asymmetrischer Chiffre hat einen gewaltigen Geschwindigkeitsvorteil, vor allem, wenn wir große Nachrichten (z.B. multimediale Nachrichten) verschlüsseln. Wir müssen nur noch einen symmetrischen Schlüssel verschlüsseln und dafür reicht in den meisten Fällen eine einzige RSA-Operation.

2. Signaturen

Auch das Signieren von Nachrichten ist eine wichtige Anwendung von RSA. Diese erlaubt es uns, gleichzeitig die Integrität und die Vertrauenswürdigkeit einer Nachricht weitgehend zu garantieren. Zum Signieren bedienen wir uns einer speziellen Funktion, der Hash-Funktion. Eine Hash-Funktion ist eine Funktion, die folgende Eigenschaften hat:

• Der Rückgabewert der Funktion kann nicht auf den Eingabewert zurückgeführt werden.
• Es ist sehr schwierig, zwei Eingabewerte zu finden, die den gleichen Rückgabewert erzeugen.
• Es ist sehr schwierig, für einen bestimmten Rückgabewert einen passenden Eingabewert zu finden.

Eine Hash-Funktion ist also eine Einwegfunktion, deren Rückgabewert nur sehr schwer auf den Eingabewert zurückzuführen ist und deren Rückgabewert schwer zu reproduzieren ist. Der Rückgabewert einer Hash-Funktion wird hash, message digest oder Prüfsumme genannt. Bekannte Hash-Funktionen sind MD5, SHA1 und RIPE-MD. Empfohlen wird die Funktion SHA1, wobei MD5 bisher am weitesten verbreitet ist. Eine intensive Beschäftigung mit Hash-Funktionen sprengt den Rahmen dieser Dokumentation. Der Leser wird auf externe Literatur verwiesen.

Um eine Nachricht zu signieren, benötigen wir an erster Linie natürlich einen RSA-Schlüssel. Dieser kann der selbe sein, der auch zum Verschlüsseln verwendet wurde. Wir bezeichnen ihn als R. Der private Teil des Schlüssels wird als Rs und der öffentliche als Rp bezeichnet. Aus der Nachricht, die signiert werden soll, berechnen wir eine Prüfsumme mit einer bewährten Hash-Funktion wie SHA1. Diese verschlüsseln wir mit Rs und fügen sie zur Nachricht hinzu.

Der Empfänger der Nachricht kann diese nun verifizieren. Da Rp invers zu Rs ist, kann er die Signatur problemlos entschlüsseln. Er erstellt eine Prüfsumme der Nachricht und vergleicht diese mit der übergebenen Prüfsumme. Stimmen die Prüfsummen überein, ist garantiert, dass die Nachricht auf jeden Fall vom Besitzer des Schlüssels R versandt wurde und vollständig intakt ist. Niemand, außer dem Besitzer von R, kann solche Signaturen erstellen, denn nur er kennt Rs.

3. Authentifizierung

Ein weiterer interessanter Anwendungsbereich von RSA ist die Authentifizierung. Statt der normalen, passwortorientierten Authentifizierung verwenden wir den öffentlichen Schlüssel als Authentifizierungsgegenstand. Diese Form der Authentifizierung wird public key authentication genannt. Das Prinzip ist sehr simpel und erlaubt unter anderem beidseitige Identitätsverifikation. Der wichtigste Vorteil aber ist die Abwehr der Man in the Middle - Attacke (siehe unten). Dazu stellen wir uns eine Kommunikation zwischen Client und Server vor.

Nachdem die Verbindung hergestellt wurde, verlangt der Server den öffentlichen Schlüssel des Clients, den dieser bereitstellt. Gleichzeitig verlangt der Client den öffentlichen Schlüssel des Servers. Der Server überprüft, ob der übergebene öffentliche Schlüssel bekannt ist. Wenn ja, dann ist der Client identifiziert, aber noch nicht authentifiziert. Gleichzeitig prüft der Client, ob der öffentliche Schlüssel des Servers bekannt ist. Wenn ja, ist der Server identifiziert, aber noch nicht authentifiziert. Nach der Initialisierungsphase findet die eigentliche Authentifizierung statt, die allerdings relativ simpel ist und vollständig automatisch abläuft.

Der Client sendet eine zufällige, mit dem öffentlichen Schlüssel des Servers verschlüsselte Nachricht an den Server. Die Nachricht sollte nicht zu kurz sein. Der Server erstellt von dieser Nachricht eine Prüfsumme und sendet diese mit dem öffentlichen Schlüssel des Clients verschlüsselt an den Client zurück. Der Client überprüft diese Prüfsumme. Wenn sie korrekt ist, ist der Server authentifiziert. Gleichzeitig sendet der Server dem Client eine zufällige, mit dem öffentlichen Schlüssel des Clients verschlüsselte Nachricht. Dieser erstellt von der Nachricht eine Prüfsumme und sendet sie mit dem öffentlichen Schlüssel des Servers verschlüsselt an den Server zurück. Stimmt die Prüfsumme, so ist auch der Client authentifiziert. Eine passwortbasierte Authentifizierung ist hier nicht mehr notwendig, denn ein Angreifer braucht unbedingt den privaten Schlüssel des Clients, um dessen Identität vorzutäuschen, bzw. den privaten Schlüssel des Servers, um die Identität des Servers vorzutäuschen, denn er kann sonst die Prüfsummen nicht erstellen.

Bereits im vorletzten Kapitel wurde auf ein Problem hingewiesen, das wir bei der Arbeit mit RSA haben. Wir benötigen riesige Primzahlen mit mehreren hundert Dezimalstellen. Hier soll nun ein etwas älterer Primzahltest vorgestellt werden. Dieser dient nur der Veranschaulichung der Eulerschen phi-Funktion. Er sollte nicht verwendet werden, da er nicht garantieren kann, dass eine Zahl prim ist. Weiter oben wurde bereits der Miller-Rabin-Primzahltest erwähnt, der hier momentan allerdings noch nicht dokumentiert ist. Das Verfahren, das hier vorgestellt wird, basiert auf Eulers Theorie, die oben genannt wurde:

// Wenn x in Z[n] und gcd(x, n) = 1, dann:
x^phi(n) = 1 (mod n)

Nehmen wir nun an, n ist prim, dann ist phi(n) definiert als phi(n) = n - 1 und damit gilt der folgende Satz:

// Wenn x ungleich 0 in Z[n] und n prim, dann:
x^(n - 1) = 1 (mod n)

Dieser Satz besagt, dass x^(n - 1) (mod n) für jedes x ungleich 0 in der Menge Z[n] immer 1 ergibt, sofern n prim ist. Beweis: jede Zahl in Z[n], außer 0, ist relativ prim zu n, sonst wäre n teilbar und damit keine Primzahl. Der Test besteht also darin, x^(n - 1) (mod n) mit verschiedenen Basen x zu berechnen und das Ergebnis mit 1 zu vergleichen. Erhalten wir für irgendeine Zahl ein Ergebnis ungleich 1, so ist n mit Sicherheit keine Primzahl.

Es zeigt sich, dass dieser Test nicht garantieren kann, dass n prim ist. Er kann nur garantieren, dass n nicht prim ist. Im Übrigen sagt dieser Test nur aus, dass eine Zahl nicht prim ist. Anhand dieses Tests erhalten wir keine Informationen über die Faktoren dieser Zahl.

Wir probieren diesen Test mit verschiedenen Werten für n aus:

// n = 3743; diese Zahl ist nicht prim:
590^3742 = 1 (mod 3743)
// aber:
591^3742 = 3349 (mod 3743)
592^3742 = 986 (mod 3743)
593^3742 = 3483 (mod 3743)
594^3742 = 92 (mod 3743)

// n = 5227; diese Zahl hingegen ist prim:
590^5226 = 1 (mod 5227)
591^5226 = 1 (mod 5227)
592^5226 = 1 (mod 5227)
593^5226 = 1 (mod 5227)
594^5226 = 1 (mod 5227)

Je mehr Einsen wir bekommen, desto unwahrscheinlicher wird es, dass n nicht prim ist. In Z[3743] gibt es beispielsweise nur vier Zahlen, die das Ergebnis 1 liefern: 1, 590, 3153 und 3742. Da die 1 relativ trivial ist, brauchen wir sie gar nicht zu testen, denn 1^x ergibt immer 1.

Unwahrscheinlicher, aber leider nicht unmöglich. Es gibt bestimmte Zahlen, die für jede Basis x als Ergebnis 1 liefern, aber nicht prim sind. Diese Zahlen werden Carmichael-Zahlen genannt und sind extrem selten. Viel seltener als Primzahlen im höheren Bereich. Jedoch existieren sie und es gibt unendlich viele solcher Zahlen. Daher sollten wir uns nicht auf diesen Test verlassen. Es gibt noch haufenweise andere Testverfahren, auf die man am einfachsten im Internet stößt. Die Entwicklungen in den letzten Jahren umfassen Funktionen, die bereits garantieren können, dass eine Zahl prim ist.

Wie im Kapitel über den Euklidschen Algorithmus bereits erwähnt wurde, hat der größte gemeinsame Teiler zweier Zahlen a (in der Menge N) und b (in der Menge N[0]) eine interessante Eigenschaft. Dieser lässt sich nämlich als Linearkombination von a und b mit ganzzahligen Koeffizienten darstellen. Somit gilt:

// u und v sind Elemente von Z
gcd(a, b) = g
g = u * a + v * b

Es gibt unendlich viele Paare u und v, die die genannte Gleichung erfüllen. Mit dem erweiterten Euklidschen Algorithmus lassen sich diese beiden Koeffizienten berechnen.

Der normale Euklidsche Algorithmus führt gcd(a, b) auf gcd(b, a mod b) zurück. Der erweiterte Euklidsche Algorithmus führt zusätzlich u * a + v * b auf u' * b + v' * (a mod b) zurück, wobei u = v' und v = u' - a / b * v' gelten (Achtung: Ganzzahldivision!). Hier das Beispiel von oben:

       a      b  a mod b       u       v
   -----  -----  -------  ------  ------
1. 55913  20449    15015     -64     175  =  47 - 55913 / 20449 * -64
2. 20449  15015     5434      47     -64  = -17 - 20449 / 15015 *  47
3. 15015   5434     4147     -17      47  =  13 - 15015 /  5434 * -17
4.  5434   4147     1287      13     -17  =  -4 -  5434 /  4147 *  13
5.  4147   1287      286      -4      13  =   1 -  4147 /  1287 *  -4
6.  1287    286      143       1      -4  =   0 -  1287 /   286 *   1
7.   286    143        0       0       1  =   1 -   286 /   143 *   0
8.   143      0        -       1       0

Nachdem unser Algorithmus durchgelaufen ist, haben wir u = -64 und v = 175 und die Gleichung u * a + v * b = g. In unserem Beispiel ist g = 143 und wir testen:

a = 55913
b = 20449
g = gcd(a, b) = 143

u = -64
v = 175

  u *     a +   v *     b =   g
-64 * 55913 + 175 * 20449 = 143

Die Gleichung geht auf. Interessant ist, dass dies für jede Zeile zutrifft. So können wir Zeile 4 aus dem Beispiel nehmen und rechnen: