RSA

RSA ist ein asymmetrisches Verschlüsselungsverfahren. Es ist nach seinen Erfindern Ronald L. Rivest, Adi Shamir and Leonard M. Adleman benannt.

Das Verfahren wurde 1977 entwickelt und basiert auf der Idee, dass die Faktorisierung einer Zahl eine sehr aufwändige Angelegenheit ist, während das Erzeugen der Zahl durch Multiplikation zweier Primzahlen trivial ist.

Table of contents

1 Schlüsselgenerierung
2 Verschlüsseln von Nachrichten
3 Entschlüsseln von Nachrichten
4 Beispiel
5 Sicherheit

Schlüsselgenerierung

Wähle zufällig und stochastisch unabhängig zwei Primzahlen p ≠ q und berechne N = p q.
Berechne φ(N) = (p-1)(q-1), wobei φ für die Eulersche φ-Funktion steht.
Wähle ein e > 1 und teilerfremd zu φ(N).
Berechne d, so dass e × d ≡ 1 mod φ(N), beispielsweise mittels des erweiterten Euklidischen Algorithmus

N und e bilden den öffentlichen, d, p und q den geheimen Schlüssel.

Verschlüsseln von Nachrichten

Um eine Nachricht m zu veschlüsseln, muss sie zunächst durch eine zu vereinbarende reversible Kodierung in eine n < N umgerechnet werden. Der Schlüsseltext c berechnet sich wie folgt:

c = m^e mod N

Entschlüsseln von Nachrichten

Der Schlüsseltext c kann durch modulare Exponentiation wieder entschlüsselt werden:

m = c^d mod N

Beispiel

P=11, q=13
N = 11*13 = 143
φ(N) = 10*12 = 120
e = 23
120 = 5 * 23 + 5 <=> 5 = 120 - 5 * 23
23 = 4 * 5 + 3 <=> 3 = 23 - 4 * 5
5 = 1 * 3 + 2 <=> 2 = 5 - 1 * 3
3 = 1 * 2 + 1 <=> 1 = 3 - 1 * 2
1 = 3-1*2 = 3-1*(5-1*3)
1 = 2*3-1*5 = 2*(23-4*5)-1*5
1 = 2*23-9*5 = 2*23-9*(120-5*23)
1 = 47*23-9*120
1 = (47*23) mod 120
d=47

Sicherheit

Theoretische Sicherheit

Die Sicherheit basiert darauf, dass der Angreifer d nicht kennt. Um d zu berechnen benötigt er φ(N). φ(N) ist aber für grosse Zahlen nicht effizient berechenbar. Nur, wer die Primfaktoren p und q kennt, kann wie oben gezeigt φ(N) leicht berechnen. Die Zerlegung von N in die zufällig gewählten Primfaktoren p und q ist ebenfalls nicht effizient lösbar, aber einfacher als die Berechnung der φ-Funktion. Man sagt daher, die Sicherheit von RSA(und der meissten anderen asymmetrischen Verfahren) beruht auf dem Problem der Primfaktorzerlegung.

Praktische Sicherheit

Bei der RSA-Verschlüsselung findet eine deterministische Substitution des Klartextes durch den Ciphertext statt. Es ist daher grundsätzlich möglich, den Klartext durch Wahrscheinlichkeitsanalyse und Known-Plaintext-Angriffe zu ermitteln, da ein Klartext immer genau einem Ciphertext zugeordnet wird(ECB, Electronic Codebook). Das auf RSA aufbauende Übertragunsprotokoll muss daher für Abhilfe sorgen, zum Beispiel in Form von pseudo-Zufall, der an im Protokollstandard definierten Stellen eingefügt und vom Empfänger nach Entschlüsselung wieder entfernt wird.