Goldwasser-Micali-Kryptosystem

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

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

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

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, dh., p\equiv q\equiv 3\mod 4, 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[Bearbeiten]

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 \mod n .

Entschlüsseln von Nachrichten (Decodierung)[Bearbeiten]

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 1 \mod p und c^{(q-1)/2}\equiv 1 \mod q, 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 1 \mod p und c^{(q-1)/2}\equiv 1 \mod q gilt.

Sicherheit[Bearbeiten]

Unter der Quadratische Rest 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[Bearbeiten]

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.

Referenzen[Bearbeiten]

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