RSA Verschlüsselung mathematisch erklärt

Mit RSA Verschlüsselung Nachrichten sicher versenden.

Mittels RSA Verchlüsselung lassen sich Nachrichten sicher verschlüsseln. Doch wie funktioniert das eigentlich genau?

Wer an einer mathematischen Erklärung des Verfahrens hinter der RSA Verschlüsselung (auch RSA Cryptosystem genannt) interessiert ist, oder auch wem die einfache Erklärung nicht ausreicht, der ist hier genau richtig. Ich beschreibe kurz und (hoffentlich) verständlich, wie man Nachrichten mit dem RSA Verfahren verschlüsselt.

Ich werde dabei so wenig Formalismus wie möglich und so viel wie nötig mit einbringen, da man es sich sonst auch bei Wikipedia anlesen kann. Man braucht für diese Seite ein Grundverständnis von Mathematik, also man sollte wissen was mit der Menge $\mathbb{Z}$ gemeint ist, was ist der größte gemeinsame Teiler ist, Grundverständnis von Äquivalenz-Umformungen, etc.
Aber es reicht aus, wenn man alles im Kapitel „Grundbegriffe der RSA Verschlüsselung“ verstanden hat.

Beispiele finden sich ganz unten, dabei habe ich mir ein kleines und ein größeres Beispiel ausgedacht (und nein, die sind nicht von Wikipedia kopiert, wie alle anderen Beispiele im Netz 😉 ).

Wer Nachrichten im realen Leben mittels RSA Verschlüsselung sichern möchte, der sollte sich Enigmail für Thunderbird angucken. Im verlinkten Artikel findet sich eine Schritt-für-Schritt-Beschreibung der Einrichtung von Enigmail.

Grundbegriffe der RSA Verschlüsselung

… besser gesagt die Mathematischen Grundbegriffe dahinter.

Primzahl

Zunächst sollte klar sein was eine Primzahl ist: Eine Zahl größer als 1 (nicht größer gleich 1!) und die nur durch 1 und sich selbst Teilbar ist. 0 und 1 sind keine Primzahlen, die kleinste Primzahl ist 2!

Kongruenz und Modulo

Es sollte auch der Begriff der Kongruenz klar sein. Zwei Zahlen $a$ und $b$ sind gegenüber einer Zahl $m$ Kongruent, wenn sie den selben Divisionsrest haben.
Beispiel: 27 und 51 sind gegenüber 6 Kongruent, denn beide haben den Divisionsrest 3. Man schreibt es als $27\equiv 51 (\text{ mod } 6)$ . Das $\text{mod}$ ist dabei die Modulo Funktion (in der Programmierung meistens als %-Operator gebräuchlich) und gibt den Divisionsrest als Ergebnis aus. Der Teiler (hier die 6) wird auch als Modul bezeichnet, was später nochmal auftaucht.

Restklassen und Repräsentanten

Viel wichtiger sind Restklassen.
Eine Restklasse ist eine Menge an Zahlen, die alle den gleichen Divisionsrest bezüglich eines Modulo haben. Man schreibt dafür $x\in[r]_m$ , wenn man sagt „Die Zahl $x$ ist in der Restklasse $r$ Modulo $m$ enthalten„.

Beispielsweise gilt für 3 und 27 mit Modulo 6: $3\text{ mod }6=27\text{ mod }6$ damit gilt $27\in[3]_6$ .
Wörtlich: Die 27 ist in der Restklasse 3 Modulo 6 enthalten, also in der Menge, in der alle Zahlen drin sind, die den Divisionsrest 3 bezüglich der 6 haben. Das sind also alle Zahlen der Form $3+i\cdot 6$ mit $i\in\mathbb{N}$ (also 3 plus ein Vielfaches von 6) was wie Menge $\{3,9,15,21,27,33,...\}$ erzeugt.
Etwas formaler: Für alle $n\in\mathbb{N}$ in dieser Restklasse gilt $n\equiv 3\text{ mod }6$ . Es ist sehr wichtig, dass man Restklassen versteht, wenn man die Mathematik hinter der RSA Verschlüsselung verstehen möchte.

