RSA Algorithmus < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:01 Fr 02.07.2010 | | Autor: | rainerS |
Hallo!
Bitte schreibe doch deine Frage vollständig auf!
Du fragst: Wenn n das Produkt zweier Primzahlen p,q ist, warum folgt dann, dass für [mm] $K\in\IZ$ [/mm] gilt:
[mm] \left(K^{\phi(pq)}\right)^k \equiv 1 \pmod{pq} [/mm] ?
Schau doch einfach in ![[]](/images/popup.gif) die Originalarbeit, Abschnitt VI.
Die Aussage folgt direkt aus dem Satz von Euler: Wenn [mm] $\mathrm{ggT}(a,n) [/mm] =1$, dann ist [mm] $a^{\phi(n)} \equiv [/mm] 1 [mm] \pmod [/mm] n$.
Da unter diesem Verfahren ja Alles modulo $pq$ gerechnet wird, muss der Klartext K eine natürliche Zahl und kleiner oder gleich $pq$ sein. Damit ist entweder [mm] $\mathrm{ggT}(K,pq) [/mm] = 1$ oder K ist ein Vielfaches von p oder q.
Wenn K ein Vielfaches von q ist, so ist [mm] $K^{p-1}\equiv [/mm] 1 [mm] \pmod{p} \implies K^{k*\phi(pq)+1} \equiv [/mm] K [mm] \pmod{p}$. [/mm] Andererseits gilt diese Identität trivialerweise auch, wenn K ein Vielfaches von p ist, also für alle [mm] $K\le [/mm] n$.
Analog gilt dies für q: [mm] $K^{k*\phi(pq)+1} \equiv [/mm] K [mm] \pmod{q}$ [/mm] und auch [mm] $\pmod{pq}$.
[/mm]
Viele Grüße
Rainer
|
|
|
| |
|
Hallo Rainer :)
Vielen Dank für deine schnelle Hilfe!!
> Hallo!
>
> Bitte schreibe doch deine Frage vollständig auf!
>
> Du fragst: Wenn n das Produkt zweier Primzahlen p,q ist,
> warum folgt dann, dass für [mm]K\in\IZ[/mm] gilt:
>
> [mm]\left(K^{\phi(pq)}\right)^k \equiv 1 \pmod{pq}[/mm] ?
>
> Schau doch einfach in
> die Originalarbeit,
> Abschnitt VI.
>
> Die Aussage folgt direkt aus dem Satz von Euler: Wenn
> [mm]\mathrm{ggT}(a,n) =1[/mm], dann ist [mm]a^{\phi(n)} \equiv 1 \pmod n[/mm].
>
> Da unter diesem Verfahren ja Alles modulo [mm]pq[/mm] gerechnet
> wird, muss der Klartext K eine natürliche Zahl und kleiner
> oder gleich [mm]pq[/mm] sein. Damit ist entweder [mm]\mathrm{ggT}(K,pq) = 1[/mm]
> oder K ist ein Vielfaches von p oder q.
>
> Wenn K ein Vielfaches von q ist, so ist [mm]K^{p-1}\equiv 1 \pmod{p} \implies K^{k*\phi(pq)+1} \equiv K \pmod{p}[/mm].
> Andererseits gilt diese Identität trivialerweise auch,
> wenn K ein Vielfaches von p ist, also für alle [mm]K\le n[/mm].
Das Problem liegt an genau dieser Stelle hier.
Falls K ein Vielfaches von q ist gilt [mm] K^{p-1}\equiv [/mm] 1 [mm] \pmod{p} \implies K^{k*\phi(pq)+1} \equiv [/mm] K [mm] \pmod{p}, [/mm] das verste ich noch, aber was genau hat man hiervon?
Die Aussage bezieht sich auf den Modul p und nicht pq :(
>
> Analog gilt dies für q: [mm]K^{k*\phi(pq)+1} \equiv K \pmod{q}[/mm]
> und auch [mm]\pmod{pq}[/mm].
>
> Viele Grüße
> Rainer
Gruß :)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:40 Fr 02.07.2010 | | Autor: | felixf |
Hallo
> Das Problem liegt an genau dieser Stelle hier.
> Falls K ein Vielfaches von q ist gilt [mm]K^{p-1}\equiv[/mm] 1
> [mm]\pmod{p} \implies K^{k*\phi(pq)+1} \equiv[/mm] K [mm]\pmod{p},[/mm] das
> verste ich noch, aber was genau hat man hiervon?
Nun, was passiert modulo $q$?
> Die Aussage bezieht sich auf den Modul p und nicht pq :(
Stichwort: Chinesischer Restsatz.
Weisst du was der tut? Wenn nicht: lies es nach!
LG Felix
|
|
|
| |
|
Hallo felixf,
wenn ich zeigen könnte, dass
$ [mm] K^{k(p-1)(q-1)}\equiv [/mm] $ 1 [mm] \pmod{p} \
[/mm]
und
$ [mm] K^{k(p-1)(q-1)}\equiv [/mm] $ 1 [mm] \pmod{q}
[/mm]
dann könnte ich mit dem Restsatz folgern, dass
$ [mm] K^{k(p-1)(q-1)}\equiv [/mm] $ 1 [mm] \pmod{pq} [/mm]
Das bekomme ich hier aber leider nicht da zwar gilt:
$ [mm] K^{k(p-1)(q-1)}\equiv [/mm] $ 1 [mm] \pmod{p} [/mm]
aber dafür
$ [mm] K^{k(p-1)(q-1)}\equiv [/mm] $ 0 [mm] \pmod{q} \
[/mm]
wenn K ein Vielfaches von q
Gruß :)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 04:17 Sa 03.07.2010 | | Autor: | felixf |
Moin,
> wenn ich zeigen könnte, dass
> [mm]K^{k(p-1)(q-1)}\equiv[/mm] 1 [mm]\pmod{p} \[/mm]
> und
> [mm]K^{k(p-1)(q-1)}\equiv[/mm] 1 [mm]\pmod{q}[/mm]
das gaube ich nicht. Was ist, wenn $K$ durch $p$ oder $q$ teilbar ist? Dann geht eins von beiden nicht. Und wenn $K$ durch $p$ und $q$ teilbar ist, sogar beides nicht!
> dann könnte ich mit dem Restsatz folgern, dass
> [mm]K^{k(p-1)(q-1)}\equiv[/mm] 1 [mm]\pmod{pq}[/mm]
Ja, wenn es modulo $p$ und $q$ gilt, dann auch modulo $p$ und $q$.
LG Felix
|
|
|
| |
|
Hey :)
Das ist ja gerade das Problem, dass
$ [mm] K^{k(p-1)(q-1)}\equiv [/mm] $ 1 $ [mm] \pmod{p} [/mm] \ $
und
$ [mm] K^{k(p-1)(q-1)}\equiv [/mm] $ 1 $ [mm] \pmod{q} [/mm] $
für [mm] ggT(K,p)\not=1\vee ggT(K,q)\not=1 [/mm] nicht gilt, deswegen weiß ich nicht genauw wie ihr mit dem Restsatz Argumentieren wollt.
Könnt ihr mir die Lösung nicht einfach hinschreiben und ich versuche das ganze nachzuvollziehen?
Das Ganze ist keine Übungsaufgabe etc und dient nur dem eigenen Verständnis
Gruß und schönes WE :)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 10:20 Sa 03.07.2010 | | Autor: | felixf |
Hallo
> Das ist ja gerade das Problem, dass
> [mm]K^{k(p-1)(q-1)}\equiv[/mm] 1 [mm]\pmod{p} \[/mm]
> und
> [mm]K^{k(p-1)(q-1)}\equiv[/mm] 1 [mm]\pmod{q}[/mm]
> für [mm]ggT(K,p)\not=1\vee ggT(K,q)\not=1[/mm] nicht gilt,
> deswegen weiß ich nicht genauw wie ihr mit dem Restsatz
> Argumentieren wollt.
Ich frage mich immer noch, warum du eigentlich [mm] $K^{k(p-1)(q-1)} \equiv [/mm] 1 [mm] \pmod{pq}$ [/mm] zeigen willst. Du willst doch [mm] $K^{k(p-1)(q-1)+1} \equiv [/mm] K [mm] \pmod{pq}$ [/mm] haben. Warum zeigst du das nicht mit dem chinesischen Restsatz?
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:23 Mo 05.07.2010 | | Autor: | MatheStein |
Oh man ich hatte einen grundlegen Fehler in meinem Gedankengang :)
Vielen Dank für eure Hilfen ;)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:50 Sa 03.07.2010 | | Autor: | rainerS |
Hallo!
Lies entweder meine Argumentation bis zum ENde durch oder die Originalarbeit.
> Hallo Rainer :)
>
> Vielen Dank für deine schnelle Hilfe!!
>
> > Hallo!
> >
> > Bitte schreibe doch deine Frage vollständig auf!
> >
> > Du fragst: Wenn n das Produkt zweier Primzahlen p,q ist,
> > warum folgt dann, dass für [mm]K\in\IZ[/mm] gilt:
> >
> > [mm]\left(K^{\phi(pq)}\right)^k \equiv 1 \pmod{pq}[/mm] ?
> >
> > Schau doch einfach in
> > die Originalarbeit,
> > Abschnitt VI.
> >
> > Die Aussage folgt direkt aus dem Satz von Euler: Wenn
> > [mm]\mathrm{ggT}(a,n) =1[/mm], dann ist [mm]a^{\phi(n)} \equiv 1 \pmod n[/mm].
> >
> > Da unter diesem Verfahren ja Alles modulo [mm]pq[/mm] gerechnet
> > wird, muss der Klartext K eine natürliche Zahl und kleiner
> > oder gleich [mm]pq[/mm] sein. Damit ist entweder [mm]\mathrm{ggT}(K,pq) = 1[/mm]
> > oder K ist ein Vielfaches von p oder q.
> >
> > Wenn K ein Vielfaches von q ist, so ist [mm]K^{p-1}\equiv 1 \pmod{p} \implies K^{k*\phi(pq)+1} \equiv K \pmod{p}[/mm].
> > Andererseits gilt diese Identität trivialerweise auch,
> > wenn K ein Vielfaches von p ist, also für alle [mm]K\le n[/mm].
>
> Das Problem liegt an genau dieser Stelle hier.
> Falls K ein Vielfaches von q ist gilt [mm]K^{p-1}\equiv[/mm] 1
> [mm]\pmod{p} \implies K^{k*\phi(pq)+1} \equiv[/mm] K [mm]\pmod{p},[/mm] das
> verste ich noch, aber was genau hat man hiervon?
Nicht nur das, es gilt für beliebge K, denn
1. es gilt, wenn [mm]\mathrm{ggT}(K,pq) = 1[/mm] ,
2. es gilt, wenn K ein Vielfaches von q ist,
3. es gilt wenn K ein Vielfaches von p ist (Trivial, da beide Seiten kongruent zu 0 sind)
>
> Die Aussage bezieht sich auf den Modul p und nicht pq :(
Deswegen geht der Beweis ja auch weiter.
> >
> > Analog gilt dies für q: [mm]K^{k*\phi(pq)+1} \equiv K \pmod{q}[/mm]
[mm]K^{k*\phi(pq)+1} \equiv K \pmod{q}[/mm] für beliebige K.
Dann Restsatz.
Viele Grüße
Rainer
|
|
|
|
