Hierbei geht es darum, ob es in einer Funktion f(x) = y möglich ist, aus einem gegebenen y das ursprüngliche x zu berechnen. In einer Einwegfunktion ist dieses nicht oder sagen wir nur mit unendlichem Aufwand möglich.
Stellen wir uns einmal vor wir sollten mit Hilfe eines Telefonbuchs zu einer Nummer den passenden Namen finden. Das wird uns recht schwer fallen, da das Telefonbuch auch eine Art Einwegfunktion darstellt. Zu einem Namen eine Telefonnummer zu ermitteln, stellt kein Problem dar. Allerdings in die andere Richtung wird schon eher eine Kunst draus.
Die Mathematik hat noch nicht beweisen können, daß solche Einwegfunktionen wirklich vorhanden sind, aber in der praktischen Anwendung hat man dann doch welche gefunden, die jedenfalls mit dem heutigen Wissensstand nicht invertiert werden können.
Zur Verschlüsselung können wir diesen Funktionstyp nicht verwenden, weil wir keine Möglichkeit hätten, die ursprüngliche Message wiederherzustellen. Hierzu brauchen wir Einwegfunktion mit einer Hintertür. Aber mit reinen Einwegfunktionen können klasse Hashfunktionen gebaut werden. Mehr dazu in den jeweiligen Abschnitten.
Auf diesem Funktionstyp basiert die gesamte asymmetrische Kryptographie.
Wie bei den Einwegfunktionen ist es auch hier “unmöglich”, aus einen gegebenen y das ursprüngliche x zu berechen. Allerdings, wenn ich im Besitz einer bestimmten Information bin, ist mir die Berechnung von x durch die Hintertür möglich.
Wie soll man sich das jetzt vorstellen?
Stellen wir uns vor, daß wir uns einen Bausatz für ein Modellschiff gekauft haben. Leider bemerken wir erst zu Hause, daß der Bauplan nicht dabei ist. Es wird uns nun wohl kaum gelingen etwas zusammenzubauen, daß halbwegs dem Bild auf der Verpackung entspricht. Wären wir allerdings im Besitz des Bauplans (unsere Hintertür), ist der Zusammenbau bei etwas Geschick im Bereich des Möglichen.
Ich möchte noch zwei Trapdoor-functions aus der Mathematik bringen, die in kryptografischen Algorithmen zur Anwendung kommen.
f(x) = xe mod n
Diese Funktion ist praktisch unmöglich zu invertieren. Sie besitzt allerdings drei Hintertüren:
Weitere Informationen beim RSA-Algorithmus.
Hashfunktionen dienen in der Kryptographie zur Generierung von unmanipulierbaren Fingerabdrücken von Nachrichten. Wozu kann das gut sein?
Bei jeder e-Mail, die wir bekommen, können wir nicht garantieren, daß der Text auf dem Weg zu uns nicht verändert wurde. Dieses Manko konnte mit Hilfe der Hashfunktionen beseitigt werden. Eine Hashfunktion bildet eine Nachricht beliebiger Länge auf einen Hashwert einer festen Länge ab, also unser Fingerabdruck.
Berechnen wir für eine Nachricht beim Verschicken den Hashwert und wiederholt der Empfänger beim Empfang diesen Vorgang, so müssen diese beiden Hashwerte übereinstimmen. Im anderen Fall wurde die Nachricht manipuliert.
Hashfunktionen müssen einige Eigenschaften besitzen, damit sie diese Integritätsfunktion erfüllen können:
Ich möchte noch einmal betonen, daß die Algorithmen für Hash-Funktionen gemäß dem Kerkhoffschen Prinzip offengelegt sind. Das Verfahren hängt also nicht von irgendeiner Geheimniskrämerei ab.