Verschlüsselung

In diesem Artikel behandeln wir ein relativ modernes Verfahren zur Verschlüsselung von Informationen, nämlich die RSA-Verschlüsselung. Dabei benötigen wir unter anderem den Satz von Euler-Fermat aus dem Artikel über Zahlentheorie. Bevor wir zu diesem Verfahren kommen, betrachten wir aber noch einfache Verschlüsselungsverfahren und deren Probleme.

Die Caesar-Verschlüsselung

Die Idee der Caesar-Verschlüsselung ist sehr simpel. Gegeben ist ein Wort bzw. ein Text, der verschlüsselt werden soll. Außerdem hat man sich auf einen Schlüssel, in diesem Fall eine ganze Zahl 0\leq s \leq 25, geeinigt. Jetzt wird jeder Buchstabe um s Positionen im Alphabet zyklisch verschoben. Wenn man dabei über das z kommt, fängt man wieder beim a an. Wenn man „hallo“ mit dem Schlüssel s=1 verschlüsselt, erhält man also „ibmmp“.

Zur Entschlüsselung verschiebt man die Buchstaben dann um s Positionen in die andere Richtung. Dieses Verfahren ist natürlich absolut unsicher und sehr leicht knackbar. Der Schlüsselraum, also die Anzahl verschiedener Schlüssel, ist mit 26 Möglichkeiten sehr gering. Im Zweifel kann man also alle Möglichkeiten ausprobieren.

Man kann dieses Verfahren etwas verallgemeinern, indem man die Buchstaben nicht nur zyklisch vertauscht, also alle Buchstaben um die gleiche Zahl verschiebt, sondern beliebige Permutationen erlaubt. Man ordnet also jedem Buchstaben im Originaltext einen Buchstaben für den Verschlüsselungstext zu und ersetzt dann alle Buchstaben entsprechend. Beim Entschlüsseln ersetzt man die Buchstaben dann in der anderen Richtung.

Hier kann man jetzt nicht mehr alle verschiedenen Schlüssel ausprobieren, weil es 26! verschiedene Schlüssel gibt. Trotzdem ist dieses Verschlüsselungsverfahren sehr unsicher. Wenn zum Beispiel ein Text der deutschen Sprache so verschlüsselt wird, kann man die Häufigkeiten der Buchstaben analysieren. Der am häufigsten vorkommende Buchstabe ist dann beispielsweise recht wahrscheinlich ein e. Zudem kann man häufig vorkommende Kombinationen gut erraten, zum Beispiel ein „und“.

Diese beiden Verfahren haben die Gemeinsamkeit, dass es einen geheimen Schlüssel gibt, den sowohl der Sender als auch der Empfänger kennen müssen, um verschlüsseln bzw. entschlüsseln zu können. Sobald dieser Schlüssel einmal ausgetauscht ist, kann in beide Richtungen verschlüsselt kommuniziert werden. Die Verfahren sind symmetrische Verschlüsselungsverfahren.

Die RSA-Verschlüsselung

Das RSA-Verfahren ist ein asymmetrisches Verschlüsselungsverfahren. Das bedeutet, dass nur der Empfänger den geheimen Schlüssel zur Entschlüsselung kennt und zuvor einen öffentlichen Schlüssel bekannt gegeben hat, den der Sender zum Verschlüsseln verwenden soll. Es ist vielleicht zunächst erstaunlich, wieso so ein Verfahren überhaupt funktionieren kann. Schließlich hat der Sender keine zusätzlichen Informationen, die nicht jeder andere auch hat und soll eine Nachricht verschlüsseln, sodass der Empfänger sie auch lesen kann.

Im Allgemeinen werden mit der RSA-Verschlüsselung nur Zahlen ver- und entschlüsselt. Allerdings kann man natürlich Buchstaben durch Zahlen darstellen und umgekehrt.

Die Vorbereitung

Bevor eine Nachricht verschlüsselt gesendet werden kann, muss der Empfänger natürlich seinen geheimen privaten Schlüssel und den öffentlichen Schlüssel erstellen. Dazu wählt er zunächst zwei Primzahlen p und q. Wir werden das Beispiel p=7 und q=11 betrachten, in der Praxis mit Computern haben diese Primzahlen mehrere hundert Stellen. Das öffentliche RSA-Modul ist N=p\cdot q, in unserem Beispiel also 77.

Man berechnet nun \varphi(N), also die eulersche Phi-Funktion. Da N das Produkt zweier Primzahlen ist, gilt \varphi(N)=(p-1)(q-1). In unserem Beispiel erhalten wir \varphi(N)=60. Nun wählt man noch einen Verschlüsselungsexponenten e, der teilerfremd zu \varphi(N) sein muss. Üblicherweise nimmt man hier eine Primzahl. Für das Beispiel nehmen wir e=17. Der öffentliche Schlüssel ist jetzt das Paar (N,e). Dieses Paar teilt man jetzt also jedem mit, der einem verschlüsselt Nachricht senden können soll. Es ist dabei eben nicht erforderlich, dass die Mitteilung des Schlüssels geheim erfolgt.

Zur Erstellung des privaten Schlüssels sind noch einige Berechnungen notwendig. Im Wesentlichen ist die Aufgabe noch einen Entschlüsselungsexponenten d zu finden, sodass e\cdot d \equiv 1 \mod \varphi(N). Es müssen also ganze Zahlen d und l gefunden werden, sodass e\cdot d = 1 + l\cdot \varphi(N). Das ist mit dem euklidischen Algorithmus effizient möglich. Hierfür ist auch die Bedingung notwendig, dass e und \varphi(N) teilerfremd sind. Ich werde dieses Verfahren nicht in der Allgemeinheit zeigen, sondern nur am Beispiel demonstrieren.

