entwickler.com

Diesmal geht es um ein asymmetrisches Verschlüsselungsverfahren: RSA. RSA wurde nach den Initialen der Nachnamen seiner Erfinder Ronald L. Rivest, Adi Shamir und Leonard Adleman benannt, die das Verfahren 1978 in "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems" PDF) vorstellten.

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 hier nicht weiter eingegangen werden soll.

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 Zahlenbeispiel:

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
 mod n.

Die Entschlüsselung erfolgt durch modulare Exponentiation mit d, für den Geheimtextblock also durch die Berechnung von
 mod n = m.

Im Zahlenbeispiel:
Verschlüsselt werden soll m=25, der öffentliche Schlüssel ist c=7 und n=33:

Geheimtext =  mod 33 = 6103515625 mod 33 = 31

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

Klartext =  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 1.024 Bit und mehr werden. Doch es gibt eine "Abkürzung":

• Mehrfaches Quadrieren führt sehr schnell zu hohen Potenzen:
  Z.B.  = ((((x²)²)²)²) * x
• Da nicht das Zwischenergebnis selbst, sondern nur der Rest benötigt wird, kann in jedem Schritt modulo n gerechnet werden:
  Z.B.  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.

Sicherheit des Verfahrens
Bei der Kryptanalyse des RSA-Verfahrens gibt es zwei Ansätze:

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

Auf die mathematischen Grundlagen soll hier nicht weiter eingegangen werden. Das Problem dabei 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 die RSA Factoring Challenge gestartet. Dabei sollen vorgegebene Zahlen mit einer Länge zwischen 576 und 2.048 Bits in ihre Primfaktoren zerlegt werden. Erfolgreich faktorisiert wurden bisher die Zahlen bis zu einer Länge von 640 Bit.

Erfolgreicher sind Angriffe auf schwache Schlüssel oder unsichere Implementierungen. Wird RSA z.B. 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 verhindert derartige Angriffe.

Dan Boneh hat 1999 einen zusammenfassenden Artikel über die Kryptanalyse von RSA veröffentlicht: "Twenty years of attacks on the RSA cryptosystem".

So lange kein effektiver Faktorisierungsalgorithmus bekannt ist, kann RSA mit ausreichend großen Schlüsseln (mindestens 1.024, besser mindestens 2.048 Bit Länge) als sicher betrachtet werden.

In der nächsten Folge geht es um die Anwendung von RSA.

Carsten Eilers