Übung 4 - ElGamal

[chris_tanase]

Hallo,
ich dachte ich poste hier mal meine Lösung zur 4. Übung in der Hoffnung, dass man mich korrigieren möge, wenn was nicht stimmt

a)
ord(G) = 58

b)
Ich hab mir einfachheitshalber g=2 ausgesucht, nachdem ich mir die Berechnung bei
http://www.am.hs-mannheim.de/KryptoLern ... ehrlich=on
angesehen habe. Oder ist hier ein spezieller Generator gefragt? Stimmt ansonsten die dortige vorgehensweise zum finden eines Generators bzw. einer Primitivwurzel?

c)
Zunächst Dez(57) -> Bin(111001)
Dann nach dem hier
http://www.fachschaft.informatik.tu-dar ... 99&t=11595
beschriebenen System vorgehen um Effiziente Exponentiation modulo n durchzuführen.
Raus kommt bei mir 30 (mod 59)

d)
ord(G) = 58;
58 = 2 * 29;
Gesucht ist also die Verschlüsselung von 29, richtig?
Öffentlicher Schlüssel h=30 wurde ja schon in c) berechnet, also fehlt noch: c=mh^k (mod p) <-- [s. Skript 4 S. 11]
c = 29 * 30^57 mod 59 = ((30^57 mod 59) * 29) mod 59 = 58

Hoffe ich hab nicht allzugroßen Mist gebaut...
Viele Grüße,
Chris

[olg]

Ich habe da mit kleinen Ausnahmen (siehe d)) das gleiche raus.


d)

Die Primfaktorzerlegung von 58 ist (2,29), Also m=29 (Habe ich also auch raus)

Du hast nur ein chiffrat angegeben, auf ts-4, S.11 steht allerdings folgendes:

\(E(m) = (c_1, c_2) = (g^k , mh^k)\) (für k zufällig).

Hier kann man beliebige k wählen, da in der Übung keins angegeben wurde (oder habe ich was übersehen?)

In meinem Fall für k=3:

\(c = (c_0, c_1) = (2^3 , 29*30^3 \text{ (mod p)}) = (8,11)\)

[gregor]

Ich hab dann noch versucht, das chiffrat zu entschlüsseln, was mir nicht gelungen ist.

laut skript: \(44 \cdot 2^{-57}\)

kann mir da jemand weiterhelfen?

[chris_tanase]

Die Formel zum Entschlüsseln im Skript lautet ja: c2*c1^-a (mod p)
Schätze ich hab daran auch was nicht verstanden, denn wenn man 11*8^-57 (mod 59) berechnet, kommt da was ganz anderes raus...
Bei wiki
http://de.wikipedia.org/wiki/Elgamal-Ve ... .BCsselung
steht die Formel als: c2*c1^(p-1-a) (mod p) --> D(8,11) = 11*8^(59-1-57) (mod 59) = 29
Das sieht schon viel besser aus...

[MikeS]

c2*c1^-a = c2*(c1^a)^-1 wobei hier mit ^-1 das multiplikative Inverse in Z(59)* gemeint ist(!)
Dieses kann man mithilfe des erweiterten Euklid berechnen.

Für D(8,11) hieße das:

D(8,11) = 11 * (8^57)^-1 (mod 59) = 11 * (37)^-1 (mod 59) = 11 * 8 (mod 59) = 29

[Capono]

Hallo,
eine Frage zu c) ich komm auf 29 und nicht auf 30. Wie berechnet man das.
Nach dem Link den du angeben hast.
Bekomme ich für d0= 57 d1 = 4 d2= 16 d3 = 20 d4 = 46 d5=51 (di+1 = di² mod n) ,,
Nun s= 57*20*46*51 = 2674440 mod 59 = 29 ...
kann mir bitte jemand sagen was ich falsch mache.

hab das auch schon mit dem Skript Algorithmus versucht komme immer auf 29 und nicht auf 30...

[Michl]

Hallo,
eine Frage zu c) ich komm auf 29 und nicht auf 30. Wie berechnet man das.
Nach dem Link den du angeben hast.
Bekomme ich für d0= 57 d1 = 4 d2= 16 d3 = 20 d4 = 46 d5=51 (di+1 = di² mod n) ,,
Nun s= 57*20*46*51 = 2674440 mod 59 = 29 ...
kann mir bitte jemand sagen was ich falsch mache.

hab das auch schon mit dem Skript Algorithmus versucht komme immer auf 29 und nicht auf 30...

Ich glaube du hast Basis und Exponent vertauscht. Wenn wir \(h = g^a = 2^{57}\) berechnen wollen ist nach [1] \(d_0 = 2\)

[1] http://www.fachschaft.informatik.tu-dar ... 99&t=11595

[c-3po]

Also mit dem Algorithmus aus dem Skript kommt man wie folgt auf die 30.

Code: Alles auswählen

y1=1	r = 1 * 2 mod 59 = 2
		 b = 2 * 2 mod 59 = 4
y2=0	b = 4 * 4 mod 59 = 16
y3=0	b = 16*16 mod 59 = 20
y4=1	r = 2 *20 mod 59 = 40
	 	b = 20*20 mod 59 = 46
y5=1	r = 40*46 mod 59 = 11
	 	b = 46*46 mod 59 = 51
y6=1	r = 11*51 mod 59 = 30

[Capono]

Hallo,
eine Frage zu c) ich komm auf 29 und nicht auf 30. Wie berechnet man das.
Nach dem Link den du angeben hast.
Bekomme ich für d0= 57 d1 = 4 d2= 16 d3 = 20 d4 = 46 d5=51 (di+1 = di² mod n) ,,
Nun s= 57*20*46*51 = 2674440 mod 59 = 29 ...
kann mir bitte jemand sagen was ich falsch mache.

hab das auch schon mit dem Skript Algorithmus versucht komme immer auf 29 und nicht auf 30...

Ich glaube du hast Basis und Exponent vertauscht. Wenn wir \(h = g^a = 2^{57}\) berechnen wollen ist nach [1] \(d_0 = 2\)

[1] http://www.fachschaft.informatik.tu-dar ... 99&t=11595

Also mit dem Algorithmus aus dem Skript kommt man wie folgt auf die 30.

Code: Alles auswählen

y1=1	r = 1 * 2 mod 59 = 2
		 b = 2 * 2 mod 59 = 4
y2=0	b = 4 * 4 mod 59 = 16
y3=0	b = 16*16 mod 59 = 20
y4=1	r = 2 *20 mod 59 = 40
	 	b = 20*20 mod 59 = 46
y5=1	r = 40*46 mod 59 = 11
	 	b = 46*46 mod 59 = 51
y6=1	r = 11*51 mod 59 = 30

Danke euch beiden. Ja ich habe die Basis vertauscht mit der Exponenten hab mich zu sehr im Beispiel auf das a fokusiert...

[mansur]

Hallo,
eine Frage zu c) ich komm auf 29 und nicht auf 30. Wie berechnet man das.
Nach dem Link den du angeben hast.
Bekomme ich für d0= 57 d1 = 4 d2= 16 d3 = 20 d4 = 46 d5=51 (di+1 = di² mod n) ,,
Nun s= 57*20*46*51 = 2674440 mod 59 = 29 ...
kann mir bitte jemand sagen was ich falsch mache.

hab das auch schon mit dem Skript Algorithmus versucht komme immer auf 29 und nicht auf 30...

d0 = g = 2
Die Basis ist bei dem Link nämlich als a benannt

EDIT: ok ist wohl schon erledigt.. hatte die seite noch die ganze zeit offen^^