RSA-Chiffre

Die Abkürzung RSA setzt sich aus den Anfangsbuchstaben der Nachnamen der Entwickler des Verfahrens, Ronald Rivest, Adi Shamir (beide Computerwissenschaftler) sowie Leonard Adleman (Mathematiker) zusammen. (v.l.n.r.) Sie arbeiteten als Forscher im MIT-Labor (Massachusetts Institute of Technology) für Computerwissenschaften zusammen und beteiligten sich an der Suche nach einer Einwegfunktion für das von Diffie und Hellman beschriebene asymmetrische Verfahren. Nach über einem Jahr intensiver, aber erfolgloser Suche, entwickelt Rivest im April 1977 sprichwörtlich "über Nacht" - er konnte nach einer Feier nicht einschlafen - das als RSA in die Geschichte eingegangene Verfahren.

Grundgedanke ist, eine allgemeine Einwegfunktion zu verwenden, die modulare Exponentiation: Geheimtext = Mitteilung^e (mod N).
Der öffentliche Schlüssel setzt sich dabei aus einem frei gewählten Wert e und einem Wert N, ein Produkt aus zwei unabhängigen Primzahlen (als p bzw. q bezeichnet), zusammen. Alice kann diesen Schlüssel frei wählen, wodurch es möglich ist, dass jeder seinen "eigenen" Schlüssel besitzt, welcher dann beispielsweise via Internet allen zugänglich gemacht wird.

Jeder kann durch Anwendung der Einwegfunktion eine Nachricht, die in Zahlen umgewandelt wird, mit dem öffentlichen Schlüssel von Alice chiffrieren. Dechiffrieren kann diese Nachricht ausschließlich Alice, die den geheimen Schlüssel besitzt, der sich aus den Werten d und N zusammensetzt.

Der Wert d lässt sich nur durch die Kenntnis der Primzahlen p und q bestimmen. [genauere Funktionsbeschreibung (Ver-/Entschlüsselung)]

Da für einen Rechner sowohl Klar- als auch Geheimtext ohnehin "nur" Zahlen sind, lässt sich problemlos mit der Einwegfunktionsformel rechnen.

Prinzipiell kann man davon ausgehen, dass die Faktorenbestimmung recht aufwändig und zeitintensiv ist. Darauf baut das RSA-Verfahren auf. So ist es ein Leichtes, zwei große Primzahlen miteinander zu multiplizieren, Rückschlüsse aus dem Produkt auf diese Zahlen zu ziehen, gestaltet sich hingegen schwierig. Offensichtlich kann man sagen: je grösser die gewählten Primzahlen sind, desto sicherer wird die Verschlüsselung.

Vor einigen Jahren hatte der Sicherheitsexperte Garfinkel geschätzt, dass man 50 Jahre mit einem Intel Pentium 100 MHz mit 8 MB RAM benötigen würde, um eine Zahl der Größe um 10¹³⁰ in ihre Faktoren zu zerlegen. Da dies beim heutigen Stand der Technik um ein Vielfaches schneller gehen würde, wurden die Schlüsselgrößen entsprechend angepasst. So liegt beispielsweise der Schlüssel für Banktransaktionen bei mindestens 10³⁰⁸ (oftmals noch größer).

Im August 1977 hatte RSA schließlich seinen ersten öffentlichen Auftritt.