Modulo-Operator < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:11 Fr 03.03.2006 | | Autor: | i-mehl |
Hallo!
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Nun, ich habe die Aufgabe zu Beweisen, weshalb die Ver- und Entschlüsselung des RSA-Algorithmus funktioniert. Soweit, sogut.
Das Problem ist hierbei, dass ich mich mit den Modulo-Operator noch nie beschäftigt habe und ich stehe jetzt vor folgendem Problem:
c = [mm] m^{e} [/mm] mod P und u = [mm] c^{d} [/mm] mod p
Zu beweisen ist, dass m = u ist.
Jetzt kann man ja folgendes schreiben:
u = [mm] c^{d} [/mm] mod P = [mm] (m^{e} [/mm] mod [mm] P)^{d} [/mm] mod P = [mm] m^{ed} [/mm] mod P
Und genau das verstehe ich nicht!
Warum ist denn [mm] (m^{e} [/mm] mod [mm] P)^{d} [/mm] mod P = [mm] m^{ed} [/mm] mod P ?
Kann mir das jemand vielleicht irgendwie anschaulich erklären oder vielleicht sogar beweisen ? :)
Bitte helft mir!
Vielen Dank schonmal im Voraus.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 01:38 Sa 04.03.2006 | | Autor: | felixf |
Hallo!
> Das Problem ist hierbei, dass ich mich mit den
> Modulo-Operator noch nie beschäftigt habe und ich stehe
> jetzt vor folgendem Problem:
>
> c = [mm]m^{e}[/mm] mod P und u = [mm]c^{d}[/mm] mod p
>
> Zu beweisen ist, dass m = u ist.
> Jetzt kann man ja folgendes schreiben:
>
> u = [mm]c^{d}[/mm] mod P = [mm](m^{e}[/mm] mod [mm]P)^{d}[/mm] mod P = [mm]m^{ed}[/mm] mod P
>
> Und genau das verstehe ich nicht!
> Warum ist denn [mm](m^{e}[/mm] mod [mm]P)^{d}[/mm] mod P = [mm]m^{ed}[/mm] mod P ?
Nun, im Prinzip reicht es aus zu zeigen, dass $((a [mm] \mod [/mm] P) [mm] \cdot [/mm] (b [mm] \mod [/mm] P)) [mm] \mod [/mm] P = (a [mm] \cdot [/mm] b) [mm] \mod [/mm] P$ ist.
Das kannst du wie folgt zeigen: Ist $a = [mm] q_1 \cdot [/mm] P + [mm] r_1$ [/mm] mit [mm] $q_1, r_1 \in \IZ$, [/mm] $0 [mm] \le r_1 [/mm] < P$ (Division mit Rest), so ist ja $a [mm] \mod [/mm] P = r$. Schreibe also auch $b = [mm] q_2 \cdot [/mm] P + [mm] r_2$, [/mm] $a b = [mm] q_3 \cdot [/mm] P + [mm] r_3$ [/mm] und [mm] $r_1 r_2 [/mm] = [mm] q_4 \cdot [/mm] P + [mm] r_4$. [/mm] Die Behauptung ist dann ja grad [mm] $r_4 [/mm] = [mm] r_3$.
[/mm]
Nun ist [mm] $r_4 [/mm] = [mm] r_1 r_2 [/mm] - [mm] q_4 [/mm] P = (a - [mm] q_1 [/mm] P) (b - [mm] q_2 [/mm] P) - [mm] q_4 [/mm] P = a b - (a [mm] q_2 [/mm] + b [mm] q_1 [/mm] + [mm] q_4) [/mm] P = [mm] (q_3 [/mm] P + [mm] r_3) [/mm] - (a [mm] q_2 [/mm] + b [mm] q_1 [/mm] + [mm] q_4) [/mm] P = [mm] (q_3 [/mm] - a [mm] q_2 [/mm] - b [mm] q_1 [/mm] - [mm] q_4) [/mm] P + [mm] r_3$.
[/mm]
Nun weisst du jedoch, dass $0 [mm] \le r_3, r_4 [/mm] < P$ ist, und somit muss also [mm] $q_3 [/mm] - a [mm] q_2 [/mm] - b [mm] q_1 [/mm] - [mm] q_4 [/mm] = 0$ und [mm] $r_3 [/mm] = [mm] r_4$ [/mm] sein!
Wenn du das jetzt gezeigt hast, kannst du [mm] $m^e \mod [/mm] P = ( [mm] \cdots [/mm] (((m [mm] \cdot [/mm] m) [mm] \mod [/mm] P) [mm] \cdot [/mm] m) [mm] \mod [/mm] P) [mm] \dots \cdot [/mm] m) [mm] \mod [/mm] P$ schreiben und analog fuer [mm] $c^d \mod [/mm] P$, und alles folgt aus dem einfachen Fall $(a [mm] \cdot [/mm] b) [mm] \mod [/mm] P = ((a [mm] \mod [/mm] P) [mm] \cdot [/mm] (b [mm] \mod [/mm] P)) [mm] \mod [/mm] P$ 
(Das gleiche kannst du auch fuer $+$ anstatt [mm] $\cdot$ [/mm] zeigen.)
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:51 Sa 04.03.2006 | | Autor: | i-mehl |
Erstmal vielen, vielen Dank für diese schnelle und ausführliche Antwort! Wirklich ein tolles Forum.
Ich habe leider noch eine dumme Frage:
...somit muss also q3 - aq2 - bq1 - q4 = 0 ... sein.
Diesen Schritt versteh ich einfach nicht :(.
Kannst du mir das noch bitte erklären? :D
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:57 Sa 04.03.2006 | | Autor: | i-mehl |
Super, danke :).
|
|
|
|
