RSA

Schlüsselerzeugung

Wir wählen mit Hilfe eines Primzahltest verschieden Primzahlen $p_A,q_A$ und berechnen

Dabei sollten $p_A$ und $q_A$ so gewählt werden (groß), sodass man die Primfaktorzerlegung von $N_A$ praktisch nicht berechnen kann.

Außerdem wählen wir eine Zahl $e_A>1$ mit

und berechnen zum Beispiel mit Hilfe des erweiterten euklidischen Algorithmus ein $d_A$ mit

Also Inverses von $e_A$.

Der Public Key ist das Tupel $(N_A, e_A)$, wobei $(N_A, d_A)$ der Private Key ist.

Verschlüsselung

Wir besorgen uns einen öffentlichen Schlüssel $(N_A, e_A)$ und wandeln unseren Klartext in eine Zahlenfolge $a_1,\dots$ mit $a_i\leq N_A-1$ um.

Dann berechnen wir mit der Square-And-Multiply-Methode den Chiffretext mit

Entschlüsselung

Wir erhalten eine Zahlenfolge $b_1,\dots$ und berechnen mit unserem privaten Schlüssel $(N_a, d_A)$ mit der Square-And-Multiply-Methode den Klartext mit

Die Zahlenfolge muss dann nur noch in Text umgewandelt werden.

Anwendung

Das BSI empfiehlt eine Schlüssellänge $N_A$ von 3000 Bits.

Es ist bis heute kein Verfahren bekannt um

bei Kentniss von $N$ und $e$ für $b$ zu lösen, wenn man die Faktorisierung von $N$ nicht kennt.

Ansonsten kann man mit dem euklidischen Algorithmus ein $d$ mit

berechnen (Modulo Invertierbarkeit). Dabei ist

eine Lösung der Gleichung. Auch den privaten Schlüssel kann man ohne Faktorisierung nicht berechnen.