RSA-Kryptosystem

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

Nachdem Whitfield Diffie und Martin Hellman eine Theorie zur Public-Key-Kryptografie veröffentlicht hatten, setzten sich die drei Mathematiker hin und versuchten, die Annahmen von Diffie und Hellmann zu widerlegen. Nachdem sie den Beweis bei verschiedenen Verfahren durchführen konnten, stiessen sie schliesslich auf eines, wo sie keinerlei Angriffspunkte fanden. Hieraus entstand dann RSA.

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.

Das Verfahren wird u.a. zur Authentisierung von französischen Telefonkarten angewendet.

Schlüsselgenerierung

1. Wähle zufällig und stochastisch unabhängig zwei Primzahlen $p\neq q$, die etwa gleich lang sein sollten. Berechne $N=p\cdot q$.
2. Berechne $\varphi (N)=(p-1)(q-1)$, wobei $\varphi$ für die Eulersche φ-Funktion steht.
3. Wähle ein $e>1$ und teilerfremd zu $\varphi (N)$.
4. Berechne $d$, so dass $e\cdot d\mod \varphi (N)=1$, beispielsweise mittels des erweiterten Euklidischen Algorithmus.

$N$ und $e$ bilden den öffentlichen, $N$ und $d$ den geheimen Schlüssel. $p$ und $q$ sollten nach der Generierung des Schlüssels sofort gelöscht werden. Denn nur mit diesen ist es für Angreifer möglich, den Schlüssel zu errechnen.

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

Signieren von Nachrichten

Um eine Nachricht m zu signieren wird diese mit dem eigenen privaten Schlüssel verschlüsselt. Der Empänger holt sich den öffentlichen Schlüssel N des Senders und benutzt seinen eigenen e zum entschlüsseln. Kommt keine vernünftige Nachricht dabei raus wird die Signatur abgelehnt. Allgemein gilt:

C = M ^d mod n

M = C ^e 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

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.

Weblinks

• Weiteres Beispiel für RSA