Paillier-Kryptosystem

Das Paillier-Kryptosystem wurde 1999 von Pascal Paillier an der Eurocrypt vorgestellt. Es handelt sich dabei um ein asymmetrisches Kryptosystem, dessen Sicherheit darauf beruht, 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.

Das Verfahren wird oft als Nachfolger des Okamoto–Uchiyama-Kryptosystems bezeichnet. Desweiteren ist es ein Spezialfall des Damgård-Jurik-Kryptosystems.

Verfahren

Im folgenden beschreiben wir die Schlüsselerzeugung, und die Algorithmen zur Ver- und Entschlüsselung von Nachrichten.

Erzeugung des öffentlichen und privaten Schlüssels

Das Schlüsselpaar wird folgendermaßen generiert:

• Man generiert zwei zufällige Primzahlen $p,q$, sodass $\operatorname {ggT} (pq,(p-1)(q-1))=1$ gilt. In der Praxis sollte n zumindest 1024, besser jedoch 1536 oder 2048 Binärstellen haben. Man setzt dann $n=pq$ sowie $\lambda =\operatorname {kgV} (p-1,q-1)$.
• Man wählt $g$ zufällig in $(\mathbb {Z} /n^{2}\mathbb {Z} )^{*}$, sodass $n$ die Ordnung von $g$ teilt, indem man prüft, ob $\mu =(L(g^{\lambda }\mod n^{2}))^{-1}\mod n$ existiert.

Dabei beschreibt $L$ die logarithmische Funktion, dh., es ist $L(x)={\frac {x-1}{n}}$, wobei die Division nicht modulo $n$, sondern in den ganzen Zahlen durchzuführen ist (bei nicht-ganzzahligen ist abzurunden.

Der öffentliche Schlüssel besteht aus $(n,g)$, der private Schlüssel aus </math>(\lambda,\mu)</math>.

Vereinfachung: Die Schlüsselerzeugung kann auch folgendermassen vereinfacht werden:

• Man wählt einen Sicherheitsparameter $k$, und die beiden Primzahlen $p,q$ zufällig in ${\left\{1||\{0,1\}^{s-1}\right\}}$, also mit gleicher Bitlänge.
• Man definiert $g=n+1$, sowie $\lambda =(p-1)(q-1)$ und $\mu =\lambda ^{-1}\mod n$.

Verschlüsseln von Nachrichten

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

• Zuerst wählt man ein zufälliges $r\in (\mathbb {Z} /n\mathbb {Z} )^{*}$.
• Die verschlüsselte Nachricht ist dann gegen durch $c=g^{m}r^{n}\mod n^{2}$.

Entschlüsseln von Nachrichten (Decodierung)

Zum Entschlüsseln eines Schlüsseltexts $c\in (\mathbb {Z} /n^{2}\mathbb {Z} )^{*}$ verfährt man wie folgt:

• Man setzt $m=L(c^{\lambda }\mod n^{2})\mu \mod n$, wobei $L()$ die logarithmische Funktion von oben ist.

Sicherheit

Unter der Decisional Compisite 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.

Aufgrund der nachstehenden Homomorphieeigenschaften ist das Verfahren allerdings nicht sicher unter gewählten Schlüsseltext-Angriffen. Es gibt in der Literatur jedoch mehrere Lösungen für dieses Problem.

Probleme der Homomorphieeigenschaften

Das Paillier-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}\cdot g^{m_{2}}r_{2}^{n}=g^{m_{1}+m_{2}}(r_{1}r_{2})^{n}=g^{m_{1}+m_{2}}r'^{n}\mod n$.

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}\cdot g^{\Delta m}=g^{m+\Delta m}r^{n}\mod n$

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

$g^{m}r^{n}\cdot \Delta r^{n}=g^{m}(r\Delta r)^{n}=g^{m}r'^{n}\mod n$

• 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})^{w}=g^{wm}(r^{w})^{n}=g^{wm}r'^{n}\mod m$.

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

Links und Quellen

Externe Links

• thep implementiert das Paillier-Kryptosystem in Java.