Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung Nächste Überarbeitung | Vorherige Überarbeitung | ||
faecher:informatik:oberstufe:kryptographie:rsamathe:start [31.03.2022 15:05] – [Modulo-Wurzelziehen] sbel | faecher:informatik:oberstufe:kryptographie:rsamathe:start [07.06.2024 10:03] (aktuell) – [Diskreter Logarithmus] Frank Schiebel | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
- | ====== | + | ====== |
===== Das RSA Verfahren ===== | ===== Das RSA Verfahren ===== | ||
Zeile 11: | Zeile 11: | ||
===== Modulo-Rechnen ===== | ===== Modulo-Rechnen ===== | ||
- | Sicherlich kennst du bereits die Module | + | Sicherlich kennst du bereits die Modulo-Operation: Sie liefert den Rest bei einer ganzzahligen Division zweier ganzer Zahlen zurück: |
< | < | ||
Zeile 28: | Zeile 28: | ||
- | FIXME Zahlenkreis als Veransachaulichung | + | FIXME Zahlenkreis als Veranschaulichung |
==== Modulo-Addition und -Subtraktion ==== | ==== Modulo-Addition und -Subtraktion ==== | ||
Zeile 149: | Zeile 149: | ||
Was fällt dir auf? Woran könnte das liegen? | Was fällt dir auf? Woran könnte das liegen? | ||
+ | |||
+ | ++++ Lösung | | ||
+ | ^ mod 15 |^ mod 13 || | ||
+ | ^ a ^ a< | ||
+ | | --------------------------------------------------------------------------------------------------------------------- | ||
+ | | 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.) | ||
+ | | 14 | 14 (196 mod 15 = 1) | 14 | 1 | | ||
+ | |||
+ | ++++ | ||
==== Modulo-Exponentiation ==== | ==== Modulo-Exponentiation ==== | ||
Zeile 165: | Zeile 187: | ||
==== Diskreter Logarithmus ==== | ==== Diskreter Logarithmus ==== | ||
- | Eine Umkehrung des Potentzierens | + | Eine Umkehrung des Potenzierens |
Für welche Zahl $x$ gilt $a^x=b\; | Für welche Zahl $x$ gilt $a^x=b\; | ||
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)$. | **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\; | ||
+ | |||
+ | 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\; | ||
+ | |||
+ | Durch die Anwendung des zweiten Satzes von obenkönnen wir die rechte Seite vereinfachen: | ||
+ | |||
+ | $(x^a)^{c(mod\; | ||
+ | |||
+ | Da $a·c = 1 (mod φ(n))$, erhalten wir auf der linken Seite: | ||
+ | |||
+ | $x^{1(mod \; | ||
+ | |||
+ | Also ist x nach dem ersten Satz von oben: | ||
+ | |||
+ | x=b^c (mod\; n) | ||
++++ | ++++ | ||
Zeile 213: | Zeile 255: | ||
$x^a=b\; | $x^a=b\; | ||
+ | |||
+ | <WRAP center round tip 90%> | ||
+ | Wenn man φ(n) kennt und a und φ(n) teilerfremd sind gilt $x=b^c\; | ||
+ | </ | ||
+ |