imported>Gerolsteiner flasche: /* growthexperiments-addlink-summary-summary:3|0|0 */

2024-09-20T14:22:25Z

growthexperiments-addlink-summary-summary:3|0|0

Neue Seite

'''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 [[Kryptologische Hashfunktion|hashen]] und anschließend eine beliebige [[Falltürfunktion|Trapdoor]]-Einweg[[permutation]] darauf anzuwenden. Die Hashfunktion wird dabei als [[Zufallsorakel]] modelliert, dessen [[Bild (Mathematik)|Bildmenge]] gleich dem [[Definitionsbereich]] der Einwegpermutation ist. Daher kommt auch der Name Full-Domain-Hash.

== Beschreibung des Protokolls ==
Das Full-Domain-Hash-Verfahren ist ein [[asymmetrisches Signaturverfahren]] dessen [[öffentlicher Schlüssel]] <math>(f,G)</math> aus einer Trapdoor-Einwegpermutation <math>f\colon \{0,1\}^k \rightarrow \{0,1\}^k</math> und einem Zufallsorakel <math>G\colon \{0,1\}^* \rightarrow \{0,1\}^k</math> gebildet wird. Der zugehörige [[geheimer Schlüssel|geheime Schlüssel]] ist die [[Umkehrfunktion]] <math>f^{-1}</math> der Trapdoor-Einwegpermutation.

Die [[digitale Signatur|Signatur]] einer Nachricht <math>x</math> wird durch folgende Funktion berechnet:
: <math>\operatorname{sig}(x) = f^{-1}(G(x))</math>

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

Der Empfänger erhält die Nachricht <math>x</math> zusammen mit der Signatur <math>y = \operatorname{sig}(x)</math>. Mit der [[Verifikation]]sfunktion
: <math>\operatorname{ver}(x,y) = \begin{cases}
\text{wahr} & \text{wenn }f(y) = G(x)\\
\text{falsch} & \text{sonst}
\end{cases}</math>
überprüft er die Nachricht. Diese gibt genau dann wahr aus, wenn die Nachricht nicht verändert wurde.

== RSA-Full-Domain-Hash ==
Verwendet man als Trapdoor-Einwegpermutation <math>f</math> die RSA-Funktion <math>f(x) = x^e \bmod N</math> mit den von [[RSA-Kryptosystem|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 ==
Wenn RSA <math>(t',\epsilon')</math>-sicher ist, dann ist das RSA-Full-Domain-Hash-Verfahren auf Basis des Zufallsorakel-Modells <math>(t,\epsilon)</math>-sicher mit
: <math>t=t'-(q_\mathrm{hash} + q_\mathrm{sig}+1) \cdot \mathcal{O}(k^3)</math>

: <math>\epsilon = \left(1+\frac{1}{q_\mathrm{sig}}\right)^{q_\mathrm{sig}+1} \cdot q_\mathrm{sig} \cdot \epsilon'</math>

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

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

== Relevanz ==
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.

== Quellen ==
* 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: [https://www.iacr.org/archive/crypto2000/18800229/18800229.pdf ''On the Exact Security of Full Domain Hash.''] (PDF; 101 kB) CRYPTO 2000: Seiten 229–235
* [[Mihir Bellare]], [[Phillip Rogaway]]: [https://www.cs.ucdavis.edu/~rogaway/papers/exact.pdf ''The Exact Security of Digital Signatures – How to Sign with RSA and Rabin.''] (PDF; 192 kB) EUROCRYPT 1996: Seiten 399–416

[[Kategorie:Signaturverfahren]]

Full-Domain-Hash - Versionsgeschichte

imported>Gerolsteiner flasche: /* growthexperiments-addlink-summary-summary:3|0|0 */