Der RSA-Algorithmus – Florian Buchner

RSA gilt als das erste asymmetrische Verschlüsselungsverfahren. Es wurde von Ronald Rivest, Adi Shamir und Leonard Adleman entwickelt. Alle drei arbeiteten damals im MIT-Labor für Computerwissenschaften und wurden durch einen Artikel von Withfield Diffie und Martin Hellman auf das Problem der asymmetrischen Verschlüsselung aufmerksam gemacht. Im Prinzip geht es dabei darum eine Funktion zu finden, die nur in eine Richtung berechnet werden kann. Bei so einer Funktion ist es einfach aus einer gegebenen Zahl ein Ergebnis zu berechnen. Aus dem Ergebnis wieder die anfängliche Zahl zu berechnen ist dagegen nur mit erheblichem Aufwand möglich.

Die Lösung für das Problem sind Primzahlen. Primzahlen sind Zahlen, die nur durch 1 oder sich selber Teilbar sind. Beispielsweise sind 7 oder 19 Primzahlen. Es ist einfach das Produkt aus 7 und 19 zu berechnen. Aus 133 allerdings wieder beide Primzahlen zu erhalten ist bedeutend schwerer. Hierfür muss man von Anfang an alle Primzahlen durchprobieren. Mann beginnt also mit 2, 3,… und teilt die 133 so lange bis eine Zahl ohne Rest heraus kommt. Eine Zahl die das Produkt aus 2 Primzahlen ist kann NUR durch diese beiden Zahlen geteilt werden. Das ist das schöne an Primzahlen. Es gibt kein anderes Produkt aus zwei Zahlen die 133 ergeben als das Produkt von 7 und 19.

Für den weiteren Teil bezeichnen wir die beiden Primzahlen mit $p$ und $q$ . Das Produkt beider Zahlen als $n$ .

(1) $\begin{gather*} n = p \cdot q \end{gather*}$

Wie findet man nun Primzahlen? Eine Primzahl ist ja, wie bereits erwähnt, durch keine andere Zahl als sich selber zu teilen. Eine Möglichkeit Primzahlen zu finden ist es daher alle bekannten Primzahlen $S$ miteinander zu Multiplizieren. Das Ergebnis daraus addiert man mit 1. Der dadurch entstandene Wert ist eine neue Primzahl $P$ .

(2) $\begin{gather*} S = {P1, P2,..., Pn} \\ P = (P1 \cdot P2 \cdot ... \cdot Pn) + 1 \end{gather*}$

Nehmen wir also an wir kennen alle Primzahlen bis 7. Das sind 2, 3, 5 und 7. Das Produkt aller Zahlen + 1 ist demnach:

$(2 \cdot 3 \cdot 5 \cdot 7)+1 = 211$

Tatsächlich ist 211 eine Primzahl. Es gibt jedoch noch jede Menge Primzahlen die zwischen 7 und 211 liegen. Um mit dieser Methode jedoch weiter machen zu können brauchen wir bekanntlich alle Zahlen bis 211. Das ganze ist also nicht sehr effektiv. Letztendlich bleibt uns nichts weiteres übrig als alle Zahlen selber durchzuprobieren. Genau aus diesem Grund sind Primzahlen in der Kryptographie auch so beliebt.

Als Übung kann man einmal selbst ausprobieren alle Primzahlen von 0-100 zu finden. Am besten werden hierfür alle Zahlen auf ein Blatt Papier geschrieben. Wenn man nun eine Primzahl gefunden hat kann man diese markieren. Es können zudem alle vielfachen der Primzahl durchgestrichen werden, da diese ja durch die Primzahl teilbar sind und daher keine Primzahlen mehr seien können. Beispielsweise ist 3 eine Primzahl. 6, 9, 12, … können demnach keine Primzahlen mehr sein. Die nächste nicht markierte Zahl ist dann die nächste Primzahl.

Alle Primzahlen bis 100 lauten: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

Ein beliebtes Werkzeug der Kryptographie ist der Modulo. Der Modulo ist der Rest einer Division. Beispielsweise ist der Modulo von 5 und 3 = 2, da 5/3 = 1 Rest 2. Der Modulo $b$ aus $a$ und $n$ kann als $a \: mod \: n = b$ geschrieben werden.

(3) $\begin{gather*} 41 \: mod \: 7 = 6 \\ 21 \: mod \: 2 = 1 \\ 87 \: mod \: 9 = 6 \end{gather*}$

