Unsicherheit von ElGamal

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

Unsicherheit von ElGamal

Beitrag von SupeRalF »

Hi,
ich habe für die Hausübung Aufgabe 3 einen Angreifer entwickelt, der nur in manchen Fällen mit Sicherheit entscheiden kann, welche der Nachrichten der Richter verschlüsselt hat. Mein Angreifer hat also zwar eine Trefferrate "deutlich über 1/2", aber eben nicht 100%.
Reicht mein Angreifer trotzdem zur vollen Punktzahl aus, oder ist ein Angreifer mit 100%-Rate erforderlich? (ich konnte bisher noch keinen solchen Angriff finden)

Gruß
Florian

Benutzeravatar
Blub
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 244
Registriert: 24. Dez 2007 14:06

Re: Unsicherheit von ElGamal

Beitrag von Blub »

Die Chance muss größer als 1/2 sein, das du entscheiden kannst welche Nachricht verschlüsselt wurde, hast du das geschafft, dann bist du fertig ;)

ob deiner korrekt ist kann ich dir natürlich nicht sagen, da ich deinen nicht kenne. Aber wenn du der Chiffrierbox 2 Nachrichten schickst, diese dir die Chiffrate zurückschickt, und du mit einer Chance größer als 1/2 sagen kannst welche Nachricht chiffriert wurde, dann erfüllst du damit ja schon die Bedingung.
Tutor GDI II SS12
Tutor Trusted Systems WS11/12, Tutor GDI II SS11
Tutor Trusted Systems WS10/11, GDI I WS10/11
Tutor GDI II SS10, Tutor Trusted Systems WS09/10

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

Re: Unsicherheit von ElGamal

Beitrag von SupeRalF »

naja, in manchen Fällen rate ich (Chance = 1/2) und in manchen Fällen kann ich es definitiv bestimmen (Chance = 1).
Muss ich mir also für die Fälle, in denen ich aktuell nur rate, noch was einfallen lassen?

Benutzeravatar
Blub
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 244
Registriert: 24. Dez 2007 14:06

Re: Unsicherheit von ElGamal

Beitrag von Blub »

wäre gut, ja.
Tutor GDI II SS12
Tutor Trusted Systems WS11/12, Tutor GDI II SS11
Tutor Trusted Systems WS10/11, GDI I WS10/11
Tutor GDI II SS10, Tutor Trusted Systems WS09/10

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

Re: Unsicherheit von ElGamal

Beitrag von SupeRalF »

Blub hat geschrieben:wäre gut, ja.
Hm, also ich komme nicht drauf wie ich den Anfriff noch verbessern soll. Mein Angreifer hat in 50% der Fälle eine Trefferrate von 1 und in 50% der Fälle eine Trefferrate von 0,5. Das ergibt eine gesamt-Trefferrate von 0,75.
Bist du dir sicher, dass ich den Angriff noch effizienter machen muss?

Benutzeravatar
Blub
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 244
Registriert: 24. Dez 2007 14:06

Re: Unsicherheit von ElGamal

Beitrag von Blub »

SupeRalF hat geschrieben:
Blub hat geschrieben:wäre gut, ja.
Hm, also ich komme nicht drauf wie ich den Anfriff noch verbessern soll. Mein Angreifer hat in 50% der Fälle eine Trefferrate von 1 und in 50% der Fälle eine Trefferrate von 0,5. Das ergibt eine gesamt-Trefferrate von 0,75.
Bist du dir sicher, dass ich den Angriff noch effizienter machen muss?
Ohne deinen Angriff zu kennen kann ich dir leider nicht sagen ob es so ok ist oder nicht. Von daher kann ich dir dazu leider keine Antwort geben.
Tutor GDI II SS12
Tutor Trusted Systems WS11/12, Tutor GDI II SS11
Tutor Trusted Systems WS10/11, GDI I WS10/11
Tutor GDI II SS10, Tutor Trusted Systems WS09/10

ElGamal
Nichts ist wie es scheint
Beiträge: 23
Registriert: 19. Dez 2011 20:56

Re: Unsicherheit von ElGamal

