Full-Domain-Hash

Das Full-Domain-Hash-Verfahren ist ein asymmetrisches Signaturverfahren dessen öffentlicher Schlüssel ${\displaystyle (f,G)}$ aus einer Trapdoor-Einwegpermutation ${\displaystyle f\colon \{0,1\}^{k}\rightarrow \{0,1\}^{k}}$ und einem Zufallsorakel ${\displaystyle G\colon \{0,1\}^{*}\rightarrow \{0,1\}^{k}}$ gebildet wird. Der zugehörige geheime Schlüssel ist die Umkehrfunktion ${\displaystyle f^{-1}}$ der Trapdoor-Einwegpermutation.

Die Signatur einer Nachricht ${\displaystyle x}$ wird durch folgende Funktion berechnet:

${\displaystyle \operatorname {sig} (x)=f^{-1}(G(x))}$

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

Der Empfänger erhält die Nachricht ${\displaystyle x}$ zusammen mit der Signatur ${\displaystyle y=\operatorname {sig} (x)}$. Mit der Verifikationsfunktion

${\displaystyle \operatorname {ver} (x,y)={\begin{cases}{\text{wahr}}&{\text{wenn }}f(y)=G(x)\\{\text{falsch}}&{\text{sonst}}\end{cases}}}$

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

Verwendet man als Trapdoor-Einwegpermutation ${\displaystyle f}$ die RSA-Funktion ${\displaystyle f(x)=x^{e}{\bmod {N}}}$ 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.

Wenn RSA ${\displaystyle (t',\epsilon ')}$-sicher ist, dann ist das RSA-Full-Domain-Hash-Verfahren auf Basis des Zufallsorakel-Modells ${\displaystyle (t,\epsilon )}$-sicher mit

${\displaystyle t=t'-(q_{\mathrm {hash} }+q_{\mathrm {sig} }+1)\cdot {\mathcal {O}}(k^{3})}$

${\displaystyle \epsilon =\left(1+{\frac {1}{q_{\mathrm {sig} }}}\right)^{q_{\mathrm {sig} }+1}\cdot q_{\mathrm {sig} }\cdot \epsilon '}$

Beachte, dass der Artikel von Jean-Sébastien Coron offenbar ${\displaystyle q_{\mathrm {sig} }>0}$ voraussetzt. Für große ${\displaystyle q_{\mathrm {sig} }}$ läuft dies auf ${\displaystyle \epsilon \sim \exp(1)\cdot q_{\mathrm {sig} }\cdot \epsilon '}$ hinaus.

Das bedeutet: Wenn es einen Algorithmus gibt, der eine existenzielle Fälschung für das Full-Domain-Hash-Verfahren mit einer Laufzeit von ${\displaystyle t}$ und Erfolgswahrscheinlichkeit von ${\displaystyle \epsilon }$ erstellen kann und dabei höchstens ${\displaystyle q_{\mathrm {hash} }}$ berechnet und höchstens ${\displaystyle q_{\mathrm {sig} }}$ Unterschriften benötigt, dann gibt es einen Algorithmus, der diskrete Logarithmen von RSA-Modulen mit einer Laufzeit von ${\displaystyle t'}$ und Erfolgswahrscheinlichkeit von ${\displaystyle \epsilon '}$ berechnet.

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.

• Douglas R. Stinson: Cryptography. Theory and Practice. 3. Auflage. Chapman & Hall/CRC, 2005, ISBN 1-58488-508-4, Seiten 304–307
• Jean-Sébastien Coron: On the Exact Security of Full Domain Hash. (PDF; 101 kB) CRYPTO 2000: Seiten 229–235
• Mihir Bellare, Phillip Rogaway: The Exact Security of Digital Signatures – How to Sign with RSA and Rabin. (PDF; 192 kB) EUROCRYPT 1996: Seiten 399–416