Document ID: /fineweb-2-swissfilter-quality_10-filterrobots/filtered/03558.jsonl.gz/432

Das 1977 von den drei Mathematikern Rivest, Shamir und Adleman entwickelte RSA galt damals als erstes asymmetrisches Verschlüsselungs-Verfahren. Es basiert auf dem aktuellen Wissensstand, dass die Faktorisierung einer grossen Zahl, also ihre Zerlegung in ihre Primfaktoren, eine sehr aufwändige Angelegenheit ist, während das Erzeugen einer Zahl durch Multiplikation zweier Primzahlen recht einfach ist.
Die eigentliche Ver- und Entschlüsselungs-Funktion ist sehr einfach. Einzig das Erzeugen der Schlüssel ist etwas komplizierter. Der öffentliche Schlüssel besteht aus zwei Zahlen: dem RSA-Modul
# Verschlüsseln
Um eine Nachricht
und erhält so aus dem Klartext
# Entschlüsseln
Der Geheimtext
mit dem nur ihm bekannten Wert
# Schlüssel generieren
Das komplette Schlüsselpaar besteht aus den drei Zahlen
- Wähle zufällig zwei Primzahlen
und so dass .
- Berechne den RSA-Modul
- Berechne die Eulersche
-Funktion von :
- Wähle eine zu
teilerfremde Zahl , für die gilt
- Berechne den Entschlüsselungsexponenten
als Multiplikativ Inverses von bezüglich des Modulus . Es soll also die folgende Kongruenz gelten:
Die Zahlen
Beispiel:
- Wir wählen
und für die beiden Primzahlen.
- Der RSA-Modul ist
- Die Eulersche
-Funktion nimmt damit den Wert an.
- Die Zahl
muss zu teilerfremd sein. Wir wählen .
Damit bilden
und den öffentlichen Schlüssel.
- Berechnung der Inversen zu
:
Es gilt:
bzw. im konkreten Beispiel:
Mit dem erweiterten euklidischen Algorithmus berechnet man nun die Faktoren
und , so dass die Gleichung aus dem Beispiel wie folgt aussieht:
bildet zusammen mit dem schon berechneten den privaten Schlüssel, während nicht weiter benötigt wird.