Damgård-Jurik-Kryptosystem

Das Damgård-Jurik-Kryptosystem ist ein semantisch sicherer, asymmetrischer Verschlüsselungsalgorithmus. Es wurde 2001 an der Konferenz PKC von den beiden Kryptographen Ivan Damgård und Mads Jurik vorgestellt.[1] Das Verfahren ist additiv-homomorph, was bedeutet, dass durch die Multiplikation zweier Schlüsseltexte die Klartexte addiert werden. Es ist also nicht nötig, die Schlüsseltexte zu entschlüsseln, um auf den Klartexten operieren zu können. Das Verfahren ist ein Nachfolger des Paillier-Kryptosystems und enthält dieses als Spezialfall.

Verfahren

Erzeugung des öffentlichen und privaten Schlüssels

Die Erzeugung d​es öffentlichen u​nd des privaten Schlüssels funktioniert w​ie folgt.

• Man wählt zwei große Primzahlen ${\displaystyle p,q}$ gleicher Bitlänge und definiert ${\displaystyle n=pq}$. In der Praxis sollte ${\displaystyle n}$ zwischen 1536 und 2048 Bits lang sein.
• Man definiert ${\displaystyle \lambda =\operatorname {kgV} (p-1,q-1)}$.
• Man wählt ${\displaystyle g\in (\mathbb {Z} /n^{s+1}\mathbb {Z} )^{*}}$ so, dass ${\displaystyle g=(1+n)^{j}x\mod n^{s+1}}$ für ein bekanntes ${\displaystyle j}$ relativ prim zu ${\displaystyle n}$ und ${\displaystyle x\in H}$, wobei ${\displaystyle H}$ isomorph zu ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*}}$ ist.
• Mittels des Chinesischen Restsatzes berechnet man ${\displaystyle d}$ mit ${\displaystyle d\mod n\in (\mathbb {Z} /n\mathbb {Z} )^{*}}$ und ${\displaystyle d=0\mod \lambda }$.

Der öffentliche Schlüssel besteht aus ${\displaystyle (n,g)}$, der private aus ${\displaystyle d}$.

Anmerkung: Um das Paillier-Kryptosystem als Spezialfall zu erhalten, wählt man ${\displaystyle s=1}$ und ${\displaystyle d=\lambda }$. Weiter kann man stets ${\displaystyle g=1+n}$ wählen, ohne die Sicherheit zu beeinträchtigen. Insbesondere muss in diesem Fall ${\displaystyle s}$ nicht ins Vorhinein fixiert werden, sondern kann ad hoc beim Verschlüsseln einer Nachricht gewählt werden.

Verschlüsseln von Nachrichten

Um eine Nachricht ${\displaystyle m\in (\mathbb {Z} /n^{s}\mathbb {Z} )}$ zu verschlüsseln, verfährt man wie folgt:

• Man wählt ${\displaystyle r}$ zufällig in ${\displaystyle (\mathbb {Z} /n^{s+1}\mathbb {Z} )^{*}}$.
• Man berechnet den Schlüsseltext als ${\displaystyle c=g^{m}\cdot r^{n^{s}}\mod n^{s+1}}$.

Entschlüsseln von Nachrichten (Decodierung)

Um einen Schlüsseltext ${\displaystyle c}$ zu entschlüsseln, verfährt man folgermaßen:

• Man berechnet ${\displaystyle c^{d}\mod n^{s+1}}$. Für gültige Schlüsseltexte ${\displaystyle c}$ muss gelten:

${\displaystyle c^{d}=(g^{m}r^{n^{s}})^{d}=((1+n)^{jm}x^{m}r^{n^{s}})^{d}=(1+n)^{jmd\mod n^{s}}(x^{m}r^{n^{s}})^{d\mod \lambda }=(1+n)^{jmd\mod n^{s}}\mod n^{s+1}}$.

Dabei verwendet man einerseits, dass ${\displaystyle (1+n)}$ in ${\displaystyle (\mathbb {Z} /n^{s+1}\mathbb {Z} )^{*}}$ die Ordnung ${\displaystyle n^{s}}$ hat. Andererseits ist anzumerken, dass ${\displaystyle (\mathbb {Z} /n^{s+1}\mathbb {Z} )^{*}\equiv G\times H}$, wobei ${\displaystyle G}$ Ordnung ${\displaystyle n^{s}}$ hat, und ${\displaystyle H}$ Ordnung ${\displaystyle \lambda =\operatorname {kgV} (p-1,q-1)}$, da ${\displaystyle H}$ isomorph zu ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*}}$ ist, und ${\displaystyle d=0\mod \lambda }$ ist. Weiters sind sowohl ${\displaystyle x}$ (per definitionem) und ${\displaystyle r^{n^{s}}}$ Elemente von ${\displaystyle H}$.

• Nun wendet man rekursiv den Entschlüsselungsmechanismus des Paillier-Kryptosystems an, um ${\displaystyle jmd}$ zu berechnen. Da ${\displaystyle j,d}$ bekannt sind, kann man nun ${\displaystyle m}$ berechnen als ${\displaystyle m=(jmd)\cdot (jd)^{-1}\mod n^{s}}$.

Sicherheit

Unter der Decisional-Composite-Residuosity-Annahme kann gezeigt werden, dass das Verfahren semantisch sicher gegen Gewählte-Klartext-Angriffe ist. Diese Annahme besagt, dass für einen zusammengesetzten Modul ${\displaystyle n}$ nicht effizient geprüft werden kann, ob ein ${\displaystyle (\mathbb {Z} /n^{2}\mathbb {Z} )}$ eine ${\displaystyle n}$-te Wurzel modulo ${\displaystyle n^{2}}$ besitzt oder nicht.

