Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:kryptographie:rsamathe:start [31.03.2022 15:09] – [Modulo-Wurzelziehen] sbel
+++ faecher:informatik:oberstufe:kryptographie:rsamathe:start [07.06.2024 10:03] (aktuell) – [Diskreter Logarithmus] Frank Schiebel
@@ Zeile 1: / Zeile 1: @@
-====== Mathematik des RSA Verfahrens ======
+====== Modulo-Rechnen ======
 ===== Das RSA Verfahren =====
@@ Zeile 11: / Zeile 11: @@
 ===== Modulo-Rechnen =====
-Sicherlich kennst du bereits die Module Operation: Sie liefert den Rest bei einer ganzzahligen Division zweier ganzer Zahlen zurück:
+Sicherlich kennst du bereits die Modulo-Operation: Sie liefert den Rest bei einer ganzzahligen Division zweier ganzer Zahlen zurück:
 <code>
@@ Zeile 28: / Zeile 28: @@
-FIXME Zahlenkreis als Veransachaulichung
+FIXME Zahlenkreis als Veranschaulichung
 ==== Modulo-Addition und -Subtraktion ====
@@ Zeile 149: / Zeile 149: @@
 Was fällt dir auf? Woran könnte das liegen?
+++++ Lösung |
+^ mod 15                                                                                                                                                       |^ mod 13                       ||
+^ a                                                                                                                       ^ a<sup>-1</sup>                      ^ a       ^ a<sup>-1</sup>      ^
+| ---------------------------------------------------------------------------------------------------------------------                                                                     ||||
+| 0                                                                                                                       | NN                                  | 0       | NN                  |
+| 1                                                                                                                       | 1                                   | 1       | 1                   |
+| 2                                                                                                                       | 8 (8*2 mod 15 =1)                   | 2       | 7                   |
+| 3                                                                                                                       | NN                                  | 3       | 9 (27 mod 13 = 1)   |
+| 4                                                                                                                       | 4 (4*4 mod 15 =1)                   | 4       | 10 (40 mod 13 = 1)  |
+| 5                                                                                                                       | NN                                  | 5       | 8 (40 mod 13 =1)    |
+| 6                                                                                                                       | NN                                  | 6       | 11 (66 mod 13 = 1)  |
+| 7                                                                                                                       | 13 (13*7 mod 15 = 91 mod 15 =  1)   | 7       | 2 (14 mod 13 =1)    |
+| 8                                                                                                                       | 2                                   | 8       | 5 (s.o.)            |
+| 9                                                                                                                       | NN                                  | 9       | 3 (s.o.)            |
+| 10                                                                                                                      | NN                                  | 10      | 4 (s.o.)            |
+| 11                                                                                                                      | 11 (11*11 mod 15 = 121 mod 15 = 1)  | 11      | 6 (s.o.)            |
+| 12                                                                                                                      | NN                                  | 12      | 12                  |
+| 13                                                                                                                      | 7  (s.o.)                           | 13      | NN                  |
+| 14                                                                                                                      | 14 (196 mod 15 = 1)                 | 14      | 1                   |
+++++
 ==== Modulo-Exponentiation ====
@@ Zeile 165: / Zeile 187: @@
 ==== Diskreter Logarithmus ====
-Eine Umkehrung des Potentzierens ist der Logarithmus. Beim Modulo-Rechnen stellt man sich die folgende Frage (a, b und n  sind gegeben):
+Eine Umkehrung des Potenzierens ist der Logarithmus. Beim Modulo-Rechnen stellt man sich die folgende Frage (a, b und n  sind gegeben):
 Für welche Zahl  $x$  gilt  $a^x=b\;(mod\; n)$ ?
@@ Zeile 208: / Zeile 230: @@
 **Satz:** Sind  $a$ ,  $i$  und  $n$  natürliche Zahlen ( $a<n$ ), dann gilt:  $a^{i (mod\; φ(n))} = a^{i} (mod\; n)$ .
+Nun kann man die die a-te Modulo-Wurzel einer Zahl berechnen. Gegeben sind a, b und n, gesucht ist die Zahl x für die gilt
+ $x^a=b\;(mod\; n)$
+Wenn a und φ(n) teilerfremd sind,  kann man mit dem euklidischen Algorithmus die Zahl  $c=a^{-1} (mod\; φ(n))$  berechnen. Mit dieser Zahl potenziert man beide Seiten der Gleichung von oben und erhält:
+ $(x^a)^{c(mod\; φ(n))} = b^{c(mod φ (n))}(mod\; n)$
+Durch die Anwendung des zweiten Satzes von obenkönnen wir die rechte Seite vereinfachen:
+ $(x^a)^{c(mod\; φ(n))} = b^c (mod\; n)$ .
+Da  $a·c = 1 (mod φ(n))$ , erhalten wir auf der linken Seite:
+ $x^{1(mod \;φ(n))}=b^c (mod\; n)$ .
+Also ist x nach dem ersten Satz von oben:
+x=b^c (mod\; n)
 ++++
@@ Zeile 214: / Zeile 256: @@
  $x^a=b\;(mod\; n)$ .
-W<WRAP center round tip 90%>
+<WRAP center round tip 90%>
-enn man φ(n)kennt und a und φ(n) teilerfremd sind gilt $x=b^c\;(mod\; n
+Wenn man φ(n) kennt und a und φ(n) teilerfremd sind gilt $x=b^c\;(mod\;n) $.\\ Für$ c $gilt dabei$ c=a^{-1} (mod\; φ(n))$.
 </WRAP>
-)$