Frage zu Übungsblatt 4 (ElGamal anwenden)

Toobee
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 225
Registriert: 7. Apr 2011 12:58

Frage zu Übungsblatt 4 (ElGamal anwenden)

Beitrag von Toobee » 30. Apr 2011 19:09

Hi,

beim Übungsblatt 4, Aufgabe 1c soll der ElGamal Algo angewendet werden. Ich hab zwar die Lösung hier, die geht aber nur bis zum Verschlüsseln, dass Entschlüsseln fehlt hier leider.

Hier mal so weit, was in der Aufgabe stand:

p = 167
a = 37
g = 4
h = g^a mod p = 76
m = nachricht = 29

Zufälliges k = 71

\(m' = (m+1)^2 mod p = (29+1)^2 \mod 167 = 65\)

\(c_1 = g^k \mod p = 4^{71} mod 167 = 132\)
\(c_2 = m' * h^k \mod p = 65 * 76^(71) mod 167 = 44\)

Enc(132, 44)
soweit alles klar, ist auch das was in der Lösung steht

Das Entschlüsseln nun:
m' = 44*(132)^(-37) mod 167 = 65

Stimmt auch noch, aber wie komme ich jetzt wieder an mein ursprüngliches m?

Toobee
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 225
Registriert: 7. Apr 2011 12:58

Re: Frage zu Übungsblatt 4 (ElGamal anwenden)

Beitrag von Toobee » 2. Mai 2011 21:50

Keiner eine Idee?

Benutzeravatar
salted
Mausschubser
Mausschubser
Beiträge: 84
Registriert: 28. Sep 2009 21:21

Re: Frage zu Übungsblatt 4 (ElGamal anwenden)

Beitrag von salted » 2. Mai 2011 22:25

Dein Fehler liegt hier:
Toobee hat geschrieben: Das Entschlüsseln nun:
m' = 44*(132)^(-37) mod 167 = 65

Stimmt auch noch, aber wie komme ich jetzt wieder an mein ursprüngliches m?
-a != -37, da hier das multiplikative Inverse von a gemeint ist, welches man mit dem Erweiterten Euklid berechnet (so, dass 37 * -a mod 167 = 1).

Siehe auch http://de.wikipedia.org/wiki/Elgamal-Kr ... %BCsselung

Toobee
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 225
Registriert: 7. Apr 2011 12:58

Re: Frage zu Übungsblatt 4 (ElGamal anwenden)

Beitrag von Toobee » 3. Mai 2011 10:41

Hi,

danke für die Antwort.

Das mul. Inverse von 37 zu 167 ist -9 bzw. 158.

37*158 mod 167 = 1

Demnach,
m = 44*(132)^(158) mod 167 = 57

Ist aber falsch :cry:

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

Re: Frage zu Übungsblatt 4 (ElGamal anwenden)

Beitrag von jno » 13. Mai 2011 23:38

Toobee hat geschrieben:Hi,
...
Stimmt auch noch, aber wie komme ich jetzt wieder an mein ursprüngliches m?
Man musste da doch glaub ich noch mit der angegebenen Formel die Wurzel ziehen oder? Ich glaub so wars... steht auch hier:
http://d120.de/forum/viewtopic.php?f=199&t=21770
Dann kommt eigentlich schon wieder m raus.

Antworten

Zurück zu „Archiv“