| Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung Nächste Überarbeitung | Vorherige Überarbeitung |
| faecher:informatik:oberstufe:kryptographie:rsaverfahren:start [01.04.2022 11:54] – [Ablauf des RSA Verfahrens] 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 ===== |