Wie funktioniert die heutzutage weitverbreitete asymmetrische Verschlüsselung? Dieser Artikel soll einen mathematischen Erklärungsansatz am Beispiel des RSA-Verschlüsselungssystems liefern.
Der Begriff Kryptographie umfasst heutzutage mehrere Themengebiete, wie z.B. die Informationssicherheit, Verschlüsselungsverfahren, etc. Belegbare Nutzung von Kryptographie tritt erstmals im dritten Jahrhundert v. Chr. bei den Ägyptern auf. Der Sprachgebrauch „kryptische Zeichen“ lässt sich auch heute noch gut zur Versinnbildlichung als Beispiel benutzen.
Was ist asymmetrische Verschlüsselung?
Bei einem asymmetrischen Verschlüsselungsverfahren erzeugt [latex]XY[/latex] einen privaten (geheimen) Schlüssel [latex]priv\_key[/latex] und einen öffentlichen (nicht geheimen) Schlüssel [latex]pub\_key[/latex]. Der öffentliche Schlüssel ist für jeden frei zugänglich und dient lediglich dem Verschlüsseln einer Nachricht [latex]m[/latex]. Diese verschlüsselte Nachricht [latex]m‘[/latex] kann nun aber nur mithilfe des privaten Schlüssels [latex]XY[/latex] wieder zur ursprünglichen Nachricht m entschlüsselt werden.
Wie funktioniert die asymmetrische Verschlüsselung?
Dazu müssen die Erzeugung der Schlüssel und die zugehörigen Bedingungen genauer betrachtet werden:
Zuerst werden zwei (eigentlich sehr große) Primzahlen, z.B. [latex]p=7[/latex] und [latex]q=17[/latex] benötigt. Damit wird [latex]N=p*q[/latex] berechnet, also in diesem Fall [latex]N=7*17=119[/latex]. Das ist schon fast der öffentliche Schlüssel. Für den zweiten Teil ([latex]e[/latex]) benötigen wir die Eulersche Phi-Funktion [latex]?(N)[/latex], welche die Anzahl an zu [latex]N[/latex] teilerfremden natürlichen Zahlen, die kleiner als [latex]N[/latex] sind, angibt.
Da [latex]N=p*q[/latex] hier das Ergebnis einer Multiplikation zweier Primzahlen ist, gilt [latex]?(N)=(p-1)*(q-1)[/latex] und dazu muss [latex]e[/latex], der zweite Teil des öffentlichen Schlüssels, teilerfremd sein. Wenn [latex]e[/latex] und [latex]?(N)[/latex] teilerfremd sind, bedeutet das, es existiert keine Zahl, welche [latex]e[/latex] oder [latex]?(N)[/latex] teilt (außer die [latex]1[/latex]). Zum Beispiel sind Vier und Fünf teilerfremd, aber Vier und Sechs nicht (die Zwei ist ein gemeinsamer Teiler: [latex]4/2=2={\text{ ganze Zahl }}=3=6/2[/latex]. Teilen meint, das Ergebnis muss eine ganze Zahl(ohne Komma) sein.
Zurück zu unserem Beispiel:
[latex]?(N)=6*16=96[/latex] und z.B. [latex]e=11[/latex] ist teilerfremd zu [latex]?(N)=96[/latex], da [latex]11[/latex] eine Primzahl ist, somit keine „echten Teiler“ (außer die Eins) hat und die [latex]96[/latex] auch nicht teilt. Der öffentliche Schlüssel ist folglich [latex](e,N)=(11,119)[/latex].
Und jetzt?
Möchte man nun [latex]XY[/latex] die Nachricht [latex]DA[/latex] verschlüsselt zu schicken, so muss zuerst die Nachricht [latex]DA[/latex] in ein Zahlenformat kodiert werden. Dazu benutzt man z.B. die einfachste Form [latex]A=1, B=2, C=3, D=…[/latex] (Wichtig: Beide Parteien müssen sich auf eine Kodierung einigen!). Somit muss nun die Nachricht [latex]m=41[/latex] ([latex]DA[/latex]) verschlüsselt werden. Dazu muss [latex]m‘ = (m^e \mod N)[/latex] berechnet werden. [latex]41^{11}[/latex] ergibt 550.329.031.716.248.441 und diese enorm große Zahl (trotz vergleichsweise sehr kleiner Primzahlen und kleinem [latex]e[/latex]), wird nun modulo [latex]119[/latex] gerechnet. Das ergibt [latex]48[/latex]. Modulo ist Teilen mit Rest, z.B errechnet man bei [latex]100 \mod 3[/latex] gerade [latex](99/3=33) {\text{ Rest }} 1[/latex] und damit ist [latex]1[/latex] das Ergebnis von [latex]100 \mod 3[/latex].
Festzuhalten bleibt, die verschlüsselte Nachricht ist [latex]m’=48[/latex].
Aber wer kann diese Nachricht entschlüsseln?
Das Entschlüsseln geht nur mit dem privaten Schlüssel von [latex]XY[/latex]. Dieser besteht zum einen aus [latex]N=p*q[/latex], also [latex]7*17=119[/latex]. Zur Erinnerung, [latex]p[/latex] und [latex]q[/latex] waren die beiden Primzahlen, die zur Erzeugung des öffentlichen Schlüssels benutzt wurden. Der zweite Teil des privaten Schlüssels ([latex]d[/latex]), ist das Inverse von [latex]e[/latex] bezüglich [latex]\mod ?(N)[/latex]. Das heißt, [latex]d[/latex] muss die Gleichung [latex](d*e \mod ?(N))=1[/latex] erfüllen.
In diesem Beispiel [latex](d*11 \mod 96)=1[/latex]. Diese Gleichung ist analog zu [latex]d*11+k*96=1[/latex], welche sich zum Beispiel mit dem erweiterten euklidischen Algorithmus lösen lässt. Dieser berechnet hier [latex]d=35[/latex] und [latex]k=(-4)[/latex]. Somit ist der private Schlüssel [latex](35,119)[/latex].
Nun geht es ans Entschlüsseln!
Die verschlüsselte Nachricht, die [latex]XY[/latex] bekommen hat, lautet [latex]m’=48[/latex]. Die Gleichung für die Entschlüsselung ist [latex]m=((m‘)^d \mod N)[/latex], und [latex]48^{35}[/latex] ergibt:69.733.796.196.349.127.882.498.386.212.799.025.430.591.303.459.053.745.733.632.
Diese riesige Zahl nun [latex]\mod 119[/latex] ist [latex]41[/latex], welches decodiert ([latex]A=1, B=2,…[/latex]) [latex]DA[/latex] ergibt.
taaa[latex]DA[/latex]!
Zusammenfassung
Zuerst wird mithilfe zweier (in der Regel sehr großen) Primzahlen [latex]N=p*q[/latex] und [latex]?(N)=(p-1)*(q-1)[/latex] berechnet. Die Primzahlen [latex]p[/latex] und [latex]q[/latex] werden nun vergessen bzw. weggeworfen und im Grunde beruht die Sicherheit der RSA-Verschlüsselung darauf, dass kein bekanntes Verfahren existiert, das die Zahl [latex]N[/latex] in realer Zeit in seine Primfaktoren [latex]p[/latex] und [latex]q[/latex] zerlegt. Denn nur mit [latex]?(N)=(p-1)*(q-1)[/latex] kann sowohl der öffentliche ([latex]pub\_ key[/latex]), als auch private ([latex]priv\_ key[/latex]) Schlüssel erzeugt bzw. berechnet werden.
Nachdem die Nachricht in ein Zahlenformat kodiert wird, kann die Verschlüsselung der Nachricht durch Potenzieren der kodierten Nachricht mit dem privaten Schlüssel und anschließend modulo [latex]N[/latex] ([latex]m’=(m^e \mod N)[/latex]) berechnet werden. Die verschlüsselte (kryptische) Nachricht [latex]m‘[/latex] kann nur durch Potenzieren mit dem privaten Schlüssel [latex]d [/latex] wieder umgekehrt bzw. entschlüsselt werden ([latex]m=((m‘)^d \mod N)[/latex]).
Schon 1998 stellten Boneh and Venkatesan auf der Eurocrypt-Konferenz Überlegungen vor, dass die Sicherheit von RSA-Verschlüsselung nicht mit dem Faktorisieren der Zahl [latex]N[/latex] in seine Primfaktoren gleichzusetzen sein könnte.
Wer noch tiefer in das Thema eintauchen möchte, dem kann ich das Paper „Another Look at ‚Provable Security‘“ von Neal Koblitz und Alfred J. Menezes sehr empfehlen.
