Rotkäppchen

Rotkäppchen und ihre Großmutter telefonieren, bevor Rotkäppchen in den Wald aufbricht. Die beiden wissen, dass der Wolf schon lange die Leitung im Wald angezapft hat und mithört. Die Großmutter will Rotkäppchen einen Tipp geben, auf welchem Wege sie kommen soll, damit sie dem Wolf nicht über den Weg läuft. Der Wolf darf das natürlich nicht wissen, also muss sie den Tipp verschlüsseln. Sie haben aber vorher keinen Code ausgemacht, was nun?

Sie verwendet das RSA-Verschlüsselungsverfahren (https://de.wikipedia.org/wiki/RSA-Kryptosystem). Dazu teilt Rotkäppchen der Großmutter ihren öffentlichen Schlüssel mit. Die Großmutter verschlüsselt ihre Nachricht mit dem öffentlichen Schlüssel von Rotkäppchen. Rotkäppchen kann mit ihrem privaten Schlüssel die Nachricht entschlüsseln. Der Wolf aber, der alles mitgehört hat, den öffentlichen Schlüssel und die verschlüsselte Nachricht, kann nichts damit anfangen, zumindest wenn Rotkäppchen und die Großmutter sich geschickt anstellen. Das nennt man ein asymmetrisches Verschlüsselungsverfahren. Weil das so sicher und praktisch ist, ist das RSA-Kryptosystem ist auch im Internet sehr weit verbreitet.

RSA-Verschlüsselung

Rotkäppchens öffentlicher Schlüssel besteht aus zwei (ganzen) Zahlen e und N. Großmutters Nachricht besteht aus zweimal einer Zahl, den Koordinaten, über die Rotkäppchen durch den Wald soll, wo übrigens auch unser Final versteckt ist. Sie nehmen, damit es einfacher ist, zwei ganze Zahlen mit je nur den Minuten des Finals N 49° XX.XXX' und E 11° YY.YYY'. Die zu verschlüsselnde Zahl lauten Z1 = XXXXX, also die Minuten mit drei Nachkommastellen ohne den Punkt und Z2 = YYYYY.

Die Großmutter verschlüsselt die Zahlen Z1 und Z2, indem sie jeweils die Zahl genau e-mal (e aus dem öffentlichen Schlüssel von Rotkäppchen) multipliziert. Damit die Zahl nicht zu groß wird, zieht sie immer wieder die Zahl N (auch aus Rotkäppchens öffentlichen Schlüssel) ab, sobald das Ergebnis größer als N wird. In Formlen geschrieben lautet das so, C1 und C2 sind die verschlüsselten Zahlen:

C1 = (Z1)^e mod N
C2 = (Z2)^e mod N

Die Großmutter nennt Rotkäppchen die so verschlüsselten Zahlen C1 und C2.

Entschlüsselung

Rotkäppchen kann mit der gleichen Rechenvorschrift die Nachricht entschlüsseln, sie nimmt jedoch ihren privaten Schlüssel d (N bleibt gleich):

Z1 = (C1)^d mod N
Z2 = (C2)^d mod N

Damit das klappt, steckt einiges an mathematischem Zauber dahinter. Das erreicht Rotkäppchen, indem sie den privaten und den öffentlichen Schlüssel zueinander passend gewählt hat.

Erzeugung der Schlüssel

Rotkäppchen wählt zwei Primzahlen p und q. Daraus ergibt sich das N für die beiden Schlüssel:

N = p*q

Dann berechnet sie die Eulersche phi-Funktion:

phi(N) = (p-1)*(q-1)

Sie wählt jetzt eine zu phi(N) teilerfremde Zahl e, für die gilt 1 < e < phi(N). Sie kann z.B. eine beliebige Zahl wählen und mit dem euklidischen Algorithmius (https://de.wikipedia.org/wiki/Euklidischer_Algorithmus) den größten gemeinsamen Teiler (ggT) der beiden Zahlen bestimmen. Ist der ggT(e,qhi(N))=1, sind die Zahlen teilerfremd. Ansonsten probiert sie eine andere Zahl für e, solange bis sie eine passende gefunden hat. Die Zahlen e und N sind ihr öffentlicher Schlüssel.

Den privaten Schlüssel d berechnet sie über den Erweiterten euklidischen Algorithmus (https://de.wikipedia.org/wiki/Erweiterter_euklidischer_Algorithmus) als multiplikatives Inverses von e modulo phi(N). Das kann sie leicht machen, da sie phi(N) kennt. Der Wolf kennt diese Zahl nicht und kann den privaten Schlüssel deshalb nicht so leicht aus dem öffentlichen Schlüssel berechnen (er kennt N, aber er kann das bei großen Zahlen praktisch nicht in p*q zerlegen, s.u.).

Anwendung in der Praxis und Grenzen

Um es einfach zu machen, hat Rotkäppchen recht kleine Zahl für p und q gewählt. Die Zahlen, die die Großmutter damit verschlüsseln kann, müssen kleiner als N sein. Da der Wolf mit dem öffentlichen Schlüssel auch Nachrichten verschlüsseln kann, kann er den Code also knacken wie im Mystery Wurzeln (https://www.opencaching.de/viewcache.php?wp=OC17D6E). Zur Berechnung kann er ein kleines Programm z.B. unter folgender Webseite eingeben und laufen lassen: https://www.onlinegdb.com/. Die größtmögliche Zahl, die auch als Zwischenergebnis auftreten kann, ist offensichtlich (N-1)*(N-1), also etwa 1,4 Millionen. Er muss aufpassen, dass das verwendete Computerprogramm mit so großen Zahlen umgehen kann.

In Realität muss N eine sehr große Zahl sein. Zahlen mit ca. 300 Stellen sind im Moment üblich, um diese Möglichkeit des Rückrechnens zu verhindern. Dann müssen auch e und d größer sein als im Beispiel.

Und schließlich kann man beim Verschlüsseln von Texten auch raten, welcher Text verschlüsselt worden ist und ausprobieren, ob man richtig lag (wie gesagt, mit dem öffentlichen Schlüssel kann ja jeder verschlüsseln). In Realität verschlüsselt man mit dem RSA-Verfahrne lieber nicht die eigentliche Nachricht, sondern verwendet das Verfahren "nur", um die Schlüssel für andere Verfahren auszutauschen, die robust gegen solche Angriffe sind. Das ist aber ein sehr wichtiger Schritt und daher ist RSA im Internet genau dafür weit verbreitet. Alle Seiten, die mit https: statt mit http: anfangen, nutzen dieses Verfahren.

Rotkäppchen und die Großmutter

Rotkäppchen nennt ihren öffentlichen Schlüssel d=6353 und N=38191.

Die Großmutter nennt die verschlüsselten Koordinaten C1=9636 und C2=4630. Die entschlüsselten Koordinaten ergeben dann den Final N 49° XX.XXX' und E 11° YY.YYY'.