Zum Inhalt springen

RSA-Verfahren

Aus FLBK-Wiki

Das RSA-Verfahren war das erste praxistaugliche asymmetrische Verschlüsselungsverfahren. Es steckt bis heute in vielen Abläufen für sichere Verbindungen, digitale Signaturen und Zertifikate.

Definition

Das RSA-Verfahren ist ein asymmetrisches Verschlüsselungsverfahren. Ronald Rivest, Adi Shamir und Leonard Adleman haben es 1977 vorgestellt, die Anfangsbuchstaben ihrer Namen ergeben den Namen des Verfahrens.

Jeder Teilnehmer besitzt ein Schlüsselpaar:

  • den öffentlichen Schlüssel [math]\displaystyle{ (e; N) }[/math], den jeder kennen darf,
  • den privaten Schlüssel [math]\displaystyle{ (d; N) }[/math], den nur der Besitzer kennt.

Die Zahl [math]\displaystyle{ N }[/math] heißt RSA-Modul. In anderen Texten heißen oft auch die Zahlen [math]\displaystyle{ e }[/math] und [math]\displaystyle{ d }[/math] allein öffentlicher und privater Schlüssel. Nachrichten sind Zahlen [math]\displaystyle{ m }[/math] mit [math]\displaystyle{ 0 \le m < N }[/math]. Texte werden vorher in Zahlen umgewandelt.

Schlüsselerzeugung

  1. Zwei verschiedene große Primzahlen [math]\displaystyle{ p }[/math] und [math]\displaystyle{ q }[/math] wählen.
  2. Den RSA-Modul berechnen: [math]\displaystyle{ N = p \cdot q }[/math].
  3. Den Wert der eulerschen φ-Funktion berechnen: [math]\displaystyle{ \varphi(N) = (p - 1) \cdot (q - 1) }[/math].
  4. Eine Zahl [math]\displaystyle{ e }[/math] mit [math]\displaystyle{ 1 < e < \varphi(N) }[/math] wählen, die zu [math]\displaystyle{ \varphi(N) }[/math] teilerfremd ist: [math]\displaystyle{ \operatorname{ggT}(e; \varphi(N)) = 1 }[/math].
  5. Die Zahl [math]\displaystyle{ d }[/math] berechnen, für die [math]\displaystyle{ e \cdot d \equiv 1 \pmod{\varphi(N)} }[/math] gilt. Sie ist das modulare Inverse von [math]\displaystyle{ e }[/math] zum Modul [math]\displaystyle{ \varphi(N) }[/math] und wird mit dem erweiterten euklidischen Algorithmus berechnet.

Veröffentlicht wird [math]\displaystyle{ (e; N) }[/math]. Geheim bleiben [math]\displaystyle{ d }[/math], die beiden Primzahlen und [math]\displaystyle{ \varphi(N) }[/math].

Verschlüsseln und Entschlüsseln

Der Sender verschlüsselt die Nachricht [math]\displaystyle{ m }[/math] mit dem öffentlichen Schlüssel des Empfängers:

[math]\displaystyle{ c = m^e \bmod N }[/math]

Der Empfänger entschlüsselt den Geheimtext [math]\displaystyle{ c }[/math] mit seinem privaten Schlüssel:

[math]\displaystyle{ m = c^d \bmod N }[/math]

Die Potenzen werden mit dem wiederholten Quadrieren und Multiplizieren berechnet (siehe Square-and-Multiply).

Korrektheit

Wegen [math]\displaystyle{ e \cdot d \equiv 1 \pmod{\varphi(N)} }[/math] gibt es eine ganze Zahl [math]\displaystyle{ k }[/math] mit [math]\displaystyle{ e \cdot d = 1 + k \cdot \varphi(N) }[/math]. Beim Entschlüsseln entsteht

[math]\displaystyle{ c^d \equiv \left(m^e\right)^d = m^{e \cdot d} = m^{1 + k \cdot \varphi(N)} \equiv m \pmod{N} }[/math]

