Beweis 2: Unterschied zwischen den Versionen

Aus RMG-Wiki
Wechseln zu: Navigation, Suche
(Die Seite wurde neu angelegt: Zu zeigen:  <math> \quad m= m^{ed}\ mod\ n</math><br>                  <math> ...)
 
Zeile 42: Zeile 42:
 
<br>
 
<br>
 
Damit ist eindeutig gezeigt, dass sich die Nachricht m aus c wieder gewinnen lässt. □<br>
 
Damit ist eindeutig gezeigt, dass sich die Nachricht m aus c wieder gewinnen lässt. □<br>
 +
<br>
 +
[[Benutzer:Deininger_Matthias/Facharbeit/RSA-Algorithmus| ''' zurück zum RSA-Algorithmus''']]

Version vom 3. September 2010, 12:26 Uhr

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

Von „http://rmg.zum.de/index.php?title=Benutzer:Deininger_Matthias/Facharbeit/RSA-Algorithmus/Beweis_2&oldid=34766“