RSA-Codierung

Verschlüsselung - Chiffrierung

Wir wählen zwei Primzahlen p und q - Mathematica unterstützt mit Befehlen PrimeQ[z] und NextPrime[z] bzw. PreviousPrime[z] - der Überprüfung, ob eine Zahl z eine Primzahl ist bzw. der Berechnung der zur eingegebenen natürlichen Zahl nächstgelegenen Primzahl größer z (Next) oder kleiner z (Previous).
Anschließend erzeugen wir die Produkte n = p q und m = (p-1) (y-1).

z1 = 24201842; p = NextPrime[z1]

PrimeQ[p]

z2 = 51200499; q = NextPrime[z2]

PrimeQ[q]

n = p q

m = (p - 1) (q - 1)

Wir brauchen neben n noch den zweiten Teil des öffentlichen Schlüssels, eine Zahl a, die teilerfremd zu m is. Die Überprüfung geht über die Frage: ist der größte gemeinsame Teiler gleich 1, GGT(m,a) = 1, Mathematica Funktion dazu lautet GCD[a,b].
Wir wählen eine beliebige Zahl, erzeugen die nächstgelegene Primzahl und überprüfen den GGT.

z3 = 7812; a = NextPrime[z3]

GCD[m, a]

Damit ist mit den beiden Zahlen n und a der öffentliche Schlüssel fertiggestellt.
Die Verschlüsselung kann damit über die Formel
y = x^a mod n
erfolgen.

Wir verschlüsseln den Text "KRYPTOGRAFIE" - dazu wandeln wir die Buchstaben in Zahlen um und verwenden dafür den international üblichen ASCII-Code. Wir fassen jeweils 6 Buchstaben zu einer Gruppe zusammen und erhalten 12-stellige Zahlen.

({{K, R, Y, P, T, O}, {75, 82, 89, 80, 84, 79}, {G, R, A, F, I, E}, {71, 82, 65, 70, 73, 69}})

Wir verwenden den  Befehl
PowerMod[x, a, n]-Resultat von x^a mod n

text1 = 758289808479

text2 = 718265707369

und erhalten unsere chiffrierten Texte.

chiffre1 = PowerMod[text1, a, n]

chiffre2 = PowerMod[text2, a, n]

Entschlüsselung - Dechiffrierung

Zuerst brauchen wir den geheimen Schlüssel - passend zum öffentlichen Schlüssel a, n.

Wir wählen den geheimen Schlüssel b so, dass das Produkt a . b kongruent 1 bezüglich des Modulus m ist. Dies ist gleichbedeutend mit b = a^(-1) mod m. Dafür verwenden wir den Befehl 
PowerMod[a, -1, m]

b = PowerMod[a, -1, m]

Anschließend kann die Entschlüsselung durchgeführt werden - analog zur Verschlüsselung, aber mit Hilfe des geheimen Schlüssels!

rein1 = PowerMod[chiffre1, b, n]

rein2 = PowerMod[chiffre2, b, n]

Vergleich mit dem ursprünglichen Text:

text1 == rein1

text2 == rein2