Um das RSA - Verfahren zu verstehen brauchst Du ein paar Grundlagen.
Primzahlen
Primzahlen, sind Zahlen, die nur durch 1 und sich selbst teilbar sind. Die ersten 13 Primzahlen lauten 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, ...
Teilbarkeit
Die Teiler einer Zahl sind die Zahlen, durch welche man die Zahl ohne Rest teilen kann.
Zum Beispiel ist die Teilermenge von 8: T8= {1, 2, 4, 8}
Die Teilermenge von 12: T12= {1, 2, 3, 4, 6, 12}
Somit ist der größte gemeinsame Teiler von 8 und 12; ggt(8,12) = 4.
Die Zahlen 8 und 12 haben einen gemeinsamen Teiler, der ungleich 1 ist.
Definition: Zwei Zahlen heißen teilerfremd, wenn sie nur den gemeinsamen Teiler 1 haben.
Die Zahlen 5 und 18 sind teilerfremd, da sie nur die Zahl 1 als gemeinsamen Teiler haben
T5={1, 5} und T18={1, 2, 3, 6, 9, 18}. ggt(5,18) = 1
Modulo
Modulo ist eine Rechenoperation (wie z. B. Addition oder Multiplikation). Sie wird für zahlreiche Verschlüsselungsverfahren und auch für Schlüsselaustausch-Verfahren benötigt. Mit Modulo, mod, wird der Rest der ganzzahligen Division bezeichnet.
So ist z. B. 16 mod 5 = 1, denn 16 : 5 = 3 R 1
Mache ein paar Aufgaben dieses BlattesSchreibe ein Programm, das Dir den Modulo zweier Zahlen ausgibt.
Die Eulersche Phi - Funktion
Die Formel φ(n) = (p - 1)(q - 1) wird als Eulersche - Phi - Funktion bezeichnet.
Man setzt zwei Primzahlen ein und kann somit φ(n) berechnen.
Seien z. B. p = 5 und q = 7, dann ist φ(n) = (p - 1) (q - 1) = (5 - 1) (7 - 1) = 4 ⋅ 6 = 24
Für das RSA - Verfahren sucht man sich nun eine Zahl e ∈ ℕ die teilerfremd zu φ(n) ist. Es soll also ggT(e,φ(n)) = 1 gelten