Wie zeigt man mathematisch, dass man beim LGamal Verfahren nicht zweimal dasselbe b nutzen soll?

Question

Wir betrachten das ElGamal Verschlüsselungsverfahren. Wir sollen zeigen, dass man zur Berechnung bon B=g^b bei einer zweiten verschlüssenden Nachricht ein anderes b als vorher nutzen sollte, weil das sonst zu u´nsicher wäre. Wie kann man das machen? Ansätze?

Danke:-)

Answer 1

Mathefrager, 
zunächst erinnere ich kurz an den Ablauf des ElGamal-Verfahrens (Quelle: meine Klausurzusammenfassung), um u.a. aufzuzeigen, auf welcher Grundlage meine Argumentation fußt.  Eine "Schwachstelle" kann tatsächlich in der Wahl des Exponenten b liegen. Seien $$m,m'$$ zwei verschiedene Nachrichten. Wählen wir dasselbe b, dann gilt: $$c=A^b\cdot m\mod p$$ $$c'=A^b\cdot m'\mod p$$ $$\Longrightarrow c\cdot c^{-1}=A^b\cdot m'\cdot (A^b)^{-1}\cdot m^{-1}=m'\cdot m^{-1}\cdot \underbrace{A^b\cdot (A^b)^{-1}}_{=1}$$$$\Longrightarrow c'\cdot c^{-1}=m' \cdot m^{-1}$$ $$\Longrightarrow c'\cdot c\cdot m = m'$$ Wenn man das Paar (c,m), also den verschlüsselten und entschlüsselten Text kennt, dann kann man zu c' bei gleichem b den Klartex m' sehr leicht berechnen, nämlich durch: $$c'=c^{-1}\cdot m^{-1}\cdot m'$$ Voraussetzung dafür ist natürlich, dass A gleich bleibt. Wenn Du Rückfragen hast, kannst Du Dich gerne wieder melden!

André, savest8

Comments

Vieeeeeeelen Dank. Wie kommst Du aber im letzten Schritt auf c'*c*m=m'?

---

Hallo Mathefrager,

die letzte Zeile erhältst Du durch Multiplikation der vorangegangenen mit dem Faktor m, also: $$c'\cdot c\cdot m=m'\cdot \underbrace{m^{-1}\cdot m}_{=m^{-1+1}=m^0=1}$$