Quadratischer Rest / Nichtrest |
| 03.01.2015, 12:22 | Gasp0de | Auf diesen Beitrag antworten » | ||||||||
| Quadratischer Rest / Nichtrest Hallo! Ich habe ein Verständnisproblem zu quadratischen Resten bzw. zum Goldwasser-Micali Kryptosystem, welches quadratische Reste verwendet. Ein quadratischer Rest ist ja wie folgt definiert: a ist quadratischer Rest bezüglich eines Modulus N, falls es ein x gibt für das gilt: x^2 = a mod N Im Goldwasser-Micali-Kryptosystem werden nun quadratische Reste genutzt um Nachrichten zu verschlüsseln. Hierbei wird darauf zurückgegriffen, dass es sehr schwer ist, große Primzahlen zu faktorisieren. Die Primzahlfaktorisierung des Modulus N wird jedoch benötigt um zu bestimmen ob eine Zahl ein quadratischer Rest hiervon ist. Der Empfänger hat N als Produkt aus 2 Primzahlen erzeugt, kennt also die Faktorisierung von N. Das Verfahren ist nun folgendes: Gegeben sind der modulus N, dessen Faktorisierung dem Empfänger bekannt ist, und ein quadratischer Nichtrest des Modulus N y. Außerdem wähle ich ein zufälliges x. Um ein Bit m der Nachricht zu verschlüsseln setze ich das verschlüsselte bit e auf x^2 mod N, falls m=0 und e=y*x^2 mod N, falls m=1. Um die Nachricht zu entschlüsseln, überprüfe ich ob e quadratischer Rest bezüglich des Modulus N ist. Falls ja, ist m=1, falls nein, so ist m=0. Meine Ideen: Mein Problem ist nun folgendes: So wie ich das verstehe, sollte es andersherum sein. Falls mein verschlüsseltes bit e=x^2 ist, so gibt es ja eine Zahl, nämlich eben dieses x, dass die Gleichung x^2 = e mod N erfüllt. Somit ist e doch quadratischer Rest oder nicht. Da e aber x^2 ist, wenn m=0 ist, und in der Entschlüsselung m=1 gesetzt werden soll, falls e ein quadratischer Rest ist, muss ich hier etwas falsch verstehen. Hilfe! ------------------------------------------- Falls der Text zu kompliziert, schlecht geschrieben oder sonst irgendwas ist, möchte ich meine Frage hier noch einmal vereinfacht stellen. Gegeben sei eine Zahl N, die das Produkt aus 2 (bekannten) Primzahlen ist, sowie eine Zahl y, die quadratischer Nichtrest bezüglich des Modulus N ist. Ich wähle außerdem x zufällig. Warum ist ein quadratischer Nichtrest und ein quadratischer Rest? Meinem Verständnis nach müsste es andersherum sein, da es für e im ersten fall ja ein x (nämlich genau das zufällig gewählte) gibt, dass die Gleichung erfüllt. Das ist ja genau die Definition eines quadratischen Rests. Grüße, Gasp0de kgV: Hab deine beiden Beiträge zusammengefügt, damit der Zähler auf null steht |
||||||||||
| 03.01.2015, 15:51 | ollie3 | Auf diesen Beitrag antworten » | ||||||||
| RE: Quadratischer Rest / Nichtrest hallo, ich habe mir die sache bei wikepedia durchgelesen, und dieses kryptosystem ist wirklich genial: 
Also, der sender sendet dem empfänger, wenn er die 0 verschlüsseln will, die zahl e= x^2, wenn er die eins verschlüsseln will, die zahl e= y*x^2. Der empfänger überprüft nun, ob e quadratischer rest ist oder nicht. Ist e quadratischer rest, dann weiss er, das es sich um die verschlüsselte 0 handelt, ist e nichtquadratischer rest, dann ist es die verschlüsselte 1. Und das funktioniert wegen den rechenregeln für das legendre-restsymbol, wenn y nichtqudratischer rest und x^2 quadratischer rest ist, muss e=y*x^2 nichtquadratischer rest sein, und du hattest natürlich recht, das war anscheinend ein übertragungsfehler. gruss ollie3 |
||||||||||
| 03.01.2015, 20:03 | Gasp0de | Auf diesen Beitrag antworten » | ||||||||
Das habe ich auch gedacht, aber ich bezweifle, dass es ein Übertragungsfehler ist, denn es steht so auf Wikipedia in allen Sprachen und auch in dem Paper der Erfinder des Goldwasser-Micali-Kryptosystems. |
||||||||||
| 04.01.2015, 01:09 | Captain Kirk | Auf diesen Beitrag antworten » | ||||||||
Hallo,
Könntest du mir zeigen wo das in den Wikipedi-Artikeln stehen soll? Das engl. Wiki hat z.B.
das exakte Gegenteil deiner (zurecht kritiisierten) Behauptung:
Ebenso das deutsche:
|
||||||||||
| 04.01.2015, 12:14 | Gasp0de | Auf diesen Beitrag antworten » | ||||||||
Tatsache. Da hatte ich wohl ein Brett vorm Kopf, dass ich das nicht gesehen habe. Manchmal muss man eben einfach eine Nacht drüber schlafen. Vielen Dank, dass ihr mir geholfen habt den Fehler zu finden, auch wenn es nur ein Verleser war! Grüße, Gasp0de |
||||||||||
|
|
