RSA-Verschlüsselung, Beispiel < Krypt.+Kod.+Compalg. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:43 Mo 22.11.2010 | | Autor: | RalU |
| Aufgabe | für eine RSA-Verschlüsselung ist folgendes gegeben:
p=7, q=11, e=17
1) Wie lautet die Chiffre-Zahl c für die Nachricht P=66 ?
2) Zeigen Sie, dass die Entschlüsselung von c wieder auf P=66 führt |
zu 1)
mit p=7 und q=11 liegt der RSA-Modul N=77 vor.
[mm] c=P^{e} [/mm] mod 77 [mm] =66^{17} [/mm] mod 77
[mm] c=66^{16} [/mm] * 66 mod 77
[mm] c=(66^{2}*66^{2}*66^{2}*66^{2}) [/mm] * 66 mod 77
Wie kann man nun weiter umwandeln, um die Aufgabe mit möglichst wenig Rechenaufwand zu lösen?
Es ist durchaus möglich, den Satz von Euler anzuwenden, etc.
Vielen Dank für Eure Hinweise...
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:49 Mo 22.11.2010 | | Autor: | felixf |
Moin!
> für eine RSA-Verschlüsselung ist folgendes gegeben:
>
> p=7, q=11, e=17
>
> 1) Wie lautet die Chiffre-Zahl c für die Nachricht P=66 ?
> 2) Zeigen Sie, dass die Entschlüsselung von c wieder auf
> P=66 führt
> zu 1)
> mit p=7 und q=11 liegt der RSA-Modul N=77 vor.
>
> [mm]c=P^{e}[/mm] mod 77 [mm]=66^{17}[/mm] mod 77
> [mm]c=66^{16}[/mm] * 66 mod 77
> [mm]c=(66^{2}*66^{2}*66^{2}*66^{2})[/mm] * 66 mod 77
Das stimmt nicht. In der letzten Zeile steht [mm] $66^{2}*66^{2}*66^{2}*66^{2} [/mm] * 66 = [mm] 66^{2+2+2+2+1} [/mm] = [mm] 66^9$.
[/mm]
> Wie kann man nun weiter umwandeln, um die Aufgabe mit
> möglichst wenig Rechenaufwand zu lösen?
Mach es so:
[mm] $(66^2)^2 [/mm] = [mm] 66^{2 \cdot 2} [/mm] = [mm] 66^4$
[/mm]
[mm] $((66^2)^2)^2 [/mm] = [mm] (66^4)^2 [/mm] = [mm] 66^{4 \cdot 2} [/mm] = [mm] 66^8$
[/mm]
[mm] $(((66^2)^2)^2)^2 [/mm] = [mm] (66^8)^2 [/mm] = [mm] 66^{8 \cdot 2} [/mm] = [mm] 66^{16}$
[/mm]
Das sind vier Quadrierungen. Besser geht es nur mit Multiplikation nicht.
> Es ist durchaus möglich, den Satz von Euler anzuwenden,
> etc.
Der bringt dir hier gar nichts, weil der Exponent zu klein ist.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 17:54 Mo 22.11.2010 | | Autor: | RalU |
Als Ergebnis dieser Aufgabe soll laut Musterlösung c=33 rauskommen.
die Zeile
> > [mm]c=(66^{2}*66^{2}*66^{2})*66^{2}[/mm] * 66 mod 77
war falsch.
Aber es gilt doch:
[mm] c=(66^{2}*66^{2}*66^{2}*66^{2})^{2}* [/mm] 66 mod 77
Dennoch komm ich hier nicht weiter.
Aber es muss sich irgendwie die Regel (a*b) mod c = a mod b * b mod c anwenden lassen, womit man dann weiter umformen kann...
trotzdem Danke für die Hilfe.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:20 Mi 24.11.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
