Rivest, Shamir, Adleman (RSA)
RSA gilt als eines der sichersten und bestbeschriebenen Public-Key-Verfahren. Die Idee, eine Verschlüsselung durch einen öffentlichen Chiffrierschlüssel und einen geheimen Dechiffrierschlüssel zu realisieren, geht auf die Kryptologen Whitfield Diffie und Martin Hellman zurück. Diese veröffentlichten 1976 mit dem Diffie-Hellman-Schlüsselaustausch ein Verfahren, das es zwei Kommunikationspartnern ermöglicht, sich über einen unsicheren Kanal gemeinsam auf einen geheimen Schlüssel zu einigen. Dabei stützten sich die Forscher auf das von Ralph Merkle entwickelte Merkles Puzzle. Man spricht daher auch vom Diffie-Hellman-Merkle-Schlüsselaustausch (DHM).
Die Kryptogen bedienten sich mathematischer Einwegfunktionen, die zwar leicht durchzuführen sind, sich aber nur mit erheblichem Rechenaufwand umkehren lassen. Noch heute kommt der nach ihnen benannte Schlüsselaustausch zur Anwendung, um geheime Schlüssel im Rahmen symmetrischer Kryptosysteme auszuhandeln. Ein weiteres Verdienst des Forscherduos stellt das Konzept der Falltür dar. Bereits in der Veröffentlichung des Diffie-Hellman-Schlüsselaustauschs werden versteckte Abkürzungen angesprochen, die es ermöglichen sollen, die Inversion einer Einwegfunktion zu beschleunigen. Einen konkreten Beweis lieferten Diffie und Hellmann nicht, regten mit ihrer Theorie der Falltür jedoch zahlreiche Kryptologen zu eigenen Untersuchungen an.
Auch Rivest, Shamir und Adleman suchten nach Abkürzungen für Einwegfunktionen – ursprünglich mit der Motivation, die Falltürtheorie zu widerlegen. Doch ihre Forschung entwickelte sich in eine andere Richtung und mündete in das schließlich nach ihnen benannte Verschlüsselungsverfahren. Heute gilt RSA als der erste wissenschaftlich publizierte Algorithmus, der eine Übertragung chiffrierter Daten ohne Austausch eines geheimen Schlüssels ermöglicht.
Beim RSA kommt ein Algorithmus zum Einsatz, der sich auf die Multiplikation großer Primzahlen stützt. Während es im Allgemeinen kein Problem darstellt, zwei Primzahlen mit 100, 200 oder 300 Stellen zu multiplizieren, existiert bis heute kein effizienter Algorithmus, der das Ergebnis einer solchen Rechenoperation im Umkehrschritt in ihre Primfaktoren zerlegen kann. Verdeutlichen lässt sich die Primfaktorisierung an einem Beispiel:
Multipliziert man die Primzahlen 14.629 und 30.491 erhält man das Produkt 446.052.839. Dieses hat lediglich vier Teiler: 1, sich selbst sowie die beiden Primzahlen, die multipliziert wurden. Streicht man die ersten beiden Teiler, da jede Zahl durch 1 und durch sich selbst teilbar ist, erhält man somit die Ausgangswerte 14.629 und 30.491.
Dieses Schema ist die Grundlage der RSA-Schlüsselerzeugung. Sowohl der öffentliche als auch der private Schlüssel stellen zwei Zahlenpaare dar:
Öffentlicher Schlüssel: (e, N)
Privater Schlüssel: (d, N)
Bei N handelt es sich um das sogenannte RSA-Modul. Dieses ist in beiden Schlüsseln enthalten und ergibt sich aus dem Produkt zweier zufällig gewählter, sehr großer Primzahlen p und q (N = p x q).
Um den öffentlichen Schlüssel zu generieren, benötigt man zudem e, eine Zahl, die mit gewissen Einschränkungen zufällig gewählt wird. Kombiniert man N und e erhält man den öffentlichen Schlüssel, der jedem Kommunikationsteilnehmer in Klartext vorliegt.
Um den private Schlüssel zu generieren, benötigt neben N auch d. Bei d handelt es sich um einen Wert, der sich aus den zufällig generierten Primzahlen p und q sowie der Zufallszahl e ergibt, die auf Basis der Eulerschen Phi-Funktion (φ) miteinander verrechnet werden.
Welche Primzahlen in die Berechnung des privaten Schlüssels eingehen, muss geheim bleiben, um die Sicherheit der RSA-Verschlüsselung zu gewährleisten. Das Produkt der beiden Primzahlen hingegen kann im öffentlichen Schlüssel in Klartext verwendet werden, da man davon ausgeht, dass es heutzutage keinen effizienten Algorithmus gibt, der das Produkt sehr großer Primzahlen in relevanter Zeit in seine Faktoren zerlegen kann. Es ist somit nicht möglich, p und q aus N zu berechnen. Es sei denn, man kann die Berechnung abkürzen. Eine solche Falltür stellt der Wert d dar, der lediglich dem Besitzer des privaten Schlüssels bekannt ist.
Die Sicherheit des RSA-Algorithmus ist in hohem Maße abhängig vom technischen Fortschritt. Die Rechenleistung von Computern verdoppelt sich in etwa alle zwei Jahre. Es ist somit nicht ausgeschlossen, dass in absehbarer Zeit ein effizientes Verfahren zur Primfaktorzerlegung in der heute üblichen Größenordnung zur Verfügung steht. In diesem Fall bietet RSA die Möglichkeit, den Algorithmus der technischen Entwicklung anzupassen, indem zur Berechnung der Schlüssel noch größere Primzahlen herangezogen werden.
Für einen sicheren Betrieb des RSA-Verfahrens gibt die Bundesnetzagentur für den Wert N (das Produkt beider Primzahlen) bis Ende 2020 eine Mindestlänge von 1.976 bit an, empfiehlt jedoch 2.048 bit. Dies entspricht Primzahlen in einer Größenordnung von etwa 300 Dezimalstellen.