RSA mit den Primzahlen 7 und 3 < Sonstige < Schule < Informatik < Vorhilfe
|
Hey, wie ist das denn mit RSA, wenn ich es selber durchrechne (siehe: http://de.wikipedia.org/wiki/RSA-Kryptosystem#Beispiel). Bisher hat alles wunderbar geklappt, von der Wahl von q,p und e bis hin zur Berechnung von d mit dem erweiterten euklidischen Algorithmus. Aber wenn ich p=7 wähle und q=3, dann erhalte ich egal welchen public key e ich wähle, auch immer den selben private key d.
Mögliche e sind ja: 5,7,11 aber auch dann erhalte ich immer d=5,7,11
Zur Kontrolle habe ich das Javamodul auf http://www.matheprisma.uni-wuppertal.de/Module/RSA/pages/node15.htm verwendet, selbe Ergebnisse, weiß jmd rat?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:36 Fr 25.04.2008 | | Autor: | rainerS |
Hallo!
> Hey, wie ist das denn mit RSA, wenn ich es selber
> durchrechne (siehe:
> http://de.wikipedia.org/wiki/RSA-Kryptosystem#Beispiel).
> Bisher hat alles wunderbar geklappt, von der Wahl von q,p
> und e bis hin zur Berechnung von d mit dem erweiterten
> euklidischen Algorithmus. Aber wenn ich p=7 wähle und q=3,
> dann erhalte ich egal welchen public key e ich wähle, auch
> immer den selben private key d.
>
> Mögliche e sind ja: 5,7,11 aber auch dann erhalte ich immer
> d=5,7,11
Du hast richtig gerechnet.
Bedenke folgendes: Du bestimmst d aus der Gleichung
[mm] e\cdot d \equiv 1 \pmod{(p-1)(q-1)} [/mm]
Wann kann $e=d$ sein? Doch nur, wenn
[mm] e\cdot e \equiv 1 \pmod{(p-1)(q-1)} [/mm]
oder:
[mm] (e-1)\cdot(e+1) \equiv 0 \pmod{(p-1)(q-1)} [/mm]
Das kann nur dann der Fall sein, wenn $(e-1)*(e+1)$ ein Vielfaches von $(p-1)(q-1)$ ist.
In deinem Fall ist $(p-1)(q-1)=12$, und für e=5,7,11 ist $(e-1)*(e+1)$ immer ein Vielfaches von 12.
Das Gleiche passiert, wenn du p=5 und q=3 wählst. Diese Zahlen sind einfach zu klein, um zu sinnvollen Werten von e und d zu führen.
Viele Grüße
Rainer
|
|
|
|
