Übung 4 El Gamal

JanPM
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 105
Registriert: 20. Mär 2009 14:25
Wohnort: Darmstadt

Übung 4 El Gamal

Beitrag von JanPM » 11. Mär 2011 15:52

Hi, hat jemand Lösungsansätze für die El Gamal Übung?

Würde mich sehr freuen,
Cya Jan

jno
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 144
Registriert: 18. Mai 2007 09:41

Re: Übung 4 El Gamal

Beitrag von jno » 12. Mär 2011 14:13

Dito... =)

jst
Neuling
Neuling
Beiträge: 6
Registriert: 1. Nov 2010 19:04

Re: Übung 4 El Gamal

Beitrag von jst » 12. Mär 2011 16:15

Hi,
also die Teile a) und b) haben wir auf Anraten unseres Tutors damals nicht bearbeitet, deshalb kann ich euch nur die c) erklären:

Wir wählen g aus G beliebig: g=4 (wir haben 4 gewählt, weils klein ist -einfacher zu rechnen- und weils quadratisch ist, G war ja die Gruppe der quadratischen Reste)
Dann berechnen wir h= g^a= 4^37 mod 167 = 76
Jetzt gucken wir uns die zu verschlüsselnde Nachricht an: 011101, das ist 29 im Dezimalsystem.
Das muss in ein Element aus G umgewandelt werden. In Aufgabenteil a) steht im dritten Absatz, dass m dazu auf (m+1)^2 mod p abgebildet wird:
(29+1)^2 mod 167 = 65
So, fast fertig. Jetzt noch ein zufälliges k wählen. Wir haben k= 71 genommen, warum weiß ich nicht mehr.
c= E(m,k) =E(65,71)= (g^k, m*h^k) =( 4^71 mod 167, 65*76^71 mod 167) = (132, 44)

Ich hoffe das hilft euch weiter.

jno
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 144
Registriert: 18. Mai 2007 09:41

Re: Übung 4 El Gamal

Beitrag von jno » 12. Mär 2011 16:24

Also bei der c) hab ich mal ein bisschen gerechnet, da kommts natürlich auch drauf an, wie man die freien Parameter wählt.
Ich habe \(g:=3\), damit ist \((p,g,A)\) mit \(A:=g^a\) mod \(p=14\) mein öffentlicher Schlüssel und für
\(m=0b011101=29\) ist meine verschlüsselte Nachricht \((B,c)\) mit \(B=g^b\) mod \(p= 9\), wobei ich \(b:=2\) gewählt habe, und \(c=A^b * m\) mod \(p = 6\).
Beim Entschlüsseln ergibt sich dann auch tatsächlich wieder \(m=B^{p-1-a}*c = 9^{129}*6\equiv 29\) mod \(167\).
Bei der b) habe ich leider keine Ahnung, bei der a) auch nicht so richtig, ehrlich gesagt weiß ich nicht mal wofür die genau gut sein sollen.
Ansatz bei der a) wäre glaube ich Surjektivität zu zeigen, das reicht bei Abbildungen zwischen endlichen Mengen um Bijektivität zu folgern. Für die Surjektivität müsste man zeigen, dass für ein Element \(r=m^2\) mod \(p \in \mathbb{G}\) mit m zwischen q und 2q+1 ein Element \(m' \in \{1,\dots,q\}\) existiert, so dass \(r=m'^2\) mod \(p\). Wie das geht, weiß ich aber nicht.

EDIT: Okay, diese Sache mit der Umwandlung in ein Element aus \(\mathbb{G}\) hab ich nicht gemacht, genauso wie ich einen Generator von \(\mathbb{Z}_p\) und nicht von \(\mathbb{G}\) genommen habe. Aber wie gesagt, ich weiß immer noch nicht ganz wofür dieser ganze Aufwand mit diesen quadratischen Resten gut ist, die Verschlüsselung hat bei mir ja auch so funktioniert...
Zuletzt geändert von jno am 12. Mär 2011 16:32, insgesamt 1-mal geändert.

JanPM
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 105
Registriert: 20. Mär 2009 14:25
Wohnort: Darmstadt

Re: Übung 4 El Gamal

Beitrag von JanPM » 12. Mär 2011 16:28

Ah ok, dann ist das wahrscheinlich eh nicht relevant. Bei der c) hab ich für das zufällige Element k=3 gewählt und Generator g = 4 und beim Chiffrat kommt bei mir dann raus: (64, 154)
Zuletzt geändert von JanPM am 12. Mär 2011 16:33, insgesamt 1-mal geändert.

