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.<ref>Vorlage:Cite book/NameVorlage:Cite book/Name: [ Probabilistic Encryption & How To Play Mental Poker Keeping Secret All Partial Information.] (PDF) , archiviert vom Vorlage:IconExternal (nicht mehr online verfügbar) am Vorlage:Cite book/URL; abgerufen am 1. Februar 2019 (englisch). Vorlage:Cite book/URLVorlage:Cite book/MeldungVorlage:Cite book/Meldung2Vorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/Meldung</ref>

Erzeugung des öffentlichen und privaten Schlüssels

Das Schlüsselpaar wird folgendermaßen generiert:

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

Der öffentliche Schlüssel besteht aus <math>(n,y)</math>, der private Schlüssel aus <math>(p,q)</math>.

Verschlüsseln von Nachrichten

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

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

Entschlüsseln von Nachrichten (Decodierung)

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

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

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

<references />