von S. Emmel


Zeitgleich mit der Gründung des Studiengangs Mathematik an der Fachhochschule Gießen-Friedberg wurde 1978 das RSA-Verschlüsselungsverfahren in den Schriften der ACM[1] vorgestellt.

Die Entdeckung des Verfahrens durch die Wissenschaftler Ronald L. Rivest, Adi Shamir und Leonard Adleman war ein Meilenstein in der Geschichte der Kryptographie, denn damit wurde endlich das Problem der so genannten Schlüsselverteilung gelöst. Bisher mussten Sender und Empfänger einer verschlüsselten Nachricht den Schlüssel, mit dem der jeweilige Algorithmus ausgeführt wurde, austauschen. Dieser Austausch des Schlüssels stellt eine Schwachstelle des jeweiligen Verschlüsselungsverfahrens dar.

image002

„Das ganze Problem der Schlüsselverteilung ist eine klassische Paradoxie. Wenn ein Mensch einem anderen eine geheime Nachricht am Telefon übermitteln will, muss er sie verschlüsseln. Dazu braucht er einen Schlüssel, der selbst wiederum ein Geheimnis ist, und so ergibt sich das Problem, diesen geheimen Schlüssel dem Empfänger zu übermitteln, damit die geheime Botschaft gesendet werden kann. Kurz, wenn zwei Menschen sich ein Geheimnis (eine verschlüsselte Botschaft) mitteilen wollen, müssen sie sich zuvor bereits ein Geheimnis (den Schlüssel) mitgeteilt haben.“

Simon Singh, Geheime Botschaften, dtv, 2001

Anhand des folgenden populären Beispiels soll das Problem des Schlüsselaustauschs nochmals erläutert werden.

Man stelle sich vor, Alice möchte Bob eine geheime Nachricht senden. Diese legt Alice in eine Kiste, die sie mit einem Schloss sichert und an Bob schickt. Wenn Bob die Kiste erhält, kann er sie nicht öffnen, da er nicht den richtigen Schlüssel besitzt. Alice könnte den richtigen Schlüssel in eine zweite Kiste legen und diese wiederum an Bob schicken; und so weiter und so fort. Bob kann aber auch die zweite Kiste nicht ohne den passenden Schlüssel öffnen. Die einzige Möglichkeit scheint darin zu bestehen, dass sich Alice und Bob treffen und Alice Bob eine Kopie des Schlüssels übergibt. In die Terminologie der Kryptographie übersetzt bedeutet dies, dass Bob die von Alice verschlüsselte Nachricht nur entschlüsseln kann, wenn er von Alice eine Kopie des Schlüssels erhält.

Eine andere Ansatzmöglichkeit besteht darin, dass Bob die verschlossene Kiste mit der Nachricht seinerseits mit einem Schloss sichert und sie an Alice zurückschickt. Alice entfernt daraufhin ihr Schloss und schickt die nur noch mit Bobs Schloss gesicherte Kiste an Bob zurück, der sie mühelos mit seinem Schlüssel öffnen kann.

Dieses Beispiel ließ die Kryptoanalytiker Hoffnung schöpfen, dass es einen Verschlüsselungsalgorithmus geben musste, der einen Schlüsselaustausch überflüssig werden ließ. Es musste nur noch die geeignete mathematische Funktion gefunden werden. Whitfield Diffie und Martin Hellmann, die sich zuerst auf die Suche nach geeigneten mathematischen Funktionen machten, konzentrierten ihre Aufmerksamkeit auf die so genannten Einwegfunktionen. Ein Beispiel für eine Einwegfunktion im alltäglichen Leben ist das Anrühren eines Kuchenteiges. Zunächst werden alle Zutaten – Mehl, Zucker, Eier, Butter und Milch – miteinander vermischt. Dieser Vorgang ist danach nicht mehr rückgängig zu machen, d.h. die einzelnen Zutaten können nicht mehr aus dem Teig extrahiert werden.

Diffie und Hellmann konzentrierten sich auf die Modul-Arithmetik, z.B. y (mod x), wobei die Zahl y durch x geteilt und der Rest notiert wird:

 

image004

Hellmann entwarf mittels der Einwegfunktion Y x(mod P) ein Verfahren, das einen geheimen Schlüssel überflüssig machte.

 

Alice

Bob

 

Vereinbarung zweier Zahlen Y und P, wobei Y < P gelten muss.

Beispiel: Y = 7 und P = 11

7 x(mod 11)

1.

Alice wählt eine beliebige Zahl A aus und hält sie geheim.

Beispiel: A = 3

Bob wählt eine beliebige Zahl B aus und hält diese ebenfalls geheim.

Beispiel: B = 6

2.

Beide setzen ihre gewählte Zahl in die Einwegfunktion Y x(mod P) für x ein.

 

7 3(mod 11) = 343(mod 11) = 2

7 6(mod 11) = 117649(mod 11) = 4

3.

Alice schickt a = 2 an Bob.

Bob schickt b = 4 an Alice

 

Üblicherweise ist diese Übermittlung kritisch, da die Nachricht abgehört werden könnte. Da aber weder a noch b Schlüssel sind, ist die Übertragung ungefährlich.

