Unsicherheit von ElGamal

SupeRalF
Mausschubser
Mausschubser
Beiträge: 56
Registriert: 4. Okt 2010 16:48

Re: Unsicherheit von ElGamal

Beitrag von SupeRalF »

e_k hat geschrieben:Kann man davon ausgehen, dass das k bei beiden Verschlüsselungen dasselbe ist? Also wird nachdem m1 verschlüsselt wurde für m2 ein neues k zufällig gewählt oder wird das k von m1 übernommen?
Wenn ich dich richtig verstanden habe, bist du der mMinung, dass bei dem Spiel der semantischen Sicherheit beide Nachrichten verschlüsselt werden. Dem ist meiner Meinung nach nicht so.
Hierbei geht es um das Spiel zu Chiffriersystemen (ts-4.pdf Folie 16), NICHT um das zu den Signaturen! Du bekommst also nur 1 (ein) Chiffrat zurück und deine Frage nach der Gleichheit von k stellst sich gar nicht erst.
e_k hat geschrieben:Können beide Legendre-Symbole = 1 sein oder ist das ausgeschlossen?
Ich habe es mit einem einfachen OR bewiesen, also kein XOR (exklusiv oder). Angenommen mein Beweis ist richtig (ich bin mir relativ sicher), so muss die Aussage auch gelten, wenn beide Legendre Symbole 1 sind.

Korrigiert mich bitte, wenn ich was falsches schreibe!

Gruß
Florian

Benutzeravatar
Domac
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 160
Registriert: 4. Okt 2010 16:11

Re: Unsicherheit von ElGamal

Beitrag von Domac »

Also das k wird bei jeder Verschlüsselung afaik neu gewählt, da es zufällig ist.
Extend my dropbox space (here).
Thanks!

e_k
Neuling
Neuling
Beiträge: 6
Registriert: 20. Dez 2011 13:27

Re: Unsicherheit von ElGamal

Beitrag von e_k »

SupeRalF hat geschrieben: Wenn ich dich richtig verstanden habe, bist du der mMinung, dass bei dem Spiel der semantischen Sicherheit beide Nachrichten verschlüsselt werden. Dem ist meiner Meinung nach nicht so.
Hierbei geht es um das Spiel zu Chiffriersystemen (ts-4.pdf Folie 16), NICHT um das zu den Signaturen! Du bekommst also nur 1 (ein) Chiffrat zurück und deine Frage nach der Gleichheit von k stellst sich gar nicht erst.
Ja, das war dämlich von mir...natürlich wird nur eine Nachricht verschlüsselt und meine Frage stellt sich gar nicht....
SupeRalF hat geschrieben: Ich habe es mit einem einfachen OR bewiesen, also kein XOR (exklusiv oder). Angenommen mein Beweis ist richtig (ich bin mir relativ sicher), so muss die Aussage auch gelten, wenn beide Legendre Symbole 1 sind.
Ich gehe auch von einem einfachen OR aus... meine Beweisführung wäre aber unvollständig, wenn es sich tatsächlich um ein XOR handeln würde... Deshalb meine Frage :roll:

Steven
Kernelcompilierer
Kernelcompilierer
Beiträge: 425
Registriert: 2. Sep 2008 10:00
Wohnort: Frankfurt am Main

Re: Unsicherheit von ElGamal

Beitrag von Steven »

Ich versuche mal, die bisher aufgelaufenen Fragen der Reihe nach zu beantworten:

Das k wird bei jeder Verschlüsselung neu gewählt. Im Modell nehmen wir es als perfekt gleichverteilt an. Du kannst also keine Aussage über k machen, der Wert ist dem Angreifer komplett unbekannt.

Die Frage nach der Wiederholung stellt sich sowieso nicht, da in diesem Szenario nur eine einzige Verschlüsselung durchgeführt wird. Du gibst dem Richter zwei Nachrichten (m0 und m1), der Richter wählt zufällig i aus {0,1} und verschlüsselt dann mi (also entweder m0 oder m1) und sendet dir das zugehörige Chiffrat ci. Du sollst dann sagen, ob das Chiffrat zu m0 oder m1 gehört. Dabei hast du nur einen einzige Versuch.

Der Angriff ist erfolgreich, wenn deine Wahrscheinlichkeit richtig zu liegen, signifikant größer als 1/2 ist. Die Erfolgswahrscheinlichkeit von 1/2 erhält man trivial durch raten, also muss ein valider Angriff signifikant besser sein. Wenn dein Angriff beweisbar (!) mit Wahrscheilichkeit 0,75 klappt, ist das eine valide Lösung.

Es ist aber keine optimale Lösung, man kann einen Angreifer kostruieren, der mit Wahrscheinlichkeit 1 richtig liegt.

Die Regel zum Legendre-Symbol hat ein inklusives ODER, es können auch beide Werte auf der linken Seite 1 sein, dann ist die rechte Seite trotdem 1 (was man auch ganz leicht beweisen kann).

Benutzeravatar
McLovin
Erstie
Erstie
Beiträge: 13
Registriert: 26. Sep 2010 23:43
Wohnort: Mainz

Re: Unsicherheit von ElGamal

Beitrag von McLovin »

Macht das was aus, wenn beide Symbole gleich 1 sind? Ich denke nicht.
Es können auch beide Fälle eintreten aber für den Beweis genügt es zu zeigen, dass ein Legendre-Symbol gleich 1 ist. Überlege dir warum :)

philipp_m
Mausschubser
Mausschubser
Beiträge: 99
Registriert: 4. Dez 2010 18:10

Re: Unsicherheit von ElGamal

Beitrag von philipp_m »

Ist hier zufällig noch ein Tutor unterwegs, den ich mal per PN etwas zur Aufgabe fragen könnte? Bin mir nicht sicher, ob es als Vorwissen oder Teil der Lösung gilt, würde es deshalb eher ungern im Forum schreiben.

Edit: Habe gerade gesehen, dass es eigentlich eine neuere Version der Hausübung geben sollte, in der der Teil sowieso etwas abgeändert ist, also frage ich einfach mal offen:
Ist g als Generator von Zp* immer ein quadratischer Nichtrest modulo p?
Habe die a) nämlich zwar für alle Möglichkeiten von g bewiesen, in der b) baut mein Angriff jedoch darauf auf, dass das der Fall ist.

Antworten

Zurück zu „Archiv“