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 | Quelltext 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 | Quelltext 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, dh., , so kann man wählen.

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

Verschlüsseln von Nachrichten[Bearbeiten | Quelltext 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 | Quelltext 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 | Quelltext 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 | Quelltext 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 | Quelltext 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.