Zeigen dass (m^e mod n)^d = m^(e*d) mod n

28.03.2006, 15:40

Bebbo

Zeigen dass (m^e mod n)^d = m^(e*d) mod n

Hallo Forum!
Beim Beweis des RSA-Algorithmus, muss irgendwann wie folgt umgeformt werden:

$\begin{eqnarray*} (m^e \end{eqnarray*}$ mod n $\begin{eqnarray*} )^d \end{eqnarray*}$ mod n = $\begin{eqnarray*} m^{e*d} \end{eqnarray*}$ mod n

Nun war mir nicht ganz bewusst, wie eine solche Behauptung zu standekommt, also hab probiert mal das ganze zu beweisen. Als Vorraussetzung ist d ein multiplikatives Inverses zu e mod n ( 1 = (e*d) mod n). Und dementsprechend ist e zu n teilerfremd.

$\begin{eqnarray*} m^e \end{eqnarray*}$ lässt sich ja auch anders schreiben:
$\begin{eqnarray*} m^e \end{eqnarray*}$ = q*n + r

r entspräche dem Rest, der bei mod n entsteht, also wird nach r umgeformt:
r = $\begin{eqnarray*} m^e \end{eqnarray*}$ - q*n

Das wird nun wieder für $\begin{eqnarray*} m^e \end{eqnarray*}$ mod n eingesetzt:

$\begin{eqnarray*} (m^e \end{eqnarray*}$ - q*n $\begin{eqnarray*} )^d \end{eqnarray*}$ mod n = $\begin{eqnarray*} m^{e*d} \end{eqnarray*}$ mod n = $\begin{eqnarray*} (m^e)^d \end{eqnarray*}$ mod n

Folglich muss gelten(wegen Vorraussetzung e*d mod n = 1):
$\begin{eqnarray*} (m^e \end{eqnarray*}$ - q*n $\begin{eqnarray*} )^d \end{eqnarray*}$ mod n = m

Für $\begin{eqnarray*} (m^e \end{eqnarray*}$ - q*n $\begin{eqnarray*} )^d \end{eqnarray*}$ mod n lässt sich wieder entsprechend umformen:
r = $\begin{eqnarray*} (m^e \end{eqnarray*}$ - q*n $\begin{eqnarray*} )^d \end{eqnarray*}$ - p*n

Nun wird eingesetzt:

$\begin{eqnarray*} (m^e \end{eqnarray*}$ - q*n $\begin{eqnarray*} )^d \end{eqnarray*}$ - p*n = m

An dieser Stelle bin ich wohl in einer Sackgasse gelandet. Könnt ihr mir vielleicht weiterhelfen?

28.03.2006, 16:58

Abakus

Auf diesen Beitrag antworten »

RE: Zeigen dass (m^e mod n)^d = m^(e*d) mod n

Zitat:

Original von Bebbo
Das wird nun wieder für $\begin{eqnarray*} m^e \end{eqnarray*}$ mod n eingesetzt:

$\begin{eqnarray*} (m^e \end{eqnarray*}$ - q*n $\begin{eqnarray*} )^d \end{eqnarray*}$ mod n = $\begin{eqnarray*} m^{e*d} \end{eqnarray*}$ mod n = $\begin{eqnarray*} (m^e)^d \end{eqnarray*}$ mod n

Hallo Bebbo,

eigentlich steht es mit der obigen Zeile fast da (ich setze mal auf der linken Seite ein):

$\begin{eqnarray*} (m^e~mod~n)^d~ mod~ n = (m^e - q*n)^d~ mod~ n = m^{e*d}~ mod~ n =~ (m^e)^d~ mod~ n \end{eqnarray*}$

Wesentlich erscheint mir hier folgendes:

$\begin{eqnarray*} (a + nb)^d~ mod~ n = (a^d + n*S)~mod~n = a^d~mod~n \end{eqnarray*}$ .

Dabei ist n*S ein Summenausdruck, der durch das Ausrechnen der Potenz entsteht, jeder Summand darin ist durch n teilbar.

Grüße Abakus smile

PS: Titel verbessert

28.03.2006, 17:08

Auf diesen Beitrag antworten »

Zitat:

Original von Bebbo
Als Vorraussetzung ist d ein multiplikatives Inverses zu e mod n ( 1 = (e*d) mod n).

Ich weiß nicht, ob du dich hier nur verschrieben hast, oder ob sich da wirklich ein inhaltlicher Fehler bei dir festgesetzt hat.
Jedenfalls muss d kein multiplikatives Inverses zu e modulo n sein, sondern modulo $\begin{eqnarray*} \varphi(n) \end{eqnarray*}$ .

EDIT: Anzumerken ist noch, dass $\begin{eqnarray*} d\cdot e\equiv 1\mod\varphi(n) \end{eqnarray*}$ eine hinreichende, aber keinesfalls eine notwendige Bedingung dafür ist, dass $\begin{eqnarray*} (m^e)^d \equiv m\mod n \end{eqnarray*}$ für alle zu $\begin{eqnarray*} n \end{eqnarray*}$ teilerfremden $\begin{eqnarray*} m \end{eqnarray*}$ gilt. Aber das weißt du ja selbst aus diesem Thread.

28.03.2006, 19:25

Bebbo

Auf diesen Beitrag antworten »

Super, vielen Dank an euch beide!
An dem Summenausdruck bin ich gescheitert, weil ich nicht wusste wie ich eine binomische Formel mit einer Variablen als Potenz umformen sollte. Aber so macht das natürlich Sinn.
Ach und ja, da hab ich mich verschrieben!
Gibt es denn eine gute Seite im Internet, wo solche modularen Regeln erläutert werden? Ich hab leider bis jetzt erfolglos gegooglet und nix gefunden...

28.03.2006, 19:41

Auf diesen Beitrag antworten »

Zitat:

Original von Bebbo
Ach und ja, da hab ich mich verschrieben!

Und wie lautet daher die Schlußfolgerung? Im Board registrieren, dann kannst du solche Fehler durch Editieren korrigieren! smile

Neue Frage »

Antworten »

Zeigen dass (m^e mod n)^d = m^(e*d) mod n

Verwandte Themen