# ElGamal signatures systems

Let $p$ prime number $q/p-1$ prime and $g\in (Z/pZ)^*$ element of order $q$.Also $a\in \{1,...,q-1\}$ the private key and $y\equiv g^a\pmod p$ the correspoding public key.For each of the following systems ElGamal give the verification(authentication) algorithm of signature $(r,s)$

1. $r\equiv g^k\pmod p$ ,$s\equiv k^{-1}(h(m)+2ar^2)\pmod q$
2. $r\equiv g^k\pmod p$,$s\equiv kh(m)+ar\pmod q$
3. $r\equiv g^{-k}\pmod p$,$s\equiv a^{-1}(kh(m)+r)\pmod q$

Can anyone give me any hints to solve this problem?

• you're looking for the corresponding verification procedures / equations right? – SEJPM Jul 28 '15 at 21:55
• yes that's right – Legolas Jul 28 '15 at 22:41
• any ideas to solve it? – Legolas Jul 29 '15 at 8:08
• concerning 2): maybe: $r^{h(m)}\equiv g^s * (y^{r})^{-1} \pmod p$ – SEJPM Jul 29 '15 at 9:59
• The general thought process should be: "Find some equation which is true if $s$ is generated correctly and that involves $h(m),r,s,y$" – SEJPM Jul 29 '15 at 10:22