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.

RSA-Verfahren für die Verschlüsselung und digitale Signatur
Abbildung: RSA-Verfahren für die Verschlüsselung und digitale Signatur – © Copyright-Vermerk


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 zwischen 2048 und 3072 Bit in binärer Darstellung für den RSA-Modulus. Der erste Wert gilt bis Ende des Jahres 2023 und der zweite darüber hinaus.

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.


Weitere Informationen zum Begriff “RSA-Verfahren”

Siehe auch Grossareintrag: Asymmetrische Verschlüsselung

Vorlesung: „Kryptographie“

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

Vorlesungen: „Vorlesungen zum Lehrbuch Cyber-Sicherheit

Bücher:

Lehrbuch Cyber-Sicherheit – Das Lehrbuch für Konzepte, Mechanismen, Architekturen und Eigenschaften von Cyber-Sicherheitssystemen in der Digitalisierung

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

  • Sicher im Internet: Tipps und Tricks für das digitale Leben
  • Der IT-Sicherheitsleitfaden
  • Firewall-Systeme – Sicherheit für Internet und Intranet, E-Mail-Security, Virtual Private Network, Intrusion-Detection-System, Personal Firewalls

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

Marktplatz IT-Sicherheit

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