Konstruktion kryptographischer Hash-Funktionen mit Expander-Graphen

Informatik Diplomarbeiten (März 2007 - September 2007) crypt

Betreuer

Michael Naehrig, Peter Schwabe,

Abstract

Anfang 2005 wurde vorgestellt, wie Kollisionen für die bis dahin neben md5 meistverwendete kryptographische Hashfunktion SHA-1 effizienter als durch einen Brute-Force Versuch erzeugt werden können. Ein Vorschlag für eine neue kryptographische Hashfunktion, der 2006 vorgestellt wurde, basiert auf sog. Expander-Graphen. Die Idee ist es, einen großen Graphen (mit etwa 2^{192} Knoten) abhängig von der Eingabe zu durchschreiten und den letzten Knoten des sich ergebenden Pfades als Hashwert zu verwenden. Damit dieses Verfahren sicher ist, muss der Graph einige Eigenschaften erfüllen, besonders geeignet sind hier spezielle Expander-Graphen, sog. Ramanujan-Graphen. Die Konstruktion solcher Graphen kann mithilfe supersingulärer elliptischer Kurven über endlichen Körpern geschehen. Inhalt und Aufgabe der Diplomarbeit ist es, dieses Hash-Verfahren zu implementieren und den benötigten Zeitaufwand für die Berechnung eines Hashwertes mit einer bereits existierenden Implementation (von Microsoft Research) zu vergleichen. In der Arbeit soll die Implementation detailliert beschrieben, sowie der mathematische Hintergrund geeignet dargestellt werden.