Seite 1 von 1

Übung 4 - ElGamal

Verfasst: 6. Mär 2012 17:11
von 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

Re: Übung 4 - ElGamal

Verfasst: 6. Mär 2012 20:02
von 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)\)

Re: Übung 4 - ElGamal

Verfasst: 7. Mär 2012 00:15
von 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?

Re: Übung 4 - ElGamal

Verfasst: 7. Mär 2012 13:45
von 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...

Re: Übung 4 - ElGamal

Verfasst: 8. Mär 2012 22:25
von 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

Re: Übung 4 - ElGamal

Verfasst: 9. Mär 2012 19:46
von 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...

Re: Übung 4 - ElGamal

Verfasst: 9. Mär 2012 20:18
von Michl
Capono hat geschrieben: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

Re: Übung 4 - ElGamal

Verfasst: 9. Mär 2012 20:19
von 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

Re: Übung 4 - ElGamal

Verfasst: 9. Mär 2012 20:32
von Capono
Michl hat geschrieben:
Capono hat geschrieben: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 hat geschrieben: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 :oops: hab mich zu sehr im Beispiel auf das a fokusiert...

Re: Übung 4 - ElGamal

Verfasst: 9. Mär 2012 22:14
von mansur
Capono hat geschrieben: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^^