Hauptmenü öffnen

Einwegfunktion

Funktion, die leicht zu berechnen, aber schwer umzukehren ist

In der Informatik ist eine Einwegfunktion eine mathematische Funktion, die komplexitätstheoretisch „leicht“ berechenbar, aber „schwer“ umzukehren ist. In einem erweiterten Sinn werden auch Funktionen so bezeichnet, zu denen bisher keine in angemessener Zeit praktisch ausführbare Umkehrung bekannt ist.

Ein anschauliches Beispiel wäre ein klassisches Papier-Telefonbuch einer größeren Stadt: Kennt man den Namen, dann findet man sehr schnell die dazugehörige Telefonnummer. Kennt man jedoch nur die Telefonnummer, so ist es sehr aufwändig, den zugehörigen Namen zu finden.

Einwegfunktionen bilden die Grundlage asymmetrischer Kryptosysteme.

DefinitionBearbeiten

Eine mathematische Einwegfunktion   muss folgende Eigenschaften aufweisen:

  • Die Berechnung des Funktionswerts   zu gegebenem   ist „einfach“, d. h., es existiert ein Algorithmus, der ihn in Polynomialzeit berechnet.
  • Die Berechnung der Umkehrung der Funktion, d. h. eines Urbildes   zu einem gegebenen   so dass  , ist allerdings „schwer“, d. h., es existiert kein probabilistischer Algorithmus  , der in Polynomialzeit läuft und mit nicht vernachlässigbarer Wahrscheinlichkeit zu dem eingegebenen Bild ein Urbild ausgibt.
    Genauer gilt für jeden probabilistischen Algorithmus   mit geeignetem Ein- und Ausgabeformat: für jedes   ist bei genügend großem   für ein zufällig gleichverteilt aus   gewähltes   die Wahrscheinlichkeit kleiner als  , dass   erfolgreich ein Urbild von   bestimmt:
     .

Problem der Existenz der EinwegfunktionenBearbeiten

Es ist nicht bekannt, ob es Funktionen gibt, die die Einweg-Bedingungen erfüllen. Tatsächlich würde der Beweis ihrer Existenz gleichzeitig den Beweis für P≠NP bedeuten. Umgekehrt folgt aus P≠NP nicht die Existenz von Einwegfunktionen: Zur Umkehrung der Funktion darf auch ein probabilistischer Algorithmus eingesetzt werden. Damit die Umkehrung also ausreichend ineffizient ist, darf zusätzlich NP keine Teilmenge der Komplexitätsklasse BPP sein.

AnwendungenBearbeiten

Einwegfunktionen sind vor allem für Anwendungen in der Kryptologie interessant. Für einen solchen Einsatz ist komplexitätstheoretisch aber noch eine weitere Forderung nötig: Die genannten Komplexitätsklassen betrachten den jeweils schlechtesten Fall (Worst Case), die längste Laufzeit eines Algorithmus. Für die kryptographische Anwendung muss der Algorithmus auch im Durchschnittsfall (Average Case) ineffizient sein.

Direkte Anwendung einer Einwegfunktion gibt es bei Passwörtern. Diese werden häufig nicht direkt abgespeichert, sondern als Ausgabe einer kryptographischen Hashfunktion, der das Passwort eingegeben wird (meist noch mit Salt ergänzt). Die Prüfung beim Login erfolgt dann nicht durch Vergleich der Passwörter im Klartext, sondern der Hashwerte. Dadurch kann ein Administrator oder ein Unberechtigter mit Systemzugang nie die Passwörter der Benutzer lesen. Er kann allenfalls mit einem Programm wie Crack mögliche Passwörter durchprobieren. Eine kryptographischen Hashfunktion verhält sich wie eine Einwegfunktion, genauer: es ist kein Weg bekannt, eine Eingabe zu einer gegebenen Ausgabe effizient zu berechnen (Preimage-Angriff).

In der Praxis kennt man Funktionen, die die Anforderungen an eine Einwegfunktion bislang ausreichend erfüllen. Es konnte jedoch bisher nicht der Beweis erbracht werden, ob es wirklich „schwierig“ ist, sie zu invertieren. Ein Beispiel für eine solche Funktion ist die Multiplikation von zwei großen Primzahlen, da man annimmt, dass eine Primfaktorzerlegung ein „schwieriges“ Problem darstellt. Ein weiteres Beispiel ist die modulare Exponentiation und deren Inverse, der diskrete Logarithmus.

Einwegfunktionen mit Falltür (Trapdoor-Einwegfunktionen)Bearbeiten

Eine Variante der Einwegfunktionen sind Trapdoor-Einwegfunktionen, auch Falltürfunktionen genannt. Diese lassen sich nur dann effizient umkehren, wenn man eine gewisse Zusatzinformation besitzt. Falltürfunktionen werden in asymmetrischen Verschlüsselungsverfahren wie zum Beispiel RSA verwendet. Eine Metapher für Falltürfunktionen ist die Funktion eines Briefkastens: Jeder kann einen Brief einwerfen. Das Herausholen ist dagegen sehr schwierig – es sei denn, man ist im Besitz des Schlüssels.

Bekannte Einwegfunktionen im erweiterten SinnBearbeiten

Als Einwegfunktionen im erweiterten Sinn werden folgende Funktionen genannt, zu denen derzeit keine effiziente Umkehrung bekannt ist:

LiteraturBearbeiten

  • Jonathan Katz, Yehuda Lindell: Introduction to Modern Cryptography: Principles and Protocols. Chapman & Hall/CRC, 2007.

WeblinksBearbeiten