RSA - Kryptographie < Krypt.+Kod.+Compalg. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Ver- und Entschlüsselung
Mit dem RSA Verfahren zu verschlüsseln ist relativ einfach. Man nehme eine Zahl m und potenziere Sie mit dem öffentlichen Schlüssel e. Das Ergebnis rechnen wir modulo n und erhalten die Geheimzahl c.
c = me % n
Der Empfänger entschlüsselt auf die Gleiche Weise, benutzt aber statt des öffentlichen Schlüssels den privaten. Er rechnet also
m' = cd % n
Wenn alles gut gegangen ist, also die Schlüssel gültig sind, dann gilt m' = m. Sie glauben es nicht? Dann nehmen wir ein Beispiel.
Beispiel
Wir wählen p = 3 und q = 7. Damit ist n = p * q = 3 * 7 = 21. Für φ(n) erhalten wir 12, denn (p-1)*(q-1) = (3-1)*(7-1) = 2*6 = 12. Nun wählen wir e = 11 (teilerfremd zu φ(n)). Daraus errechnen wir d = 23, da 23 * 11 % 12 = 1 ist.
Wir wollen nun die Zahl 9 verschlüsseln. Wir rechnen also:
9^11 % 21 = 31381059609 % 21 = 18
Der Empfänger rechnet:
18^23 % 21 = 74347713614021927913318776832 % 21 = 9
Er erhält also genau die "Geheime Nachricht", die wir im zukommen lassen wollten. |
Der Modulo ist ein Divisionsrest. Doch in dem Beispiel ist der Modulo das Produkt der Primzahlen p * q = n.
Frage 1:
Sehe ich das richtig, das Modulo hier tatsächlich Divisionsrest einer Division ist? Wenn ja, von welcher Division?
Frage 2:
Wenn ich eine kleinere Beispielaufgabe hernehme und sage:
10 % 6 = 4
!0/6=1 Rest 4. Da sich der Modulo NICHT um das tatsächliche Ergebis einer Disvision kümmert, sondern um den Divisionsrest ist das korrekte Ergebnis dieser Aufgabe 4 und nicht 1.
Allerdings sind in dem Beispiel sehr große Zahlen % 21 gerechnet. Aber wie, ich komme einfach nicht darauf wäre hier die Modulo-Rechnungs-Herleitung aussehen würde.
9^11 = 31381059609 %21 = 18 beispielsweise.
9^11 = 9*9*9*9*9*9*9*9*9*9*9
Werden evtl während diesen potenzierens bereits Modulo-Rechnungen durchgeführt?.
Wäre echt klasse, wenn Ihr mir den letzten Schliff noch nahebringt.
Gruß
Neutrino_2003
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo und guten Tag,
genau, zB ist
[mm] 9^{2k} \equiv 81^k\:\equiv\: 19\:\: [/mm] modulo [mm] \:\:21.
[/mm]
Gruss,
Mathias
|
|
|
|
