Paillier-Kryptosystem

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Das Paillier-Kryptosystem wurde 1999 von Pascal Paillier an der Eurocrypt vorgestellt[1]. 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 Element in (\mathbb{Z}/n^2\mathbb{Z}) eine n-te Wurzel modulo n^2 besitzt oder nicht. Eine besondere Eigenschaft des Paillier-Kryptosystems ist, dass zwei verschlüsselte Nachrichten addiert werden können, ohne die Nachrichten vorher zu entschlüsseln.

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

Verfahren[Bearbeiten]

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

Erzeugung des öffentlichen und privaten Schlüssels[Bearbeiten]

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.

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

Vereinfachung: Die Schlüsselerzeugung kann auch folgendermaßen vereinfacht werden:

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

Verschlüsseln von Nachrichten[Bearbeiten]

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 gegeben durch  c=g^m r^n \mod n^2 .

Entschlüsseln von Nachrichten (Decodierung)[Bearbeiten]

Zum Entschlüsseln definiert man zuerst die Funktion L(x) = \frac{x-1}{n}. Für einen Schlüsseltext c\in (\mathbb{Z}/n^2\mathbb{Z})^* verfährt man dann wie folgt:

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

In diesem Schritt ist zu beachten, dass die Division modulo n durchgeführt werden muss, d. h., durch Multiplikation mit dem multiplikativ Inversen. Die Division in der Berechnung der logarithmischen Funktion L() wird über den ganzen Zahlen ausgeführt.

Vereinfachung: Hat man die vereinfachte Variante der Schlüsselgenerierung gewählt, ergibt sich die Entschlüsselung zu:

  • Man setzt m = \frac{L(c^{\lambda} \mod n^{2})}{\lambda}\mod n, wobei die Division wieder modulo n zu verstehen ist.

Sicherheit[Bearbeiten]

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 Element in (\mathbb{Z}/n^2\mathbb{Z}) eine n-te Wurzel modulo n^2 besitzt oder nicht.

Homomorphieeigenschaften[Bearbeiten]

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_1r_2)^n = g^{m_1+m_2} r'^n\mod n^2  = m_1 + m_2 \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^2
  • Durch Multiplikation eines Schlüsseltextes c mit \Delta r^n, d.h. der Addition des verschlüsselten Wertes "0", 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^2
  • 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 n^2.

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

Vorteile[Bearbeiten]

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[Bearbeiten]

Aufgrund der angeführten Homomorphieeigenschaften ist das Verfahren allerdings nicht IND-CCA sicher, d. h. nicht sicher unter gewählten Schlüsseltext-Angriffen. Jedes Verschlü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.

Vollständiges Beispiel[Bearbeiten]

Die oben angeführten Schritte sollen hier an einem kleinen Beispiel veranschaulicht werden.

Schlüsselerzeugung[Bearbeiten]

Zunächst wählen wir den Sicherheitsparameter k=10, und wählen p=1.019 und q=883. Dies erlaubt uns nun, die vereinfachte Variante der Schlüsselerzeugung zu wählen. Damit erhalten wir:

n = p \cdot q = 899777
g = n+1 = 899778
\lambda = (p-1) \cdot (q-1) = 897876

Der öffentliche Schlüssel ist damit gegeben durch: (n,g) = (899.777, 899.778).

Der geheime Schlüssel lautet (\lambda) = (897.876).

Vorarbeiten[Bearbeiten]

In einem ersten Schritt muss der zu verschlüsselnde Text in Zahlen kleiner als n übersetzt werden. Wir ersetzen dazu einfach jeden Buchstaben durch seine Position im Alphabet:

A=01 B=02 C=03 usw. (00 = Leerzeichen)

Wir verschlüsseln nun je drei Zeichen auf einmal, da vier aufeinanderfolgende Buchstaben unter Umständen einen zu großen Wert liefern könnten.

Klartext:  P  A  I  L  L  I  E  R
Kodierung: 16 01 09 12 12 09 05 18 00

Verschlüsselung[Bearbeiten]

Wir haben drei zu verschlüsselnde Klartexte (m_1=160109, m_2=121209 und m_3=051900), für die wir jeweils ein r_i\in(\mathbb{Z}/n\mathbb{Z})^* benötigen.

r1 =  12312
r2 = 623543
r3 = 215688

Die Verschlüsselungen c_i ergeben sich damit zu:

ci = gmirin mod n2
c1 = 899778160109 12312899777 mod 809598649729 = 594091908920
c2 = 508000332395
c3 = 8964598855

Entschlüsselung[Bearbeiten]

Da wir zur Schlüsselgenerierung die vereinfachte Variante gewählt hatte, können wir die Nachrichten entschlüsseln durch:

mi = L(ci\lambda mod n2) / \lambda mod n

Wichtig ist hier, dass die Division \mod n ausgeführt wird. Wir berechnen daher mittels des erweiterten Euklidischen Algorithmus das multiplikative Inverse von \lambda modulo n, und erhalten damit \lambda^{-1} = 141522\mod n. Damit ergibt sich die Entschlüsselung zu:

m1 = L(594091908920897876 mod 809598649729) * 141522 mod 899777 = 160109
m2 = 121209
m3 = 051900

Durch Invertierung der Substitutionsvorschrift kann man diese Werte nun wieder in Buchstaben übersetzen.

Weblinks[Bearbeiten]

  • thep implementiert das Paillier-Kryptosystem in Java.

Referenzen[Bearbeiten]

  1. Pascal Paillier: Public-Key Cryptosystems Based on Composite Degree Residuosity Classes (englisch). In: Eurocrypt 99, Springer Verlag, 1999, S. 223-238. 
  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.