Als nächstes muss der Begriff der Kongruenz geklärt werden. Die Kongruenz ist eine Beziehung zwischen drei Zahlen. Man nennt zwei Zahlen kongruent bezüglich der dritten zahl, wenn diese bei einer Division durch die dritte Zahl (den Modul) den gleichen Rest haben. Beispielsweise sind 5 und 11 kongruent bezüglich 3, da 5/3 = 1 Rest 2 und 11/3 = 3 Rest 2. Beide Zahlen haben den gleichen Rest. Um die Kongruenz zwischen a und b bezüglich n darzustellen schreibt man $a \equiv b (mod \: n)$

(4) $\begin{gather*} 13 \equiv 5 (mod \: 8) \\ 5 \equiv 26 (mod \: 7) \end{gather*}$

Um diesen Sachverhalt bei zwei Zahlen schnell feststellen zu können berechnet man zuerst $a-b$ . Das Ergebnis muss sich nun ohne Rest durch $n$ Teilen lassen. $a$ und $b$ sind also kongruent, wenn

(5) $\begin{gather*} (a-b)mod \: n = 0 \end{gather*}$

Das letzte Konzept das wir brauchen ist der größte gemeinsame Teiler, kurz $ggT$ . Der $ggT$ beschreibt, wie der Name schon sagt, die größte natürliche Zahl, durch die zwei verschiedene Zahlen geteilt werden können, ohne das ein Rest entsteht. Die 12 kann beispielsweise durch 1, 2, 3, 4, 6 und 12 geteilt werden. Die 18 kann ducht 1, 2, 3, 6, 9 und 18 geteilt werden. Der größter gemeinsame Teiler von 12 und 18 ist 6.

(6) $\begin{gather*} ggT(12,18)=6 \end{gather*}$

Es gilt zudem:

(7) $\begin{gather*} ggT(a, b) = ggT(a \: mod \: b, b) \end{gather*}$

Nun geht es ans Eingemachte. Wie bereits erwähnt funktioniert RSA mit zwei Schlüsseln. Einem privaten und einem öffentlichen. Mit beiden Schlüsseln können Nachrichten verschlüsselt werden. Entschlüsseln kann man die Nachrichten jedoch nur mit dem Gegenstück.

Angenommen jemand möchte uns eine verschlüsselte Nachricht $m$ schicken, dann nimmt er den öffentlichen Schlüssel $E_B$ und verschlüsselt damit die Nachricht $E_B(m)$ . Der öffentliche Schlüssel ist dabei für jeden verfügbar. Um die Nachricht wieder zu entschlüsseln benutzen wir nun unseren privaten Schlüssel $D_B$ und wenden ihn auf die verschlüsselte Nachricht $E_B(m)$ an und erhalten dadurch wieder unsere Nachricht.

(8) $\begin{gather*} D_B(E_B(m)) = m \end{gather*}$

Das ganze funktioniert auch in die andere Richtung. Beispielsweise möchte nun jemand von uns Wissen, ob wir wirklich derjenige sind, der wir vorgeben zu sein. In diesem Fall gibt er uns eine Nachricht die wir mit unserem privaten Schlüssel verschlüsseln sollen. Da nur wir den privaten Schlüssel haben kann das niemand anderes sonst tun. Entschlüsselt wird die Nachricht in diesem Fall mit dem öffentlichen Schlüssel. Die von uns verschlüsselte Nachricht kann von jedem entschlüsselt werden, da der öffentliche Schlüssel für jeden zugänglich ist. Es geht dabei also nicht darum eine Nachricht zu entschlüsseln, sondern vielmehr darum zu beweisen, dass man selbst im Besitz des privaten Schlüssels ist.

Um einen privaten und öffentlichen Schlüssel zu generieren sind 5 einfache Schritte notwendig.

Finde zwei Primzahlen $p$ und $q$
Berechne das Produkt $n = p \cdot q$
Berechne $\Phi (n) = (p-1)(q-1)$
Finde eine Zahl $e$ welche Teilerfremd zu $\Phi (n)$ ist. Es gilt also $ggT(e, \Phi (n)) = 1$
Finde eine Zahl $d$ für die gilt, dass $ed \equiv 1 (mod \: \Phi (n))$

Das war es auch schon. Der private Schlüssel ist $d$ , während $e$ und $n$ zusammen den öffentliche Schlüssel darstellen. Gerade die Schritte 4 und 5 sehen schwieriger zu berechnen aus als sie sind. Wir kommen später in einem Beispiel darauf zurück. Die beiden Primzahlen $p$ und $q$ können nun ohne Bedenken verworfen werden. Zum ver- und entschlüsseln der Nachricht werden diese nicht mehr gebraucht, sie sind jedoch ein großes Sicherheitsrisiko wenn sie bekannt werden.

