# Whether changing the random number selected for each message increase security in Schnorr scheme?

I was reading about Schnorr scheme and in that for signing the signer generates a random number and continues with his operation. I am trying to implement this in a scenario where the signature length is small and the number of possible messages are also very less.

Whether generating a random number and signing, for each message is a good option in this case?

-
well, the reason is the same with ElGamal, if you use same random number to sign two messages, then the adversary can recovery the secret key which is used for signing. –  Alex Jan 26 at 6:51

It is not only a good idea to choose independent and fresh randomness for every signature, it is (as Alex mentioned in his comment) necessary, as otherwise anyone who gets two signatures of you computed with same randomness for different messages can extract the private signing key with overwhelming probability.

I'm using the notation from the Wikipedia article of Schnorr signatures.

Assume you have two signatures $(r,s)$ and $(r',s')$ for two messages $M\neq M'$. Using the same randomness means that $r=r'$ (since $k=k'$) and since $M\neq M'$ we know in practice that $s\neq s'$ (since we assume $H$ to be a secure cryptographic hash function).

Now, we know that $s\equiv k-xe \pmod q$ and $s'\equiv k-xe' \pmod q$.

Consequently, since $k$ (the randomness) is identical for both signatures, we have that

$s+xe \equiv s'+xe' \pmod q$ and thus $s-s' \equiv x(e'-e) \pmod q$ and thus

$x\equiv (s-s')(e'-e)^{-1} \pmod q$.

Ignoring the very unlikely cases where $s-s'$ and $e'-e$ are $0$ (if you habe a hash collision), the attacker can extract $x$, which is the private key.

So, when using Schnorr's signature, it is essential, that the value $k$ is chosen independently and randomly for every signature.

Just as a side note, Schnorr signature can essentially be viewed as a non-interactive version of a honest-verifier proof of knowledge of a discrete logarithm, obtained by applying the Fiat-Shamir heuristic (including the first message (commitment) and the message $M$ in the hash function). The attack described above is exactly the efficient knowledge extractor $\cal E$ for the witness (the secret) of the proof of knowledge (as required by the special soundness property).

-