slider

RSA-Verfahren - Prof. Dr. Norbert Pohlmann

RSA-Verfahren

RSA-Verfahren - Glossar Cyber-Sicherheit - Prof. Norbert Pohlmann

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, was bedeutet, dass das Verfahren für einen definierten Zeitraum als „sicher“ gelten kann. Kryptografie-Experten empfehlen derzeit eine Länge zwischen 2048 und 3072 Bit in binärer Darstellung für den RSA-Modulus, wobei der erste Wert bis Ende des Jahres 2023 und der zweite darüber hinaus gilt.


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


Weitere Informationen zum Begriff “RSA-Verfahren”:


Vorlesung: „Kryptographie“

Artikel:
„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

Informationen über das Lehrbuch: „Cyber-Sicherheit“

Glossar Cyber-Sicherheit: Bundesamt für Sicherheit in der Informationstechnik (BSI)

Zurück zur Übersicht
RSA-Verfahren - Glossar Cyber-Sicherheit - Prof. Norbert Pohlmann
RSA-Verfahren Prof. Dr. Norbert Pohlmann - Cyber-Sicherheitsexperten