Übung 4 - ElGamal

chris_tanase
Erstie
Erstie
Beiträge: 22
Registriert: 23. Okt 2008 18:08

Übung 4 - ElGamal

Beitrag 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

Benutzeravatar
olg
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 297
Registriert: 1. Okt 2008 19:24

Re: Übung 4 - ElGamal

Beitrag 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)\)
"To Perl, or not to Perl, that is the kvetching." ~Larry Wall

gregor
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 101
Registriert: 14. Okt 2008 07:20
Wohnort: Darmstadt
Kontaktdaten:

Re: Übung 4 - ElGamal

Beitrag 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?

chris_tanase
Erstie
Erstie
Beiträge: 22
Registriert: 23. Okt 2008 18:08

Re: Übung 4 - ElGamal

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

MikeS
Erstie
Erstie
Beiträge: 19
Registriert: 4. Okt 2010 16:15

Re: Übung 4 - ElGamal

Beitrag 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

Capono
Windoof-User
Windoof-User
Beiträge: 35
Registriert: 27. Okt 2011 16:01

Re: Übung 4 - ElGamal

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

Benutzeravatar
Michl
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 293
Registriert: 12. Apr 2009 08:53
Wohnort: Darmstadt

Re: Übung 4 - ElGamal

Beitrag 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

c-3po
Erstie
Erstie
Beiträge: 11
Registriert: 4. Nov 2010 17:16

Re: Übung 4 - ElGamal

Beitrag 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

Capono
Windoof-User
Windoof-User
Beiträge: 35
Registriert: 27. Okt 2011 16:01

Re: Übung 4 - ElGamal

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

Benutzeravatar
mansur
Windoof-User
Windoof-User
Beiträge: 30
Registriert: 14. Okt 2007 02:21

Re: Übung 4 - ElGamal

Beitrag 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^^

Antworten

Zurück zu „Archiv“