RSA Verfahren

Kategorisierung:	Moderne asymmetrische Chiffre
Siehe auch	Primzahlenfaktoren, Primzahlen (Alphabet und Position)
Herkunft / Verwendung:	Das RSA Verfahren ist nach ihren Entwicklern Ronald Rivest, Adi Shamir und Leonard Adleman benannt und ist ein asymmetrisches kryptografisches Verfahren, das sowohl zum Verschlüsseln als auch zum digitalen Signieren verwendet werden kann. Es verwendet ein Schlüsselpaar, bestehend aus einem privaten Schlüssel, der zum Entschlüsseln oder Signieren von Daten verwendet wird, und einem öffentlichen Schlüssel, mit dem man verschlüsselt oder Signaturen prüft. Der private Schlüssel wird geheim gehalten und kann nur mit extrem hohem Aufwand aus dem öffentlichen Schlüssel berechnet werden. Nachdem Whitfield Diffie und Martin Hellman eine Theorie zur Public-Key-Kryptografie veröffentlicht hatten, versuchten die drei Mathematiker Rivest, Shamir und Adleman am MIT, die Annahmen von Diffie und Hellman zu widerlegen. Nachdem sie den Beweis bei verschiedenen Verfahren durchführen konnten, stießen sie schließlich auf eines, bei dem sie keinerlei Angriffspunkte fanden. Hieraus entstand 1977 RSA, das erste veröffentlichte asymmetrische Verschlüsselungsverfahren.

Beschreibung RSA Algorithmus

Die Verschlüsselung und die Signatur mit RSA basiert auf einer Einwegfunktion mit Falltür (engl. trapdoor one-way permutation, kurz TOWP). Die Einwegeigenschaft ist der Grund, warum die Entschlüsselung (bzw. das Signieren) ohne den geheimen Schlüssel (die Falltür) schwierig ist.

Während es einfach und schnell ist, zwei Primzahlen zu multiplizieren, ist es schwierig und sehr zeitaufwendig aus dem Produkt durch Primfaktorenzerlegung die Faktoren zu berechnen.

Der öffentliche Schlüssel (public key) ist ein Zahlenpaar (e, N) und der private Schlüssel (private key) ist ebenfalls ein Zahlenpaar (d, N), wobei N bei beiden Schlüsseln gleich ist. Man nennt N den RSA-Modul, e den Verschlüsselungsexponenten und d den Entschlüsselungsexponenten. Diese Zahlen werden durch das folgende Verfahren erzeugt:

• Wähle zufällig und stochastisch unabhängig zwei Primzahlen p ungleich q. Diese sollen die gleiche Größenordnung haben, aber nicht zu dicht beieinander liegen, so dass der folgende Rahmen ungefähr eingehalten wird: 0,1 < |log₂ p - log₂ q| <30. (In der Praxis erzeugt man dazu so lange Zahlen der gewünschten Länge und führt mit diesen anschließend einen Primzahltest durch, bis man zwei Primzahlen gefunden hat.)
• Berechne den RSA-Modul: N = p ∗ q
• Berechne die Eulersche φ-Funktion von N: φ(N) = (p-1) ∗ (q-1)
• Wähle eine zu φ(N) teilerfremde Zahl e, für die gilt: 1 < e < φ(N).
• Berechne den Entschlüsselungsexponenten d als Multiplikatives Inverses von e bezüglich des Moduls φ(N).
  Es soll also die folgende Kongruenz gelten: e ∗ d ≡ 1 (mod φ(N))

Die Zahlen p, q und φ(N) werden nicht mehr benötigt und können nach der Schlüsselerstellung gelöscht werden. Es ist jedoch relativ einfach, diese Werte aus e, d und N zu rekonstruieren. Aus Effizienzgründen wird e klein gewählt, üblich ist die 4. Fermat-Zahl 2¹⁶+1 = 65537. Kleinere Werte von e können zu Angriffsmöglichkeiten führen. Bei Wahl eines d mit weniger als einem Viertel der Bits des RSA-Moduls kann d – sofern nicht bestimmte Zusatzbedingungen erfüllt sind – mit einem auf Kettenbrüchen aufbauenden Verfahren effizient ermittelt werden.

Beispiel:

• Wir wählen p = 11 und q = 13 für die beiden Primzahlen.
• Der RSA-Modul ist N = p ∗ q = 143.
• Die eulersche f-Funktion nimmt damit den Wert φ(N) =φ(143) = (p-1) ∗ (q-1) = 120 an.
• Die Zahl e muss zu 120 teilerfremd sein. Wir wählen e = 23. Damit bilden e = 23 und N = 143 den öffentlichen Schlüssel.
• Berechnung der Inversen zu e bezüglich mod φ(N): Es gilt: e ∗ d + k ∗ φ(N) = 1 = ggT(e,φ(N))
  bzw. im konkreten Beispiel: 23 ∗ d + k ∗ 120 = 1 = ggT(23, 120).
  Mit dem erweiterten euklidischen Algorithmus berechnet man nun die Faktoren d=47 und k=-9, so dass die Gleichung aus dem Beispiel wie folgt aussieht: 23 ∗ 47 + (-9 )∗ 120 = 1
  
  d ist der geheime Exponent, während k nicht weiter benötigt wird.

Um eine Nachricht m zu verschlüsseln, verwendet der Absender die Formel c ≡ m^e (mod N) und erhält so aus der Nachricht m den Geheimtext c. Die Zahl m muss dabei kleiner sein als der RSA-Modul N.

Der Geheimtext c kann durch modulare Exponentiation wieder zum Klartext m entschlüsselt werden. Der Empfänger benutzt die Formel m ≡ c^d (mod N) mit dem nur ihm bekannten Wert d sowie N.

Quellen, Literaturverweise und weiterführende Links

Singh, Simon: Geheime Botschaften, Hanser Verlag 2000, S. 329
Kippenhahn, Rudolf: Verschlüsselte Botschaften, Nikol Verlag 2006, S. 291
Bauer, Friedrich L.: Entzifferte Geheimnisse, Springer Verlag 1995, S. 160
Gómez, Joan: Geheimsprachen und Decodierung, Librero Verlag 2016, S. 104
Beutelspacher, Albrecht: Geheimsprachen - Geschichte und Techniken, C. H. Beck Verlag, 2002, S. 67
Beutelspacher, Neumann und Schwarzpaul: Kryptografie in Theorie und Praxis, Vieweg Verlag 2005, S. 117-133
Ertel, Wolfgang: Angewandte Kryptographie, Hanser Verlag 2012, S. 79-86
Beutelspacher, Albrecht: Kryptologie - Eine Einführung..., Springer Spektrum Verlag 2015, S. 121
Schmeh, Klaus: Kryptografie: Verfahren - Protokolle - Infrastrukturen, dpunkt Verlag, 5. Auflage 2013, iX-Edition, S. 190
Kuhn, Nico: Das Buch der geheimen Verschlüsselungstechniken, Data Becker Verlag 2009, S. 105
Wobst, Reinhard: Abenteuer Kryptologie, Addison-Wesley-Verlag 2001, S. 162