Zur MathePrisma-Startseite
Zur Modul-Startseite  


RSA (RSA 5)
 

 
 
Frage
 
Das Verfahren kann natürlich nur dann funktionieren, wenn beim Entschlüsseln wieder der Klartext \(M\) herauskommt, d.h. wenn
\(C^d \bmod N = M \).
Den Geheimtext \(C\) kann man auch anders schreiben, nämlich genau so, wie er aus dem Klartext entstanden ist. Das ergibt
\(C^d \bmod N = (M^e)^d \bmod N = M^{e\cdot d} \bmod N \).
Gilt also \( M^{e\cdot d} \bmod N = M\)?
 
Antwort
 
Die Antwort auf diese Frage lautet natürlich JA.

Für den Beweis brauchen wir den kleinen Satz von Fermat (das ist ein Spezialfall des  Satzes von  Euler):

 
kleiner Satz von Fermat
 
Sei \(m\) eine natürliche Zahl, die teilerfremd zur Primzahl \(p\) ist. Dann gilt:

\[ m^{(p-1)} \bmod p = 1 . \]

 
Beweis
 
Der Beweis, dass die Entschlüsselung korrekt ist, geht damit ganz so:
 
 
zurück reset vor
 
Seite 9/12 
 
Wir wissen, dass
\(e \cdot d \bmod (p-1)(q-1) = 1.\)
element61
Das heißt, es gibt eine Zahl k, so dass
\(e \cdot d = k \cdot (p-1)(q-1) + 1 .\)
element62
Damit können wir ausrechnen:
element63
\(M^{e\cdot d} - M \bmod p = M^{k\cdot (p-1)(q-1) + 1}- M \bmod p \)
element64
\(  = \left(M^{(p-1)}\right)^{(q-1)k} \cdot M - M \bmod p\)
element65
\(= 1^{(q-1)k} \cdot M - M \bmod p = 0\)
element66
(Hier haben wir nun den kleinen Satz von Fermat benutzt!)
element66b
Das gilt auch, wenn \(p\) ein Teiler von \(M\) ist, denn dann kommt überall 0 heraus.
element67
Ganz analog sieht man, dass

\[ M^{e\cdot d}- M \bmod q = 0 \]

element68
Die Primzahlen \(p\) und \(q\) teilen also dieselbe Zahl \(M^{e\cdot d} - M\), also muss auch ihr Produkt diese Zahl teilen.

Daraus folgt die Korrektheit der Entschlüsselung:

\(M^{e\cdot d} mod\; p\cdot q = M.\)

element69