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

Schlüsselgenerierung

1. Wähle zufällig und stochastisch unabhängig zwei Primzahlen p ≠ q und berechne N = p q.
2. Berechne φ(N) = (p-1)(q-1), wobei φ für die Eulersche φ-Funktion steht.
3. Wähle ein e > 1 und teilerfremd zu φ(N).
4. 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

1. P=11, q=13
2. N = 11*13 = 143
3. φ(N) = 10*12 = 120
4. 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
   
5. 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