imported>Leyo: falschen Freund Referenzen (≠ references) ersetzt

2022-10-26T22:00:08Z

falschen Freund Referenzen (≠ references) ersetzt

Neue Seite

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 [[Bit]]s. Das Verfahren ist [[Gruppenhomomorphismus|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üssel (Kryptologie)|Schlüsselerzeugung]], und die [[Algorithmus|Algorithmen]] zur Ver- und Entschlüsselung von Nachrichten.<ref>{{cite web | url=https://www.cs.purdue.edu/homes/ninghui/readings/Qual2/Goldwasser-Micali82.pdf | title= Probabilistic Encryption & How To Play Mental Poker Keeping Secret All Partial Information | accessdate=2019-02-01 | format= PDF | author=[[Shafrira Goldwasser]] und [[Silvio Micali]] | language= englisch}}</ref>
=== Erzeugung des öffentlichen und privaten Schlüssels ===
Das Schlüsselpaar wird folgendermaßen generiert:
* Zuerst generiert man zwei zufällige [[Primzahl]]en <math>p,q</math>, und definiert <math>n=pq</math>. In der Praxis sollte n zumindest 1024, besser jedoch 1536 oder 2048 [[Bit|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 Rest|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 [[Geheimtext|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 [[Legendre-Symbol|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 ''[[Quadratischer Rest#Anwendung in der Kryptologie|Quadratischen-Reste-Annahme]]'' kann gezeigt werden, dass das Verfahren [[Sicherheitsbegriff#Semantische Sicherheit|semantisch sicher]] gegen [[Ciphertext Indistinguishability#Definition von IND-CPA|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 [[#Erzeugung des öffentlichen und privaten Schlüssels|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 />

[[Kategorie:Asymmetrisches Verschlüsselungsverfahren]]

Goldwasser-Micali-Kryptosystem - Versionsgeschichte

imported>Leyo: falschen Freund Referenzen (≠ references) ersetzt