Bisher wurde immer vorausgesetzt, dass ein sicherer Kanal zum Austausch des geheimen Schlüssels zwischen beiden Parteien, etwa dem Sender $\text{[math]}$ und dem Empfänger $\text{[math]}$ existiert. Ein vermeintlich sicherer Kanal kann natürlich ein großer Unsicherheitsfaktor sein.

Ein weiteres Problem ist, dass bisher der geheime Schlüssel nur den beiden Teilnehmern $\text{[math]}$ und $\text{[math]}$ bekannt war. Ein Dritter, etwa $\text{[math]}$ , konnte keine Nachricht an $\text{[math]}$ verschlüsselt übermitteln, die auch von $\text{[math]}$ hätte korrekt entschlüsselt werden können.

Diffie und Hellman schlugen daher 1976 vor, Systeme zu suchen bzw. zu entwickeln, bei denen ein Teil des Schlüssels öffentlich ist ( $\text{[math]}$ kann an $\text{[math]}$ senden, wenn ein Teil von $\text{[math]}$ 's Schlüssel öffentlich ist) und der andere Teil des Schlüssels privat und geheim ist. Derartige Kryptosysteme werden Public-Key-Systeme (oder auch asymmetrische Kryptosysteme) genannt.

Ist der Schlüssel von $\text{[math]}$ allgemein bekannt, so kann jeder an $\text{[math]}$ Nachrichten (verschlüsselt) senden! In diesem Fall ist kein sicherer Kanal zur Schlüsselübergabe mehr notwendig.

Nach einer Idee von Rivest, Shamir und Adleman entstand das RSA-System, benannt nach den Anfangsbuchstaben der Namen der drei Erfinder.

Wir nehmen im Folgenden an, dass der Klartext eine Folge von Bits ist, die in Blöcke gleicher Länge unterteilt wird. Jeder Block, interpretiert als natürliche Zahl, wird einzeln verschlüsselt.

Sei $\text{[math]}$ eine Nachricht, die verschlüsselt von $\text{[math]}$ an $\text{[math]}$ gesandt werden soll. Die Nachricht $\text{[math]}$ ist in natürlicher Weise (etwa mit der Binärdarstellung) aus einem $\text{[math]}$ -Klartextblock der Länge maximal $\text{[math]}$ entstanden. Später werden wir sehen, dass wir beliebige Nachrichten $\text{[math]}$ verwenden können.

Setup für das RSA-System

Verschlüsselung

$\text{[math]}$ möchte an $\text{[math]}$ eine Nachricht $\text{[math]}$ senden. Dazu nimmt er den öffentlichen Schlüssel $\text{[math]}$ von $\text{[math]}$ , berechnet

Entschlüsselung

Empfängt $\text{[math]}$ die Nachricht $\text{[math]}$ ( $\text{[math]}$ ) von $\text{[math]}$ , so nimmt er seinen geheimen privaten Schlüssel $\text{[math]}$ und berechnet

und erhält die gesendete Nachricht $\text{[math]}$ . Dieses müssen wir natürlich noch verifizieren, zu diesem Zweck weisen wir die Korrektheit des RSA-Verfahrens nach.

Korrektheit

Wir wollen zeigen, dass man für alle $\text{[math]}$ , die wie beschrieben verschlüsselt und anschließend wieder entschlüsselt werden, genau die Nachricht $\text{[math]}$ erhält, dass also gilt:

Mit dem Satz von Euler und Satz 41 sieht man nun für die Nachricht $\text{[math]}$ die Korrektheit des RSA-Verfahrens wie folgt ein:

Ein wichtiger Aspekt beim RSA-Verfahren ist das effiziente Auffinden geeigneter Primzahlen $\text{[math]}$ und $\text{[math]}$ . Dies ist mit verschiedenen probabilistischen Primzahlverfahren wie etwa der Methode von Solovay und Strassen effizient möglich.

Effizienz des RSA-Systems

Wir wollen kurz einige Überlegungen zur Effizienz bzw. Laufzeit des RSA-Systems durchführen.

Beim Setup des Systems benötigen wir eine effiziente Erzeugung zweier großer Primzahlen, die wir wie erwähnt beispielsweise mit dem Algorithmus von Solovay und Strassen durchführen können. Seit einiger Zeit ist sogar ein polynomieller deterministischer Algorithmus zum Primzahltest bekannt, aber der Algorithmus von Solovay und Strassen ist aufgrund von kleinen Konstanten in der Laufzeit besonders schnell.

Desweiteren entsteht im Wesentlichen Aufwand durch die Multiplikation zweier langer Zahlen sowie durch Aufrufe des Euklidischen Algorithmus zur Bestimmung des größten gemeinsamen Teilers zweier Zahlen bzw. durch Aufrufe des erweiterten Euklidischen Algorithmus zur Bestimmung des multiplikativen Inversen einer Zahl. Mit der Schulmethode kann das Produkt zweier $\text{[math]}$ -Bit Zahlen mit Aufwand $\text{[math]}$ bestimmt werden, also effizient in der Eingabelänge. Für den Euklidischen Algorithmus überlegt man sich, dass dieser aufgerufen auf Zahlen $\text{[math]}$ höchstens $\text{[math]}$ viele Iterationen mit Zeitaufwand jeweils $\text{[math]}$ benötigt, was einen Aufwand von $\text{[math]}$ , also ebenfalls polynomiell in der Eingabelänge bedeutet. Bis auf die Tatsache, dass wir beim Setup Zahlen auswürfeln und unter Umständen mehrere Versuche benötigen, bis geeignete Zahlen gefunden sind, lassen sich die Schritte des Setups also effizient ausführen.

Dass man beim "Auswürfeln von Primzahlen" nicht zu viele Versuche benötigt kann man mit einem Satz aus der Zahlentheorie zeigen, der besagt dass die Anzahl der Primzahlen der Größe höchstens $\text{[math]}$ ungefähr $\text{[math]}$ ist. Damit gibt es unter allen $\text{[math]}$ -stelligen Binärzahlen im wesentlichen

viele Primzahlen. Also können wir folgern, dass die Wahrscheinlichkeit, beim Auswürfeln einer $\text{[math]}$ -Bit Zahl eine Primzahl zu erhalten, $\text{[math]}$ ist. Wir benötigen daher im Erwartungswert $\text{[math]}$ viele Zufallsexperimente, um eine Primzahl der Länge $\text{[math]}$ zu erhalten.

Bei der Ver- und Entschlüsselung entsteht Aufwand durch das Potenzieren langer Zahlen. Da wir alle Rechnungen modulo $\text{[math]}$ durchführen, besitzen alle Zwischenergebnisse diese Maximallänge, und eine Multiplikation lässt sich polynomiell in der Eingabelänge durchführen. Die Potenzen berechnet man nun mit der Methode des fortgesetzten Quadrierens. Dazu benutzt man die Identität $\text{[math]}$ . Wollen wir $\text{[math]}$ berechnen für eine $\text{[math]}$ -Bit-Zahl $\text{[math]}$ in Binärdarstellung, $\text{[math]}$ , so berechnen wir $\text{[math]}$ und multiplizieren die Terme zu den Potenzen, für die $\text{[math]}$ gilt. Damit kommen wir mit höchstens $\text{[math]}$ vielen Multiplikationen aus und die Potenzierung lässt sich effizient durchführen.

Kryptoanalyse

Die Sicherheit des RSA-Systems beruht auf der (höchstwahrscheinlich korrekten) Annahme, dass die Faktorisierung einer Zahl $\text{[math]}$ nicht effizient durchführbar ist, also nicht in Zeit $\text{[math]}$ . Auch ist es schwierig, in $\text{[math]}$ Wurzeln, etwa die $\text{[math]}$ -te, $\text{[math]}$ , zu ziehen. In $\text{[math]}$ Wurzeln zu ziehen ist jedoch bei ganzzahligem Ergebnis einfach, da man die binäre Suche anwenden kann.

Wir betrachten nun einige Fälle, bei denen ein Angreifer über verschiedene Informationen verfügt und prüfen, wie diese zum Brechen des Kryptosystems verwendet werden können:

Wir wollen nun noch einmal zum ersten Gliederungspunkt zurückkommen und Möglichkeiten für einen Angriff durch Faktorisierung diskutieren. Als Beispiel eines Verfahrens zur Faktorisierung natürlicher Zahlen wird hier der $\text{[math]}$ -Algorithmus von Pollard (1974) vorgestellt.

Idee beim Verfahren: Ist $\text{[math]}$ eine Primzahl mit $\text{[math]}$ und $\text{[math]}$ für jede Primzahlpotenz $\text{[math]}$ mit $\text{[math]}$ , dann gilt $\text{[math]}$ . Diese Aussage ist folgendermaßen begründet: Für die Primfaktorenzerlegung $\text{[math]}$ und $\text{[math]}$ für $\text{[math]}$ gilt $\text{[math]}$ für $\text{[math]}$ , und somit folgt aus $\text{[math]}$ für $\text{[math]}$ auch $\text{[math]}$ . Speziell ist dieses Verfahren für Zahlen $\text{[math]}$ geeignet, bei denen $\text{[math]}$ kleine Primfaktoren enthält.

Die Korrektheit ist offensichtlich. Falls $\text{[math]}$ gilt, so ist $\text{[math]}$ , also $\text{[math]}$ , wobei $\text{[math]}$ ein Primfaktor von $\text{[math]}$ ist.

Laufzeit: Im ersten Schritt zur Berechnung von $\text{[math]}$ führt man $\text{[math]}$ modulare Exponentiationen jeweils $\text{[math]}$ aus, jede kann mit maximal $\text{[math]}$ modularen Multiplikationen durchgeführt werden. Das Rechnen modulo $\text{[math]}$ kann insgesamt in Zeit $\text{[math]}$ durchgeführt werden. Im zweiten Schritt kann der $\text{[math]}$ in Zeit $\text{[math]}$ mit dem Euklidischen Algorithmus berechnet werden.

Für $\text{[math]}$ ist $\text{[math]}$ , also Polynomialzeit, aber die Erfolgswahrscheinlichkeit für das Finden eines Teilers ist eventuell klein.

Bemerkung: Wird ein Las Vegas Algorithmus mit Parameter $\text{[math]}$ nun $\text{[math]}$ -mal gestartet (Multi-Start-Ansatz), so liefert er mit Wahrscheinlichkeit höchstens $\text{[math]}$ jedesmal keine Antwort. Eine korrekte Antwort erfolgt also mit Wahrscheinlichkeit mindestens $\text{[math]}$ .

Für $\text{[math]}$ erhält man also schon bei 10 Starts eine Antwort mit Wahrscheinlichkeit mindestens $\text{[math]}$ .

Beweis Zunächst machen wir einige Vorbemerkungen. Sei $\text{[math]}$ Produkt zweier ungerader Primzahlen $\text{[math]}$ und $\text{[math]}$ mit $\text{[math]}$ . Es gilt dann:

\text{[math]}

Dieses bedeutet, dass die Kongruenz $\text{[math]}$ vier Lösungen hat. Also gibt es neben den trivialen Lösungen $\text{[math]}$ und $\text{[math]}$ noch zwei weitere nichttriviale Lösungen. Diese findet man mit dem Chinesischen Restsatz, durch Lösen der simultanen Kongruenzen $\text{[math]}$ und $\text{[math]}$ oder $\text{[math]}$ und $\text{[math]}$ .

Sei $\text{[math]}$ nichttriviale Lösung von $\text{[math]}$ . Dann gilt

\text{[math]}

und folglich $\text{[math]}$ oder $\text{[math]}$ und analog ist $\text{[math]}$ gleich $\text{[math]}$ oder $\text{[math]}$ . Die größten gemeinsamen Teiler können mit dem Euklidischen Algorithmus berechnet werden.

Kennt man also eine nichtriviale Lösung der Kongruenz $\text{[math]}$ , so erhält man mit polynomiellem Zeitaufwand die Faktorisierung von $\text{[math]}$ . Wir haben daher den folgenden Algorithmus:

Algorithmus Faktorisierung bei gegebenem öffentlichen Schlüssel $\text{[math]}$

Gegeben: Ein Algorithmus, der zu gegebenen Werten $\text{[math]}$ mit $\text{[math]}$ für Primzahlen $\text{[math]}$ ein $\text{[math]}$ berechnet mit $\text{[math]}$ , wobei $\text{[math]}$ Produkt zweier verschiedener Primzahlen ist.

Beweis Der Algorithmus liefert keine Antwort (schlechte Wahl von $\text{[math]}$ ), wenn eine der Aussagen gilt:

$\text{[math]}$
$\text{[math]}$ für ein $\text{[math]}$

Wir zählen im folgenden die Anzahl der Lösungen der einzelnen Kongruenzen für $\text{[math]}$ für Primzahlen $\text{[math]}$ .

zu 1.: Gilt $\text{[math]}$ , so gilt auch $\text{[math]}$ und $\text{[math]}$ . Andererseits können Lösungen von $\text{[math]}$ und $\text{[math]}$ mit dem Chinesischem Restsatz zu einer Lösung $\text{[math]}$ kombiniert werden. Wir betrachten daher die Anzahl der Lösungen der einzelnen Kongruenzen $\text{[math]}$ sowie $\text{[math]}$ .

Zunächst betrachten wir die Kongruenz $\text{[math]}$ . Sei $\text{[math]}$ erzeugendes Element von $\text{[math]}$ , also ist $\text{[math]}$ für ein $\text{[math]}$ . Dann gilt $\text{[math]}$ , also nach dem Satz von Fermat

\text{[math]}

Mit

\text{[math]}

für ungerade $\text{[math]}$ und

\text{[math]}

folgt

\text{[math]}

Damit gilt $\text{[math]}$ und $\text{[math]}$ .

Mit $\text{[math]}$ folgt $\text{[math]}$ , also $\text{[math]}$ , da $\text{[math]}$ ungerade ist. Mit $\text{[math]}$ und $\text{[math]}$ folgt, dass $\text{[math]}$ möglich ist. Die Anzahl Lösungen von $\text{[math]}$ ist daher maximal $\text{[math]}$ . Entsprechend gilt, dass die Anzahl Lösungen von $\text{[math]}$ maximal $\text{[math]}$ ist. Die Anzahl Lösungen der Kongruenz $\text{[math]}$ ist daher maximal $\text{[math]}$ .

zu 2.: Wir bestimmen nun für $\text{[math]}$ die Anzahl Lösungen der Kongruenz

\text{[math]}

Wie vorher betrachten wir die Kongruenzen $\text{[math]}$ und $\text{[math]}$ .

Für $\text{[math]}$ und $\text{[math]}$ folgt $\text{[math]}$ . Da $\text{[math]}$ erzeugendes Element in $\text{[math]}$ ist, gilt $\text{[math]}$ , also nach dem Satz von Fermat

\text{[math]}

Für $\text{[math]}$ gibt es hier keine Lösungen. Für $\text{[math]}$ sind die Lösungen $\text{[math]}$ genau ungerade Vielfache von $\text{[math]}$ , da $\text{[math]}$ ungerade ist. Die Anzahl dieser Vielfachen ist

\text{[math]}

Analoges folgt für die Kongruenz $\text{[math]}$ . Damit ist die Anzahl Lösungen von $\text{[math]}$ maximal

\text{[math]}

Mit der Annahme $\text{[math]}$ ist die Anzahl der schlechten Wahlen von $\text{[math]}$ daher maximal

\text{[math]}

Mit $\text{[math]}$ (da $\text{[math]}$ ungerade) haben wir

\text{[math]}

Weiter gilt

\text{[math]}

also folgt

\text{[math]}

Da wir $\text{[math]}$ gemäß der Gleichverteilung wählen, sind mindestens $\text{[math]}$ gute Wahlen für $\text{[math]}$ dabei, also ist die Erfolgswahrscheinlichkeit mindestens $\text{[math]}$ .

Übungen

Aufgabe 1
Beim RSA-Verfahren verwendet jemand als öffentliche Schlüssel $\text{[math]}$ und $\text{[math]}$ , wobei $\text{[math]}$ ein Produkt zweier verschiedener Primzahlen $\text{[math]}$ ist. Welche Probleme treten auf?

Aufgabe 2
Eine Nachricht $\text{[math]}$ wird mittels RSA verschlüsselt und an $\text{[math]}$ Empfänger mit den öffentlichen Schlüsseln $\text{[math]}$ , $\text{[math]}$ und $\text{[math]}$ gesendet. Bestimmen Sie aus den Chiffraten

das Chiffrat zu einem Klartext $\text{[math]}$ . Zeigen Sie, dass eine natürliche Zahl $\text{[math]}$ mit

Aufgabe 4
Ein Klartext $\text{[math]}$ wird zweimal mit den öffentlichen Schlüsseln $\text{[math]}$ und $\text{[math]}$ verschlüsselt. Kann, wenn $\text{[math]}$ ist, ein Angreifer aus den Chiffraten

Hinweis: Zu $\text{[math]}$ existieren $\text{[math]}$ mit $\text{[math]}$ (vgl. Bemerkung 20 (iv)).

Aufgabe 5
Zeigen Sie, dass man mit der RSA-Dechiffrierfunktion $\text{[math]}$ tatsächlich den Klartext $\text{[math]}$ erhält.

Aufgabe 6
Zur Beschleunigung der Dechiffrierung bei einem RSA-System mit den Parametern $\text{[math]}$ führt der Empfänger eines Chiffrats $\text{[math]}$ folgendes aus:

Er berechnet $\text{[math]}$ sowie $\text{[math]}$ und berechnet mit dem Chinesischen Restsatz ein $\text{[math]}$ mit

Aufgabe 7
Von einer natürlichen Zahl $\text{[math]}$ sei bekannt, dass sie das Produkt zweier verschiedener Primzahlen ist.

Aufgabe 8
Beim Setup des RSA-Systems werden versehentlich die gleichen Primzahlen $\text{[math]}$ und $\text{[math]}$ gewählt.

Aufgabe 9
Im RSA-System mit öffentlichem Schlüssel $\text{[math]}$ heißt eine Nachricht $\text{[math]}$ ein Fixpunkt, wenn gilt

Hinweis: Es gibt für Primzahlen $\text{[math]}$ ein erzeugendes Element $\text{[math]}$ mit $\text{[math]}$ .

Aufgabe 10
Betrachten Sie folgenden Primzahltest. In dem Intervall $\text{[math]}$ , wobei der Einfachheit halber $\text{[math]}$ durch $\text{[math]}$ teilbar ist, wird zufällig gemäß der Gleichverteilung eine natürliche Zahl $\text{[math]}$ ausgewählt. Sodann wird geprüft, ob die Zahl $\text{[math]}$ durch $\text{[math]}$ , $\text{[math]}$ oder $\text{[math]}$ teilbar ist. Ist dieses der Fall, so wird die Antwort "keine Primzahl" gegeben, ansonsten die Antwort "wahrscheinlich eine Primzahl".

Das RSA-System