| Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung Nächste Überarbeitung | Vorherige Überarbeitung |
| faecher:informatik:oberstufe:kryptographie:rsaverfahren:start [31.03.2022 18:07] – [Aus Einweg mach Falltür] sbel | faecher:informatik:oberstufe:kryptographie:rsaverfahren:start [19.01.2023 07:33] (aktuell) – Frank Schiebel |
|---|
| * φ(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]]) |
| |
| | <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. | 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 |}} | {{ :faecher:informatik:oberstufe:kryptographie:rsaverfahren:rsa.drawio.png?700 |}} |
| |
| * 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 Bon weitergibt. Ein Angreifer Mallory darf diesen auch erhalten. | * 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 ihr geheimer 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. |
| Kennt Bob Alices öffentlichen Schlüssel e, dann verschlüsselt er damit seine Nachricht m, die er wie oben gezeigt als Zahl betrachtet. Dazu berechnet er c:=me (mod n). c ist der Geheimtext, den er an Alice schickt. Die Verschlüsselung entspricht einer Modulo-Exponentiation. | |
| | |
| Die von Bob erhaltene Nachricht c kann Alice nun entschlüsseln, indem sie cd (mod n) berechnet. Das Ergebnis ist dann genau der Klartext m, den Bob abgeschickt hat. Dieses 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 nicht kennt. | |
| |
| | Für die teilerfremde Zahl e kann man ein Primzahl wählen, z.B. 3, 17 oder 65537. |
| |