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

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  , und definiert  . In der Praxis sollte n zumindest 1024, besser jedoch 1536 oder 2048 Binärstellen haben.
  • Man wählt   zufällig in  , sodass   ein quadratischer Nichtrest modulo   ist und Jacobi-Symbol   hat. Ein solches   kann man zum Beispiel effizient finden, indem man es zufällig wählt und prüft, ob das Legendre-Symbol   erfüllt, und andernfalls von vorne beginnt. Ist   eine Blum-Zahl, d. h.,  , so kann man   wählen.

Der öffentliche Schlüssel besteht aus  , der private Schlüssel aus  .

Verschlüsseln von Nachrichten

Bearbeiten

Um eine Nachricht   zu verschlüsseln, verfährt man wie folgt:

  • Zuerst wählt man ein zufälliges  .
  • Die verschlüsselte Nachricht ist dann gegeben durch  .

Entschlüsseln von Nachrichten (Decodierung)

Bearbeiten

Zum Entschlüsseln eines Schlüsseltextes   prüft man, ob   ein quadratischer Rest oder Nichtrest modulo   ist:

  • Gilt   und  , so setzt man  , andernfalls ist  .

Die Korrektheit der Entschlüsselung kann man sehen, indem man beachtet, dass ein Element in   genau dann ein quadratischer Rest modulo   ist, wenn es ein quadratischer Rest modulo   und modulo   ist. Dies ist wiederum nach dem Eulerschen Kriterium genau dann der Fall, wenn   und   gilt.

Sicherheit

Bearbeiten

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   nicht effizient geprüft werden kann, ob ein Element in   eine Quadratwurzel modulo   besitzt oder nicht, falls   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.

Einzelnachweise

Bearbeiten
  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).