Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung Nächste Überarbeitung | Vorherige Überarbeitung | ||
faecher:informatik:oberstufe:kryptographie:rsaverfahren:start [31.03.2022 11:38] – sbel | faecher:informatik:oberstufe:kryptographie:rsaverfahren:start [19.01.2023 07:33] (aktuell) – Frank Schiebel | ||
---|---|---|---|
Zeile 8: | Zeile 8: | ||
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 " | 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 " | ||
- | <WRAP center round tip 60%> | + | <WRAP center round tip 90%> |
- | Eine Funktion, die einfach | + | Eine Funktion, die man einfach berechnen |
+ | |||
+ | Existiert eine " | ||
</ | </ | ||
+ | |||
+ | |||
+ | {{ : | ||
+ | |||
+ | |||
+ | |||
+ | ===== Primzahl-Multiplikation als Einwegfunktion ===== | ||
+ | |||
+ | Die (normale) Multiplikation zweier Primzahlen ist eine Einwegfunktion. Eine Primzahl-Multiplikation ist heutzutage mit Computerunterstützung einfach durchführbar, | ||
+ | |||
+ | Im Gegensatz dazu sind keine effizienten Verfahren bekannt, mit denen aus dem Produkt zweier großer Primzahlen die beiden Faktoren bestimmt werden können. | ||
+ | |||
+ | ---- | ||
+ | {{: | ||
+ | === (A1) === | ||
+ | |||
+ | * Berechne im Kopf 13·17 | ||
+ | * Bestimme die beiden Primzahlen, die miteinander multipliziert 1189 ergeben (auch im Kopf...) | ||
+ | |||
+ | Je größer die beiden Primzahlen sind, desto komplexer ist dieses sogenannte **Faktorisierungsproblem**: | ||
+ | |||
+ | <WRAP center round info 90%> | ||
+ | Die **Multiplikation zweier großer Primzahlen ist eine Einwegfunktion**. Es ist **einfach, das Produkt zu berechnen**, | ||
+ | </ | ||
+ | |||
+ | Anmerkungen: | ||
+ | |||
+ | * 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> | ||
+ | |||
+ | ===== 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: | ||
+ | |||
+ | * Die a-te Wurzel der Zahl b modulo n lässt sich leicht berechnen, wenn man φ(n) kennt und $a$ und $φ(n)$ teilerfremd sind. ([[..: | ||
+ | * φ(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) ([[..: | ||
+ | |||
+ | <WRAP center round info 90%> | ||
+ | Nach heutigem Kenntnisstand gibt es außer der im Abschnitt [[..: | ||
+ | </ | ||
+ | |||
+ | |||
+ | {{ : | ||
+ | |||
+ | ===== Ablauf des RSA Verfahrens ===== | ||
+ | |||
+ | Alice möchte, dass Bob ihr eine mit RSA verschlüsselte Mitteilung senden kann. | ||
+ | |||
+ | * Alice muss zunächst vorarbeiten: | ||
+ | * 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**, | ||
+ | * Alice berechnet $d=e^{-1}(mod\; | ||
+ | * 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 | ||
+ | |||
+ | Für die teilerfremde Zahl e kann man ein Primzahl wählen, z.B. 3, 17 oder 65537. | ||