Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- faecher:informatik:oberstufe:kryptographie:rsaverfahren:start [31.03.2022 17:20] – [Aus Einweg mach Falltür] sbel
+++ faecher:informatik:oberstufe:kryptographie:rsaverfahren:start [Unbekanntes Datum] (aktuell) – gelöscht - Externe Bearbeitung (Unbekanntes Datum) 127.0.0.1
@@ Zeile 1: / Zeile 1: @@
-====== 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.
-===== 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.
-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.
-<WRAP center round tip 90%>
-Eine Funktion, die man einfach berechnen kann, bei der die Umkehrung aber nur mit großem Aufwand berechnet werden kann, nennt man **Einwegfunktion**.
-Existiert eine "versteckte Abkürzung", also eine Zusatzinformation, mit der die ansonsten schwierige Umkehrung einfach gemacht wird, dann spricht man von einer **Falltürfunktion**.
-</WRAP>
-{{ :faecher:informatik:oberstufe:kryptographie:rsaverfahren:ewfalltuer.drawio.png?600 |}}
-===== Primzahl-Multiplikation als Einwegfunktion =====
-Die (normale) Multiplikation zweier Primzahlen ist eine Einwegfunktion. Eine Primzahl-Multiplikation ist heutzutage mit Computerunterstützung einfach durchführbar, auch bei großen Zahlen macht das keine Probleme.
-Im Gegensatz dazu sind keine effizienten Verfahren bekannt, mit denen aus dem Produkt zweier großer Primzahlen die beiden Faktoren bestimmt werden können.
-----
-{{:aufgabe.png?nolink  |}}
-=== (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**: "Finde die beiden Primzahlen, die miteinander multipliziert die Zahl X ergeben". Bei Zahlen über tausend Bit Länge ist dieses Problem auch von aktuellen Superrechnern nicht mehr lösbar.
-<WRAP center round info 90%>
-Die **Multiplikation zweier großer Primzahlen ist eine Einwegfunktion**. Es ist **einfach, das Produkt zu berechnen**, aber sehr **schwierig/unlösbar**, zu einer großen Zahl **die beiden Prim-Faktoren zu bestimmen**, die miteinander multipliziert diese Zahl ergeben.
-</WRAP>
-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>Miller-Rabin-Test]] gelöst, dessen Betrachtung hier aber zu weit führen würde.
-===== Aus Einweg mach Falltür =====
-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.
-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 ([[..: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) FIXME Link