RSA | MathePrisma

Eine Einwegfunktion ist eine Funktion, die einfach zu berechnen aber sehr schwer umkehrbar ist. Im täglichen Leben findet man viele 'Einwegfunktionen':

sich ein Bein brechen
Zahnpasta aus der Tube drücken
Brief zerreißen

Die korrekte (mathematische) Definition lautet:

Einwegfunktion

Eine Einwegfunktion (engl. one-way-function) ist eine injektive Funktion $f : X \rightarrow Y$ für die folgendes gilt:

Es gibt ein effizientes (!) Verfahren zur Bestimmung von $y = f(x) \; \forall x \in X$ .
Die Umkehrung ist praktisch (!) unmöglich, d.h. es gibt kein effizientes Verfahren zur Bestimmung von $x = f^{-1}(y) \; \forall y \in f(X)$ .

Achtung Falle!

Das heißt nicht, dass eine Einwegfunktion nicht umkehrbar ist, die Umkehrung ist nur so schwierig, dass sie praktisch nicht umzusetzen ist.
Das heißt dann aber, dass eine Verschlüsselung durch eine Einwegfunktion weder von Unbefugten geknackt, noch vom rechtmäßigen Empfänger der Nachricht entschlüsselt werden kann.
Man braucht also etwas anderes: Einwegfunktionen mit Falltür.

Falltür

Eine Einwegfunktion mit Falltür (engl. trap-door one-way-function) ist eine injektive Funktion $f : X \rightarrow Y$ für die folgendes gilt:

Es gibt effiziente Verfahren zur Berechnung von $y = f(x) \; \forall x \in X$ und $x = f^{-1}(y) \; \forall y \in f(X)$ .
Das Verfahren zur Berechnung von $f^{-1}$ kann nicht aus dem Verfahren zur Berechnung von $f$ hergeleitet werden. Man benötigt eine (geheime) Zusatzinformation.

Auch Einwegfunktionen mit Falltür gibt es im täglichen Leben:

ein Schloss zuschnappen lassen (geht nur mit dem richtigen Schlüssel wieder auf)
Brief in einen Briefkasten werfen (der Briefträger kann ihn leicht wieder herausholen)

MultipleChoice

Was heißt das bezogen auf das Kiste/Schloss/Schlüssel-Beispiel?

Die Einwegfunktion entspricht dem	Schloss Schlüssel
Die Falltür entspricht dem	Schloss Schlüssel

Wie findet man nun konkrete Einwegfunktionen mit Falltür, um eine Nachricht zu verschlüsseln?