RSA-Kryptosystem ausprobieren

Erzeugung eines RSA-Schlüsselpaars

Um ein RSA-Schlüsselpaar zu erzeugen, müssen zunächst zwei große Primzahlen p und q bestimmt werden. Dies Primzahlen sollten nicht zu nahe beieinander liegen, aber von ähnlicher Größenordnung sein. Die Primzahlen sollten mindestens 1024 Bit lang sein. Nun werden die Zahlen n = p*q und Φ(n) = (p-1)*(q-1) berechnet.

Schließlich müssen die beiden Zahlen f und g gewählt werden. Die Zahl f soll zwischen 1 und Φ(n) liegen und teilerfremd zu Φ(n) sein, also ggT(f, Φ(n)) = 1.

Die Zahl g muss jetzt das multiplikative Inverse zu f bezüglich (mod Φ(n)) sein, dass gilt f*g ≡ 1 (mod Φ(n)).

Der öffentliche Schlüssel setzt sich aus n und f zusammen, der private Schlüssel aus n und g. Die Zahlen p, q und Φ(n) werden nicht mehr benötigt und sollten gelöscht werden. Sind p und q groß genug gewesen, dauert es mit der heutigen Rechenkapazität Jahrhunderte oder länger, um von f auf g zu schließen. Somit lässt sich der private Schlüssel praktisch nicht aus dem öffentlichen Schlüssel berechnen.

Bei der Schlüsselerzeugung ist darauf zu achten, dass der Wert für f groß genug ist. Ist f < 1/3*n1/4 besteht eine sehr hohe Wahrscheinlichkeit, dass die von Michael J. Wiener entwickelte Wiener Attacke gelingt und sich f aus g und N berechnen lässt.