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 $\exists\ (man\ spricht: es\ existiert\ ein)\ 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