Der RSA-Algorithmus wurde 1978 von R. Rivest, A. Shamir und L. Adleman erfunden. Das lustige an dieser Erfindung war, dass die drei eigentlich beweisen wollten, dass asymmetrische Verschlüsselung unmöglich ist. Dieses Ziel wurde knapp verfehlt. ;-)
Das grundlegende mathematische Prinzip, das diesem Alghorithmus zu Grunde liegt, ist das modulare Potenzieren:
c = me mod n bzw. m = cd mod n.
c = Cipher
m = Message
e = Public-Key
d = Private Key
n = eine lustige Zahl
Mit der ersten Formel kann ich also meine Message chiffrieren und mit der zweiten Formel kann ich sie wieder dechiffrieren.
Erzeugt werden muß der Public-Key e, der Private-Key d und die Zahl n:
Damit das Verfahren sicher ist, müsssen p und q sehr gross gewählt werden!! Ausserdem müssen p und q nach der Generierung vernichtet werden.
Warum das Verfahren gerade so ist, werde ich demnächst skizzieren. Vorerst möchte ich nur erwähnen, dass die Grundlage Fermats little Theorem ist.
Mal ein kleines Beispiel:
Schritt 5 im Detail
Bestimmen des GGT nach Euklid:
I. 8 = 1 * 5 + 3
II. 5 = 1 * 3 + 2
III. 3 = 1 * 2 + 1
IV. 2 = 2 * 1 + 0 -> GGT = 1
Bestimmen von d und b nach Euklid erweitert:
3 = 1 * 2 + 1
1 = 3 - 1 * 2 aus II. 2 = 5 - 1 * 3
1 = 3 - 1 *(5 - 1 * 3)
1 = 3 - 1 * 5 + 1 * 3
1 = 2 * 3 - 1 * 5 aus I. 8 = 1 * 5 + 3
1 = 2 *(8 - 1 * 5) - 1 * 5
1 = 2 * 8 - 2 * 5 - 1 * 5
1 = 2 * 8 - 3 * 5 -> d = -3
Negative Zahlen sind unerwünscht und somit müssen wir das ganze noch positivieren:
-3 + 8 = 5 -> d = 5 (Erklärung folgt in der nächsten Zeit)
Hat sich zum Schluss als ziemlich unglückliches Beispiel herausgestellt, weil e und d zufaellig identisch sind, normalerweise ist dieses natürlich nicht so!!!
Chiffrieren eines "C"(m = Zahlencode = 3) mit e = 5, d = 5 und n = 15:
me mod n = c
35 mod 15 = 3 -> c = 3
Dechiffrieren:
cd mod n = m
35 mod 15 = 3 -> m = 3
Wie schon oben gesagt ein dummes Beispiel!!!