faecher:informatik:oberstufe:kryptographie:rsaverfahren: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:rsaverfahren:start [03.02.2025 09:16] – [Das RSA Verfahren] Frank Schiebelfaecher:informatik:oberstufe:kryptographie:rsaverfahren:start [06.05.2025 06:10] (aktuell) – [Ablauf des RSA Verfahrens] Svenja Müller
Zeile 4: Zeile 4:
  
 ===== Einwegfunktionen und Falltürfunktionen ===== ===== Einwegfunktionen und Falltürfunktionen =====
-Im vorigen Wiki-Abschnitt haben wir uns mit der Modulo-Rechnung beschäftigt - diese ist in der Kryptografie wichtig, da einge der Modulo-Rechenarten sind sehr** einfach durchgeführt** werden können, ihre **Umkehrung** oft aber sehr ziemlich **aufwändig** ist.+Im vorigen Wiki-Abschnitt haben wir uns mit der Modulo-Rechnung beschäftigt - diese ist in der Kryptografie wichtig, da einige der Modulo-Rechenarten sehr** einfach durchgeführt** werden können, ihre **Umkehrung** oft aber extrem **aufwändig** ist.
  
-So kann man die **einfache Rechnung als Verschlüsselung** und die **komplizierte Umkehrung als Entschlüsselung** verwenden -- allerding nur dann, wenn es bei der komplizierten Umkehrung eine "versteckte Abkürzung" gibt, die man als **Schlüssel** nehmen kann. +So kann man die **einfache Rechnung als Verschlüsselung** und die **komplizierte Umkehrung als Entschlüsselung** verwenden -- allerdings nur dann, wenn es bei der komplizierten Umkehrung eine "versteckte Abkürzung" gibt, die man als **Schlüssel** nutzen kann. 
  
 <WRAP center round tip 90%> <WRAP center round tip 90%>
Zeile 40: Zeile 40:
 Anmerkungen: Anmerkungen:
  
-  * Es lässt sich mathematisch nicht beweisen, dass dass die Primzahl-Multiplikation eine Einwegfunktion ist, es spricht jedoch alles dafür.+  * Es lässt sich mathematisch nicht beweisen, dass die Primzahl-Multiplikation eine Einwegfunktion ist, es spricht jedoch alles dafür.
   * Ein zentrales Problem dieser Einwegfunktion ist die Erzeugung großer Primzahlen. Das wird meist mit dem [[wpde>Miller-Rabin-Test]] gelöst, dessen Betrachtung hier aber zu weit führen würde.   * Ein zentrales Problem dieser Einwegfunktion ist die Erzeugung großer Primzahlen. Das wird meist mit dem [[wpde>Miller-Rabin-Test]] gelöst, dessen Betrachtung hier aber zu weit führen würde.
  
Zeile 46: Zeile 46:
  
  
-Des RSA Verfahren basiert darauf, eine passende Falltürfunktion zu finden, die bei geeignet Wahl der beteiligten Zahlen eine Information als Schlüssel liefert, mit der sie umgekehrt werden kann.+Das RSA Verfahren basiert darauf, eine passende Falltürfunktion zu finden, die bei geeigneter Wahl der beteiligten Zahlen eine Information als Schlüssel liefert, mit der sie umgekehrt werden kann.
  
 Dazu benötigt man die Modulo-Rechnung aus einem der vorigen Wiki-Abschnitte: Dazu benötigt man die Modulo-Rechnung aus einem der vorigen Wiki-Abschnitte:
  