Das $n$ wird auch Repräsentant der Restklasse genannt. Allgemein ist jede Zahl $r\in \mathbb{Z}$ und $m\in\mathbb{N}$ einer Restklasse $[r]_m$ genau dann ein Repräsentant dieser Restklasse, wenn $r<m$ gilt. Im obigen Beispiel sind also 0, 1, 2, 3, 4, 5 Repräsentanten, da alle kleiner als 6 sind. Für die 6 selbst würde wieder $6\text{ mod }6\equiv 0\text{ mod }6$ gelten und so würde man die 0 als Repräsentanten wählen.

Multiplikatives Inverses innerhalb einer Restklasse

Wo wir schon bei Restklassen sind, muss man auch wissen, was das multiplikative Inverse einer Zahl zu einem bestimmten Modulo ist (also einer Zahl innerhalb einer Restklasse). Für das multiplikative Inverse $i$ einer Zahl $a$ bezüglich $\text{mod }n$ gilt $i\cdot a\equiv 1\text{ mod }n$ .
Man findet das multiplikative Inverse mittels des Euklid’schen Algorithmus für den ggt (größten gemeinsamen Teiler) gepaart mit einem Verfahren zum Rückeinsetzen. Dabei hilft die Tatsache, dass man $ggt(a,b)=x\cdot a+y\cdot b$ schreiben kann, wobei $x,y\in\mathbb{Z}$ gilt. Gut erklärt in diesem Skript unter Kapitel 2.2.4.

Mini-Exkurs zur Vorstellung was das multiplikative Inverse ist:
Wenn man nicht in einer Restklasse, sondern z.B. in den Natürlichen Zahlen rechnet, so ist das multiplikative Inverse gegenüber $a$ genau der Kehrwert $\frac{1}{a}$ , denn $a\cdot\frac{1}{a}=1$ .

Eulersche phi-Funktion

Für später brauchen wir auch noch die Eulersche phi-Funktion, sie gibt die Anzahl der Teilerfremden Zahlen bis zu einer Grenze an. So ist beispielsweise ist $\varphi(40)=16$ (es gibt 16 Zahlen von 0 bis 39, die zu 40 teilerfremd sind), wohingegen bei 41 (also einer Primzahl) $\varphi(41)=40$ ist.

Generell gilt: Bei einer Primzahl $p$ ist $\varphi(p)=p-1$ (Begründung hier). Das ist für später sehr wichtig und hilfreich.

Gruppen (für interessierte)

Interessierte sollten auch die Struktur einer Gruppe kennen, denn auf ihr basiert das Verfahren der RSA Verschlüsselung (genauer gesagt basiert die Idee der Restklasse auf Ringen und die wiederum auf Gruppen). Ich werde darauf aber weniger eingehen, da das Feld der Gruppentheorie zu weit führt 😉
Im Prinzip ist eine Gruppe aber nichts anderes als eine Menge an Elementen mit einer Verknüpfung. Beispiel: $\mathbb{Z}$ (Menge an ganzen Zahlen) mit $+$ (Addition) bildet eine Gruppe. Darüber hinaus gelten verschiedene Axiome, die man aber nachlesen kann 😉

Schlüsselerzeugung

Für die RSA Verschlüsselung benötigen wir zunächst den öffentlichen und den privaten Schlüssel (da die RSA Verschlüsselung ein asymmetrisches Verfahren ist). Den groben Nutzen und die Verwendung dieser beiden Schlüssel habe ich ein der allgemeinen Erklärung beschrieben.

Schritt 1: Primzahlen finden

Zunächst wählt man zwei ungleiche Primzahlen. Je nach Bit-Länge der (üblich sind derzeit 1024 oder 2048 Bit) Zahlen sind diese mehrere hundert Dezimalstellen lang. Die beiden werden meistens $p$ und $q$ genannt und es muss eben $p\neq q$ gelten.

Schritt 2: RSA-Modul berechnen

