Nachricht entschlüsseln < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Der böse Agent X übermittelt seinem Partner Y seinen Standort. Dabei verschlüsselt er seine Koordinaten mit dem öffentlichen Schlüssel von Agent Y:n=667 und e=233. Die verschlüsselte Nachricht lautet (455,536). James Bond will Agent X verhaften. Helfen Sie ihm dabei, die Nachricht zu entschlüsseln |
Hallo,
ich soll diese Aufgabe lösen mit dem RSA-Verfahren.
Ich schreib mal auf, was ich bisher geschafft oder gemacht habe:
1.Primfaktorzerlegung von 667=23*29
=> [mm] \phi(667)=\phi(23)*\phi(29)=22*28=616
[/mm]
2. Berechne das Inverse d zu e=233 mod 616
Dazu berechne ich mit dem erweiterten euklidischen Algorithmus mit dén Zahlen 616 und 233 und durch Rückwärtseinsetzen erhalte ich die Bézout-koeffizienten, die ich benötige.
193*233-73*616=1 => d=193
3. Jetzt muss ich folgende 2 Kongruenzen berechnen:
[mm] 455^{193}\equiv [/mm] X (mod 667)
[mm] 233^{193}\equiv [/mm] Y (mod 667)
Wenn ich die Zahlen X und Y habe, dann muss ich sie nur rückübersetzen, wobei A=01, B=02
Jetzt möchte ich die erste Kongruenz lösen und betrachte es mod. 23 und 29
Modulo 23 gilt
[mm] 455\equiv [/mm] 18 (mod [mm] 23)\equiv [/mm] -5 (m 23)
[mm] 18^{22}\equiv [/mm] 1 (m [mm] 23)\equiv (-5)^{22}
[/mm]
Besser ich rechne mit der -5, oder? Mir wurde gesagt, man sollte immer versuchen, die zahl zu klein wie möglich zu halten.
[mm] (-5)^{193}\equiv ((-5)^{22})^8*(-5)^17 \equiv ((-5)^2)^8*(-5) \equiv 2^8*(-5) \equiv [/mm] -1280 [mm] \equiv [/mm] -15 (m 23)
Modulo 29
455 [mm] \equiv [/mm] 20 (m 29) [mm] \equiv [/mm] -3 (m 29)
[mm] =>(-3)^{28} \equiv [/mm] 1 (m 29)
[mm] =>(-3)^{193} \equiv ((-3)^{28})^6*(-3)^{25}\equiv (-3)^{25} \equiv [/mm] -14 (m. 29) (Das habe ich mit dem Taschenrechner gerechnet. Ich habe es per Hand versucht mit [mm] (-3)^4 [/mm] und ähnlichem, aber hab es nicht hinbekommen. Hat da einer ne Idee, wie man das per Hand ausrechnen kann?)
Damit habe ich folgendes System aufgestellt:
X [mm] \equiv [/mm] -14 (m 29)
X [mm] \equiv [/mm] 8 (m 23)
Nun wollte ich den chinesichem Restsatz anwenden, da ggt(23,29)=1, also [mm] m_1'=23 [/mm] und [mm] m_2'=29, [/mm] aber was muss ich jetzt schreiben für das Fragezeichen
[mm] 23m_1 \equiv [/mm] ? (m 29)
[mm] 29m_2 \equiv [/mm] 6 (m 23)
Es wäre schön, wenn jemand über meine Rechnungen drüberguckt und mir dann bei meinem Problem hilft!
Vielen Dank schonmal
TheBozz-mismo
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:20 Fr 24.05.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
