Beweis 2

Zu zeigen: $\quad m= m^{ed}\ mod\ n$
$\quad m^{de}\ mod\ n = m^{ed}\ mod\ n$

Der Beweis basiert auf dem Satz von Euler und dem Satz von Fermat.

Danach gilt: $1\equiv m^{\varphi(n)}\ mod\ n\ \mathrm{f{\ddot u}r}\ ggT(m,n)=1$
$und\ m^{p-1}\equiv 1\ mod\ p\ \mathrm{f{\ddot u}r}\ ggT(m,p) = 1\ und\ p \in \mathbb P (Primzahl)$

1. Mit $e\cdot d\equiv 1\ mod\ \varphi(n)$ , d.h. $e\cdot d = k\cdot \varphi(n)+1$ gilt:
$m^{ed}\ mod\ n = m^{k\cdot \varphi(n)+1}\ mod\ n = m^{de}\ mod\ n$ .

2. Es bleibt also zu zeigen: $m^{ed}\ mod\ n = m$
Man unterscheidet nun die Fälle, dass p m teilt, und das p m nicht teilt. Falls p Teiler von m ist, gilt (mit einem passenden $i \in \N$ )

$m^{ed}\ mod\ p = m^{k\cdot \varphi(n)+1}\ mod\ p$
$\quad = (i\cdot p)^{k\cdot \varphi(n)+1}\ mod\ p = 0 = m\ mod\ p$
$\Rightarrow \quad i\cdot p \equiv 0\ mod\ p$

Ist p nicht Teiler von m, dann gilt: ggT (p,m) = 1, da p eine Primzahl ist.

Die Sätze von Euler und Fermat sind anwendbar und es gilt:

$m^{p-1} \equiv 1\ mod\ p$

Da $(p-1)\quad \varphi(n)$ teilt, gilt weiterhin:

$m^{k(p-1)\cdot (q-1)}\ mod\ p = 1^{k(q-1)}\ mod\ p =1\ mod\ p$

Also auch $m^{k(p-1)(q-1)+1}\ mod\ p = 1\cdot m\ mod\ p$

Und damit: $m^{k\cdot \varphi(n)+1}\ mod\ p = m\ mod\ p$

Also: $m^{ed}\ mod\ p = m^{k\cdot \varphi(n)+1}\ mod\ p = m\ mod\ p$

Analog gilt für $q: m^{ed}\ mod\ q = m\ mod\ q$
Es existiert weiterhin $i,j \in \N$ mit

$i\cdot q +m = m^{ed} = j\cdot q +m\ und\ damit\ i\cdot p = j\cdot p$

da p und q Primzahlen sind, gilt es gibt $\ r \in \N : j = r\cdot p,\ i = r\cdot q$

Damit gilt: $m^{ed} = j\cdot q+m = r\cdot p\cdot q +m,\ also\ m^{ed}\ mod\ n = (r\cdot n + m)\ mod\ n = m$

Damit ist eindeutig gezeigt, dass sich die Nachricht m aus c wieder gewinnen lässt. □

zurück zum RSA-Algorithmus

zurück zur Übersicht