| Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung Nächste Überarbeitung | Vorherige Überarbeitung |
| faecher:informatik:oberstufe:kryptographie:rsaverfahren:start [31.03.2022 16:07] – [Aus Einweg mach Falltür] sbel | faecher:informatik:oberstufe:kryptographie:rsaverfahren:start [03.02.2025 09:35] (aktuell) – Frank Schiebel |
|---|
| ====== Das RSA Verfahren ====== | ====== 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 ===== | ===== 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%> |
| 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]]) |
| |
| 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 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?700 |}} | |
| | {{ :faecher:informatik:oberstufe:kryptographie:rsaverfahren:rsa.drawio.png?900 |}} |
| |
| ===== Ablauf des RSA Verfahrens ===== | ===== Ablauf des RSA Verfahrens ===== |
| |
| * 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. |
| |