Beweis 2: Unterschied zwischen den Versionen

Aus RMG-Wiki
Wechseln zu: Navigation, Suche
Zeile 44: Zeile 44:
 
<br>
 
<br>
 
[[Benutzer:Deininger_Matthias/Facharbeit/RSA-Algorithmus| ''' zurück zum RSA-Algorithmus''']]
 
[[Benutzer:Deininger_Matthias/Facharbeit/RSA-Algorithmus| ''' zurück zum RSA-Algorithmus''']]
 +
<br>
 +
<br>
 +
[[Benutzer:Deininger_Matthias/Facharbeit| zurück zur Übersicht]]
 
<br>
 
<br>
 
<br>
 
<br>
 
----
 
----
−
Der, auf dieser Seite, dargestellte Beweis stammt aus [5, S.324 f.]<br>
+
Der auf dieser Seite dargestellte Beweis stammt aus [5, S.324 f.]<br>
 
[[Benutzer:Deininger_Matthias/Facharbeit/Literaturverzeichnis| siehe dazu Literaturverzeichnis]]
 
[[Benutzer:Deininger_Matthias/Facharbeit/Literaturverzeichnis| siehe dazu Literaturverzeichnis]]

Version vom 18. Dezember 2010, 15:15 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

zurück zur Übersicht

Der auf dieser Seite dargestellte Beweis stammt aus [5, S.324 f.]
siehe dazu Literaturverzeichnis

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