RSA verschlüsselung (problem mit aufgabe)

[pong]

oder auch

Der Algorithmus

Der Algorithmus besteht aus zwei Teilen. Neben dem eigentlichen
Chiffrieralgorithmus ist die Schlüsselerzeugung von großer Wichtigkeit für die Sicherheit des Verfahrens.

Schlüsselerzeugung:

1. Wähle zufällig zwei große Primzahlen p und q.
Die Länge der Zahlen sollte zwischen 384 und 512 Bit liegen.

2. Berechne n = pq (n hat dann eine Länge von 512 bis 1024 Bit).

3. Wähle eine kleine ungerade natürliche Zahl e, die zu
j(n)=(p - 1)(q - 1) relativ prim ist, d.h. es gilt ggT(e,j(n)) = 1

4. Berechne d als Lösung der Gleichung ed = 1 mod j(n).
Es existiert d und ist eindeutig bestimmt. Das d kann berechnet werden mit dem erweiterten Euklidischen Algorithmus.

5. Gib das Paar P = (e, n) bekannt als öffentlichen Schlüssel.

6. Halte das Paar S = (d, n) geheim als geheimen Schlüssel.


Anwendung von RSA:
Verschlüsseln: Die Nachricht M aus Zn wird codiert durch
E(M) = M^e mod n.

Entschlüssseln: Ein Chiffretext C aus Zn wird decodiert durch
D(C) = C^d mod n.

Beispiel mit kleinen Zahlen:
Wir wählen p = 61 und q = 97 und erhalten
n = pq = 5917,
sowie
j(n) = (p - 1)(q - 1) = 60 - 96 = 5760.
Als Wert für e wählen wir 47 (teilerfremd zu 5760) und berechnen mit
dem erweiterten Euklidischen Algorithmus
d = 47^-1 mod 5760 = 1103.
Nun werden p und q vernichtet und (47,1103) als öffentlicher Schlüssel bekannt gegeben. Zur Verschlüsselung der Nachricht
M = 348613407195771184
wird diese in Blöcke zerlegt, so dass jeder Block kleiner als
n = 5917 ist.
Wir wählen als Blocklänge drei Ziffern und schreiben
M = 348 613 407 195 771 184.
Der erste Block wird verschlüsselt:
348^47 mod 5917 = 4479.
Der Chiffretext lautet dann
C = 4479 1333 3931 2523 3725 1038.
Das Entschlüsseln des ersten Blocks ergibt
4479^1103 mod 5917 = 348.
Der RSA-Algorithmus ist korrekt. Die Funktionen E und D sind invers zueinander und es gilt für beliebiges M aus Zn:
D(E(M)) = E(D(M)) = M.

pong