# MATU - 2018-05-17

## Das Diskrete Logarithmus Problem

![](https://i.imgur.com/rZPRsfg.png)

## 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

![](https://i.imgur.com/RMdeu7n.png)

> 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

![](https://i.imgur.com/1yigfUH.jpg)
![](https://i.imgur.com/iFxOyo1.jpg)

### Primzahlentests