Damgård–Jurik-Kryptosystem

Das Damgård–Jurik Verschlüsselungssystem 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 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 = λ. 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üsselungs-Mechanismus 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² besitzt oder nicht.

Homomorphieeigenschaften

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

• Durch Multiplikation von zwei Schlüsseltexten c₁,c₂ werden die verschlüsselten Klartexte m₁,m₂ addiert:

$g^{m_1} r_1^{n^s} \cdot g^{m_2} r_2^{n^s} = g^{m_1+m_2} (r_1r_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^Δm kann ein beliebiger Wert Δ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, dh. 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 Paillier-Kryptosystem in eine IND-CCA sichere Variante zu transformieren^[2][3]. Ob diese Transformationen angebracht sind oder nicht, ist von der jeweiligen Anwendung abhängig.

Quellen

1. ↑ Ivan Damgård und Mads Jurik: A Generalisation, a Simplification and Some Applications of Paillier's Probabilistic Public-Key System (englisch). In: PKC 01, Springer Verlag, 2001, S. 119-136. 
2. ↑ Eiichiro Fujisaki und Tatsuako Okamoto: How to Enhance the Security of Public-Key Encryption at Minimum Cost (englisch). In: PKC 99, Springer Verlag, 1999, S. 53-68. 
3. ↑ Pascal Paillier und David Pointcheval: Efficient Public-Key Cryptosystems Provably Secure Against Active Adversaries (englisch). In: ASIACRYPT 99, Springer Verlag, 1999, S. 165-179.