Wir möchten also eine ganzzahlige Lösung für 17d=1+60l finden. Es muss also 17d-60l=1 gelten. Wir wollen also eine sogenannte Linearkombination von 17 und 60 zu 1 finden. Wir schauen nun, wie oft 17 in die 60 reinpasst und betrachten den Rest. Es gilt 60=3\cdot 17 + 9. Das heißt insbesondere, dass man 9 aus 17 und 60 linear kombinieren kann. Also können wir die 60 durch eine 9 ersetzen, und versuchen 17 und 9 zu 1 linear zu kombinieren. Schließlich können wir die 9 im Nachhinein wieder ersetzen. Dieses Verfahren wiederholt man jetzt so lange, bis ein Rest von 1 bleibt. Es ergeben sich die folgenden Gleichungen im Beispiel:

\begin{aligned}60&=3\cdot 17+9\\17&=1\cdot 9 +8\\9&=1\cdot 8+1\end{aligned}

Jetzt ersetzen wir rückwärts die Linearkombination von 1 und erhalten:

\begin{aligned}1&=9-8=9-(17-9)=2\cdot 9 - 17 \\&= 2 \cdot (60-3\cdot 17) - 17 = 2\cdot 60 - 7\cdot 17\end{aligned}

Also haben wir d=-7 gefunden. Wir rechnen modulo \varphi(N)=60, also nehmen wir d=53. Für die Entschlüsselung ist jetzt nur noch das Paar (N, d) relevant.

Wie funktioniert die verschlüsselte Kommunikation?

Es soll eine Nachricht a, dargestellt als natürliche Zahl, verschlüsselt werden. Dabei ist notwendig, dass die Zahl kleiner als N ist. Außerdem muss die Nachricht teilerfremd zu p und q sein. In unserem Beispiel müssen wir darauf achten, in der Realität sind die Primzahlen so groß, dass das nicht passiert. Der Sender bestimmt nun b\equiv a^e \mod N, sodass 0\leq b \lt N. Es soll also der Rest von a^e bei Division durch N bestimmt werden. Dafür kann man beispielsweise immer wieder mit a multiplizieren und N abziehen, wenn man dabei über N kommt. Wir wollen im Beispiel mal die Nachricht a=3 verschlüsseln. Zur Vereinfachung der Rechnung nutzen wir 3^4=81 \equiv 4 \mod 77:

3^{17}=3^4\cdot 3^4 \cdot 3^4 \cdot 3^4 \cdot 3 \equiv 4^4 \cdot 3 = 256 \cdot 3 \equiv 25 \cdot 3 = 75 \mod 77

Als Geheimtext erhalten wir also b=75.

Zur Entschlüsselung rechnet der Empfänger nun a\equiv b^d \mod N aus. In unserem Beispiel ist das der Rest von 75^53 bei Division durch 77. Hier ist die Rechnung etwas aufwändiger:

\begin{aligned}75^{53}&\equiv (-2)^{53} \\&\equiv (-2)^{48} \cdot (-32)\\&=256^6 \cdot (-32) \\&\equiv 25^6 \cdot (-32) \\&= 625^3 \cdot (-32) \\&\equiv 9^3 \cdot 45 \\&= 729 \cdot 45 \equiv 36 \cdot 45 \\&= 1620 \\&\equiv 3 \mod 77\end{aligned}

Diese Rechnung steht eigentlich nur dazu da, damit ersichtlich wird, dass diese Aufgabe viel einfacher ist, als 75^{53} direkt auszurechnen. Wir haben also die Nachricht a=3 richtig entschlüsselt.

Wieso funktioniert die Entschlüsselung?

Wenn wir die Nachricht a mit e potenzieren und danach mit d potenzieren (bei der Entschlüsselung), erhalten wir das Gleiche, wie wenn man gleich mit e\cdot d potenziert. Dieses Potenzgesetz folgt direkt aus dem Zählen der Anzahlen Faktoren. Wir wissen aber einerseits, dass e\cdot \equiv 1 \mod \varphi(N) aus Konstruktion und andererseits a^{\varphi(N)} \equiv 1 \mod N aus dem Satz von Euler-Fermat. Damit können wir folgern:

a^{e\cdot d} = a^{l\cdot \varphi(N)} \cdot a^1 \equiv 1^l \cdot a^1 = a \mod N

Also führt die Entschlüsselung tatsächlich zur Originalnachricht.

Wie kann diese Verschlüsselung „sicher“ sein?

Um diese Verschlüsselung zu knacken, müsste man aus der verschlüsselten Nachricht b ein a bestimmen, sodass b\equiv a^e \mod N. Man müsste also die Wurzel modulo N ziehen. Der Empfänger umgeht dieses Problem, indem er mit einem geeigneten d potenziert. Um dieses d einfach bestimmen zu können, muss man aber \varphi(N) kennen und dafür benötigt man die Primfaktoren von N. Es gibt aber bis heute auch keinen effizienten Algorithmus zur Primfaktorenzerlegung. Die Verschlüsselung besteht also zum Teil auch aus dem Prinzip, dass es deutlich einfacher ist, zwei Primzahlen zu multiplizieren (das ist zur Erzeugung des Schlüssels relevant), als ihr Produkt in Primfaktoren zu zerlegen.

Dieses Verschlüsselungsverfahren wird auch heutzutage teilweise noch angewendet, meist in Kombination mit weiteren Verschlüsselungen.

Im nächsten Artikel beschäftigen wir uns mit Spieltheorie.