Beweis 2: Unterschied zwischen den Versionen
| Zeile 7: | Zeile 7: | ||
<math>und\ m^{p-1}\equiv 1\ (mod\ p)\ \mathrm{f{\ddot u}r}\ ggT(m,p) = 1\ und\ p \in \mathbb P (Primzahl)</math><br> | <math>und\ m^{p-1}\equiv 1\ (mod\ p)\ \mathrm{f{\ddot u}r}\ ggT(m,p) = 1\ und\ p \in \mathbb P (Primzahl)</math><br> | ||
<br> | <br> | ||
| − | 1.Mit <math>e\cdot d\equiv 1\ (mod\ \varphi(n))</math>, d.h. <math>e\cdot d = k\cdot \varphi(n)+1</math> gilt:<br> | + | 1. Mit <math>e\cdot d\equiv 1\ (mod\ \varphi(n))</math>, d.h. <math>e\cdot d = k\cdot \varphi(n)+1</math> gilt:<br> |
<math>m^{ed}\ (mod\ n) = m^{k\cdot \varphi(n)+1}\ (mod\ n) = m^{de}\ (mod\ n)</math>.<br> | <math>m^{ed}\ (mod\ n) = m^{k\cdot \varphi(n)+1}\ (mod\ n) = m^{de}\ (mod\ n)</math>.<br> | ||
<br> | <br> | ||
| − | 2.Es bleibt also zu zeigen: <math>m^{ed}\ (mod\ n) = m</math><br> | + | 2. Es bleibt also zu zeigen: <math>m^{ed}\ (mod\ n) = m</math><br> |
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 <math>i \in \N</math>)<br><br> | 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 <math>i \in \N</math>)<br><br> | ||
<math>m^{ed}\ (mod\ p) = m^{k\cdot \varphi(n)+1}\ (mod\ p)</math><br> | <math>m^{ed}\ (mod\ p) = m^{k\cdot \varphi(n)+1}\ (mod\ p)</math><br> | ||
Version vom 18. Dezember 2010, 15:13 Uhr
Zu zeigen: 
Der Beweis basiert auf dem Satz von Euler und dem Satz von Fermat.
Danach gilt: 
1. Mit 
, d.h. 
gilt:
.
2. Es bleibt also zu zeigen: 
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 
)
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:
Da 
teilt, gilt weiterhin:
Also auch 
Und damit: 
Also: 
Analog gilt für 
Es existiert weiterhin 
mit
da p und q Primzahlen sind, gilt 
Damit gilt: 
Damit ist eindeutig gezeigt, dass sich die Nachricht m aus c wieder gewinnen lässt. □
zurück zum RSA-Algorithmus
Der, auf dieser Seite, dargestellte Beweis stammt aus [5, S.324 f.]
siehe dazu Literaturverzeichnis