4.

Alice rechnet b A(mod 11)

4 3(mod 11) = 64(mod 11) = 9

Bob rechnet a B(mod 11):

2 6(mod 11) = 64(mod 11) = 9

 

Beide erhalten dasselbe Ergebnis, das dem Schlüssel entspricht.

Dieses Verfahren benötigt zwar keinen Schlüsselaustausch mehr, doch besteht immer noch das Problem, das Alice und Bob die Zahlen Y und P miteinander vereinbaren müssen.

Parallel zu Hellmanns Verfahren erfand Diffie den Begriff des so genannten asymmetrischen Verschlüsselungsverfahrens. Die bisherigen Verfahren waren allesamt symmetrisch, d.h. zur Ver- und Entschlüsselung einer Nachricht wurde jeweils der gleiche Schlüssel benutzt. Bei einem asymmetrischen Verfahren unterscheiden sich jedoch Chiffrier- und Dechriffrierschlüssel voneinander; man benötigt also ein so genanntes Schlüsselpaar. Der Dechiffrierschlüssel muss geheim gehalten werden, der Chiffrierschlüssel kann öffentlich hinterlegt werden.

Wenn Bob Alice eine Nachricht schicken will, chiffriert er sie mit Alices öffentlichem Schlüssel. Nur Alice, die ihren geheimen Dechiffrierschlüssel kennt, kann die Nachricht dechiffrieren.

Diffie fand jedoch keine mathematische Funktion, die in der Lage war ein solches Schlüsselpaar zu erzeugen. An diesem Punkt übernahmen Rivest, Shamir und Adleman, die eine geeignete Einwegfunktion fanden. Im Folgenden wird die Mathematik des RSA-Verfahrens in Anlehnung an Anhang J von Geheime Botschaften (Simon Singh, dtv, 2001) dargestellt.

1. Zunächst muss Alice zwei sehr große Primzahlen p und q auswählen und sie geheim halten. Beispielsweise könnte sie der Einfachheit halber p = 17 und q = 11 wählen.
   
2. Im zweiten Schritt multipliziert Alice p und q miteinander und berechnet damit die Zahl N. Im Beispiel ist N gleich 187. Nachdem N berechnet ist, muss Alice wiederum eine Zahl e auswählen; sie wählt beispielsweise e = 7. Die Zahlen e und (p – 1)(q – 1) sollten dabei teilerfremd sein.
   
3. Alice hat mit der Berechnung von N und der Wahl von e ihren öffentlichen Schlüssel erstellt. Sie kann nun beide in einem öffentlichen Verzeichnis hinterlegen, da beide Zahlen für die Verschlüsselung notwendig sind. Die Zahl e kann dabei bei mehreren Personen gleich sein, jedoch muss sich der Wert von N für alle unterscheiden.
   
4. Eine Mitteilung kann nur verschlüsselt werden, wenn sie in eine Zahl M umgewandelt wurde. Dies kann beispielsweise durch die Interpretation der ASCII-Darstellung als Dezimalzahl geschehen. M kann nach der Formel C = M e(mod N) verschlüsselt werden, wobei C der Geheimtext ist.
   
5. Wenn Bob Alice den Buchstaben X, der in ASCII durch den Wert 1011000 dargestellt wird, schicken möchte, wandelte er sie in eine Dezimalzahl um. 1011000 entspricht der Zahl 88 im Dezimalsystem, womit gilt: M = 88.
   
6. Zunächst muss Bob sich Alices öffentlichen Schlüssel beschaffen mit N = 187 und e = 7, die er in die Verschlüsselungsformel einsetzen kann. Damit ergibt sich für C: 88 7(mod 187) = 11(mod 187) und somit C = 11. Bob kann jetzt C an Alice verschicken.
   
7. Alice berechnet mit ihren geheimen Werten p und q die Zahl d nach der Formel e . d = 1(mod (p - 1)(q - 1)). Sie berechnet 7 . d = 1(mod 16 . 10) beispielsweise mit dem euklidischen Algorithmus und erhält für d den Wert 23.
   
8. Mithilfe von d kann Alice die Nachricht entschlüsseln, indem sie M = C d(mod N) rechnet., also M = 11 23(mod 187) = 88.

In der Realität wählt man für die Zahlen p und q, deren Produkt N ist, sehr große Primzahlen. Da p und q geheim sind, muss – wenn die Nachricht geknackt werden soll – N in seine Primfaktoren zerlegt werden. Es wird geschätzt, dass es bei einem Wert von 10 308 für N tausend Jahre dauern würde, bis N mit hundert Millionen vernetzter PCs in seine Primfaktoren zerlegt wird.

Heute werden unwahrscheinlich große Werte für p und q genutzt, so dass das RSA-Verfahren auf lange Sicht hin, das sicherste asymmetrische Verfahren bleiben wird. Eine moderne Anwendung des RSA-Algorithmus findet sich im Programm PGP – Pretty Good Privacy, einem Programm von Phil Zimmermann zur computergestützten Verschlüsselung.



[1] A Method for Obtaining Digital Signatures and Public-Key-Cryptosystems, Communications of the ACM 2/1978