Asymmetrische Verfahren II

RSA - Verfahren

1. Kapitel

... in dem Bob zwei magische Schlüssel erzeugt

p =

q =

und berechnet damit

n = p · q =

und

φ(n) = (p-1) · (q-1) =

φ(n) ist die sogenannte Eulersche Phi-Funktion, auf die hier aber nicht näher eingegangen werden soll.
Außerdem wählt er eine natürliche Zahl e (encrypt) größer als 1 und kleiner als φ(n), die zu φ(n) teilerfremd ist, d.h. ggt(e, φ(n)) = 1.

e =

Jetzt fehlt noch die Zahl d (decrypt). Diese ergibt sich durch Lösen der Gleichung
e · d mod φ(n) = 1

2. Kapitel

... in dem Alice eine Nachricht verschlüsselt

Die Hauptarbeit ist nun erledigt, so dass Alice ins Geschehen eingreifen kann.
Vorweg sei gesagt, dass die Nachricht m (message) hier als ganze Zahl verstanden wird. Zudem muss die Bedingung 1 < m < n erfüllt sein.
Mit Hilfe des public key und folgender einfacher Formel kann Alice ihre Nachricht m in den Geheimtext c (cyphertext) umwandeln.

public key					message
n =		e =			m =

c =

mod

3. Kapitel

... in dem Bob die Nachricht entschlüsselt

Bob hat inzwischen die geheime Botschaft (cyphertext) empfangen und kann diese mit seinem private key entschlüsseln.

private key					cyphertext
n =		d =			c =

m =

mod

Epilog

Die Sicherheit des RSA-Verfahrens besteht in der Schwierigkeit, die Zahl n in das Produkt der beiden Primzahlen p und q zu zerlegen. Was für kleine Zahlen sehr einfach scheint, ist bei sehr großen Zahlen ein zeitaufwendiger Algorithmus.
Werfen wir abschließend noch mal einen Blick auf die beiden Kernformeln des RSA-Verfahrens.

Verschlüsseln

Entschlüsseln

		e
c =	m		mod	n

		d
m =	c		mod	n