Berechen von e*d=1 mod phi(n) < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:06 Fr 04.05.2007 | | Autor: | Jonez |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo,
ich hab am Dienstag eine Kryptografie-Prüfung und hab noch Probleme mit dem RSA-Algorithmus.
Dabei muss man unter anderem zwei Zahlen e und d bestimmen, so dass gilt:
e [mm] \* [/mm] d [mm] \equiv [/mm] 1 (mod phi(n))
Anscheinden wählt man das d zufällig und bestimmt dann mit dem "Extended Euklid" - Algorithmus das d, jedoch ist mir da nicht so ganz klar wie das gehen soll.
Kann mir da jemand weiterhelfen?
Danke,
Jonas
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:27 Sa 05.05.2007 | | Autor: | felixf |
Hallo Jonas,
> Dabei muss man unter anderem zwei Zahlen e und d bestimmen,
> so dass gilt:
>
> e [mm]\*[/mm] d [mm]\equiv[/mm] 1 (mod phi(n))
>
> Anscheinden wählt man das d zufällig und bestimmt dann mit
> dem "Extended Euklid" - Algorithmus das d, jedoch ist mir
> da nicht so ganz klar wie das gehen soll.
man waehlt $d$ nicht ganz zufaellig, sondern so, dass es teilerfremd zu [mm] $\phi(n)$ [/mm] ist (und das es nicht zu klein ist und auch noch andere gewisse Eigenschaften erfuellt, so dass gewisse Attacken nicht durchfuehrbar sind).
Wenn nun $d$ und [mm] $\phi(n)$ [/mm] teilerfremd sind, gibt es wegen Bezout zwei ganze Zahlen $a, b [mm] \in \IZ$ [/mm] mit $a d + b [mm] \phi(n) [/mm] = 1$. Der Erweiterte Euklidische Algorithmus tut nichts anderes, als $a$ und $b$ zu berechnen. Mit diesen $a$ und $b$ gilt nun $1 = a d + b [mm] \phi(n) \equiv [/mm] a d [mm] \pmod{\phi(n)}$, [/mm] da $b [mm] \phi(n) \equiv [/mm] 0 [mm] \pmod{\phi(n)}$ [/mm] gilt. Wenn du also $e := a [mm] \mod \phi(n)$ [/mm] setzt, hast du mittels `Extended Euclid' $e$ aus $d$ und [mm] $\phi(n)$ [/mm] berechnet.
Hilft dir das weiter? Wenn nicht, sag bitte genau was du nicht verstehst.
LG Felix
|
|
|
|