JanPM
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 105
Registriert: 20. Mär 2009 14:25
Wohnort: Darmstadt

Re: Übung 4 El Gamal

Beitrag von JanPM » 12. Mär 2011 16:32

Darf der Generator 3 sein? Ich glaube der muss quadratisch sein, allerdings bin ich mir auch nicht sicher.

jno
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 144
Registriert: 18. Mai 2007 09:41

Re: Übung 4 El Gamal

Beitrag von jno » 12. Mär 2011 16:33

Siehe EDIT

jst
Neuling
Neuling
Beiträge: 6
Registriert: 1. Nov 2010 19:04

Re: Übung 4 El Gamal

Beitrag von jst » 12. Mär 2011 16:52

Der Generator g muss aus G sein, sonst könnte er G ja nicht generieren :wink:

FidorDewski
Erstie
Erstie
Beiträge: 13
Registriert: 8. Mär 2011 18:29

Re: Übung 4 El Gamal

Beitrag von FidorDewski » 12. Mär 2011 18:14

Klar muss der Generator aus G sein. Allerdings sind, wenn man G als die Menge der quadratischen Reste nimmt, nicht alle Elemente der Menge nötigenfalls Quadrate, denn man rechnet ja m^2 mod p. Als Beispiel: Wie in der Übung: p = 167. Wähle m = 13 (ist Element Z_167). Dann ist 13^2 = 169 = 2 (mod p) - aber 2 ist keine Quadratzahl. Somit muss g KEIN Quadrat sein.

PS.: Wenn ihr Lösungsansätze zu a) und b) haben wollt: a) hab ich schon gelöst, b) hatte ich erstmal übersprungen (könnte mich aber noch mal dransetzen). Ich glaube aber kaum, dass die auch nur irgendwie klausurrelevant sind.

PPS.: Aufgabenteil b) sagt übrigens gerade, dass jedes Element g != 1 aus G ein Generator von G ist, also muss man nur schauen, dass man tatsächlich einen Rest einer Quadratzahl erwischt.

jack_90
Mausschubser
Mausschubser
Beiträge: 75
Registriert: 29. Sep 2009 22:38
Wohnort: Darmstadt
Kontaktdaten:

Re: Übung 4 El Gamal

Beitrag von jack_90 » 14. Mär 2011 14:26

Die Verschlüsselung mit m = 29 hat vermutlich funktioniert, da 29 auch ein quadratischer rest aus G ist. Die Nachricht zu 29 müsste dann aber 14 sein (siehe Definition von G).
Was mir noch nicht ganz klar ist, ist die Entschlüsselung. Mit (132, 44) als chiffrat erhalte ich D(c1,c2) = c1*c2^(-a) = 65, was (m+1)² mod 167 entspricht.
Wie komme ich jetzt von 65 auf meine ursprüngliche Nachricht m = 29 ohne die Reste durchzuprobieren, also die Gl.: (m+1)² = k*167 + 65 zu lösen, wobei k von 0-166 geht.
EiSE Tutor WS 12/13

jst
Neuling
Neuling
Beiträge: 6
Registriert: 1. Nov 2010 19:04

Re: Übung 4 El Gamal

Beitrag von jst » 14. Mär 2011 14:44

Das steht in der Übung in Aufgabenteil a) ganz unten:
"An dieser Stelle sei erwähnt, dass i auch effizient invertierbar ist..."
Man muss w= 65^((167+1)/4) mod 167 rechnen. Dann erhält man w=137, das ist eine Lösung (und hier nicht die gesucht), die zweite Lösung ist -w, also hier 30.
Und 30-1=29.

jno
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 144
Registriert: 18. Mai 2007 09:41

Re: Übung 4 El Gamal

Beitrag von jno » 14. Mär 2011 14:48

Das geht mit der Formel die auch am Ende der a) steht. Du berechnest die Wurzel aus (m+1)^2 durch 65^((167+1)/4) mod 167 = 137. Die andere Wurzel ist dann -137, was kongruent zu 30 modulo 167 ist und tatsächlich passt es für die 2. Wurzel: m+1=30 => m=29.

....zu langsam :P

jack_90
Mausschubser
Mausschubser
Beiträge: 75
Registriert: 29. Sep 2009 22:38
Wohnort: Darmstadt
Kontaktdaten:

Re: Übung 4 El Gamal

Beitrag von jack_90 » 14. Mär 2011 15:14

Ah natürlich, das macht Sinn. Wie konnte ich das nur übersehen...
Danke euch :wink:
EiSE Tutor WS 12/13

Antworten

Zurück zu „Archiv“