Recovering the random number r

Question

For a padded message, M, using the El Gamal encryption schema, how can we determine the random number $r$, when we are given $p$, the prime number, $g$ which is the primitive root of $p$, $b$ and $x$ which is the private key.

So the public key is $(g,b,p)$ where $b=g^x$ $mod$ $p$.

To encrypt, we compute: $y_1 = g^r$ mod $p$ and $y_2 = M*b^r$ mod $p$. Then the encrypted version of $M$ is the pair $(y_1,y_2).$

I also know $s=(M-a^y)(r^{-1})$ mod $p-1$. Now we know the El Gamal signature on $M$ which is $(y,s)$.

So in conclusion, I know $(g,b,p,x,y,s)$ where $y$ is the message. I want to know how to determine $r$ from all this information. How can I do that?

Answer 1

At first glance

$r = s^{-1} (M - a^y) \bmod p-1$

would appear to be what you're looking for.

If $s$ isn't invertable modulo $p-1$, then you can work around this by working with the factors of $p-1$; in this case, $p-1 = uv$ where $s$ is a multiple of $u$ and $s$ is relatively prime to $v$.

So, we can solve:

$r_v = s^{-1} (M - a^y) \bmod v$

and so we have:

$r = r_v + kv$

for some integer $k$; if you know $y_1 = g^r \bmod p$, then you can recover the correct $k$ in $O( \sqrt{u})$ time.