I'm stuck with the following problem on ElGammal encryption.

We work on $\mathbb{Z}_{p}^*$ where $p$ is prime and we are given $p$, the generator $g$ of $\mathbb{Z}_{p}^*$ , the public key used $y$ and five encryptions $(u_1,v_1), \cdots, (u_5,v_5)$ where each of them is a encryption of a message $m$ that can be $1$ or $-1$.

Please refer to the second scheme of this question if you need more details on the ElGammal cryptosystem I'm using.

As a hint I'm told to look for a subgroup of index two. I tried to solve the discrete logarithm problem in that subgroup with sage but as this post discusses the complexity is only reduced by a constant so that it is still intractable.

I give you the code I was using in case you have some comments.

F = Integers(p)
gmod = F(g)
q = p // 2
F2 = Integers(q)
gmod2 = F2(g)
ymod2 = F2(y)
gmod2 = F2(g)
ymod2 = F2(y)

Can you figure out how this could be solved?


In my case $\frac{p-1}{2}$ is already prime.

  • 1
    $\begingroup$ Hint: we know that (for any $1 \le z < p$, we have $z^{p-1} \equiv 1$ (Fermat's Little Thereom); $z^{p-1} = (z^q)^2$; and so we know that, whatever $z^q$ is, when squared, it gives us 1. Given that $p$ is prime, what are the possible squareroots of 1? Does that give you a hint what $(y^r)^q$ could be? $\endgroup$ – poncho Nov 1 '16 at 17:58

Further hint: suppose we computed $q = (p-1)/2^\lambda$ odd, and given $(u_1, v_1) = (g^r, m y^r)$, we compute $(g^r)^q, (m y^r)^q$. Once we have done that, how can you distinguish the $m=1$ and $m= -1$ cases?


Thanks to poncho's hints we can work as follows:

1.Compute $(g^r)^q$. I claim that:

$ (g^r)^q = \begin{cases} 1 &\quad\text{if r is even}\\ \neq 1 &\quad\text{if r is odd} \ \end{cases} $

For the first case we have $(g^{r})^{\frac{p-1}{2}} = (g^{p-1})^{\frac{r}{2}} = 1$. For the second case, the result was one then $ord(g) = p-1$ divides $r \frac{p-1}{2}$. However, $p-1$ is even and we assumed that $r$ and $\frac{p-1}{2}$ are odd numbers. An even number cannot divide an odd one.

2.Compute $(my^r)^q = m^q y^{rq} = m y^{rq}$ where we used that $m \in \{-1,1\}$.

3.Compute $y^{rq}$. I claim that (assume x is the private key of the algorithm):

$ y^{rq} = \begin{cases} 1 &\quad\text{if (r is even) or (r is odd and x is even)}\\ -1 &\quad\text{if r is odd and x is odd} \ \end{cases} $

If r is even we can reason as we did in the first case. Assume r is odd. Then $(y^{rq})^2 = y^{2rq} = 1$ and as $\mathbb{Z}_p$ is a field we know that this equation has at most 2 solutions, namely -1 and 1.

If assume that $y^{rq} = 1$ then by definition of $y$ we get $y^{rq} = g^{xrq} = 1$ so that $ord(g) = p-1$ divides $xr \frac{p-1}{2}$. Here $r$ and $\frac{p-1}{2}$ are odd numbers (in my edit I specified that $\frac{p-1}{2}$ was prime) so that necessarily $x$ must be even. Therefore, if we now assume that $y^{rq} = g^{xrq} = -1$, $x$ needs to be odd.

4.Compute $y^q = g^{xq}$ so that as in the first case you'll get:

$ g^{xq} = \begin{cases} 1 &\quad\text{if x is even}\\ \neq 1 &\quad\text{if x is odd} \ \end{cases} $

Let's wrap up. We can decide if $x,r$ are odd or even. This implies we can decide if $y^{rq}$ is 1 or -1 and this implies that we can decide if $(my^r)^q$ is m or -m.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.