Zur MathePrisma-Startseite
Zur Modul-Startseite  


RSA (Einwegfunktionen 1)
 

 
 

 
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?
 
Seite 3/12 
 
Eine Funktion f heißt injektiv, wenn verschiedene Argumente zu verschiedenen Funktionswerten führen, d.h.

\[ x \neq y \Rightarrow f(x) \neq f(y). \]