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.

Erzeugung des öffentlichen und privaten Schlüssels

Das Schlüsselpaar wird folgendermaßen generiert:

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

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

Verschlüsseln von Nachrichten

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

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

Entschlüsseln von Nachrichten (Decodierung)

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

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

Die Korrektheit der Entschlüsselung kann man sehen, indem man beachtet, dass ein Element in $(\mathbb{Z}/n\mathbb{Z}{)}^{*}$ genau dann ein quadratischer Rest modulo $n$ ist, wenn es ein quadratischer Rest modulo $p$ und modulo $q$ ist. Dies ist wiederum nach dem Eulerschen Kriterium genau dann der Fall, wenn $c^{(p-1)/2}\equiv 1modp$ und $c^{(q-1)/2}\equiv 1modq$ 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 $n$ nicht effizient geprüft werden kann, ob ein Element in $(\mathbb{Z}/n\mathbb{Z})$ eine Quadratwurzel modulo $n$ besitzt oder nicht, falls $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.