Beitrag von ElGamal »

Darf man annehmen, dass der Angreifer bei 3b) die Primzahl p kennt oder sie(effizient) berechnen kann? Sonst kann man ja schlecht das Legendre-Symbol benutzen, oder :?:

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

Re: Unsicherheit von ElGamal

Beitrag von Domac »

Ich wäre jetzt davon ausgegangen, dass der Angreifer p kennt. In der Aufgabenstellung steht jedoch nichts davon... ich komm da im moment auch nicht wirklich weiter...
Extend my dropbox space (here).
Thanks!

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

Re: Unsicherheit von ElGamal

Beitrag von SupeRalF »

Also ich bin auch davon ausgegangen, dass p bekannt ist. Davon wird schließlich auch zb bei der Signierung mittels RSA ausgegangen. Überhaupt ist p eigentlich überall immer jedem bekannt... warum nicht auch hierbei? wäre p nicht bekannt, also die Gruppe, in der sich ElGamal befindet, wäre es schließlich auch beim Einsatz als Verschlüsselung nicht möglich, die Nachrichten wieder zu entschlüsseln. Es wäre noch nicht einmal möglich eine Nachricht zu generieren die verschlüsselt werden kann, denn diese könnte ja auch zu groß für die Gruppe sein.

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

Re: Unsicherheit von ElGamal

Beitrag von Domac »

Ja stimmt, SuperRalf hat recht! Der Angreifer muss eine Nachricht m \(\in\) {0,1, ... , p-1} wählen.
Extend my dropbox space (here).
Thanks!

ElGamal
Nichts ist wie es scheint
Beiträge: 23
Registriert: 19. Dez 2011 20:56

Re: Unsicherheit von ElGamal

Beitrag von ElGamal »

SupeRalF hat geschrieben:Also ich bin auch davon ausgegangen, dass p bekannt ist. Davon wird schließlich auch zb bei der Signierung mittels RSA ausgegangen. Überhaupt ist p eigentlich überall immer jedem bekannt... warum nicht auch hierbei? wäre p nicht bekannt, also die Gruppe, in der sich ElGamal befindet, wäre es schließlich auch beim Einsatz als Verschlüsselung nicht möglich, die Nachrichten wieder zu entschlüsseln. Es wäre noch nicht einmal möglich eine Nachricht zu generieren die verschlüsselt werden kann, denn diese könnte ja auch zu groß für die Gruppe sein.
Ok super, vielen Dank! Damit funktioniert mein Angriff zu 100% :wink:

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

Re: Unsicherheit von ElGamal

Beitrag von SupeRalF »

ElGamal hat geschrieben:Ok super, vielen Dank! Damit funktioniert mein Angriff zu 100% :wink:
Wie jetzt, du kriegst eine Trefferrate von 100%? ich komme nur auf 75%... mist :(

ElGamal
Nichts ist wie es scheint
Beiträge: 23
Registriert: 19. Dez 2011 20:56

Re: Unsicherheit von ElGamal

Beitrag von ElGamal »

SupeRalF hat geschrieben:Wie jetzt, du kriegst eine Trefferrate von 100%? ich komme nur auf 75%... mist :(
Naja in der Aufgabenstellung ist ja nicht explizit 100% gefordert, von daher denke ich, dass 75% auch in Ordnung sind. Du solltest halt nur begründen können, wo die 75% herkommen und dass die dem Angreifer garantiert sind... 8)

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

Re: Unsicherheit von ElGamal

Beitrag von e_k »

Zu dieser Aufgabe habe ich auch eine Frage:

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?

Vielen Dank im Voraus!

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

Re: Unsicherheit von ElGamal

Beitrag von e_k »

Eine weitere Frage hinterher:

Beim Beweis in der a):

Kann man davon ausgehen, dass es sich bei dem "oder" in der zu beweisenden Äquivalenz um ein nicht-ausschließendes Oder handelt?

Also: Können beide Legendre-Symbole = 1 sein oder ist das ausgeschlossen?

Vielen Dank im Voraus!

Antworten

Zurück zu „Archiv“