-  * Die a-te Wurzel der Zahl b modulo n lässt sich leicht berechnen, wenn man φ(n) kennt und $a$ und φ(n) teilerfremd sind.  ([[..:rsamathe:start#modulo-wurzelziehen |Modulo-Wurzelziehen]])+{{:faecher:informatik:oberstufe:kryptographie:rsaverfahren:message.png  |}} 
 +  * Die e-te Wurzel der Zahl c modulo n lässt sich leicht berechnen, wenn man φ(n) kennt und Hochzahl $e$ und φ(n) teilerfremd sind.  ([[..:rsamathe:start#modulo-wurzelziehen |Modulo-Wurzelziehen]])
   * φ(n) kann man leicht berechnen, wenn es sich bei n um das Produkt zweier Primzahlen p und q handelt. Dann gilt φ(n)=(p-1)·(q-1) ([[..:rsamathe:start#modulo-wurzelziehen |Modulo-Wurzelziehen]])   * φ(n) kann man leicht berechnen, wenn es sich bei n um das Produkt zweier Primzahlen p und q handelt. Dann gilt φ(n)=(p-1)·(q-1) ([[..:rsamathe:start#modulo-wurzelziehen |Modulo-Wurzelziehen]])
  
Zeile 65: Zeile 66:
  
   * Alice muss zunächst vorarbeiten: Sie wählt zufällig zwei große Primzahlen p und q und berechnet daraus den Modulus n=p·q.   * Alice muss zunächst vorarbeiten: Sie wählt zufällig zwei große Primzahlen p und q und berechnet daraus den Modulus n=p·q.
-  * Anschließend wählt sie eine natürliche Zahl e, die teilerfremd zu φ(n) ist. Zur Erinnerung φ(n)=(p-1)·(q-1)). Die Zahlen **n und e bilden zusammen den öffentlichen Schlüssel**, den Alice öffentlich bekannt macht, also auch an Bob weitergibt. wenn ein Angreifer (Mallory) den schlüssel in die Hände bekommt ist das kein Problem.+  * Anschließend wählt sie eine natürliche Zahl e, die teilerfremd zu φ(n) ist. Zur Erinnerung φ(n)=(p-1)·(q-1)). Die Zahlen **n und e bilden zusammen den öffentlichen Schlüssel**, den Alice öffentlich bekannt macht, also auch an Bob weitergibt. Wenn ein Angreifer (Mallory) den Schlüssel in die Hände bekommt ist das kein Problem.
   * Alice berechnet $d=e^{-1}(mod\; φ(n))$. d ist der geheime Schlüssel, den sie natürlich für sich behalten muss.   * Alice berechnet $d=e^{-1}(mod\; φ(n))$. d ist der geheime Schlüssel, den sie natürlich für sich behalten muss.
-  * Nachdem Bob Alices öffentlichen Schlüssel hat (e,n), kann er damit seine Nachricht m, die er als Zahl betrachtet verschlüsseln. Dazu berechnet er $c=m^e mod\; n$. $c$ ist der Geheimtext, den er dann an Alice sendet. Die Verschlüsselung entspricht einer Modulo-Exponentiation.+  * Nachdem Bob Alices öffentlichen Schlüssel hat (n, e), kann er damit seine Nachricht m, die er als Zahl betrachtet, verschlüsseln. Dazu berechnet er $c=m^e mod\; n$. $c$ ist der Geheimtext, den er dann an Alice sendet. Die Verschlüsselung entspricht einer Modulo-Exponentiation.
   * Die verschlüsselte  Nachricht $c$ kann Alice entschlüsseln, indem sie $c^d (mod\; n)$ berechnet. Das Ergebnis ist der Klartext m, den Bob abgeschickt hat. Das Entschlüsseln entspricht einem Modulo-Wurzelziehen: Alice zieht die e-te Modulo-Wurzel von c, indem sie die d-te Potenz berechnet. Mallory kann d nicht ermitteln, weil er die Faktorisierung von n und damit φ(n) nicht kennt.   * Die verschlüsselte  Nachricht $c$ kann Alice entschlüsseln, indem sie $c^d (mod\; n)$ berechnet. Das Ergebnis ist der Klartext m, den Bob abgeschickt hat. Das Entschlüsseln entspricht einem Modulo-Wurzelziehen: Alice zieht die e-te Modulo-Wurzel von c, indem sie die d-te Potenz berechnet. Mallory kann d nicht ermitteln, weil er die Faktorisierung von n und damit φ(n) nicht kennt.
  
 Für die teilerfremde Zahl e kann man ein Primzahl wählen, z.B. 3, 17 oder 65537. Für die teilerfremde Zahl e kann man ein Primzahl wählen, z.B. 3, 17 oder 65537.
  
  • faecher/informatik/oberstufe/kryptographie/rsaverfahren/start.1738574215.txt.gz
  • Zuletzt geändert: 03.02.2025 09:16
  • von Frank Schiebel