Dipl.-Inform. Carsten Eilers

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

1. Wähle zufällig und stochastisch unabhängig zwei Primzahlen p und q, p≠q
2. Berechnen n = p * q und φ(n) = (p-1) * (q-1) (φ ist die Eulersche φ-Funktion)
3. 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)
4. 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:

1. Wir wählen p=3 und q=11
2. n = p * q = 3 * 11 = 33,
   φ(n) = (p-1) * (q-1) = (3-1) * (11-1) = 2 * 10 = 20
3. c muss teilerfremd zu 20 sein, wir wählen willkürlich 7.
4. Berechnung der Inversen:
   

   Es gilt	c * d ≡ 1 mod φ(n),
   also	7 * d ≡ 1 mod 20

   Wie man in diesem Fall mit bloßen Auge sieht, ist d=3.

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 m^c mod n.

Die Entschlüsselung erfolgt durch modulare Exponentiation mit d, für den Geheimtextblock m^c also durch die Berechnung von (m^c)^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 = 25⁷ mod 33 = 6103515625 mod 33 = 31

Entschlüsselt wird mit dem geheimen Schlüssel d=3 und n=33:

Klartext = 31³ 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
  x¹⁷ = ((((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
  x¹⁷ 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:

1. 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 K^c ≡ G mod n.
   Die Schwierigkeit liegt darin, dass es schwer ist, Wurzeln modulo n zu berechnen.
2. 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.

Carsten Eilers