Question

Asymmetrische Verschlüsselung /  RSA-Verfahren

Das Prinzip der asymmetrischen Verschlüsselung beruht darauf, dass zwei Kommunikationspartner jeweils ein Schlüsselpaar, bestehend aus einem privaten Schlüssel (dieser wird geheim gehalten) und einem öffentlichem Schlüssel (dieser ist jedem zugänglich), besitzen.

Um es einfacher zu machen, nehmen wir an, dass der öffentliche Schlüssel ein Schloss ist, welches nur von einem Schlüssel, dem privaten Schlüssel, geöffnet werden kann.

Nehmen wir an Person A möchte nun Person B eine Nachricht schicken, die kein anderer lesen soll. Dafür stellt Person B nun Person A einen öffentlichen Schlüssel zur Verfügung, also ein Schloss, welches nur Person B wieder öffnen kann. Person A schreibt nun eine Nachricht und steckt den Brief beispielsweise in eine Kiste und verschließt sie mit dem Schloss von Person B. Nun kann keiner außer Person B diese Kiste öffnen, da nur sie den Schlüssel für die Kiste besitzt und die Nachricht kann sicher gelesen werden.

In der heutigen Praxis sieht das ganze natürlich etwas anders aus. Die RSA-Verschlüsselung ist eine Verschlüsselungsart, die heute sehr häufig genutzt wird. Hierbei wird eine sogenannte Einweg-Funktion verwendet. Diese wird oft mit einer „mathematischen Einbahnstraße“ beschrieben. Dabei ist die Berechnung in die eine Richtung (Verschlüsselung) sehr einfach, doch der Rückweg (Entschlüsselung ohne Schlüssel) ist sehr schwierig. So eine Einweg-Funktion kann man sehr gut mit der Multiplikation von Primzahlen beschreiben.

3259 * 5431 = 17699629

Diese Rechnung war nicht schwer zu lösen. Es wurden zwei beliebige Primzahlen miteinander multipliziert. Dies war der Weg in die einfache Richtung. Würde man diese Rechnung jetzt aber rückwärts lösen wollen, also alle Teiler der Zahl 17.699.629 suchen, würde man schon deutlich länger an dem Problem sitzen. Außerdem gibt es für das Zerlegen einer Zahl in seine Primfaktoren keinen bekannten Algorithmus, oder andere Methoden. Ein Computerprogramm kann aber solche Rechnungen für uns durchführen, doch geht dies nur, wenn die Zahlen nicht zu groß sind. Heutzutage benutzt man mindesten 150-stellige Primzahlen zur Verschlüsselung, wofür ein Computer sehr, sehr viel Zeit benötigt. Falls es einmal schnellere Computer geben sollte, muss man einfach nur die Anzahl der Ziffern der Primzahl erhöhen.

Jetzt stellt sich aber die Frage, wie dadurch denn eine Kommunikation entstehen kann, wenn die Entschlüsselung doch so lange dauert. Die RSA-Verschlüsselung arbeitet mit diesen „Falltürfunktionen“ und ermöglicht es, auch den Rückweg einfach zu berechnen, aber nur für den Kommunikationspartner.

Wie dieses Verfahren funktioniert wird nun mit kleinen Primzahlen und einer sehr kurzen Nachricht, die aus einem Zeichen besteht, erklärt.

Hierfür muss man die Verwendung von Modulo nachvollziehen können. Zur Erinnerung einige Beispiele:

20 ÷ 6 = 3, mit Rest 2,       20 mod 6 = 2

43 ÷ 5 = 8, mit Rest 3,       43 mod 5 = 3

Person B erzeugt zunächst seinen privaten Schlüssel, also den, den nur er kennt:

Dazu wählt er zwei beliebige Primzahlen, z.B. p = 17 und q = 11. Nun muss noch eine Zahl e gewählt werden. Dabei sollte e von  ((p - 1) * (q - 1))  teilerfremd sein. Wir wählen wir für e = 7.

Den privaten Schlüssel d berechnet man nun mit folgender Formel:

1 = (e * d) mod ((p - 1) * (q - 1))

Die Werte können nun eingesetzt werden.

1 = (7 * d) mod ((17 - 1) * (11 - 1))

1 = (7 * d) mod 160

Aus der Gleichung ergibt sich für d = 23. Denn (7 * 23) mod 160 =  161 mod 160  = 1

Diese Zahl kennt nur Person B. Jetzt wird der öffentliche Schlüssel erzeugt, der jedem zugänglich ist. Dieser besteht aus zwei Zahlen. Die erste Zahl ist e = 7 vom privaten Schlüssel.

Die Zweite Zahl ergibt sich aus dem Produkt von p und q, also N = 17 * 11 = 187.

Diese Zahlen e und N sind der öffentliche Schlüssel. Person B hat nun alle Vorbereitungen getätigt und kann eine Nachricht von Person A erhalten. Jetzt wird die zu verschlüsselnde Nachricht von Person A in eine Zahl M umgewandelt. Als Beispiel nehmen wir hier den sogenannten Klartext „X“ als Nachricht und wandeln in ihn mit dem ASCII-Code um. Der Buchstabe X hat in diesem Code den Dezimalwert 88. Also ist M = 88.

Person A erzeugt nun aus dem Klartext für M die verschlüsselte Nachricht C. Diese berechnet man mit der Formel:

C = M^e  mod  N

Person A kann alle Werte in die Formel eintragen und es ergibt sich:

C = 88⁷  mod  187 = 11

