MathePrisma Logo

RSA

RSA

RSA

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:

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