Um einen Buchstaben $m_k$ der Nachricht $m$ mit dem öffentlichen Schlüssel $n$ und $e$ zu verschlüsseln wird folgende Formel benutzt:

(9) $\begin{gather*} M_k = m_k e \: mod \: n \end{gather*}$

Dabei ist $M_k$ das verschlüsselte Ergebnis and Position $k$ . Um das ganze nun wieder in den ursprünglichen Buchstaben $m_k$ zu entschlüsseln benötigen wir den privaten Schlüssel $d$ und den Modul $n$ .

(10) $\begin{gather*} m_k = M_K y \: mod \: n \end{gather*}$

Am besten machen wir das ganze einmal mit einem Beispiel. Zuerst brauchen wir also zwei Primzahlen. In unserem Beispiel nehmen wir 5 und 13. Aus beiden Zahlen bilden wir den Modul $n$ .

(11) $\begin{gather*} n = 5 \cdot 13 = 65 \end{gather*}$

Jetzt müssen wir $\Phi (n)$ berechnen. Hierführ setzen wir unsere Zahlen in die Formel ein.

(12) $\begin{gather*} \Phi (n) = (p-1)(q-1) \\ \Phi (n) = (5-1)(13-1) \\ \Phi (n) = 48 \end{gather*}$

Jetzt muss der Exponent $e$ gefunden werden. Dieser muss Teilerfremd zu $\Phi (n)$ sein. Wir benötigen also eine Zahl, durch welche sich 48 nicht ohne Rest teilen lässt. Ist die gesuchte Zahl gerade, so kann eine ungerade Zahl verwendet werden und umgekehrt. Wir benutzen in diesem Beispiel die Zahl 5. Damit haben wir schon einmal alles was wir brauchen um eine Nachricht zu verschlüsseln. Wir möchten jetzt die Nachricht „HALLO WELT“ verschlüsseln. Hiefür wandeln wir die Buchstaben in Zahlen um. Das geschieht am besten nach dem ABC. Also ist A=1, B=2,… Das Leerzeichen ist in diesem Fall 28.

H = 08
A = 01
L = 12
L = 12
O = 15
_ = 28
W = 23
E = 05
L = 12
T = 20

Die Nachricht 08 01 12 12 15 28 23 05 12 20 kann Anschließend mit dem Exponenten $e$ = 5 und dem Modul $n$ = 65 verschlüsselt werden.

(13) $\begin{gather*} m_k^e \: mod \: n = M_K \end{gather*}$

(14) $\begin{gather*} 8^5 \: mod \: 65 = 8 \\ 1^5 \: mod \: 65 = 1 \\ 12^5 \: mod \: 65 = 12 \\ 12^5 \: mod \: 65 = 12 \\ 15^5 \: mod \: 65 = 45 \\ 28^5 \: mod \: 65 = 58 \\ 23^5 \: mod \: 65 = 43 \\ 5^5 \: mod \: 65 = 5 \\ 12^5 \: mod \: 65 = 12 \\ 20^5 \: mod \: 65 = 50 \\ \end{gather*}$

Unsere verschlüsselte Nachricht lautet nun 08 01 12 12 45 58 43 05 12 50. Ich habe hiefür einen Taschenrechner benutzt. Es gibt aber auch einen Trick um den Modul auf dem Papier zu berechnen.

(15) $\begin{gather*} c^{a+b} = c^a \cdot c^b \end{gather*}$

Zudem gilt.

(16) $\begin{gather*} ab \: mod \: c = ((a \: mod \: c)(b \: mod \: c)) \: mod \: b \end{gather*}$

und

(17) $\begin{gather*} (a + b) \: mod \: c = ((a \: mod \: c) + (b \: mod \: c)) \: mod \: b \end{gather*}$

Diese Rechenregel kann man auch auf unsere Rechnung übertragen. Das ganze einmal an einem Beispiel verdeutlicht.

(18) $\begin{gather*} 15^5 \: mod \: 65 \\ \Leftrightarrow (15^1 \cdot 15^2 \cdot 15^2) \: mod 65 \\ \Leftrightarrow ((15^1 \: mod \: 65)(15^2 \: mod \: 65)(15^2 \: mod \: 65)) \: mod 65 \\ \Leftrightarrow ((15 \: mod \: 65)(225 \: mod \: 65)(225 \: mod \: 65)) \: mod 65 \\ \Leftrightarrow ((15)(30)(30)) \: mod 65 \\ \Leftrightarrow 759375 \: mod \: 65 \\ \Leftrightarrow (37875 + 6500 + 65000 + 650000) \: mod \: 65 \\ \Leftrightarrow (37875 \: mod \: 65 + 0 + 0 + 0) \: mod \: 65 \\ \Leftrightarrow 45 \end{gather*}$

