Suppose you have an ElGamal system over $G=\mathbb{F}_p^* = <g>$ $$\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)$


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)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.