RSA-Verfahren

Das RSA-Verfahren ist das populärste asymmetrische Verschlüsselungsverfahren.

1. Voraussetzungen:

Man wählt zwei große Primzahlen p und q und . Dabei soll pq > 10²⁰⁰ gelten; p und q müssen sich als Dezimalzahlen in ihrer Länge um einige Stellen unterscheiden; die Differenz zischen p und q darf aber auch nicht zu groß sein. Weiterhin sollen p-1 und q-1 große Primfaktoren enthalten, und der größte gemeinsame Teiler von p-1 und q-1 soll möglichst klein sein. Man wähle ein , das teilerfremd zu (p-1)(q-1) ist, und berechne ein d mit modulo . Dann bilden n und e den öffentlichen Schlüssel und d den privaten Schlüssel.

2. Verschlüsselungsoperation:

3. Entschlüsselungsoperation:

Damit gilt D(E(m))=E(D(m))=m für jede Nachricht .

Die zur Verschlüsselung verwendete Funktion ist für n=pq>10²⁰⁰ ein Kandidat für eine
Einwegfunktion mit Falltür. Die Zusatzinformation liegt hier in der Kenntnis der Primfaktorenzerlegung von . Ohne diese Information ist es praktisch unmöglich, die Kongruenz
zu lösen.

Das RSA-Verfahren gilt weithin als praktisch sicher, sofern die oben genannten Bedingungen erfüllt sind. Als Nachteil gegenüber anderen Verfahren sind die relativ große Schlüssellänge und die Tatsache zu beachten, daß RSA gegenüber DES um etwa den Faktor 1000 langsamer ist.