Rechnernetze

Die Schlüsselbildung beim RSA-Verfahren

In einem Public-Key-System werden zwei verschiedene Schlüssel zur Ver- und Entschlüsselung von Nachrichten benötigt; dabei dürfen die Schlüssel nicht auseinander ableitbar sein. Es werden immer wieder neue Algorithmen zu dieser Fragestellung entwickelt. Im folgenden soll das wichtigste und verbreitetste dieser Verfahren vorgestellt werden.

1978 wurde von Shamir, Adleman und Rivest am MIT ein Verfahren entwickelt, welches darauf beruht, dass für sehr große Zahlen (mehrere hundert Dezimalstellen) der Aufwand für die Zerlegung in Primfaktoren extrem hoch wird (der Zeitaufwand für die Zerlegung würde das Alter des Universums bei weitem übersteigen). Andererseits ist es aber für sehr große Zahlen noch in einer vertretbaren Zeit möglich festzustellen, ob es sich um Primzahlen handelt.

Im wesentlichen wird wieder die Exponentiation einer Nachricht H mit einem Schlüssel e bzw. dessen reziprokem Wert d=e^-1 durchgeführt:

E_e(H) = H^e mod m

D_d(H^e) = (H^e)^d = H¹ = H mod m

Aus m und e kann einfach d berechnet werden, wenn m eine Primzahl ist. Ist m=p*q jedoch keine Primzahl, so ist dieses sehr viel schwieriger. Man muss im Prinzip zunächst einmal die Primfaktoren von m bestimmen, was zahlentheoretisch ein schwieriges Problem ist und damit so zeitaufwendig, dass es für große Zahlen p und q praktisch nicht durchführbar ist.

Die Auswahl oder Berechnung des Schlüssels erfolgt nach den folgenden Schritten:

1. Auswählen zweier Primzahlen p und q mit jeweils mehr als 100 Dezimalstellen.
2. Berechnung von m = p*q und r = KGV [p-1 ; q-1].
3. Auswählen der Zahl e, die zu (p-1) und (q-1) relativ prim sein muss, sowie der Zahl d=e^-1, so dass d´e=1 mod r.

Für die Verschlüsselung zerteilt man die zu übertragende Information in Blöcke, die als Binärzahlen aufgefasst kleiner als m sind, und erhebt diese Binärzahlen in die e-te Potenz, wobei man Arithmetik modulo m verwendet. In analoger Weise kann die Entschlüsselung durchgeführt werden, indem man die einzelnen Blöcke zur d-ten Potenz erhebt.

Wird eine Zahl H in die k-te Potenz erhoben: H^k mod r, so wird für ein bestimmtes k zum ersten Mal H^k+1=H sein. Dieses k wird als Periode bezeichnet. Ist diese bekannt, so lässt sich aus der Kenntnis von k und e der reziproke Wert d=e^-1 einfach bestimmen. Ist m eine Primzahl, so ist die Periode gleich m. Ist jedoch, wie im RSA-Algorithmus, m keine Primzahl, so ist die Berechnung der Periode nur möglich, wenn die Primfaktoren von m bekannt sind. Diese sind jedoch aufgrund der Konstruktion im RSA-Verfahren nicht bekannt. Die Sicherheit dieses Verfahrens beruht also darauf, dass die Primfaktoren einer großen Zahl nur schwierig zu bestimmen sind. Dieses ist jedoch ein bekanntes zahlentheoretisches Problem, welches bis heute noch nicht einfach gelöst ist. Daher basiert die Sicherheit dieses Verfahrens tatsächlich darauf, dass bisher zu einem bestimmten mathematischen Problem noch keine Lösung veröffentlich wurde.