RSA-Algorithmus < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:11 Di 13.03.2012 | | Autor: | Jack159 |
| Aufgabe | | Keine Aufgabe, nur Frage zum Beispiel. |
Hallo,
Folgendes Beispiel vom RSA-Algorithmus:
p=7
q=19
n=7*19=133
Phi(133)=6*18=108
e=5
Geheimen Schlüssel d mit dem erweit. Euklid. Algorithmus berechnen.
5*d+k*108=1
ergibt: 1=2*108-43*5
[mm] d=-43\equiv65 [/mm] mod 108
An der Stelle habe ich eine Frage.
Wie kommt man dort auf die 65? (Den Rest verstehe ich).
|
|
| |
|
Restklassenrechnerei [mm]\IZ /108 \IZ[/mm]:
[mm]d\equiv -43 \equiv -43 + 108 \equiv -43 + 108+108 \mod 108[/mm]
[mm]d\equiv -43 \equiv 65 \equiv 173 \mod 108[/mm]
oder worauf zielte deine Frage ab?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:39 Di 13.03.2012 | | Autor: | Jack159 |
> Restklassenrechnerei [mm]\IZ /180 \IZ[/mm]:
>
> [mm]d\equiv -43 \equiv -43 + 108 \equiv -43 + 108+108 \mod 180[/mm]
>
> [mm]d\equiv -43 \equiv 65 \equiv 173 \mod 180[/mm]
>
> oder worauf zielte deine Frage ab?
Achso, also einfach 108-43=65 ergibt die 65....?
Wieso rechnet man aber 108-43 ? Wieso ist nicht -43 die Modulare Inverse?
Hier z.b. wird nicht erst noch irgendetwas Minus gerechnet, sondern direkt das d aus dem erw. euk. alg. genommen:
http://wwwlehre.dhbw-stuttgart.de/~lichtens/Referate/WS2009/Handout_MultInv.pdf
Etwas runterscrollen.
|
|
|
| |
|
> > Restklassenrechnerei [mm]\IZ /108 \IZ[/mm]:
> >
> > [mm]d\equiv -43 \equiv -43 + 108 \equiv -43 + 108+108 \mod 108[/mm]
>
> >
> > [mm]d\equiv -43 \equiv 65 \equiv 173 \mod 108[/mm]
> >
> > oder worauf zielte deine Frage ab?
>
> Achso, also einfach 108-43=65 ergibt die 65....?
Ja. Es wird alles modulo 108 gerechnet.
108 durch 108 = 1 Rest 0
216 durch 108 = 2 Rest 0
>
> Wieso rechnet man aber 108-43 ? Wieso ist nicht -43 die
> Modulare Inverse?
Ist sie doch! Verwirrt?
In [mm] $\IZ/108\IZ$ [/mm] sind -43 und 65 die gleiche Zahl ist. Generell gilt hier in [mm] $\IZ/108\IZ$
[/mm]
[mm] $x\equiv [/mm] x + [mm] n\cdot [/mm] 108 [mm] \mod [/mm] 108$
also ist auch hier
...=-907=-799=-691=-583=-475=-367=-259=-151=-43=65=173=281=389=497=605=713=821=...
Nimm dir ein x her, dann gilt [mm] $x\equiv [/mm] x+ n108 [mm] \mod [/mm] 108$. Du kannst also auf jedes Element 108 hinzuaddieren und es bleibt das gleiche Element.
>
> Hier z.b. wird nicht erst noch irgendetwas Minus gerechnet,
> sondern direkt das d aus dem erw. euk. alg. genommen:
>
> http://wwwlehre.dhbw-stuttgart.de/~lichtens/Referate/WS2009/Handout_MultInv.pdf
> Etwas runterscrollen.
>
>
PS: Ich hatte mich in meinem vorherigen Beitrag vertan. Da müsste eine 108 stehen und keine 180. Hab ich jetzt verbessert.
|
|
|
|
