imported>314artemis: /* growthexperiments-addlink-summary-summary:2|0|0 */

2025-04-23T19:43:30Z

growthexperiments-addlink-summary-summary:2|0|0

Neue Seite

{{Belege fehlen}}
In der [[Informatik]] ist eine '''Einwegfunktion''' eine [[Funktion (Mathematik)|mathematische Funktion]], die [[Komplexitätstheorie|komplexitätstheoretisch]] „leicht“ berechenbar, aber „schwer“ [[Umkehrfunktion|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 [[asymmetrisches Kryptosystem|asymmetrischer Kryptosysteme]].

== Definition ==
Eine mathematische Einwegfunktion <math>f</math> muss folgende Eigenschaften aufweisen:
* Die Berechnung des Funktionswerts <math>y = f(x)</math> zu gegebenem <math>x</math> ist „einfach“, d. h., es existiert ein [[Algorithmus]], der ihn in [[Polynomialzeit]] berechnet.
* Die Berechnung der Umkehrung der Funktion, d. h. eines Urbildes <math>x</math> zu einem gegebenen <math>y</math> so dass <math>f(x) = y</math>, ist allerdings schwierig, d. h., es existiert kein [[Randomisierter Algorithmus|probabilistischer Algorithmus]] <math>F</math>, der in Polynomialzeit läuft und mit nicht vernachlässigbarer [[Wahrscheinlichkeit]] zu dem eingegebenen Bild ein Urbild ausgibt.<br />Genauer gilt für jeden probabilistischen Algorithmus <math>F</math> mit geeignetem Ein- und Ausgabeformat: für jedes <math>c \in \N</math> ist bei genügend großem <math>n \in \N</math> für ein zufällig [[Diskrete Gleichverteilung|gleichverteilt]] aus <math>\{0,1\}^n</math> gewähltes <math>x</math> die Wahrscheinlichkeit kleiner als <math>n^{-c}</math>, dass <math>F</math> erfolgreich ein Urbild von <math>f(x)</math> bestimmt:<br /><math>\forall c \in \N: \exist n_0 \in \N: \forall n \geq n_0: P_{x \in \{0,1\}^n}\big(\,f(F(f(x))) = f(x) \, \big) \, < \, n^{-c}</math>.

== Problem der Existenz der Einwegfunktionen ==
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-Problem|P≠NP]] bedeuten.<ref name="Goldreich">[[Oded Goldreich]] (2001). Foundations of Cryptography: Volume 1, Basic Tools, S. 70. ([http://www.wisdom.weizmann.ac.il/~oded/PSBookFrag/part2N.ps Entwurf verfügbar] auf Autoren-Webseite). Cambridge University Press. ISBN 0-521-79172-3. Siehe auch [http://www.wisdom.weizmann.ac.il/~oded/foc-book.html wisdom.weizmann.ac.il].</ref> 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 (Komplexitätsklasse)|NP]] keine [[Teilmenge]] der [[Komplexitätsklasse]] [[BPP (Komplexitätsklasse)|BPP]] sein.

== Anwendungen ==
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 [[Kennwort|Passwörtern]]. Diese werden häufig nicht direkt abgespeichert, sondern als Ausgabe einer [[Kryptographische Hashfunktion|kryptographischen Hashfunktion]], der das Passwort eingegeben wird (meist noch mit [[Salt (Kryptologie)|Salt]] ergänzt). Die Prüfung beim [[Login (Informationstechnik)|Login]] erfolgt dann nicht durch Vergleich der Passwörter im Klartext, sondern der Hashwerte. Dadurch kann ein [[Administrator (Rolle)|Administrator]] oder ein Unberechtigter mit Systemzugang nie die Passwörter der Benutzer lesen. Er kann allenfalls mit einem Programm wie ''[[Crack (Passwortüberprüfungsprogramm)|Crack]]'' mögliche Passwörter durchprobieren. Eine kryptographische 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 [[diskreter Logarithmus|diskrete Logarithmus]].

== Einwegfunktionen mit Falltür (Trapdoor-Einwegfunktionen) ==
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 [[Asymmetrische Verschlüsselung|asymmetrischen Verschlüsselungsverfahren]] wie zum Beispiel [[RSA-Kryptosystem|RSA]] verwendet. Ein Vergleich für Falltürfunktionen ist die Funktion eines Tresors: Jeder kann einen Gegenstand im Tresor einschließen. Das Herausholen ist dagegen nahezu unmöglich – es sei denn, man ist im Besitz des Schlüssels / der Schlüsselkombination.

== Bekannte Einwegfunktionen im erweiterten Sinn ==
Als Einwegfunktionen im erweiterten Sinn werden folgende Funktionen genannt, zu denen derzeit keine effiziente Umkehrung bekannt ist:
* die [[Kryptografische Hashfunktion|kryptographischen Hashfunktionen]] wie [[SHA-2]]
* die Multiplikation zweier [[Primzahl]]en bzw. zweier [[Ganze Zahl|ganzer Zahlen]] ist einfach, während die Umkehrung, die [[Primfaktorzerlegung]], schwierig ist
* die Berechnung der [[Diskrete Exponentialfunktion|n-ten Potenz]] eines Elementes einer [[Endliche Gruppe|endlichen Gruppe]] ist bei geeigneter Wahl der Gruppe einfach, während das Auffinden eines Exponenten durch Berechnung des [[Diskreter Logarithmus|diskreten Logarithmus]] aufwändig ist

== Literatur ==
* Jonathan Katz, Yehuda Lindell: ''Introduction to Modern Cryptography: Principles and Protocols''. Chapman & Hall/CRC, 2007.
* Rüdiger Reischuk, Markus Hinkelmann: ''One-Way Functions. Mind the Trap – Escape Only for the Initiated''. In Algorithms Unplugged, S. 131–139. Springer, 2011.

== Einzelnachweise ==
<references responsive />

[[Kategorie:Kryptologie]]
[[Kategorie:Ungelöstes Problem der Informatik]]

Einwegfunktion - Versionsgeschichte

imported>314artemis: /* growthexperiments-addlink-summary-summary:2|0|0 */