Full-Domain-Hash

Signaturverfahren aus dem Bereich der Kryptologie

Full-Domain-Hash (Abkürzung FDH) ist ein Signaturverfahren aus dem Bereich der Kryptologie. Der Empfänger einer Nachricht kann damit überprüfen, ob die Nachricht, die der Absender an ihn gesandt hat, durch einen Dritten verändert wurde oder nicht.

Das Prinzip des Verfahrens besteht darin, eine Nachricht zuerst zu hashen und anschließend eine beliebige Trapdoor-Einwegpermutation darauf anzuwenden. Die Hashfunktion wird dabei als Zufallsorakel modelliert, dessen Bildmenge gleich dem Definitionsbereich der Einwegpermutation ist. Daher kommt auch der Name Full-Domain-Hash.

Beschreibung des Protokolls

Bearbeiten

Das Full-Domain-Hash-Verfahren ist ein asymmetrisches Signaturverfahren dessen öffentlicher Schlüssel   aus einer Trapdoor-Einwegpermutation   und einem Zufallsorakel   gebildet wird. Der zugehörige geheime Schlüssel ist die Umkehrfunktion   der Trapdoor-Einwegpermutation.

Die Signatur einer Nachricht   wird durch folgende Funktion berechnet:

 

Die Nachricht wird dann zusammen mit der Signatur an den Empfänger gesandt.

Der Empfänger erhält die Nachricht   zusammen mit der Signatur  . Mit der Verifikationsfunktion

 

überprüft er die Nachricht. Diese gibt genau dann wahr aus, wenn die Nachricht nicht verändert wurde.

RSA-Full-Domain-Hash

Bearbeiten

Verwendet man als Trapdoor-Einwegpermutation   die RSA-Funktion   mit den von RSA bekannten Parametern, dann spricht man vom RSA-Full-Domain-Hash. Das Verfahren ist nachweislich sicher, das heißt, es kann auch mit einem Angriff mit frei wählbarem Klartext keine existenzielle Fälschung erzeugt werden.

Sicherheit des RSA-Full-Domain-Hash

Bearbeiten

Wenn RSA  -sicher ist, dann ist das RSA-Full-Domain-Hash-Verfahren auf Basis des Zufallsorakel-Modells  -sicher mit

 
 

Beachte, dass der Artikel von Jean-Sébastien Coron offenbar   voraussetzt. Für große   läuft dies auf   hinaus.

Das bedeutet: Wenn es einen Algorithmus gibt, der eine existenzielle Fälschung für das Full-Domain-Hash-Verfahren mit einer Laufzeit von   und Erfolgswahrscheinlichkeit von   erstellen kann und dabei höchstens   berechnet und höchstens   Unterschriften benötigt, dann gibt es einen Algorithmus, der diskrete Logarithmen von RSA-Modulen mit einer Laufzeit von   und Erfolgswahrscheinlichkeit von   berechnet.

Relevanz

Bearbeiten

Die Autoren (Bellare, Rogaway) von Full-Domain-Hash haben ein weiteres Verfahren vorgeschlagen, das Probabilistic Signature Scheme (PSS), welches ihrer Ansicht nach bessere kryptografische Eigenschaften hat. Daher wird FDH praktisch nicht eingesetzt, da PSS im Rahmen von PKCS #1 v2.1 standardisiert wurde.