Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:kryptographie:rsaverfahren:start [31.03.2022 16:40] – [Aus Einweg mach Falltür] sbel
+++ faecher:informatik:oberstufe:kryptographie:rsaverfahren:start [19.01.2023 07:33] (aktuell) – Frank Schiebel
@@ Zeile 46: / Zeile 46: @@
-Des RSA Verfahren basiert darauf, aus der Einwegfunktion "Primzahlmultiplikation" durch geeignete Wahl der beteiligten Zahlen  eine Falltürfunktion zu machen, so dass man bei Kenntnis gewisser Informationen (Schlüssel), eine Faktorisierung einfach bestimmen kann.
+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:
+  * 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]])
+  * φ(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-Wuzel 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?700 |}}
+===== 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.