Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Nicht-rsa verschlüsselung
III-4
Nachrichten, die mittels Zahlen m N2003 numerisch kodiert wurden, können mittels x → x17 mod 2003 verschlüsselt werden. (NB: 2003 ist Primzahl)
Welches ist der Exponent d für die zugehörige Entschlüsselungsabbildung x → xd mod 2003 ?
kann mir des bitte jemand erklären? Aus dem script allein werd ich net schlau…
du rechnest den erweiterten Euklid mit primzahl -1 und dem verschlüsselungsexponenten aus. Der zum Verschlüsselungsexponent passende Bezout ist das Inverse von e also das gesuchte d.
ok
tust du mir den gefallen und machst es mal vor?
ich tu mir dann im nachvollziehen leichter, danke für die Mühe!
1 0 2002
0 1 17 | 117
1 -117 13 | 1
-1 118 4 | 3
4 -471 1
Das gesuchte d ist -471 mod 2002 = 1531 mod 2002
1 0 2002
0 1 17 passt 117 mal in 2002, Rest 13
1 -117 13 passt 1x in 17, Rest 4
-1 118 4 3x ; 1
4 -471 1
— ----- 0
ggT(2002,17) = 1 ; Inverses von 17 im R[sub]2002[/sub]= -471 ≡ 1531 mod 2002
Edit: ich schreib zu langsam…
dafür hast es schöner erklärt… :-p
schonmal vielen Dank!
ich weiss, dass ich wenig weiss, aber erklärt mir bitte trotzdem, wie das mit dem erweiterten euklid genau funzt; woher kommen die nullen und einsen in den ersten beiden zeilen und vor allem, warum wird die 117 negativ und dann zur 118?
und wenn wir schon dabei sind:
2. wie viele Multiplikationen in Z2003 benötigt man für eine solche Entschlüsselung? (2 Pkte)
Nix für ungut, aber das fällt dir reichlich spät ein… :anx:
die 1 0 0 1 sind immer fest und sozusagen die startwerte des Algo
die -117 errechnet sich durch 0 (erste Zeile) - (1[aus zweiter Zeile] * 117[div])
die 118 errechnet sich durch 1[zweite Zeile] - (-117 * 1 [div])
-471 = -117 - (118 * 3)
Entschlüsselung funzt mit schneller Expo und die Anzahl der Multiplikationen bei der schnellen Expo ist Anzahl der binärstelllen ohne führende 0 + anzahl der „1“ -2
1531 hat 11 binärstellen und 9 einsen - macht 11 + 9 - 2 = 18 Mult
Da hast du recht.
Trotzdem vielen Dank, hast mir sehr geholfen
jetzt muss ich nur noch wissen, was die erste spalte bei dem algorithmus tut (irgendwie braucht man die net, oder täuscht das?) und wie ich von
dem inversen aufs ergebnis komme, wenns nicht zufällig negativ ist?
wäre bspw 471 auch ≡ 1531 mod 2002 oder wäre das 471 mod 2002 (oder was ganz anders?
In der ersten Spalte steht das selbe, bloß für die andere Zahl.
Die Zeilen kannst du auch lesen als:
12002 + 017 = 2002
02002 + 117 = 17
.
.
42002 - 47117 = 1
4 ist Bézout-Koeffizient zu 2002, (-471) ist Bézout-Koeffizient zu 17, 1 ist ggT der beiden
ha, wunderbar, vielen dank.
und die 2. frage?
1532 = 2002 - 471
einfach Modulo gerechnet halt…
ich depp
danke für die hilfe
Habt ihr vor der Klausur schön hier mitgelesen? :*)
natürlich 1531 
ich hab mich auch leicht verarscht gefühlt, als ich die Aufgabe in der Klausur gesehen hatte… 
und ich hab mich gefreut 
Ich mich auch :o)