RSA Entschlüsselungsexponent < Sonstiges < Schule < Mathe < Vorhilfe
|
Ich verstehe nicht ganz, wie man auf den Entschlüsselungsexponenten d beim RSA-System kommt. N ist das Produkt zweier Primzahlen, für den Verschlüsselungsexponenten e muss gelten: 1<e<phi(N), soweit nachvollziehbar. Jetzt soll gelten: e*d [mm] \equiv [/mm] 1 (mod phi(N)). Das bedeutet ja, dass der Rest der Division von e*d durch phi(N) gleich dem Rest der Division von 1 durch phi(N) sein muss (wenn ich es soweit richtig verstanden habe). Dann, habe ich mir überlegt, muss 1 mod phi(N) ja 1 sein, weil phi(N) auf jeden Fall größer als 1 ist. Also müsste gelten:
e*d = k*phi(N) + 1
wobei k der größtmögliche natürliche Faktor ist. Wenn ich die Formel dann umstelle gilt:
e*d - k*phi(N) =1
Bei Wikipedia steht da aber ein +, also
e*d + k*phi(N) =1
Sieht jemand meinen Denkfehler?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:46 Mo 15.12.2008 | | Autor: | rainerS |
Hallo!
> Ich verstehe nicht ganz, wie man auf den
> Entschlüsselungsexponenten d beim RSA-System kommt. N ist
> das Produkt zweier Primzahlen, für den
> Verschlüsselungsexponenten e muss gelten: 1<e<phi(N),
> soweit nachvollziehbar. Jetzt soll gelten: e*d [mm]\equiv[/mm] 1
> (mod phi(N)). Das bedeutet ja, dass der Rest der Division
> von e*d durch phi(N) gleich dem Rest der Division von 1
> durch phi(N) sein muss (wenn ich es soweit richtig
> verstanden habe). Dann, habe ich mir überlegt, muss 1 mod
> phi(N) ja 1 sein, weil phi(N) auf jeden Fall größer als 1
> ist. Also müsste gelten:
> e*d = k*phi(N) + 1
> wobei k der größtmögliche natürliche Faktor ist. Wenn ich
> die Formel dann umstelle gilt:
> e*d - k*phi(N) =1
> Bei Wikipedia steht da aber ein +, also
> e*d + k*phi(N) =1
> Sieht jemand meinen Denkfehler?
Ja 
Du hast übersehen, dass die Kongruenz
[mm] e*d \equiv 1 \pmod{\phi(N)} [/mm]
bedeutet, dass k eine beliebige ganze Zahl sein darf. Weder ist es auf die natürlichen Zahlen beschränkt noch muss es die größtmögliche solche Zahl sein.
Der Unterschied zwischen deiner Gleichung und der in der Wikipedia ist nur, ob du k als positive oder negative Zahl wählst.
Viele Grüße
Rainer
|
|
|
| |
|
Prima, danke! Habe gar nicht darüber nachgedacht, dass k auch negativ sein kann :D, logisch
|
|
|
| |
|
Hmm...Tut mir Leid, aber jetzt wo ich ein eigenes Beispiel ausrechnen wollte, glaube ich, dass ich es doch noch nicht so richtig verstanden habe.
13 [mm] \cdot [/mm] d [mm] \equiv [/mm] 1 (mod 60)
Dann müsste ja gelten:
13 [mm] \cdot [/mm] d + k [mm] \cdot [/mm] 60 = 1
Mit Hilfe des erweiterten euklidischen Algorithmus habe ich herausbekommen, dass d=-23 und k=5, was ja in die letzte Gleichung passen würde. Aber 13 [mm] \cdot [/mm] (-23) [mm] \equiv [/mm] 1(mod 60) passt ja nicht...Ich weiß, dass für d eigentlich 37 rauskommen sollte, aber wie kommt man darauf?
|
|
|
| |
|
Hiho,
die Lösung stimmt doch, da [mm]13*(-23) = 1\text{ (mod 60)}[/mm]
Denn:
[mm]-300 = 0\text{ (mod 60)} \gdw -299 - 1 = 0\text{ (mod 60)} \gdw -299 = 1 \text{ (mod 60)} \gdw 13*(-23) = 1\text{ (mod 60)}[/mm]
Oder Kürzer: bzgl mod 60 gilt -23 = 37, da -23 + 60 = 37 ist.
MfG,
Gono.
|
|
|
| |
|
Prima, vielen Dank für die Antwort. Ich dachte: -299 = -4 [mm] \cdot [/mm] 60 R-59, was ja schwachsinnig ist, anstatt -299 = -5 [mm] \cdot [/mm] 60 R1.
|
|
|
|