Danach wird das RSA-Modul (zum Begriff Modul s.o.) berechnet. Wir nennen es $N$ und es wird mittels $N=p\cdot q$ berechnet. Ver- und Entschlüsselte Nachrichten werden stets $\text{mod }N$ betrachtet.

Warum muss $N=p\cdot q$ sein?
Um eine RSA Verschlüsselung zu knacken müsste man aus dem $N$ die Primfaktoren $p$ und $q$ finden, welche man für Ver- und Entschlüsselung benötigt. Wer das Wort Primfaktoren hört wird auch schnell an Primfaktorzerlegung denken und genau das müsste man machen. Um eine Nachricht entschlüsseln zu können müsste man $N$ in seine beiden Primfaktoren zerlegen, was durch die Größe von $N$ jedoch nicht in brauchbarer Zeit machbar ist.

Schritt 3: Die phi-Funktion und der Verschlüsselungsexponent

Danach kommt die erwähnte phi-Funktion. Wir benötigen $\varphi(N)$ wobei $\varphi(N)=\varphi(p\cdot q)$ gilt, was sich leicht berechnen lässt: $\varphi(p\cdot q)=(p-1)\cdot(q-1)$ .

Wenn man den Wert von $\varphi(N)$ bestimmt hat, sucht man sich eine Zahl $e$ mit $1<e<\varphi(N)$ für die gilt, dass sie teilerfremd zu $\varphi(N)$ ist. Diese Zahl wird auch Verschlüsselungsexponent genannt, denn man braucht sie zum Verschlüsseln.

Warum muss $1<e<\varphi(N)$ gelten und warum müssen $e$ und $\varphi(N)$ teilerfremd sein?
Man sollte meinen, dass es mehr Sinn macht, wenn man statt $\varphi(N)$ direkt $N$ betrachtet, aber dem ist nicht so. Grund dafür ist der Satz von Euler-Fermat, der besagt, dass $e^{\varphi(N)}\equiv 1\text{ mod }N$ gilt. Dieser Satz ist sehr wichtig, da er der Grundstein für das erfolgreiche entschlüsseln ist. Warum diese Kongruenzbedingung bei den Schlüsselexponenten gelten muss wird beim entschlüsseln klar (weiter unten gibt es eine kleine Erklärung zu dem Satz von Euler-Fermat).

Schritt 4: Der Entschlüsselungsexponent

Nun kommt das multiplikative Inverse zum Einsatz, denn damit finden wir den Entschlüsselungsexponenten $d$ , er ist das multiplikative Inverse zum Verschlüsselungsexponenten bezüglich $\varphi(N)$ .

Es gibt verschiedene Verfahren das multiplikative Inverse zu finden, aber am einfachsten ist das Verfahren über den Euklid Algorithmus für den größten gemeinsamen Teiler (bereits oben beschrieben).

Die Schlüssel

Bisher haben wir nur die Schlüsselexponenten berechnet, doch der eigentliche öffentliche und private Schlüssel enthält zusätzlich noch den RSA-Modul, damit man beim ver-/entschlüsseln weiß in welche Restklasse man sich befindet.

Die eigentlichen Schlüssel sind Tupel aus dem Exponenten und dem RSA-Modul, sprich $(e,N)$ (öffentlichen Schlüssel) und $(d,N)$ (privaten Schlüssel).

Wer die Sachen mit Restklassen und multiplikativen Inversen verstanden hat, der weiß auch warum $(e,N)$ als privater und $(d,N)$ als öffentlicher Schlüssel (also öffentlichen und privaten Schlüssel vertauscht) genauso gut funktioniert und kein Sicherheitsrisiko für die RSA Verschlüsselung birgt.

Die Primzahlen $p$ und $q$ , sowie der Wert $\varphi(N)$ werden nun nicht mehr benötigt und können (bzw. sollten) gelöscht werden.

Ver- und Entschlüsseln einer Nachricht

Vorbereitung: Nachricht codieren