Homomorphieeigenschaften

Das Damgård-Jurik-Kryptosystem i​st additiv-homomorph, wodurch d​urch Operationen a​uf Schlüsseltexte unbekannte Klartexte addiert werden können:

• Durch Multiplikation von zwei Schlüsseltexten ${\displaystyle c_{1},c_{2}}$ werden die verschlüsselten Klartexte ${\displaystyle m_{1},m_{2}}$ addiert:

${\displaystyle g^{m_{1}}r_{1}^{n^{s}}\cdot g^{m_{2}}r_{2}^{n^{s}}=g^{m_{1}+m_{2}}(r_{1}r_{2})^{n^{s}}=g^{m_{1}+m_{2}}r'^{n^{s}}\mod n^{s+1}}$.

Dabei sind manchmal zwei Sonderfälle von besonderem Interesse:

• Durch Multiplikation eines Schlüsseltextes ${\displaystyle c}$ mit ${\displaystyle g^{\Delta m}}$ kann ein beliebiger Wert ${\displaystyle \Delta m}$ zum verschlüsselten Klartext ${\displaystyle m}$ addiert werden:

${\displaystyle g^{m}r^{n^{s}}\cdot g^{\Delta m}=g^{m+\Delta m}r^{n^{s}}\mod n^{s+1}}$.

• Durch Multiplikation eines Schlüsseltextes ${\displaystyle c}$ mit ${\displaystyle \Delta r^{n^{s}}}$ kann eine Verschlüsselung von ${\displaystyle m}$ erneut randomisiert werden, ohne die Nachricht ${\displaystyle m}$ zu ändern:

${\displaystyle g^{m}r^{n^{s}}\cdot \Delta r^{n^{s}}=g^{m}(r\Delta r)^{n^{s}}=g^{m}r'^{n^{s}}\mod n^{s+1}}$.

• Durch Exponentiation eines Schlüsseltexts ${\displaystyle c}$ mit einer natürlichen Zahl ${\displaystyle w}$ kann die verschlüsselte Nachricht ${\displaystyle m}$ ver-w-facht werden

${\displaystyle (g^{m}r^{n^{s}})^{w}=g^{wm}(r^{w})^{n^{s}}=g^{wm}r'^{n^{s}}\mod n^{s+1}}$.

Allerdings g​ibt es k​eine bekannte Möglichkeit, u​m durch Operationen a​uf zwei Schlüsseltexten d​ie enthaltenen Nachrichten miteinander z​u multiplizieren.

Vorteile

Die homomorphen Eigenschaften werden u. a. i​m Zusammenhang m​it den folgenden Anwendungen ausgenützt.

• E-Voting: Nachdem jeder Wahlberechtigte seine Stimme (im einfachsten Fall eine 1 für ja, eine 0 für nein) verschlüsselt und an die Wahlbehörde übermittelt hat, werden alle Schlüsseltexte multipliziert, und die resultierende Verschlüsselung enthält die Verschlüsselung der Gesamtanzahl an Ja-Stimmen. Durch Entschlüsseln erhält man nun das Wahlergebnis. Wichtig ist, dass die den ersten Schritt ausführende Partei keine Kenntnis des geheimen Schlüssels benötigt, wodurch keine einzelnen Stimmen entschlüsselt werden können.
• eCash
• Zero-Knowledge-Beweise im Universal-Composability-Modell

Nachteile

Aufgrund d​er angeführten Homomorphieeigenschaften i​st das Verfahren allerdings n​icht IND-CCA-sicher, d. h. n​icht sicher u​nter Gewählter-Schlüsseltext-Angriffen. Jedes Verschlüsselungssystem, d​as diese Sicherheit besitzt, müsste nämlich a​uch nicht-verformbar sein, e​ine Eigenschaft, d​ie zur Homomorphie i​m Widerspruch steht. In d​er Literatur findet m​an auch Transformationen, d​as Damgård-Jurik-Kryptosystem i​n eine IND-CCA-sichere Variante z​u transformieren.[2][3] Ob d​iese Transformationen angebracht s​ind oder nicht, i​st von d​er jeweiligen Anwendung abhängig.

Quellen

1. Ivan Damgård, Mads Jurik: A Generalisation, a Simplification and Some Applications of Paillier’s Probabilistic Public-Key System. In: Kwangjo Kim (Hrsg.): Public Key Cryptography. Band 1992. Springer, Berlin/Heidelberg 2001, ISBN 3-540-41658-7, S. 119–136, doi:10.1007/3-540-44586-2_9.
2. Eiichiro Fujisaki, Tatsuaki Okamoto: How to Enhance the Security of Public-Key Encryption at Minimum Cost. In: Public Key Cryptography. Band 1560. Springer, Berlin/Heidelberg 1999, ISBN 3-540-65644-8, S. 53–68, doi:10.1007/3-540-49162-7_5.
3. Pascal Paillier, David Pointcheval: Efficient Public-Key Cryptosystems Provably Secure Against Active Adversaries. In: Kwok-Yan Lam, Eiji Okamoto, Chaoping Xing (Hrsg.): Advances in Cryptology - ASIACRYPT’99. Band 1716. Springer, Berlin/Heidelberg 1999, ISBN 3-540-66666-4, S. 165–179, doi:10.1007/978-3-540-48000-6_14.