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?

  • $\begingroup$ you're looking for the corresponding verification procedures / equations right? $\endgroup$ – SEJPM Jul 28 '15 at 21:55
  • $\begingroup$ yes that's right $\endgroup$ – Legolas Jul 28 '15 at 22:41
  • $\begingroup$ any ideas to solve it? $\endgroup$ – Legolas Jul 29 '15 at 8:08
  • $\begingroup$ concerning 2): maybe: $r^{h(m)}\equiv g^s * (y^{r})^{-1} \pmod p$ $\endgroup$ – SEJPM Jul 29 '15 at 9:59
  • 1
    $\begingroup$ 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$" $\endgroup$ – SEJPM Jul 29 '15 at 10:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.