Zunächst muss man die zu verschlüsselnde Nachricht in eine Zahl codieren. Der ASCII, bzw. mittlerweile der UTF-Standard, hilft da ungemein. Man kann nun also eine Nachricht in eine Zahl umwandeln.

Formal muss jedoch für die Nachricht $m$ folgendes gelten: $m<N$ . Simpel, aber sonst geht durch die Modulo Funktion eine Menge Information verloren. Gilt diese Eigenschaft nicht mehr, so muss man die Nachricht aufteilen und mehrere Blöcke verschlüsseln.

Verschlüsseln

Nun geht es an das eigentliche verschlüsseln.

Wir haben also eine Nachricht $m$ , die als Zahl codiert wurde, mit $0\leq m<N$ und den öffentlichen Schlüssel $(e,N)$ .

Nun können wir verschlüsseln. Dabei rechnen wir einfach $m^e$ in der Restklasse Modulo $N$ , sprich die Restklasse $[m^e]_N$ . Man nimmt nun den Repräsentanten als verschlüsselte Nachricht und verschickt diesen.

Entschlüsseln

Das entschlüsseln geht denkbar einfach: Man rechnet $(m^e)^d$ innerhalb der Restklasse Modulo $N$ , also $[(m^e)^d]_N$ , und der Repräsentant dieser Restklasse ist dann die entschlüsselte Nachricht.

Das funktioniert, da $e$ und $d$ eben multiplikativ invers sind. Genauer gesagt wegen dem Satz von Euler-Fermat, der besagt, dass $e^{\varphi(N)}\equiv 1\text{ mod }N$ gilt.
Man kann das auch einfach herausfinden. Zunächst gibt es ein $k\in\mathbb{Z}$ , sodass $e\cdot d=k\cdot\varphi(N)+1$ gilt. Da $e\cdot d\equiv 1(\text{mod } \varphi(N))$ gilt findet man das $k$ auch tatsächlich. Außerdem gilt durch Potenzgesetze $(m^e)^d\equiv m^{e\cdot d}$ und man etwas umformen:

$\begin{align*} (m^e)^d&\equiv m^{e\cdot d}\\ &\equiv m^{k\cdot\varphi(N)+1}\\ &\equiv (m^{\varphi(N)})^k+m\\ &\equiv 1^k+m\tag{Infos siehe unten}\\ &\equiv m~\text{mod }N \end{align*}$

Hier noch eine Erklärung zum Schritt $(m^{\varphi(N)})^k+m\equiv 1^k+m$ . Man kann den Beweis aufteilen in insgesamt drei Fälle, aber bei allen Fällen kommt es darauf hinaus, dass $m^{\varphi{N}}=1^k$ ist (was man auch noch beweisen kann, aber nun gut).
Den ausführlichen Beweis findet man hier in Kapitel 3.2.

Beispiele

Da in den beiden Beispielen sehr große Zwischenergebnisse vorkommen, kann man entweder zu Algebra-Software greifen oder online Angebote wie WolframAlpha nutzen. Für reale Szenarien mit RSA Verschlüsselung gibt es natürlich Verfahren wie man dennoch mit so großen Zahlen gut rechnen kann.

Kleines Beispiel

Wir möchten nun eine kleine Nachricht verschlüsslen. Sagen wir den Buchstaben C, welcher den ASCII Code 67 hat. Gegeben ist also schon mal $m=67$ . Wir brauchen nun zwei Primzahlen, die groß genug sind. Sagen wir $p=13$ und $q=31$ . Dadurch ist $N=p\cdot q=13\cdot 37=481$ und $\varphi(N)=\varphi(481)=432$ .

Hier noch mal die gegebenen Zahlen:

$\begin{align*} m&=67\\ p&=13\\ q&=37\\ N&=481\\ \varphi(N)&=432 \end{align*}$

Schlüssel generieren

Wir brauchen zunächst die teilerfemde Zahl $e$ mit $1<e<432$ . Sagen wir $e=175$ . Der öffentliche Schlüssel ist also $(175, 481)$ .

Das multiplikative Inverse von 175 Modulo 432 ist 79. Dadurch ist der private Schlüssel $(79, 481)$ .

