Einweg-Funktion

Eine Einweg-Funktion ist eine Funktion, die komplexitätstheoretisch leicht berechenbar, aber schwer umzukehren ist.

Die Existenz von Einwegfunktionen ist bis heute nicht bewiesen. Falls sie existieren, ist aber bewiesen dass dann auch gilt.

Siehe auch

P-NP-Problem

Trapdoor-Einwegfunktionen

Trapdoor-Einwegfunktionen sind spezielle Einweg-Funktionen, die sich dann effizient umkehren, wenn man eine gewisse Zusatzinformation besitzt. Trapdoor-Einwegfunktionen werden in asymmetrischen Verschlüsselungsverfahren genutzt.

Beispiel

Gegeben ist und die Funktion

Das Umkehren von ist schwierig ohne Kenntnis von beiden Variablen und

Gute Kandidaten für Einwegfunktionen

• SHA-2
• Multiplikation von Primzahlen - Primfaktorisierung
• Potenzierung im - Diskreter Logarithmus