50 lines
951 B
Markdown
50 lines
951 B
Markdown
# 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
|
|
|
|
|
|
|
|
|
|
### Primzahlentests
|
|
|