Kryptographie-Grundlagen

Schlüsselgenerierung bei RSA

1. Schritt: Der Sender, A, wählt zwei große Primzahlen p und q. A berechnet das Produkt n = p * q. Wichtig: p und q müssen sich in ihrer Länge deutlich unterscheiden. Andernfalls könnten sie aus n leicht bestimmt werden, indem in der Umgebung von (Wurzel aus n) alle Primzahlen getestet werden.

2. Schritt: A wählt seinen öffentlichen Schlüssel e so, dass e und (p-1) * (q-1) keinen gemeinsamen Primfaktor außer der 1 haben.

3. Schritt: A berechnet seinen privaten Schlüssel d mit Hilfe der Formel: ed = 1 mod ((p-1) * (q - 1)). Das bedeutet: Zur Berechnung seines privaten Schlüssels ist die Kenntnis von p und q erforderlich, die daher ebenfalls geheim gehalten werden müssen.

Die Zahlen e und n bilden den öffentlichen Schlüssel, d ist der private Schlüssel. Die beiden, zur Generierung der Schlüssel verwendeten Primzahlen, können jetzt verworfen werden, denn sie werden nicht mehr benötigt. Selbstverständlich dürfen sie niemals bekannt gegeben werden.

Zur Verschlüsselung einer Nachricht wird diese in Blöcke zerlegt, deren Länge sich aus der größten Zweierpotenz bestimmt, die kleiner ist, als n Stellen hat. Die Verschlüsselung erfolgt mit:

Die Entschlüsselung der verschlüsselten Blöcke ci erfolgt mit