slider

RSA-Verfahren - Prof. Dr. Norbert Pohlmann

RSA-Verfahren

RSA-Verfahren als Verschlüsselungsalgorithmus

Was ist das RSA-Verfahren?


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 .

Asymmetrische Verschlüsselung als Ablaufdiagramm
Abbildung: Asymmetrische Verschlüsselung – © Copyright-Vermerk


Der Algorithmus von RSA 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 3.000 Bit in binärer Darstellung für den RSA-Modulus.

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 beim RSA-Verfahren 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 auf der Basis des RSA-Verfahrens wird folgende Berechnung durchgeführt:

c = me mod n.


Die Entschlüsselung auf der Basis des RSA-Verfahrens 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

Digitale Signatur mithilfe des RSA-Verfahrens

Eine wichtige Anwendung des RSA-Verfahrens ist die digitale Signatur. Sie nutzt beide Komponenten – sowohl den öffentlichen als auch den geheimen Schlüssel –, um mit ihrer Hilfe ein elektronisches Äquivalent zur eigenhändigen Unterschrift zu erzeugen, das ebenso rechtsverbindlich und im juristischen Sinn beweiskräftig ist wie eine eigenhändige Unterschrift.

Klartext-Daten, die mit einem bestimmten geheimen Schlüssel „verschlüsselt“ wurden, können nur mithilfe des dazugehörigen öffentlichen Schlüssels wieder „entschlüsselt“ werden.

Hat nun eine Person die Klartext-Daten mit ihrem geheimen Schlüssel digital signiert, kann mithilfe des öffentlichen Schlüssels überprüft werden, ob die digitale Signatur der Klartext-Daten wirklich von dieser Person stammt. Die erfolgreich durchgeführte Überprüfung der digitalen Signatur ist der Beweis für die Authentizität des Absenders und Integrität der Nachricht, dem Klartext.

Mit dem Prinzip der digitalen Signatur steht somit ein Äquivalent zur eigenhändigen Unterschrift zur Verfügung. Das bekannteste Public-Key-Verfahren, mit dem gleichzeitig signiert und verschlüsselt werden kann, ist der RSA-Algorithmus.

Authentische RSA-Schlüssel

Ein offenes Problem bei Public-Key-Verfahren wie dem RSA-Verfahren ist die Frage, wie der öffentliche Schlüssel zum Kommunikationspartner gelangt. Wie kann überprüft werden, dass ein öffentlicher Schlüssel in einem Verzeichnis wirklich der echte ist? Selbst im Fall der Verwendung öffentlicher Schlüssel müssen diese authentisch ausgetauscht werden. Siehe die Abbildung.

Eine elegante Möglichkeit, öffentliche Schlüssel authentisch auszutauschen, ist die Einrichtung eines Zertifizierungssystems, eines Trustcenters oder einer Public-Key-Infrastruktur. Der öffentliche Schlüssel jedes Nutzers wird von einer Public-Key-Infrastruktur (Zertifizierungssystem) in Form eines „digitalen Zertifikate “ zur Verfügung gestellt.



Schlussbetrachtung und Herausforderungen des RSA-Verfahrens

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.

Die Sicherheit von Public-Key-Verfahren hängt sehr stark von der Leistungsfähigkeit der aktuellen 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

RSA-Verfahren als Verschlüsselungsalgorithmus
Abbildung: RSA-Verfahren – © Copyright-Vermerk




Weitere Informationen zum Begriff “RSA-Verfahren”:



Kryptographie: Von der Geheimwissenschaft zur alltäglichen Nutzanwendung“
Elementare Verschlüsselungsverfahren
Symmetrische Verschlüsselungsverfahren
Asymmetrische Verschlüsselungsverfahren
Prüfsummen, Zertifikate und die elektronische Signatur
Public Key Infrastruktur (PKI)
Vertrauensmodelle von Public-Key-Infrastrukturen



Lehrbuch Cyber-Sicherheit

Übungsaufgaben und Ergebnisse zum Lehrbuch Cyber-Sicherheit

Bücher im Bereich Cyber-Sicherheit und IT-Sicherheit zum kostenlosen Download



Vorlesungen zum Lehrbuch Cyber-Sicherheit



Trusted Blockchain Interfaces

Blockchain-Technologie als Tool für Industrial Security

The Future of Trust in Ecosystems – Global Challenges

Blockchain Security



Forschungsinstitut für Internet-Sicherheit (IT-Sicherheit, Cyber-Sicherheit)

Master-Studiengang Internet-Sicherheit (IT-Sicherheit, Cyber-Sicherheit)

Marktplatz IT-Sicherheit

Marktplatz IT-Sicherheit: IT-Notfall

Marktplatz IT-Sicherheit: IT-Sicherheitstools

Marktplatz IT-Sicherheit: Selbstlernangebot

Vertrauenswürdigkeits-Plattform


Zurück zur Übersicht




Summary
RSA-Verfahren
Article Name
RSA-Verfahren
Description
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
Publisher Name
Institut für Internet-Sicherheit – if(is)
Publisher Logo
RSA-Verfahren als Verschlüsselungsalgorithmus
RSA-Verfahren Prof. Dr. Norbert Pohlmann - Cyber-Sicherheitsexperten