RSA-Kryptosystem
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.
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 = me mod N
Entschlüsseln von Nachrichten
Der Schlüsseltext c kann durch modulare Exponentiation wieder entschlüsselt werden:
- m = cd 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
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.