# Message extraction from specific ElGamal encryption system

Suppose you have an ElGamal system over $$G=\mathbb{F}_p^* = $$ $$\mathcal{E}(k,m)=k^rm$$ $$\mathcal{D}(b,w, x)=wx^{-b}$$ Where the key is $$k=y=g^b$$, the message is $$m$$, and where $$r$$ is a random number. And the cipher text is: $$(x,w)$$, $$x=g^r$$, $$w=\mathcal{E}(k,m)$$

(you only know $$x,y,g,w,p, l)$$

Problem:

Suppose $$p$$ is a prime such that the discrete logarithm problem is hard in $$\mathbb{F}_p^*$$. Suppose also that $$p-1$$ is dicisible by a (small) known prime $$l$$, and that $$m\in\mathbb{F}_p^*$$ has order $$l$$. Show that $$m$$ can be recovered from an encryption of $$m$$ using essentially a small multiple of $$\sqrt{l}$$ group operations.

Now i can only come up with the following solutions, using a multiple of $$l$$ group operations.

My "solution":

$$l|(p-1) \Rightarrow \exists d\in \mathbb{Z}_{p-1}$$ s.t. $$dl \equiv 0 (mod (p-1))$$

Calculate $$wy^i$$ (wil at max try (l-1)) try the following til you recover a message.

You wil recover a message when $$l|((r+i)b)$$. As: $$wy^i=mg^{br}g^{bi}=mg^{b(r+i)}$$ $$l|((r+i)b) \Rightarrow \exists n, nl=(r+i)b$$ $$\Rightarrow wy^i=mg^{nl}$$ $$\Rightarrow (wy^i)^d=m^dg^{dnl}=m^dg^{n(p-1)}=m^d$$ m would thus be a d-th rooth of $$(wy^i)^d$$

We can easily calulate all the possible l d-th roots (small amount as l is small) $$g^{0d},g^{1d},g^{2d} ... g^{(l-1)d}$$ One of these will thus be the message if it maches a $$(wy^i)^d$$

Do you guys have any input or better solutions? (As I assume there exists as mine is only a l-multiple)