Das RSA-Verfahren wurde 1978 von Ron Rivest (Massachusetts Institute of Technology – MIT), Adi Shamir (Weizmann-Institut für Wissenschaften) und Leonard Adleman (Stanford University) entwickelt und findet seine Verwendung bei Verschlüsselung, digitalen Signaturen und beim Key Management.
Der Algorithmus basiert auf dem Problem, dass das Produkt zweier großer Primzahlen nur schwer in seine Faktoren zu zerlegen ist. Dazu ein Beispiel: 377 ist das Produkt aus 13 und 29, mit anderen Worten: das Ergebnis der Multiplikation der sechsten mit der zehnten Primzahl. Sind die Primzahlen bekannt beziehungsweise wie hier klein genug, ist die Operation einfach.
Werden die Faktoren dagegen hinreichend groß gewählt, kann die Zerlegung eine praktisch unlösbare Aufgabe darstellen. Das bedeutet, dass das Verfahren für einen definierten Zeitraum als „sicher“ gelten kann. Kryptografie-Experten empfehlen derzeit eine Länge von mindestent 3000 Bit in binärer Darstellung für den RSA-Modulus. Der erste Wert gilt ab 2024 verbindlich.
RSA-Schlüsselgenerierung
Um einen Schlüssel nach RSA zu erzeugen, wird zunächst nach zwei großen Primzahlen p und q gesucht. Dann wird das Produkt n = p * q berechnet. Als nächstes wird eine zu ((p − 1) * (q − 1)) teilerfremde Zahl e ausgewählt. Diese bildet mit dem Produkt n den öffentlichen Schlüssel (e, n). Dann wird der erweiterte Euklidische Algorithmus verwendet, um eine Zahl d zu berechnen, wobei e * d mod ((p − 1) (q − 1)) = 1 gilt. Die Zahl d ist der geheime Schlüssel, der es ermöglicht, die Trap-Door-Eigenschaften des Verfahrens auszunutzen. Die Qualität des so erstellten Schlüssels und damit die Sicherheit des RSA-Verfahrens hängen von den verwendeten Primzahlen ab. Es gibt zum Beispiel Faktorisierungsmethoden, die mithilfe der Faktoren in p-1 und q-1 zu viel besseren Ergebnissen kommen. Aus diesem Grund sollen die Primzahlen für das RSA-Verfahren noch besondere Eigenschaften aufweisen, die mit starken Primzahlen bezeichnet werden.
Die Eigenschaften sind für die Primzahlen p und q: • p ist eine große Zahl (zum Beispiel 1500 Bit) • p ist eine Primzahl (kann sehr unterschiedlich nachgewiesen werden) • p wurde zufällig ausgewählt (Zufallszahlengenerator) • p hat eine vorher festgelegte Länge (zum Beispiel zwischen 1480 und 1520 Bit) • 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
RSA-Verschlüsselungsvorschrift
Eine Klartextnachricht m soll in einen Schlüsseltext c durch Verschlüsselung umgewandelt werden. Aus der Schlüsselgenerierung steht der öffentlichen Schlüssel (e, n) zur Verfügung, bestehend aus der zu ((p − 1) * (q − 1)) teilerfremden Zahl und dem Produkt der Primzahlen n. Außerdem steht der geheime Schlüssel d zur Verfügung.
Für die Verschlüsselung wird folgende Berechnung durchgeführt:
c = me mod n.
Die Entschlüsselung erfolgt jedenfalls mit der Berechnung von:
m = cd mod n
Öffentlicher Schlüssel (ÖS) ist das Zahlenpaar (e, n) Geheimer Schlüssel (GS) ist die Nummer d
Beispiel RSA-Verschlüsselung
p = 61 erste Primzahl q = 53 zweite Primzahl n = p * q = 3233 Modulus – (Teil des öffentlichen Schlüssels) e = 17 öffentlicher Exponent – (Teil des öffentlichen Schlüssels) d = 2753 geheimer Exponent – (der geheime private Schlüssel) c = m17 mod 3233 Verschlüsselungsoperation d = c2753 mod 3233 Entschlüsselungsoperation
Aufgabe 1 Verschlüssele die Zahl m = 123 Ergebnis 1 c = 12317 mod 3233 = 337587917446653715596592958817679803 mod 3233 = 855
Aufgabe 2 Entschlüssle die Zahl c = 855 Ergebnis 2 d = 8552753 mod 3233 = 5,043288895841606873 442289912739e + 8071 mod 3233 = 123
Asymmetrische Verschlüsselungsverfahren sind im Vergleich zu symmetrischen Verschlüsselungsverfahren leider sehr rechenintensiv, weswegen die Ver- und Entschlüsselung deutlich langsamer vor sich geht. Die verwendeten Algorithmen müssen daher mit Blick auf Rechenleistung und Speicherplatz des verwendeten IT-Systems sowie die zur Verfügung stehende Zeit angepasst werden, um eine effektive Lösung zu realisieren.
Schlussbetrachtung Die Sicherheit von Public-Key-Verfahren hängt sehr stark von der Leistungsfähigkeit der IT-Systeme ab. Eine besondere Aufmerksamkeit der Kryptologen gilt daher der Entwicklung sog. Quantencomputer, die bisher als sicher geltende Verfahren wie RSA aushebeln könnten: Da diese möglicherweise effizientere Berechnungsverfahren zur Faktorisierung der Produkte großer Primzahlen ermöglichen, könnte aus einem Problem mit exponentialer eines mit polynomialer Laufzeit werden – die Schwelle zur Lösbarkeit wäre überschritten. Siehe: Quantensichere Algorithmen / Post-Quanten-Kryptographie Aus diesem Grund ist die Suche nach geeigneten Ersatzverfahren für asymmetrische Verschlüsselungen eine kontinuierliche Aufgabe. Siehe auch: Krypto-Agilität
Lehrbuch Cyber-Sicherheit – Das Lehrbuch für Konzepte, Mechanismen, Architekturen und Eigenschaften von Cyber-Sicherheitssystemen in der Digitalisierung
Das RSA-Verfahren wurde 1978 entwickelt und findet seine Verwendung bei Verschlüsselung, digitalen Signaturen und beim Key Management. Der Algorithmus basiert auf dem Problem, dass das Produkt zweier großer Primzahlen nur schwer in seine Faktoren zu zerlegen ist.
Author
Prof. Norbert Pohlmann
Publisher Name
Institut für Internet-Sicherheit – if(is)
Publisher Logo
RSA-Verfahren Prof. Dr. Norbert Pohlmann - Cyber-Sicherheitsexperten
