Verfahren der Kryptographie, Teil 8: RSA
RSA ist ein asymmetrisches Verschlüsselungsverfahren. Es wurde nach den Initialen der Nachnamen seiner Erfinder Ronald L. Rivest, Adi Shamir und Leonard Adleman benannt, die das Verfahren 1978 im Paper "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems" (PDF) vorgestellt haben.
Die Sicherheit des RSA-Verfahrens basiert auf der sog. Faktorisierungsannahme: Es gibt keinen effizienten Algorithmus, um eine gegebene große Zahl in ihre Primfaktoren zu zerlegen. Der RSA-Algorithmus selbst ist sehr einfach.
Schlüsselerzeugung
- Wähle zufällig und stochastisch unabhängig zwei Primzahlen p und q, p≠q
- Berechnen n = p * q und φ(n) = (p-1) * (q-1) (φ ist die Eulersche φ-Funktion)
- Wähle eine Zahl c, für die gilt 1 < c < φ(n), die teilerfremd zu φ(n) ist (d.h. der größte gemeinsame Teiler ggT(c,φ(n)) = 1)
- Berechne d aus p, q und c als
multiplikatives Inverses von c modulo φ(n), also
c * d ≡ 1 mod φ(n).
Dazu wird der erweiterte euklidische Algorithmus verwendet, auf den ich hier nicht weiter eingehe.
Der öffentliche Schlüssel (public key) besteht aus c und n, der private Schlüssel (private key) aus d und n. Meist werden auch die Faktoren p und q gespeichert, da sie bei der Entschlüsselung verwendet werden können. Ein Einsatz von RSA als Verschlüsselungssystem zeigt Abbildung 1.
Abb. 1: Das RSA-Verfahren als Verschlüsselungssystem (Konzelationssystem)
Ein Zahlenbeispiel
Das Verfahren wird viel verständlicher, wenn man es mit Zahlen betrachtet:
- Wir wählen p=3 und q=11
- n = p * q = 3 * 11 = 33,
φ(n) = (p-1) * (q-1) = (3-1) * (11-1) = 2 * 10 = 20 - c muss teilerfremd zu 20 sein, wir wählen willkürlich 7.
- Berechnung der Inversen:
Es gilt c * d ≡ 1 mod φ(n), also 7 * d ≡ 1 mod 20
Der öffentliche Schlüssel besteht also aus c=7 und n=33, der geheime Schlüssel aus d=3 und n=33.
Ver- und Entschlüsselung
Klartexte werden als Zahlen m, 0 ≤ m ≤ n, dargestellt. Zu lange Klartexte müssen ggf. in passende Blöcke aufgespalten werden.
Die Verschlüsselung erfolgt durch modulare Exponentiation mit c, für den Klartextblock m also durch die Berechnung von mc mod n.
Die Entschlüsselung erfolgt durch modulare Exponentiation mit d, für den Geheimtextblock mc also durch die Berechnung von (mc)d mod n = m.
Und wieder das Zahlenbeispiel
Betrachten wir das ganze an Hand des Zahlenbeispiels vom oben. Verschlüsselt werden soll m=25, der öffentliche Schlüssel ist c=7 und n=33:
Geheimtext = 257 mod 33 = 6103515625 mod 33 = 31
Entschlüsselt wird mit dem geheimen Schlüssel d=3 und n=33:
Klartext = 313 mod 33 = 29791 mod 33 = 25
Da diese doch sehr kleinen Zahlen schon zu großen Zwischenergebnissen führen, kann man sich vorstellen, wie groß diese bei den für RSA tatsächlich verwendeten Zahlen mit einer Länge von 2.048 Bit und mehr werden. Doch es gibt eine "Abkürzung":
- Mehrfaches Quadrieren führt sehr schnell zu hohen
Potenzen. Zum Beispiel gilt
x17 = ((((x²)²)²)²) * x - Da nicht das Zwischenergebnis selbst, sondern nur der Rest
benötigt wird, kann in jedem Schritt modulo n gerechnet
werden. Zum Beispiel gilt
x17 mod n = ((((x² mod n)² mod n)² mod n)² mod n) * x mod n
Damit muss in jedem Schritt nur mit Werten gerechnet werden, die kleiner als n sind.
Die Sicherheit des RSA-Verfahrens
Bei der Kryptanalyse des RSA-Verfahrens gibt es zwei Ansätze:
- Das sog. RSA-Problem:
Bekannt sind der öffentliche Schlüssel, bestehend aus c und n, und der Geheimtext G. Gesucht wird der dazugehörige Klartext K, für den gilt Kc ≡ G mod n.
Die Schwierigkeit liegt darin, dass es schwer ist, Wurzeln modulo n zu berechnen. - Das sog. RSA-Schlüsselproblem:
Bekannt ist der öffentliche Schlüssel, bestehend aus c und n. Gesucht wird der geheime Schlüssel d mit c * d ≡ 1 mod φ(n).
Die Schwierigkeit liegt hier darin, dass es schwer ist, φ(n) ohne Kenntnis von p und q zu berechnen und n nicht leicht zu faktorisieren ist.
Beide Probleme lassen sich in Spezialfällen lösen, ohne dass das Faktorisierungsproblem gelöst werden muss. Dazu müssen allerdings unter anderem sehr kurze private bzw. öffentliche Schlüssel verwendet werden, so dass bei ausreichend langen Schlüsseln keine Gefahr besteht.
Auf die mathematischen Grundlagen will ich jetzt nicht weiter eingehen. Das größte Problem bei allem ist, dass bisher nicht bewiesen wurde, ob die Faktorisierung tatsächlich schwer ist oder nicht. Es spricht vieles dafür, ein endgültiger Beweis steht aber noch aus.
Von den RSA Laboratories wurde 1991 die RSA Factoring Challenge gestartet. Es sollten vorgegebene Zahlen mit einer Länge zwischen 576 und 2.048 Bits in ihre Primfaktoren zerlegt werden. Bis zur Einstellung der Challenge 2007 wurden die Zahlen bis zu einer Länge von 640 Bit faktorisiert. 2009 wurde dann noch die Zahl mit der Länge von 768 Bit faktorisiert.
Erfolgreicher sind Angriffe auf schwache Schlüssel oder unsichere Implementierungen. Wird RSA zum Beispiel wie oben beschrieben als Konzelationssystem verwendet, kann ein Angreifer ausnutzen, dass RSA ein deterministisches System ist: Gleiche Klartexte ergeben gleiche Geheimtexte. Er kann einen wahrscheinlichen Klartext(block) raten und mit dem öffentlichen Schlüssel verschlüsseln. Stimmt das Ergebnis mit einem belauschten Geheimtext(block) überein, kennt er den dazu gehörenden Klartext(block). Das Hinzufügen von Zufallswerten zum Klartext (Padding) verhindert derartige Angriffe.
So lange kein effektiver Faktorisierungsalgorithmus bekannt ist, kann RSA mit ausreichend großen Schlüsseln (mindestens 2.048 Bit Länge, besser mehr) als sicher betrachtet werden. Kurze Schlüssel wie die anfangs üblichen 768-Bit-Schlüssel sind dagegen nicht mehr sicher, aber darauf komme ich später noch mal zurück.
In der nächsten Folge geht es um die Anwendung von RSA.
Trackbacks
Dipl.-Inform. Carsten Eilers am : Verfahren der Kryptographie, Teil 8: RSA als digitales Signatursystem
Vorschau anzeigen
Dipl.-Inform. Carsten Eilers am : Verfahren der Kryptographie, Teil 10: RSA absichern
Vorschau anzeigen
Dipl.-Inform. Carsten Eilers am : Verfahren der Kryptographie, Teil 14: Hashfunktionen - Einführung
Vorschau anzeigen
Dipl.-Inform. Carsten Eilers am : Kryptographie - Ein Überblick
Vorschau anzeigen
www.ceilers-news.de am : PingBack
Die Anzeige des Inhaltes dieses Trackbacks ist leider nicht möglich.Dipl.-Inform. Carsten Eilers am : Drucksache: PHP Magazin 1.18 - Welche Kryptoverfahren sollte man verwenden bzw. meiden?
Vorschau anzeigen
Dipl.-Inform. Carsten Eilers am : Drucksache: Windows Developer 1.18 - Sicherheit von Kryptoverfahren
Vorschau anzeigen
Dipl.-Inform. Carsten Eilers am : Drucksache: Entwickler Magazin Spezial Vol. 16: Security
Vorschau anzeigen
entwickler.de am : PingBack
Die Anzeige des Inhaltes dieses Trackbacks ist leider nicht möglich.