Der RSA Algorithmus

RSA wurde von Rivest, Shamir und Adleman 1977 als ein public key Verfahren entwickelt. Dieser Algorithmus ermöglicht sowohl Verschlüsselungen als auch digitale Signaturen. Die Sicherheit dieses Algorithmus beruht auf der Schwierigkeit der Faktorisierung großer Zahlen. Das ist besonders schwierig wenn diese große Zahl das Produkt zweier ungefähr gleich großer Primzahlen ist. Große Zahlen sind in diesem Fall mehrere hundert dezimal Stellen lang.

Um einen Schlüssel zu erzeugen wählt man 2 zufällige, große Primzahlen $p$ und $q$ Nun berechnet man das Produkt $n=p x q$. Als nächstes wählt man den öffentlichen Exponenten $e$, sodaß der größte gemeinsame Teiler von $e$ und $(p-1)x(q-1)$ gleich $1$ ist. Um eine schnelle Verschlüsselung zu gewährleisten wird $e$ meist niedrig gewählt. der geheime Exponent berechnet sich dann :

$d= e-1(mod [(p-1)(q-1)])$

Jetzt ist der öffentliche Schlüssel $n$ und $e$, der geheime Schlüssel ist $d$.

Die Verschlüsselung der Nachricht $M$ erfolgt dann durch:

$C= M^e mod n$

Die Entschlüsselung wird dann durch:

$M=C^d mod n$ berechnet

Die Erstellung einer Signatur verläuft genau umgekehrt:

$S=H^d mod n$ wobei $H$ der Hashwert der Nachricht ist. Die Verifikation erfolgt durch überprüfen ob $H=S^e mod n$ gleich dem Hashwert ist.

Übliche Längen für den Modulus sind 512, 1024 und 2048 Bit, wobei 512 Bit nicht wirklich empfohlen werden kann.