951 B
951 B
MATU - 2018-05-17
Das Diskrete Logarithmus Problem
Der RSA Algorithmus
Schluesselerzeugung
Wie erzeugt man ein Schluesselpaar?
- Waehle zwei verschiedene Primzahlen p,q (in der Praxis: gross)
- berechne
n = p * q - berechne
m = (p - 1)(q - 1)
m = φ(n)
- waehle
e ∈ Z_n, e teilerfremd zu m
Weil e teilerfremd zu m, gibt es ein multiplikatives Inverese
- berechne
d = 1/e mod m
gebe bekannt:
- (e, n) ... oeffentlicher Schluessel
behalte (geheim):
- d ... geheimer Schluessel
p,q,m werden nicht mehr benoetigt
Ver- und Entschluesselung
p = 5, q = 11 x = 8
Sicherheit
Die Sicherheit des RSA-Algorithmus beruht auf der Schwierigkeit n in die Primzahlen p,q zu zerlegen. ("Faktorisierungsproblem")
Methode von Fermat
