RSA-Verfahren
Das im Kapitel Zahlentheorie beschriebene RSA-Verfahren ist das
populärste asymmetrische Verschlüsselungsverfahren.
1. Voraussetzungen: Man wählt zwei große Primzahlen 
und 
und
.
Dabei soll 
gelten;
und
müssen sich als Dezimalzahlen in ihrer
Länge um einige Stellen unterscheiden; die Differenz zischen
und
darf aber
auch nicht zu groß sein.
Weiterhin sollen 
und 
große Primfaktoren enthalten, und der größte
gemeinsame Teiler von
und
soll möglichst klein sein.
Man wähle ein 
,
das teilerfremd zu 
ist, und berechne ein 
mit
modulo 
.
Dann bilden 
und 
den öffentlichen Schlüssel und
den privaten Schlüssel.
2. Verschlüsselungsoperation:
 |
(5.290a) |
3. Entschlüsselungsoperation:
 |
(5.290b) |
Damit gilt 
für jede Nachricht 
.
Die zur Verschlüsselung verwendete Funktion ist für 
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.