Der letzte Schritt folgt aus dem Satz von Euler, wenn [math]\displaystyle{ m }[/math] und [math]\displaystyle{ N }[/math] teilerfremd sind. Für einen RSA-Modul lässt sich zeigen, dass die Gleichung auch für alle übrigen Nachrichten gilt. Weil [math]\displaystyle{ m }[/math] kleiner als [math]\displaystyle{ N }[/math] ist, liefert die Rechnung genau die Nachricht [math]\displaystyle{ m }[/math].

Sicherheit

Ein Angreifer kennt den öffentlichen Schlüssel [math]\displaystyle{ (e; N) }[/math] und den Geheimtext [math]\displaystyle{ c }[/math]. Um [math]\displaystyle{ d }[/math] zu berechnen, braucht er [math]\displaystyle{ \varphi(N) }[/math], und dafür die Primzahlen [math]\displaystyle{ p }[/math] und [math]\displaystyle{ q }[/math]. Er müsste also [math]\displaystyle{ N }[/math] in seine Primfaktoren zerlegen.

  • Einwegfunktion mit Falltür: Zwei Primzahlen zu multiplizieren ist leicht. Für die Umkehrung, die Primfaktorzerlegung einer großen Zahl, ist kein schnelles Verfahren bekannt. Die Falltür ist die Kenntnis von [math]\displaystyle{ p }[/math] und [math]\displaystyle{ q }[/math].
  • Schlüssellänge: Im Jahr 2020 wurde ein RSA-Modul mit 829 Bit (250 Dezimalstellen) faktorisiert. Das Bundesamt für Sicherheit in der Informationstechnik (BSI) empfiehlt einen Modul von mindestens 3000 Bit (Technische Richtlinie TR-02102-1, Version 2026-01).
  • Kleine Zahlen: Rechenbeispiele mit zwei- bis vierstelligen Zahlen zeigen nur den Ablauf. Ihr Modul lässt sich sofort faktorisieren.
  • Auffüllen der Nachricht: In der beschriebenen Grundform ergibt dieselbe Nachricht immer denselben Geheimtext, und kurze Nachrichten lassen sich durch Probieren erraten. In der Praxis wird die Nachricht deshalb vor dem Verschlüsseln mit Zufallswerten aufgefüllt.
  • Echtheit des Schlüssels: Der Sender muss sicher sein, dass der öffentliche Schlüssel wirklich dem Empfänger gehört (siehe Zertifikat und Man-in-the-Middle-Angriff).

RSA rechnet viel langsamer als symmetrische Verfahren. Große Datenmengen werden deshalb mit einem hybriden Verfahren verschlüsselt. Mit vertauschten Rollen der beiden Schlüssel dient RSA auch zum Signieren (siehe Digitale Signatur).

Beispiele

Schlüsselpaar erzeugen

Bob erzeugt ein Schlüsselpaar.

  1. Primzahlen wählen: [math]\displaystyle{ p = 7 }[/math] und [math]\displaystyle{ q = 19 }[/math]
  2. RSA-Modul berechnen: [math]\displaystyle{ N = 7 \cdot 19 = 133 }[/math]
  3. [math]\displaystyle{ \varphi(N) = (7 - 1) \cdot (19 - 1) = 6 \cdot 18 = 108 }[/math]
  4. [math]\displaystyle{ e }[/math] wählen, teilerfremd zu 108: [math]\displaystyle{ e = 5 }[/math], denn [math]\displaystyle{ \operatorname{ggT}(5; 108) = 1 }[/math]
  5. [math]\displaystyle{ d }[/math] berechnen mit [math]\displaystyle{ 5 \cdot d \equiv 1 \pmod{108} }[/math]: Der erweiterte euklidische Algorithmus liefert [math]\displaystyle{ d = 65 }[/math]. Probe: [math]\displaystyle{ 5 \cdot 65 = 325 = 3 \cdot 108 + 1 }[/math]

