Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:kryptographie:rsaverfahren:start [31.03.2022 14:37] – [Primzahl-Multiplikation als Einwegfunktion] sbel
+++ faecher:informatik:oberstufe:kryptographie:rsaverfahren:start [03.02.2025 09:35] (aktuell) – Frank Schiebel
@@ Zeile 1: / Zeile 1: @@
 ====== Das RSA Verfahren ======
-Um die Funktionsweise des RSA Verfahrens nachzuvollziehen, musst du dir Klartext, Geheimtext und Schlüssel nicht als Bit-Folgen wie bei AES, sondern einfach als natürliche Zahlen vorstellen. Für den Computer macht das sowieso keinen Unterschied, da dieser alle Daten als Bit-Folge abspeichert udn verarbeitet.
+Um die Funktionsweise des RSA Verfahrens nachzuvollziehen, musst du dir Klartext, Geheimtext und Schlüssel nicht als Bit-Folgen wie bei AES, sondern einfach als natürliche Zahlen vorstellen. Für den Computer macht das sowieso keinen Unterschied, da dieser alle Daten als Bit-Folge abspeichert und verarbeitet.
 ===== 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%>
@@ Zeile 42: / Zeile 42: @@
   * Es lässt sich mathematisch nicht beweisen, dass 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.
+===== Aus Einweg mach Falltür =====
+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.
+Dazu benötigt man die Modulo-Rechnung aus einem der vorigen Wiki-Abschnitte:
+{{: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]])
+<WRAP center round info 90%>
+Nach heutigem Kenntnisstand gibt es außer der im Abschnitt [[..:rsamathe:start#modulo-wurzelziehen |Modulo-Wurzelziehen]] beschriebenen Methode unter Zuhilfenahme von φ(n) keine effektive Methode, die Modulo-Wurzel zu bestimmen. Damit ist das Modulo-Potenzieren eine Falltürfunktion - die Information, die sie umkehrbar macht sind die beiden Primzahlfaktoren aus denen der Modulus n berechnet werden kann. Da die Primzahlmultiplikation eine Einwegfunktion ist, kann man diese Faktoren nachträglich aus n bei genügend großen Primzahlen nicht mehr bestimmen.
+</WRAP>
+{{ :faecher:informatik:oberstufe:kryptographie:rsaverfahren:rsa.drawio.png?900 |}}
+===== Ablauf des RSA Verfahrens =====
+Alice möchte, dass Bob ihr eine mit RSA verschlüsselte Mitteilung senden kann.
+  * 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.
+  * 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.
+  * 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.