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-x^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?
Simply $r = s^{-1}(y - x^y) \pmod{p-1}$. Note that, with overwhelming probability, $s$ is invertible modulo $p-1$ (just as $r$ is).