Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- ef:kryptographie:rsa [2023/09/07 12:32] – lehmannr
+++ ef:kryptographie:rsa [2023/09/14 14:56] (aktuell) – lehmannr
@@ Zeile 22: / Zeile 22: @@
 <WRAP nicebox green>
-**Aufgabe ** \\
+**Aufgabe 1** \\
   - Bestimme $\varphi(n)$ für alle Zahlen $n<20$.
   - Wie gross ist $\varphi(p)$ für eine Primzahl $p$?
@@ Zeile 66: / Zeile 66: @@
 <WRAP nicebox green>
 **Aufgabe 2** \\
-  - Verschlüssle den Text m=6 mit dem öffentilchen Schlüssel $e=19, n=65$
+  - Verschlüssle den Text m=6 mit dem öffentlichen Schlüssel $e=19, n=65$
-  - Knacke den öffentlichen Schlüssel von oben, d.h. finden $\varphi(n)$ und den privaten Schlüssel $d$.
+  - Knacke den öffentlichen Schlüssel von oben, d.h. finde $\varphi(n)$ und den privaten Schlüssel $d$.
   - Worauf basiert die Sicherheit des RSA-Verfahrens? Weshalb ist es schwierig, einen öffentlichen Schlüssel zu knacken?
-  - Jemand fängt die Nachricht $c=15$ ab und er weiss, dass der Absender den öffentlichen Schlüssel $e=7$ und $n=27$ hat.\\ Wie lautet der Klartext?
+  - Jemand fängt die Nachricht $c=15$ ab und er weiss, dass der Absender den öffentlichen Schlüssel $e=7$ und $n=77$ hat.\\ Wie lautet der Klartext?
   - Versuche mit Hilfe von Python/Mathematica den Schlüssel aus dem Einführungsbeispiel zu knacken ($e = 24'019$ und $n=213'693'769$).
 </WRAP>
@@ Zeile 77: / Zeile 77: @@
 === Der Satz von Euler ===
-Für zwei teilerfremde Zahlen $a$ und $n$ gilt: $a^{\varphi(n)}=1$ mod n.
+Für zwei teilerfremde Zahlen $a$ und $n$ gilt: $a^{\varphi(n)} mod n =1$.
-Beim RSA-Verfahren wird die Meldung $m$ zu einem Geheimtext $c$ verschlüsselt durch $c=m^e$ mod $n$. Danach wird der Geheimtext wieder hoch den privaten Schlüssel $d$ gerechnet, man hat also insgesamt: $( (m^e)$ mod n $)^d$ mod n. Und dies sollte wieder m geben.\\
+Beim RSA-Verfahren wird die Meldung $m$ zu einem Geheimtext $c$ verschlüsselt durch $c=m^e$ mod $n$. Danach wird der Geheimtext wieder hoch den privaten Schlüssel $d$ gerechnet, man hat also insgesamt: $( (m^e)$ mod n $)^d$ mod n. Und dies sollte wieder m geben.
+Das Obige kann man auch mit einem einzigen mod n schreiben: $m^{e\cdot d}$ mod n sollte also wieder m geben.
-Da $d$ so gewählt ist, dass $e\cdot d = 1$ mod $\varphi(n)$, ist $e\cdot d = 1 + k \cdot \varphi(n)$
+Da $d$ so gewählt ist, dass $e\cdot d = 1$ mod $\varphi(n)$, ist $e\cdot d = 1 + k \cdot \varphi(n)$, woraus folgt:
+$m^{e\cdot d}$ mod n  = $m^{1 + k \cdot \varphi(n)} = m^1 \cdot m^{k\cdot \varphi(n)} = m^1 \cdot (m^{\varphi(n)})^k$
+Und da $m^{\varphi(n)=1}$ mod n (zumindest für m teilerfremd zu n), gilt:
+$m^{e\cdot d}$ mod n $=m$.
 [[ef:start|Zurück zur Übersicht]]
 </WRAP>