Öffentlicher Schlüssel: [math]\displaystyle{ (e; N) = (5; 133) }[/math]. Privater Schlüssel: [math]\displaystyle{ (d; N) = (65; 133) }[/math]. Die Werte [math]\displaystyle{ p }[/math], [math]\displaystyle{ q }[/math] und [math]\displaystyle{ \varphi(N) }[/math] werden nicht mehr gebraucht und bleiben geheim oder werden gelöscht.

Nachricht verschlüsseln

Alice verschlüsselt die Nachricht [math]\displaystyle{ m = 4 }[/math] mit Bobs öffentlichem Schlüssel [math]\displaystyle{ (5; 133) }[/math]:

[math]\displaystyle{ c = m^e \bmod N = 4^{5} \bmod 133 }[/math]
[math]\displaystyle{ 4^{1} = 4 }[/math]
[math]\displaystyle{ 4^{2} \equiv 4 \cdot 4 = 16 }[/math]
[math]\displaystyle{ 4^{3} \equiv 16 \cdot 4 = 64 }[/math]
[math]\displaystyle{ 4^{4} \equiv 64 \cdot 4 = 256 \equiv 123 }[/math]
[math]\displaystyle{ 4^{5} \equiv 123 \cdot 4 = 492 \equiv 93 }[/math]

Der Geheimtext ist [math]\displaystyle{ c = 93 }[/math].

Geheimtext entschlüsseln

Bob entschlüsselt mit seinem privaten Schlüssel [math]\displaystyle{ (65; 133) }[/math]:

[math]\displaystyle{ m = c^d \bmod N = 93^{65} \bmod 133 }[/math]

Der Exponent ist [math]\displaystyle{ 65 = 1000001_2 }[/math]. Mit Square-and-Multiply sind nur 6 Quadrierungen und 1 Multiplikation nötig:

Bit Potenz Quadrat mod 133 Zwischenergebnis mod 133
1 [math]\displaystyle{ 93^{1} }[/math] [math]\displaystyle{ 93 }[/math] [math]\displaystyle{ 93 }[/math]
0 [math]\displaystyle{ 93^{2} }[/math] [math]\displaystyle{ 93^{2} = 8649 \equiv 4 }[/math] –
0 [math]\displaystyle{ 93^{4} }[/math] [math]\displaystyle{ 4^{2} = 16 }[/math] –
0 [math]\displaystyle{ 93^{8} }[/math] [math]\displaystyle{ 16^{2} = 256 \equiv 123 }[/math] –
0 [math]\displaystyle{ 93^{16} }[/math] [math]\displaystyle{ 123^{2} = 15129 \equiv 100 }[/math] –
0 [math]\displaystyle{ 93^{32} }[/math] [math]\displaystyle{ 100^{2} = 10000 \equiv 25 }[/math] –
1 [math]\displaystyle{ 93^{64} }[/math] [math]\displaystyle{ 25^{2} = 625 \equiv 93 }[/math] [math]\displaystyle{ 93 \cdot 93 = 8649 \equiv 4 }[/math]

Das letzte Zwischenergebnis ist der Klartext [math]\displaystyle{ m = 4 }[/math].

Kleinen Modul faktorisieren

Eve kennt nur den öffentlichen Schlüssel [math]\displaystyle{ (5; 133) }[/math]. Weil 133 klein ist, findet sie die Primfaktoren durch Probieren: 133 ist nicht durch 2, 3, 5 teilbar, aber [math]\displaystyle{ 133 = 7 \cdot 19 }[/math].

Damit berechnet Eve [math]\displaystyle{ \varphi(N) = 6 \cdot 18 = 108 }[/math] und daraus wie Bob die Zahl [math]\displaystyle{ d = 65 }[/math] des privaten Schlüssels. Der Schutz ist gebrochen. Bei einem Modul der empfohlenen Länge von 3000 Bit, das sind rund 900 Dezimalstellen, gelingt die Primfaktorzerlegung mit den bekannten Verfahren nicht.