Tag Info

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 ...
Let us assume that we have the public key $y=g^x \pmod p$ and the private key to be $x$. Computing an ElGamal signature for a message $m \in Z_p^*$ amounts to: choosing $k\in Z_p^*$ $r\equiv g^k \pmod p$ $s\equiv (m-xk)k^{-1} \pmod{p-1}$ which is equivalent to $m\equiv xr+sk \pmod{p-1}$ The signature for $m$ is the pair $(r,s)$ and verifying the ...