Mit der verschlüsselten Nachricht C  kann man nun, ohne den privaten Schlüssel von Person B nichts mehr anfangen. Denn wollte man den Klartext M ermitteln müsste man die Gleichung umstellen, da man alle Werte außer den für M  hat. Und für diese Gleichung

11 = x⁷  mod  187

gibt es unendlich viele Lösungen.

Person A schickt die verschlüsselte Nachricht C = 11 nun an Person B. Person B kann mit folgender Formel den Klartext M  lesen und außer ihm kein anderer.

M = C^d  mod  N

M = 11²³ mod 187

M = 88

Bei diesem Beispiel wurden sehr kleine Zahlen verwendet. In der Realität werden viel größere Zahlen verwendet, um das Verfahren noch sicherer zu machen. Die RSA-Verschlüsselung ist jedoch nicht sehr gut für längere Nachrichten geeignet. Es benötigt sehr viel mehr Zeit als das symmetrische Verschlüsselungsverfahren DES. Bei diesem Verfahren ist jedoch ein großer Nachteil, dass der gemeinsame Schlüssel zwischen den Kommunikationspartnern ausgetauscht werden muss. Und um diese gemeinsamen Schlüssel dem jeweils anderen bekannt zu machen eignet sich das RSA-Verfahren sehr gut, da es kurze Nachrichten, bzw. Schlüssel sehr sicher übertragen kann. Beide Verfahren hängen also miteinander zusammen und erzeugen so eine hohe Effektivität mit niedrigem Risiko.

Comments

Weiterer Beitrag zur RSA-Verschlüsselung

Das RSA-Verfahren ist nach seinen Urhebern Rivest, Shamir und Adleman benannt. Es handelt sich um ein asymmetrisches Verschlüsselungsverfahren (die Entschlüsselung ist für Unbefugte praktisch unmöglich). Der Sender verschlüsselt den Klartext m mit dem öffentlich zugänglichen Schlüssel (bestehend aus einem Exponenten e und einem Divisor n) des Empfängers; der Empfänger entschlüsselt das Ergebnis, den Geheimtext c, mit seinem zugehörigen privaten Schlüssel (bestehend aus einem geheimen Exponenten d und dem gleichen Divisor n).

Der Klartext m (also das, was Verschlüsselt weitergegeben werden soll) wird in eine Zahl überführt. In diesem Beispiel wird – um eine Einführung in die Binärzahlen zu vermeiden – eine Zahl im Dezimalsystem angestrebt (in der Praxis ist es eine Binärzahl). Um beispielsweise einen sprachlichen Text in eine Zahl zu überführen, ordnet man den 26 Buchstaben von A bis Z die zweistelligen Zahlen 01 bis 26 zu. Der Klartext „CODE“ wird auf diese Weise zu m=03150405. Dieser Klartext wird zunächst mit dem öffentlichen Schüssel e des Empfängers potenziert. Der Einfachheit halber wählen wir e=3 und erhalten 31267932387602680125. Dieses Zwischenergebnis wird durch die öffentliche Zahl n dividiert. n muss das Produkt aus zwei Primzahlen p und q sein, die in der Praxis sehr groß sind, sodass die Zerlegung von n in ihre Primfaktoren auch von schnellen Rechnern noch Jahre in Anspruch nehmen würde. Wir wählen hier p=6563 und q=6971, also viel zu kleine Zahlen, die aber das Prinzip der Verschlüsselung verdeutlichen. Dann ist n=45750673. Dabei haben wir darauf geachtet, dass m < n gilt.  Nun wird der natürliche Rest von m^e bei Division durch n also der Rest von 31267932387602680125: 45750673 berechnet (das ist 18983229). Solche Rechnungen bewältigt ein Computer-Algebra-System in Bruchteilen von Sekunden. Dieser Rest 18983229 ist dann der verschlüsselte Text c. Die Berechnung eines Restes c der Potenz m^e bei Division durch n geschieht in der Computer-Algebra im allgemeinen durch den Befehl mod(m^e,n).

Für die Entschlüsselung wird jetzt der verschlüsselte Text c mit einem Exponenten d potenziert und mod(c^d,n) berechnet. Das Ergebnis dieser Berechnung ist dann der Klartext m. Um diesen Exponenten d der Entschlüsselung zu finden, müsste ein Unbefugter die beiden Primfaktoren p und q der Verschlüsselungszahl n kennen (was ja praktisch wegen der Größe der Zahlen nicht der Fall sein kann). Führen wir an Hand der (viel zu kleinen) Zahlen p=6563 und q=6971 einmal vor, was zu rechnen ist, um d herauszufinden:
Beide Primfaktoren sind um 1 zu vermindern und die kleinste natürliche Zahl ist zu finden, die durch 6562 und 6970 (ohne Rest) teilbar ist. Man nennt diese Zahl ‚das kleinste gemeinsame Vielfache‘ (abgekürzt kgV) und kgV(6562, 6970)=1345210. Unter den um 1 vermehrten natürlichen Vielfachen von 1345210 (also 1345211, 2690421,…) sucht man die kleinste durch e=3 teilbare Zahl und findet 2690421:3=896807. Dann ist der Exponent d für die Entschlüsselung d=896807. Die Aufgabe mod(18983229⁸⁹⁶⁸⁰⁷, 45750673)= 3150405 berechnet Computeralgebra schlagartig. Von hinten in Zweierblöcke aufteilen und vorne ggf. eine 0 ergänzen, ergibt 03|15|04|05| also den Klartext.

Eine Begründung für dieses Vorgehen zur Bestimmung der Schüsselzahl d der Dechiffrierung liefert insbesondere der Kleine Satz von Fermat. Aber das ist ein neues umfangreiches Thema.