[Die Projektidee]  [Das Projekttagebuch]
Folie [1]  [2]  [3]  [4]  [5]  [6]  [7]  [8]  -  [Die RSA-Verschlüsselung]
Die RSA-Verschlüsselung

Die RSA-Verschlüsselung baut darauf auf, das es schwierig ist, eine hohe Zahl in ihre
Primfaktoren zu zerlegen. Es ist ein asymmetrisches Verschlüsselungsverfahren, d.h.
das es einen öffentlichen Schlüssel zum Verschlüsseln gibt, und einen Privaten der für
die Entschlüsselung gebraucht wird. Mit dem Öffentlichen kann man nur Verschlüsseln
aber nicht entschlüsseln.

Um mit RSA zu verschlüsseln braucht man eigentlich nur 2 Formeln:

C = K^e mod N (Verschlüsseln)
und
K = C^d mod N (Entschlüsseln)



Verschlüsseln


Zuerst müssen wir zwei Primzahlen nehmen (p und q) und diese multiplizieren. Wir
erhalten N. Jetzt multiplizieren wir (p-1) und (q-1) und erhalten f(N). Nun suchen wir uns
eine teilerfemde Zahl zu f(N) die wir e nennen. Diese Zahl e (wiederum eine Primzahl)
müssen wir nun mit der Zahl d (eine Primzahl, die wir uns natürlich wieder aussuchen)
multiplizieren, und das Ergebnis mit f(N) dividieren. Wenn nun "(e*d) / f(N) = REST 1"
ergibt, haben wir das richtige d gefunden. Und das ganze noch mal kurz in Formeln:

p*q = N
(p - 1)*(q - 1) = f(N)
(e*d) mod f(N) = 1

Jetzt haben wir schon die beiden Schlüssel. Der Private ist d, der den keiner kennen darf.
Der Öffentliche besteht aus e und N, die man z.B. ins Internet stellt und die jeder benutzen
kann, um dem Besitzer eine verschlüsselte Nachricht zu schicken. Aber wie wird so eine
Nachricht nun verschlüsselt? Zuerst muss man das verwendete Alphabet und dessen Länge
kennen, um die Buchstaben in Zahlen umwandeln zu können. Nehmen wir mal das 4-stellige
Alphabet ABCD. Jedem Buchstaben aus dem Alphabet wird nun eine Zahl zugewiesen, also
A=0, B=1 und so weiter. Versuchen wir mal das Wort ABCD in eine Zahl umzuwandeln.
Dieses Wort müsste folgendermaßen umgewandelt werden:

ABCD = 0*4^3 + 1*4^2 + 2*4^1 + 3*4^0 = 27

Schauen wir uns das mal genauer an:

0*4^3 (Null mal vier hoch drei) 0 steht für den Buchstaben A

4 steht für die Länge des Alphabets

Jetzt haben wir unseren Klartext (die Zahl 27). Übernehmen wir mal nun für die folgende
Beispielrechnung folgende Werte:

p=11
q=7
N=77
f(N)=60
e=13
d=37

Verschlüsselt wird er mit der Formel K^e mod N.

27^13 mod 77 = 48

So, jetzt haben wir unsere Verschlüsselte Zahl, aber sollten es nicht Buchstaben sein?

48 = 0*4^3 + 3*4^2 + 0*4^1 + 0*4^0 = AADA

Na also, es ist die selbe Rechnung wie beim Umwandeln von Buchstaben in Zahlen,
nur diesmal andersrum.



Entschlüsseln


Entschlüsselt wird mit der Formel C^d mod N.
 
48^37 mod 77 = 27

Und 27 ist wie wir von weiter oben wissen:

27 = 0*4^3 + 1*4^2 + 2*4^1 + 3*4^0 = ABCD

Das war's schon! Jetzt sagt jemand vielleicht, das das doch gar nicht so schwer sei.
Irrtum, in dieser Beispielrechnung haben wir der Übersicht halber kleine Zahlen genommen.
In Wirklichkeit werden über 100-stellige Primzahlen eingesetzt. Und genau darin liegt die
Schwierigkeit: aus welchen Primzahlen wurde N gebildet? Da RSA im Moment noch ziemlich
sicher ist, und sich das in nächster Zeit wahrscheinlich auch nicht ändern wird, werden solche
Schlüssel meist einmal generiert und dann lange benutzt.
Ich hoffe das ich beim Verständnis über RSA hilfreich sein konnte.

[Zurück]