Entschlüsselung von ElGamal

01.05.2011, 22:27	Elijotto	Auf diesen Beitrag antworten »
Entschlüsselung von ElGamal Hi, ich hab eine El-Gamal Verschlüsselungsaufgabe. Anhand der Lösung schein ich auch richtig gerechnet zu haben, nur die Lösung beinhaltet nicht den Entschlüsselungsschritt - und bei dem kleppts grade. p = 167, mein modulo a = 37, mein privater key g = 4, mein generator und erster öffentlicher schlüssel h = g^a mod p = 76, mein zweiter öffentlicher m = nachricht = 29 Zufälliges k = 71 $\begin{eqnarray} m' = (m+1)^2 mod p = (29+1)^2 \mod 167 = 65 \end{eqnarray}$ $\begin{eqnarray} c_1 = g^k \mod p = 4^{71} \mod 167 = 132 \end{eqnarray}$ $\begin{eqnarray} c_2 = m' h^k \mod p = 65 * 76^{71} \mod 167 = 44 \end{eqnarray}$ Enc(132, 44) soweit alles klar, ist auch das was in der Lösung steht Das Entschlüsseln nun: $\begin{eqnarray} m' = 44(132)^{(-37)} \mod 167 = 65 \end{eqnarray}$ Jetzt bin ich wieder bei meinem m', aber wie komme ich jetzt auf meine ursprüngliche Nachricht zurück? Edit: LaTeX korrigiert. Gruß, Reksilat.
02.05.2011, 14:01	Elijotto	Auf diesen Beitrag antworten »
Weiß keiner was?
02.05.2011, 23:22	Reksilat	Auf diesen Beitrag antworten »
Hi Elijotto, Sollte so was nicht eher in Deinem Skript stehen? Bei Wiki steht auch nichts von einem $\begin{eqnarray} m' \end{eqnarray}$ ,aber ansonsten wird alles genauso verschlüsselt wie bei Dir. Ich sehe auch nicht den Sinn darin so ein $\begin{eqnarray} m' \end{eqnarray}$ zu berechnen und dieses zu verschlüsseln, wenn man auch gleich das $\begin{eqnarray} m \end{eqnarray}$ auf gleichem Wege verschlüsseln kann. Zumal ja dann auch jeder mit dem gleichen Aufwand aus $\begin{eqnarray} m' \end{eqnarray}$ das $\begin{eqnarray} m \end{eqnarray}$ berechnen kann - das kann insofern nicht mehr zur eigentlichen Entschlüsselung gehören. Gruß, Reksilat.
03.05.2011, 01:31	Dopap	Auf diesen Beitrag antworten »
die Entschlüsselung ist ein wenig aufwendiger: $\begin{eqnarray} m=DEENC(m') = DEENC(c_1,c_2): \end{eqnarray}$ $\begin{eqnarray} K= MOD(c_1^a, p) \end{eqnarray}$ Potenz- Modulo $\begin{eqnarray} G= INVMOD(K,p) \end{eqnarray}$ inverser- Modulo $\begin{eqnarray} m= MULTMOD(c_2, G , p) \end{eqnarray}$ multiplikativer- Modulo
03.05.2011, 10:37	Elijotto	Auf diesen Beitrag antworten »
Hi, also m' = (m+1)^2 soll verwendet werden, da das ganze ja durch die Modulo operation trotzdem funktionieren soll. Das versuche ich ja grade zu bestätigen, durch ver- und entschlüsseln. Der "einfache" ElGammal, ohne dieses m' funktioniert. Nur bei diesem Beispiel soll oder muss Entschlüsselung auch möglich sein. Nur es funktioniert nicht @Dopap Dein Weg führt mich wieder zu der 65, also m' und nicht mein ursprüngliches m. DEENC(132, 44) $\begin{eqnarray} K = 132^{37} \mod 167 = 124<br /> G = (12466 \mod 167 = 1) => G = 66<br /> m = 4466 mod 167 = 65 \end{eqnarray}$
03.05.2011, 12:25	Reksilat	Auf diesen Beitrag antworten »
Letztlich ist der ElGamal hier doch gar nicht von Bedeutung. Du berechnest aus $\begin{eqnarray} m \end{eqnarray}$ Dein $\begin{eqnarray} m' \end{eqnarray}$ , verschlüsselst dieses wie auch immer, entschlüsselst es wieder, und willst nun aus dem $\begin{eqnarray} m' \end{eqnarray}$ wieder Dein $\begin{eqnarray} m \end{eqnarray}$ bestimmen. Dies geht aber nicht, da zum Beispiel auch $\begin{eqnarray} m=136 \end{eqnarray}$ das gleiche $\begin{eqnarray} m' \end{eqnarray}$ liefert. Die Abbildung $\begin{eqnarray} m\to(m+1)^2 \mod p \end{eqnarray}$ ist eben nicht injektiv, Du verlierst Informationen, die Du nicht wieder zurückgewinnen kannst.
Anzeige

04.05.2011, 06:21	Elijotto	Auf diesen Beitrag antworten »
Hi, also eigentlich sollte es gehen. Es war der vorherige Teil der Übung zu zeigen, dass diese Abbildung bijektiv ist. Ich hab mal bei Rapidshare das Aufgabenblatt mit der Lösung bei Rapidshare hochgeladen. Kann gut sein, dass dort vorher noch ein Fehler drin ist...aber ich meine das müsste gehen (oder ich hab was total falsch verstanden) Hier der Link: rapidshare.com/files/460503587/ElGamal.zip Sind wneiger als 0.5 MB
04.05.2011, 11:07	Reksilat	Auf diesen Beitrag antworten »
Mach doch lieber einen Screenshot und lade das Bild als Anhang hoch. Siehe dazu: [User-Tutorial] Bilder einfügen Ich zum Beispiel kann gerade nicht auf Rapidshare zugreifen, da diese Seite für mich gesperrt ist. Letztlich ist diese Abbildung trotzdem nicht bijektiv, da $\begin{eqnarray} (29+1)^2\equiv (136+1)^2\pmod{167} \end{eqnarray}$ . Bevor ich mir also irgendwas angucke könntest Du Dir ja mal darüber Gedanken machen. Allgemein ist quadrieren modulo $\begin{eqnarray} p \end{eqnarray}$ (für $\begin{eqnarray} p>2 \end{eqnarray}$ ) nie bijektiv, da ja $\begin{eqnarray} x \end{eqnarray}$ und $\begin{eqnarray} -x \end{eqnarray}$ immer das gleiche Bild haben. Gruß, Reksilat.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »