Einwegfunktion
Eine Funktion, die sich vorwärts leicht berechnen, praktisch aber nicht umkehren lässt.
Multipliziert man zwei große Primzahlen, hat man das Produkt in Sekundenbruchteilen. Es wieder zu zerlegen kann je nach Größe der Zahlen Jahre dauern. Einwegfunktionen bilden die Grundlage von Hashing, Passwortspeicherung und digitalen Signaturen. Man speichert den Hash statt des Passworts, und wer die Datenbank stiehlt, bekommt eine Funktion, die er nicht rückwärts laufen lassen kann.
Dass Einwegfunktionen existieren, ist nicht bewiesen. Es ist eine Annahme, und ein Beweis würde zugleich zeigen, dass P ungleich NP ist. Die Kryptographie ruht also auf etwas, das wir glauben, aber noch nicht belegen können – eine unbequeme Lage für ein Fach, das Beweise liebt.