Goldwasser-Micali-Kryptosystem

Das Goldwasser-Micali-Kryptosystem wurde 1982 von Shafrira Goldwasser und Silvio Micali vorgestellt. Es handelt sich dabei um ein asymmetrisches Kryptosystem zur Verschlüsselung einzelner Bits. Das Verfahren ist additiv-homomorph, d. h., zwei verschlüsselte Nachrichten können addiert werden, ohne die Nachrichten vorher zu entschlüsseln.

Das Verfahren wurde später von Josh Benaloh zum Benaloh-Kryptosystem erweitert, mit dem auch längere Nachrichten verschlüsselt werden können.

Verfahren

Im Folgenden beschreiben wir die Schlüsselerzeugung, und die Algorithmen zur Ver- und Entschlüsselung von Nachrichten.^[1]

Erzeugung des öffentlichen und privaten Schlüssels

Das Schlüsselpaar wird folgendermaßen generiert:

• Zuerst generiert man zwei zufällige Primzahlen ${\displaystyle p,q}$, und definiert ${\displaystyle n=pq}$. In der Praxis sollte n zumindest 1024, besser jedoch 1536 oder 2048 Binärstellen haben.
• Man wählt ${\displaystyle y}$ zufällig in ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*}}$, sodass ${\displaystyle y}$ ein quadratischer Nichtrest modulo ${\displaystyle n}$ ist und Jacobi-Symbol ${\displaystyle \left({\frac {y}{n}}\right)=+1}$ hat. Ein solches ${\displaystyle y}$ kann man zum Beispiel effizient finden, indem man es zufällig wählt und prüft, ob das Legendre-Symbol ${\displaystyle \left({\frac {y}{p}}\right)=\left({\frac {y}{q}}\right)=-1}$ erfüllt, und andernfalls von vorne beginnt. Ist ${\displaystyle n}$ eine Blum-Zahl, d. h., ${\displaystyle p\equiv q\equiv 3\mod 4}$, so kann man ${\displaystyle y=n-1}$ wählen.

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

Verschlüsseln von Nachrichten

Um eine Nachricht ${\displaystyle m\in \{0,1\}}$ zu verschlüsseln, verfährt man wie folgt:

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

Entschlüsseln von Nachrichten (Decodierung)

Zum Entschlüsseln eines Schlüsseltextes ${\displaystyle c\in (\mathbb {Z} /n\mathbb {Z} )^{*}}$ prüft man, ob ${\displaystyle c}$ ein quadratischer Rest oder Nichtrest modulo ${\displaystyle n}$ ist:

• Gilt ${\displaystyle c^{(p-1)/2}\equiv 1\mod p}$ und ${\displaystyle c^{(q-1)/2}\equiv 1\mod q}$, so setzt man ${\displaystyle m=0}$, andernfalls ist ${\displaystyle m=1}$.

Die Korrektheit der Entschlüsselung kann man sehen, indem man beachtet, dass ein Element in ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*}}$ genau dann ein quadratischer Rest modulo ${\displaystyle n}$ ist, wenn es ein quadratischer Rest modulo ${\displaystyle p}$ und modulo ${\displaystyle q}$ ist. Dies ist wiederum nach dem Eulerschen Kriterium genau dann der Fall, wenn ${\displaystyle c^{(p-1)/2}\equiv 1\mod p}$ und ${\displaystyle c^{(q-1)/2}\equiv 1\mod q}$ gilt.

Sicherheit

Unter der Quadratischen-Reste-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 Element in ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )}$ eine Quadratwurzel modulo ${\displaystyle n}$ besitzt oder nicht, falls ${\displaystyle n}$ wie oben beschrieben gewählt wurden.

Homomorphieeigenschaften

Das Goldwasser-Micali-Kryptosystem ist additiv-homomorph. Das bedeutet, dass durch Multiplikation zweier Schlüsseltexte die darin enthaltenen Klartexte modulo 2 addiert werden. Allerdings gibt es keine bekannte Möglichkeit, um durch Operationen auf zwei Schlüsseltexten die enthaltenen Nachrichten miteinander zu multiplizieren.

Einzelnachweise

1. Shafrira Goldwasser und Silvio Micali: Probabilistic Encryption & How To Play Mental Poker Keeping Secret All Partial Information. (PDF) Abgerufen am 1. Februar 2019 (englisch).