Jedem, der schon einmal etwas mit Kryptographie zu tun hatte sollte hierbei sofort etwas auffallen: Falls wir wirklich so verschlüsseln wollen wäre das schlecht. Der gleiche Buchstabe erhält immer die gleiche verschlüsselte Zahl. Anhand der Häufigkeitsanalyse könnte auf diese Art sehr schnell die Nachricht entschlüsselt werden. In diesem Beispiel ist es sogar so, dass nur drei Buchstaben durch die Verschlüsselung überhaupt geändert haben. Man kann hier kaum von einer vernünftigen Verschlüsselung sprechen. Aus diesem Grund werden mehrere Buchstaben zu einem Block zusammengefasst. Beispielsweise wird aus 02 und 05, 0205 gemacht. Dieser gesamte Block wird anschließend verschlüsselt. Ist für den letzten Buchstaben kein zweiter Buchstabe vorhanden, so wird der Rest mit 00 aufgefüllt. Zudem sollte der Modul $n$ möglichst groß sein. Um dieses Beispiel jedoch einfach zu halten habe ich den Modul möglichst klein gehalten. Der Modul muss jedoch immer größer sein, als der zu verschlüsselnde Block. Wäre dies nicht der Fall, könnte keine Eindeutigkeit mehr bei der Entschlüsselung hergestellt werden.

Das ganze können wir nun mit dem privaten Schlüssel $d$ wieder entschlüsseln. Diesen müssen wir zunächst jedoch Berechnen. Um den privaten Schlüssel zu erhalten benötigen wir eine Zahl $d$ für die gilt, dass

(19) $\begin{gather*} ed \equiv 1 (mod \: \Phi(n)) \end{gather*}$

Wenn wir unsere Zahlen einsetzen erhalten wir: $5d \equiv 1 (mod \: 48)$ . Das heist also, dass $5d-1$ ein vielfaches von 48 sein muss. Das ganze lässt sich auf verschiedene Arten durchprobieren. Ich stelle hierfür die Formel um und sage: $5d = (k \cdot 48)+1$ . Die Zahl $k$ ist dabei beliebig und muss immer weiter erhöht werden, bis man eine Zahl gefunden hat, die sich durch 5 Teilen lässt. In unserem Fall ist $k = 3$ . Dann ist $5d = 145$ und damit ist $d = 29$ . Mehr brauchen wir nicht um die Nachricht wieder zu entschlüsseln. Um in etwa die Möglichen Zahlen einschätzen zu können muss man nur $\Phi(n) \cdot k$ durch $e$ Teilen. In unserem Beispiel erhält man für $k=1,2,3 und 4$ die Zahlen 9.6, 19.2, 28,2 und 38,4. Mit 28,2 lagen wir dabei schon sehr nahe an der 29.

(20) $\begin{gather*} m_k = M_k d \: mod \: n \end{gather*}$

Die Nachricht können wir nun ganz einfach Entschlüsseln.

(21) $\begin{gather*} 8^29 \: mod \: 65 = 8 \\ 1^29 \: mod \: 65 = 1 \\ 12^29 \: mod \: 65 = 12 \\ 12^29 \: mod \: 65 = 12 \\ 45^29 \: mod \: 65 = 15 \\ 58^29 \: mod \: 65 = 28 \\ 43^29 \: mod \: 65 = 23 \\ 5^29 \: mod \: 65 = 5 \\ 12^29 \: mod \: 65 = 12 \\ 50^29 \: mod \: 65 = 20 \\ \end{gather*}$

Was brauchen wir nun, wenn wir den privaten Schlüssel $d$ nicht haben und trotzdem die Nachricht entschlüsseln wollen? Um $d$ zu berechnen benötigen wir die beiden Primzahlen $p$ und $q$ . Diese sollten jedoch streng geheim sein. Es bleibt uns also nichts anderes übrig als diese selbst zu berechnen. Beide Zahlen sind in dem Modul $n$ enthalten. Aus diesem Grund sollte der Modul auch möglichst groß gewählt werden.

Die Folgende Nachricht ist mit dem öffentlichen Schlüssel $n = 2813$ und $e = 5$ verschlüsselt worden. Den privaten Schlüssel daraus zu berechnen und die Nachricht zu entschlüsseln überlasse ich dem Leser.

2469 0599 0697 0548 2107 1928