Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I was reading about Schnorr's 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 is also very small.

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

share|improve this question
3  
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. –  T.B Jan 26 at 6:51

1 Answer 1

A small message space is no problem and I do not really know what you mean by "signature length is very small".

However, 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. Otherwise anyone who gets two signatures of you computed with same randomness for different messages can extract your private signing key with overwhelming probability.

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

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

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$, and since $(e'-e)^{-1}$ thus always exists, 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 such that these "randomness collisions" do not happen.

All ElGamal type signatures (such as DSA/ECDSA) suffer from the same problem when re-using the randomness $k$ and actually this is what doomed Sony's private key back in 2010/2011 (i.e., they re-used $k$ over different signatures).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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