faecher:informatik:oberstufe:kryptographie:rsamathe:start

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung
Nächste Überarbeitung		 Vorherige Überarbeitung
faecher:informatik:oberstufe:kryptographie:rsamathe:start [31.03.2022 16:58] – [Modulo-Wurzelziehen] sbelfaecher:informatik:oberstufe:kryptographie:rsamathe:start [12.01.2023 09:35] (aktuell) – [Modulo-Multiplikation und -Division] Frank Schiebel
Zeile 1: Zeile 1:
-====== Mathematik des RSA Verfahrens ======+====== Modulo-Rechnen ======
  
 ===== Das RSA Verfahren ===== ===== Das RSA Verfahren =====
Zeile 11: Zeile 11:
 ===== Modulo-Rechnen ===== ===== 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> <code>
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<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 ==== ==== Modulo-Exponentiation ====
Zeile 202: Zeile 224:
 Beispiel:  Beispiel: 
  
-  * $3^3=3 (mod\;6)$, da $3=1 (mod\; (φ (6))$ +  * $3^3=3 (mod\;6)$, da $3=1 (mod\; (φ(6))$ 
-  * a=3, b=3 n=6, b-1=2  +  * Hier ist: $a=3$, $b=3$, $n=6$, $b-1=2$ und $φ(6) = 2$. $b-1=2$ ist ein Vielfaches $φ(6) = 2$
-Aus diesem Satz folgt (wenn wir beide Seiten der Gleichung mit einer Zahl i ieren) ein weiterer:+
  
-Satz: Sind a, i und n natürliche Zahlen (a<n), dann gilt: ai (mod\; φ(n)) = ai (mod n).+Aus diesem Satz folgt (wenn wir beide Seiten der Gleichung mit einer Zahl i potenzieren) ein weiterer 
 + 
 +**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)
 ++++ ++++
 +
 +Unter Beachtung einiger mathematischer Sätze kann man die die a-te Modulo-Wurzel einer Zahl folgendermaßen berechnen: Gegeben sind a, b und n, gesucht ist die Zahl x für die gilt
 +
 +$x^a=b\;(mod\; n)$.
 +
 +<WRAP center round tip 90%>
 +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>
 +
  • faecher/informatik/oberstufe/kryptographie/rsamathe/start.1648738724.txt.gz
  • Zuletzt geändert: 31.03.2022 16:58
  • von sbel