I need some help to demonstrate how to forge signatures in the Schnorr scheme if I eliminate the random string $r=g^k$ used in the hash – using $H(M)$ instead of $H(M||r)$.

How would one be able to forge signatures in the Schnorr scheme if $r=g^k$ is eliminated?

  • 2
    $\begingroup$ What becomes signature verification if $r$ is removed? A pair $(s,e)$ for any $s$ and $e=H(M)$ is a valid signature on message $M$. $\endgroup$ – user94293 May 29 '16 at 3:07

I suppose that you address the question to a signature scheme, in which the signature is still the pair $(r,s)$ with $r=g^k \bmod p$ as the exponentiated nonce and $$s = H(m)\cdot x + k \mod q,$$ where $h = H(m)$ depends solely on the message $m$ being signed. Here $x$ denotes the secret signing key and $q$ the order of the generator $g$ of a prime subgroup of $\mathbb Z_p^*$. Creating a valid pair $(r,s)$ for an arbitrary message is done follows:

  • choose any value for $s$,
  • determine $r$ directly by the verification equation $$g^s = y^h \cdot r \mod p,$$ where $y=g^x$ is the public verification key, and not via its logarithm $k$. This yields $r = g^s\cdot y^{-h}\bmod p$.

This attack is the same as for Schnorr's identification protocol once one knows the verifier's challenge in advance, and shows (at least to me) how careful one has to be with cryptographic protocols: naivly, one is led to think it is impossible to forge a signature without knowing the components of the linear functional, i.e. the coefficients $x$ and $k$.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.