RSA hat seinen Namen nach denen seiner
Entwickler erhalten: Ronald L. Rivest, Adi Shamir und Leonard Adleman*,
die das Verfahren 1977 ("On Digital Signatures and Public Key Cryptosystems",
MIT Laboratory for Computer Science Technical Memorandum 82, April 1977)
bzw. 1978 ( "A Method for Obtaining Digital Signatures and Public-Key
Cryptosystems" , Communications of the ACM 2/1978) vorstellten.
RSA gehört, wie auch z.B. ElGamal
, zu den asymmetrischen
Verschlüsselungsverfahren , bei denen ein Schlüssel für
die Verschlüsselung und ein anderer für die Entschlüsselung
benutzt wird. Somit ist RSA für die Erzeugung
digitaler Signaturen geeignet.
Grundlage von RSA sind zahlentheoretische
Überlegungen, bei denen angenommen wird, daß große Zahlen
nur schwer faktorisierbar, d.h. in Primfaktoren zerlegbar sind. Es handelt
sich um das sogenannte Faktorisierungsproblem.
Der vermutete Rechenaufwand ist dabei so groß, daß die Verschlüsselung
bei geeignet gewählten Schlüsseln praktisch nicht zu brechen
ist. Die Schlüssel sollten dabei mindestens 512 Bit lang sein, bei
notwendiger Geheimhaltung über lange Zeiträume entsprechend länger.
Arbeitsweise
Es werden zwei große Primzahlen benötigt. Da es kein Verfahren
gibt, das große Primzahlen generiert (das `Sieb
des Erathostenes' ist nur für kleine Primzahlen praktibabel),
werden zwei Zahlen gewählt und mit einem geeigneten Verfahren auf
die Primzahleigenschaft geprüft.
Übliche Tests sind (z.B. nach [Damm
1995]):
-
das Verfahren von Miller-Rabin
-
das Verfahren von Solovay-Strassen
Beide Verfahren stellen mit einer gewissen Wahrscheinlichkeit fest, ob
eine gegebene Zahl eine Primzahl ist, oder nicht. Aufgrund der Einschränkung,
daß mit Wahrscheinlichkeiten operiert wird, sind derartige Verfahren
deutlich schneller als Faktorisierungsverfahren.
Aus beiden Primzahlen, in der Literatur üblicherweise mit p und
q bezeichnet, wird das Produkt n berechnet:
p und q müssen unterschiedliche Zahlen sein. Die Länge von n
sei dabei k Bit. Normalerweise wird k vorgegeben und p und q so gewählt,
daß n die Länge k hat. n wird zum ersten Bestandteil des öffentlichen
Schlüssels.
Dann berechnet man das Produkt z der Vorgänger von p und q:
Nun werden der geheime Schlüssel und der zweite Bestandteil des öffentlichen
Schlüssels gewählt. Beide müssen so gewählt werden,
daß sie folgende Bedingung erfüllen:
e * d = 1 mod( z ), e hat keinen gemeinsamen Teiler mit z
Ob dabei e oder d als privater Schlüssel verwendet werden, ist im
Prinzip egal. Der andere wird dann zum Bestandteil des öffentlichen
Schlüssels. In der Literatur (z.B. bei [Schneier
1996]) steht e üblicherweise im öffentlichen Schlüssel
und d ist der private Schlüssel.
p und q müssen unbedingt geheim bleiben!
Wenn man ganz sicher gehen will, sollte man sie vernichten.
Damit hat man folgende Schlüssel erhalten:
-
Privater Schlüssel: d
-
Öffentlicher Schlüssel: (e, n)
Man könnte auch (d, n) als den privaten Schlüssel bezeichnen.
In der Literatur findet man es allerdings so, wie oben angegeben.
Verschlüsselung
Der Klartext wird in Blöcke zerlegt, die kürzer als n sind. Handelt
es beim Klartext sich nicht um Zahlen oder Bitmuster, so muß man
diese erst entsprechend aufbereiten. (Buchstaben könnte man z.B. durch
ihre Stellung im Alphabet ersetzen.) Die einzelnen Blöcke sollten
gleich lang sein, wozu man ggf. Nullen voranstellt. Ein solcher Block wird
dann entsprechend der folgenden Formel verschlüsselt:
Geheimtextblock = (Klartextblock ^ e) mod n
Entschlüsselung
Die Entschlüsselung erfolgt dann so:
Klartextblock = (Geheimtextblock ^ d) mod n
Durch die Verschlüsselung mit dem öffentlichen Schlüssel
ist sichergestellt, daß nur der berechtigte Empfänger, der als
einziger über den geheimen (privaten) Schlüssel d verfügt,
den Klartext wiederherstellen kann.
Beispiel
Wenn zur Verschlüsselung anstelle des öffentlichen Schlüssels
e der geheime Schlüssel d verwendet wird, kann jeder, der die Nachricht
mit dem öffentlichen Schlüssel entschlüsselt, sicher sein,
daß die Nachricht vom Besitzer des geheimen Schlüssels stammt.
Dies ist der Grundgedanke bei der Verwendung von RSA
für die Erstellung digitaler
Signaturen.
Sicherheit
RSA ist seit 1977 (1978) bekannt. Bis heute
ist kein erfolgreicher Angriff auf eine korrekte RSA-Implementierung
mit ausreichend langem Schlüssel bekannt.
Die Sicherheit von RSA beruht auf dem Faktorisierungsproblem.
Bisher ist keine Methode bekannt, RSA zu brechen,
die schneller als die Faktorisierung wäre. Die schnellsten bekannten
Faktorisierungsverfahren sind ([Damm
1995], S. 17):
-
Multiple Polynomial Quadratic Sieve (MPQS)
-
General Number Field Sieve (GNFS)
Es gibt verschiedene Angriffsmöglichkeiten auf Systeme, die
RSA verwenden (nach [Schneier
1996], S. 537 ff):
Angriffsmethode |
|
Chosen-Ciphertext-Attack |
Keine unbekannten Dokumente signieren, ohne vorher eine Einweg-Hashfunktion
anzuwenden. |
Angriff mit gemeinsamem Modul |
Niemals den gleichen Wert von n für mehrere Benutzer wählen. |
Angriff bei kleinem Verschlüsselungsexponenten |
Der Klartext sollte etwa die gleiche Größe wie n haben.
Gegebenenfalls sollte der Klartext mit Zufallswerten ergänzt werden. |
Angriff bei kleinem Entschlüsselungsexponenten |
d sollte einen Großen Wert ggü. e haben. |
Bedeutung
RSA ist der zivil meistgenutzte asymmetrische
Verschlüsselungsalgorithmus. Er wird zum Beispiel im Programm PGP
verwendet. RSA ist gut für die Erzeugung
digitaler Signaturen geeignet. Der Netscape Navigator/Communicator setzt
ebenfalls auf RSA-Sicherheit, wie aus der Startseite ersichtlich (Bildausschnitt):
Patente
RSA ist in den USA unter der Nummer 4.405.829
bis zum 20. September 2000 patentiert. Anwender benötigen demnach
ein gültige Lizenz, die von RSADSI erhältlich
ist.
Es gibt allerdings begründete Zweifel an der Gültigkeit des
Patents. Der Umfang des Patents ist ebenfalls zweifelhaft. (Siehe dazu
die Annotation.)
 |
Patrick J. Flinn, James M. Jordan III:
Using the RSA Algorithm for Encryption and Digital Signatures: Can
You Encrypt, Decrypt, Sign and Verify without Infringing the RSA Patent?
Internet: http://www.cyberlaw.com
Eine Zusammenfassung. |