RSA

Das RSA-Verfahren

Das heutzutage gängigste Public-Key-Verfahren ist das RSA-Verfahren [RSA_1978]. Weitere Vertreter dieser Kategorie sind z.B. das Hellman Pohlig Verfahren (1977), das Merkle-Hellman Verfahren (1978), das Fiat-Shamir Verfahren (1986) und das ElGamal Verfahren [Schneier_1996]. RSA ist von Ronald Rivest, Adi Shamir und Leonhard Adleman als erster praktischer Vorschlag eines Public-Key-Verfahrens entwickelt worden. Wir stellen RSA beispielhaft vor, um die notwendigen Algorithmen und die damit verbundenen Problematiken erklären zu können.

Das RSA-Verfahren basiert auf einer Integer-Arithmetik, wobei der Klartext durch eine positive Integerzahl repräsentiert wird, die zwischen 0 und n - 1 liegen muss. Aus diesem Grund müssen Nachrichten, die in ihrer numerischen Darstellung größer als n - 1 sind, in Blöcke aufgeteilt werden. Die folgende Abbildung zeigt die Ver- und Entschlüsselungsoperation beim RSA-Verfahren. Dabei ergeben sich die Schlüsselpaare:

(e, n) als öffentlicher Schlüssel

wobei diese folgendermaßen angewendet werden:

K = Klartext, S = Schlüsseltext
S = K^e mod n
K = S^d mod n

Aus der folgenden Gleichung kann der Schlüssel d berechnet werden:

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

Dies erfolgt durch inverse Multiplikation, die mit Hilfe des Extended Euklid Algorithmus [Denning_1982] durchgeführt werden kann.

Im Folgenden soll anhand eines einfachen Beispiels die für das RSA-Verfahren erforderliche Rechenkapazität aufgezeigt werden:

Gewählt wird: p = 11, q = 19 und e = 17

Lässt sich der Klartext durch K = 5 darstellen, so erhält man den Schlüsseltext S wie folgt:

S = K ^e mod n

Durch die inverse Transformation ergibt sich wieder der Klartext:

K = S^d mod n

Anhand dieses Minimalbeispiels wird deutlich, dass beispielsweise der Darstellungsbereich eines Taschenrechners überschritten wird (80⁵³).

Obwohl n als Bestandteil des öffentlichen Schlüssels bekanntgegeben wird, führt es zu unüberwindlichen Schwierigkeiten, die Primzahlen p und q aus n zu ermitteln, wenn an p und q besondere Anforderungen gestellt werden. Die Sicherheit des RSA-Verfahrens beruht also auf der Schwierigkeit, eine große Zahl in ihre Primfaktoren zu zerlegen. Ansätze, die sich mit der Lösung dieses Problems beschäftigen, basieren z.B. auf Methoden, die auf der Kenntnis der (teilweisen) Faktorisierung von p - 1 oder p + 1 bzw. q - 1 oder q + 1 beruhen. Es werden daher die Zahlen als starke Primzahlen bezeichnet, die neben ihrer Primzahleneigenschaft noch mehrere, die Sicherheit erhöhende Merkmale, wie große Primteiler in p-1 und p+1 haben und die somit diese Methoden erschweren. Es werden folgende Forderungen an die zu suchenden Zahlen p bzw. q gestellt [Gordon_1984]:

p ist eine große Zahl
p ist eine Primzahl
p wurde zufällig ausgewählt
p hat eine vorher festgelegte Länge
p-1 hat einen großen Primteiler r
p+1 hat einen großen Primteiler s
r-1 hat einen großen Primteiler
s-1 hat einen großen Primteiler

Es gibt sehr viele Methoden, Primzahlen zu berechnen. Die meisten Methoden gehen aber davon aus, dass eine Zahl zufällig erzeugt wird und anschließend mit Hilfe von Wahrscheinlichkeitsverfahren überprüft wird, ob die vorliegende Zahl eine Primzahl ist oder nicht. Verfahren dieser Art sind z.B.:

der Fermat Test
der Wahrscheinlichkeitsalgorithmus nach Solovay und Straßen
das Rabin-Verfahren

Es gibt aber auch sehr schnelle deterministische Algorithmen, mit denen sich definitive Primzahlen unter Berücksichtigung aller Eigenschaften einer starken Primzahl erzeugen lassen [Kemkes_1986] [Ruland_1987].

Wie bereits erwähnt soll es ein Public-Key-Verfahren ermöglichen, den Urheber bzw. Sender einer Nachricht rechtssicher zu ermitteln. Dies ist beim RSA-Verfahren dadurch möglich, dass man auf eine Nachricht zuerst die Operation mit dem geheimen Schlüssel anwendet. In der nachfolgenden Abbildung wird dargestellt, wie mit Hilfe des RSA-Verfahrens eine beliebig lange Information signiert werden kann.

Der Absender sendet die Information zum gewünschten Empfänger und berechnet gleichzeitig mit einer speziellen One-Way-Hashfunktion „h“ eine kryptographisch sichere Prüfsumme von der Information. (Eine Hash-Funktion generiert aus einer beliebig langen Information einen kurzen „Extrakt“ (MD5=128Bit, SHA-1=160Bit) und zwar derart, dass aus dem Extrakt die ursprüngliche Information nicht rekonstruierbar ist und eine andere Information nicht den gleichen Hash-Wert liefert. So wird zum Beispiel der Hash-Wert, den die auf den Text einer E-Mail angewendete Hash-Funktion liefert, mit dem privaten Schlüssel verschlüsselt, um die E-Mail digital zu unterschreiben.) Diese Prüfsumme wird unter Verwendung des geheimen Schlüssels signiert und an den Empfänger gesendet. Der Empfänger berechnet auf die empfangene Information dieselbe Prüfsumme und vergleicht diese mit der verifizierten digitalen Unterschrift der Information. Mit Hilfe dieser Methode wird, unabhängig von der Länge der Information, die RSA-Operation vom Sender und Empfänger jeweils nur einmal auf den Hashwert angewendet.