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. 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 des öffentlichen und des privaten Schlüssels funktioniert wie folgt.

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

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

Anmerkung: Um das Paillier-Kryptosystem als Spezialfall zu erhalten, wählt man $s=1$ und $d=\lambda$. Weiters kann man stets $g=1+n$ wählen, ohne die Sicherheit zu beeinträchtigen. Insbesondere muss in diesem Fall $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 $m\in (\mathbb {Z} /n^{s}\mathbb {Z} )$ zu verschlüsseln, verfährt man wie folgt:

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

Entschlüsseln von Nachrichten (Decodierung)

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

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

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

• Nun wendet man rekursiv den Entschlüsselungsmechanismus des Paillier-Kryptosystems an, um $jmd$ zu berechnen. Da $j,d$ bekannt sind, kann man nun $m$ berechnen als $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 $n$ nicht effizient geprüft werden kann, ob ein $(\mathbb {Z} /n^{2}\mathbb {Z} )$ eine $n$-te Wurzel modulo $n^{2}$ besitzt oder nicht.

Homomorphieeigenschaften

Das Damgård-Jurik-Kryptosystem ist additiv-homomorph, wodurch durch Operationen auf Schlüsseltexte unbekannte Klartexte addiert werden können:

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

$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 $c$ mit $g^{\Delta m}$ kann ein beliebiger Wert $\Delta m$ zum verschlüsselten Klartext $m$ addiert werden:

$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 $c$ mit $\Delta r^{n^{s}}$ kann ein eine Verschlüsselung von $m$ erneut randomisiert werden, ohne die Nachricht $m$ zu ändern:

$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 $c$ mit einer natürlichen Zahl $w$ kann die verschlüsselte Nachricht $m$ ver-w-facht werden

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

Allerdings gibt es keine bekannte Möglichkeit, um durch Operationen auf zwei Schlüsseltexten die enthaltenen Nachrichten miteinander zu multiplizieren.

Vorteile

Die homomorphen Eigenschaften werden u. a. im Zusammenhang mit 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 der angeführten Homomorphieeigenschaften ist das Verfahren allerdings nicht IND-CCA-sicher, d. h. nicht sicher unter gewählten Schlüsseltext-Angriffen. Jedes Verschüsselungssystem, das diese Sicherheit besitzt müsste nämlich auch nicht-verformbar sein, eine Eigenschaft die zur Homomorphie im Widerspruch steht. In der Literatur findet man auch Transformationen, das Damgård-Jurik-Kryptosystem in eine IND-CCA-sichere Variante zu transformieren. Ob diese Transformationen angebracht sind oder nicht, ist von der jeweiligen Anwendung abhängig.