Verschlüsseln

Jetzt erhalten wir als Sender den öffentlichen Schlüssel $(175,481)$ und verschlüsseln damit unsere Nachricht.

Einfach $[m^e]_N$ rechnen, sprich $[67^{175}]_{481}=[36~567 \dots 443]_{481}=115$ . Die verschlüsselte Nachticht lautet also 115, was als ASCII Buchstabe ein s wäre.

Entschlüsseln

Als Empfänger mit dem privaten Schlüssel $(79,481)$ können wir nun $[(m^e)^d]_N$ rechnen (wobei $m^e$ natürlich unsere 115 ist), also $[115^{79}]_{481}=[6~239 \dots 875]_{481}=67$ . Die Nachricht lautet also 67 und wenn wir uns an den Anfang dieses Beispiels erinnern stimmt das auch.

Großes Beispiel

Meistens möchte man aber größere Nachrichten als einen Buchstaben verschlüsslen. Da die Zahlen dann sehr sehr groß werden, wir aber hier im Beispiel nicht mit gigantischen Zahlen hantieren möchten, kann man die Nachricht in Blöcke unterteilen und dann verschlüsseln. Ich werde hier jeden Buchstaben als Block ansehen und die Rechenschritte etwas verkürzen.

Als Nachricht nehmen wir curi0sity und als Schlüssel die aus dem kleinen Beispiel von oben. Also öffentlicher Schlüssel $(175,481)$ und privater Schlüssel $(79,481)$ . Die Nachricht codieren wir Buchstabenweise in Zahlen nach dem ASCII-Standard, sprich

$\begin{alignat*}{3} \texttt{c } & m_0&=99\\ \texttt{u } & m_1&=117\\ \texttt{r } & m_2&=114\\ \texttt{i } & m_3&=105\\ \texttt{0 } & m_4&=48\\ \texttt{s } & m_5&=115\\ \texttt{i } & m_6&=105\\ \texttt{t } & m_7&=116\\ \texttt{y } & m_8&=121 \end{alignat*}$

Verschlüsseln

Als Sender rechnen wir für jeden Nachrichtenteil $m_i$ ganz normal $[m_i^e]_N$ .

$\begin{align*} [99^{175}]_{481}&=317\\ [117^{175}]_{481}&=364\\ [114^{175}]_{481}&=400\\ [105^{175}]_{481}&=339\\ [48^{175}]_{481}&=48\\ [115^{175}]_{481}&=262\\ [105^{175}]_{481}&=339\\ [116^{175}]_{481}&=246\\ [121^{175}]_{481}&=121 \end{align*}$

Das 48 und 121 genau sich selbst als Ergebnis haben ist hier tatsächlich Zufall. Auch kann man bei Buchstabenweiser Verschlüsselung natürlich herausfinden welche Buchstaben an welchen Positionen vermutlich identisch sind. Man würde bei realer Verschlüsselung größere Blöcke nehmen.

Als ASCII String wäre aus curi0sity der String ĽŬƐœ0Ćœöy geworden. Meistens macht man jedoch eine Base64-Codierung darauf woraus dann xL3FrMaQxZMwxIbFk8O2eQ== wird. Das kann man dann leichter als E-Mail versenden.

Entschlüsseln

Als Empfänger der verschlüsselten Nachricht (ggf. convertiert man die Base64-Codierung vorher zurück) rechnen wir einfach $[(m_i^e)^d]_N$ , was mit dem privaten Schlüssel $(79,481)$ wie folgt aussieht:

$\begin{align*} [317^{79}]_{481}&=99\\ [364^{79}]_{481}&=117\\ [400^{79}]_{481}&=114\\ [339^{79}]_{481}&=105\\ [48^{79}]_{481}&=48\\ [262^{79}]_{481}&=115\\ [339^{79}]_{481}&=105\\ [246^{79}]_{481}&=116\\ [121^{79}]_{481}&=121 \end{align*}$

Damit hat man die originale Nachricht curi0sity wieder zurück.