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?