Aufgabe zum RSA-Verf. < Krypt.+Kod.+Compalg. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 18:35 Mi 26.01.2011 | | Autor: | RalU |
| Aufgabe | Bei einer Beispiel-Verschlüsselung nach dem RSA-Verfahren (Public-Key-Verschlüsselung) sind folgende Werte bekannt:
Zwei Primzahlen p=7, q=11, öffentlicher Exponent e=17, RSA-Modul: m=pq=77, damit auch [mm] \phi(77) [/mm] = (p-1)*(q-1) = 60
a) Welche Eigenschaft muss e=17 erfüllen, damit ein privater Schlüssel d existiert?
b) Zu bestimmen ist der private Schlüssel (beim Ausprobieren am besten mit negativen Zahlen beginnen)
c) Welcher Zahlenbereich kann als Nachricht versendet werden (dezimale Zahlen)?
e) Wie lautet die Chiffre-Zahl C für die Nachricht P=66?
f) Zeigen Sie, dass die Entschlüsselung von c wieder auf P=66 führt |
zu a) Es muss folgende Gleichung erfüllt werden:
eq mod m [mm] \equiv [/mm] 1, da e=17, sowie [mm] \phi(m)=60 [/mm] bekannt, muss also ein passendes d gefunden werden [mm] (d=e^{-1}), [/mm] dass die Gleichung erfüllt, z.B. mit Hilfe des erweiterten Euklidischen Algorithmus oder duch ausprobieren.
zu b) Ausprobieren:
mit [mm] d=-7+\phi(77) [/mm] = -7+60 = 53 gilt:
ed mod m [mm] \equiv [/mm] 1, also 17*53 mod 77 [mm] \equiv [/mm] 1
zu c)
Der Zahlenbereich reicht von 1 bis < der Länge des RSA-Moduls, also von 1 bis 76, bin mir da aber nicht sicher....
zu d)
[mm] C=66^{17} [/mm] mod 77
[mm] \equiv 66^{16}*66 [/mm] mod 77
[mm] \equiv (66^{2}*66^{2}*66^{2}*66^{2})^{2}*66 [/mm] mod 77
[mm] \equiv [/mm] (44 * 44 * 44 * [mm] 44)^{2} [/mm] * 66 mod 77
[mm] \equiv [/mm] (11 * [mm] 11)^{2} [/mm] * 66 mod 77
[mm] \equiv (121)^{2} [/mm] * 66 mod 77
[mm] \equiv 44^{2} [/mm] * 66 mod 77
[mm] \equiv [/mm] 11 * 66 mod 77
[mm] \equiv [/mm] 33
-> C = 33
zu e)
Entschlüsselung beim RSA:
P = [mm] C^{d} [/mm] mod m, also
= [mm] 33^{53} [/mm] mod 77
Gibt es einen Weg, dies von Hand auszurechnen?
Aber es gilt ja:
P = [mm] C^{d} [/mm] und C = [mm] P^{e}, [/mm] so dass man auch einsetzen kann:
also
P = [mm] C^{d} [/mm] mod m
= [mm] (P^{e})^{d} [/mm] mod m
= [mm] (66^{17})^{53} [/mm] mod 77
[mm] \equiv 66^{17*53} [/mm] mod 77
[mm] \equiv 66^{901} [/mm] mod 77
Es gilt: ggT(66, 77) = 1 -> Satz von Euler anwenden:
[mm] \equiv 66^{901 mod \phi{77}} [/mm] mod 77
[mm] \equiv 66^{901 mod 60} [/mm] mod 77
[mm] \equiv 66^{1} [/mm] mod 77
[mm] \equiv [/mm] 66
Gezeigt wurde damit zwar die Aufgabenstellung. Allerdings kann Derjenige, der die Nachricht wieder entschlüsselt ja nicht so vorgehen, was mich etwas verwirrt...
Stimmen die Angaben so?
Mit freundlichem Gruß,
Ralf
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:21 Fr 28.01.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
