RSA < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
Status: |
(Frage) beantwortet | Datum: | 12:02 Fr 16.01.2009 | Autor: | mavis |
Aufgabe | Im RSA Chiffrierschema sei n=391=17 * 23 gewählt und s= 145 der öffentliche Schlüssel.Dekodieren Sie die geheime Nachricht 101 aus {0, 1, ... 390}.
|
Hallo,
ich sitze gerade vor dieser einen Examensaufgabe und komme leider bei der Dekodierung nicht weiter. Über jegliche Hilfestellung wäre ich sehr dankbar.
n und s ist gegeben, also ist phi von n einfach zu berechnen: 16*22= 352, mit erw. euklid. Algo habe ich auch den privaten Schlüssel 17 berechnet. Zum entschlüsseln muss ich doch jetzt 101^17 mod 391 rechnen oder? Erhalte dann 52. Ist das so richtig?
|
|
|
|
> Im RSA Chiffrierschema sei n=391=17 * 23 gewählt und s= 145
> der öffentliche Schlüssel.Dekodieren Sie die geheime
> Nachricht 101 aus {0, 1, ... 390}.
>
> Hallo,
>
> ich sitze gerade vor dieser einen Examensaufgabe und komme
> leider bei der Dekodierung nicht weiter. Über jegliche
> Hilfestellung wäre ich sehr dankbar.
> n und s ist gegeben, also ist phi von n einfach zu
> berechnen: 16*22= 352, mit erw. euklid. Algo habe ich auch
> den privaten Schlüssel 17 berechnet. Zum entschlüsseln muss
> ich doch jetzt 101^17 mod 391 rechnen oder?
So weit: Ja.
> Erhalte dann 52. Ist das so richtig?
Ich erhalte als Ergebnis: 118
|
|
|
|
|
Status: |
(Mitteilung) Reaktion unnötig | Datum: | 13:17 Fr 16.01.2009 | Autor: | mavis |
Vielen DAnk für die schnelle Rückantwort, aber kannst du mir bitte erklären wie du auf dieses Ergebnis kommst? Wie hab ich das in den Taschenrechner einzugeben? Ich habe 17 in zweierpotenzen umgeschrieben. Also 17= 1 + 16 und hab das dann so einzeln ausgerechnet. Wie rechnet man das geschickt aus?
|
|
|
|
|
> Vielen Dank für die schnelle Rückantwort, aber kannst du
> mir bitte erklären wie du auf dieses Ergebnis kommst? Wie
> hab ich das in den Taschenrechner einzugeben? Ich habe 17
> in Zweierpotenzen umgeschrieben. Also 17= 1 + 16 und hab
> das dann so einzeln ausgerechnet. Wie rechnet man das
> geschickt aus?
hallo mavis,
ich habe im Moment nicht einmal einen Taschenrechner
hier und habe deshalb mit der Rechnerfunktion von
Google gerechnet. Folgendermassen:
$\ [mm] (101^4)\ [/mm] mod\ 391=104 060 401\ mod\ 391= 52$
$\ [mm] \left(101^{16}\right)\ [/mm] mod\ [mm] 391=(101^4)^4\ [/mm] mod\ 391 = [mm] 52^4\ [/mm] mod\ 391 = 307$
$\ [mm] \left(101^{17}\right)\ [/mm] mod\ [mm] 391=(101^{16}*101^1)\ [/mm] mod\ 391 = (307*101)\ mod\ 391 =$ 118
... und erst jetzt entdecke ich, dass die Modulo-Rechnung
im Google-Rechner tatsächlich funktioniert (vorher habe
ich es noch mit Division, Subtraktion etc. gemacht). Auf die
Eingabe 101 ^ 7 mod 391 liefert Google den Wert 50, für
höhere Exponenten kapituliert er dann aber doch.
Gruß
|
|
|
|
|
Status: |
(Mitteilung) Reaktion unnötig | Datum: | 14:36 Fr 16.01.2009 | Autor: | mavis |
Vielen Dank, jetzt sehe ich auch wo mein Fehler in der Rechnung lag.
vg,
mavis
|
|
|
|