Übung 4 El Gamal

[JanPM]

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

Würde mich sehr freuen,
Cya Jan

[jno]

Dito... =)

[jst]

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]

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...

[JanPM]

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)

[JanPM]

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

[jno]

Siehe EDIT

[jst]

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

[FidorDewski]

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]

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.

[jst]

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]

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

[jack_90]

Ah natürlich, das macht Sinn. Wie konnte ich das nur übersehen...
Danke euch