5
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 4
    $\begingroup$ 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. $\endgroup$
    – T.B
    Commented Jan 26, 2014 at 6:51

1 Answer 1

Reset to default
5
$\begingroup$

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).

Improve this answer
$\endgroup$
3
  • $\begingroup$ Doesn't finding $(e′−e)^{−1}$ s.t $x(e′−e)(e′−e)^{−1} \equiv x$ involve finding the discrete log of $x(e′−e)$. For instance if find these inverses is easy why not find $G^{-1}$ so that you can determine the secret key $x = (kG)(G^{-1})$. $\endgroup$
    – Ethan Heilman
    Commented Jan 15, 2017 at 21:05
  • 1
    $\begingroup$ @EthanHeilman Note that $(e'-e)$ can easily be inverted as it is in $\mathbb{Z}_q$. The point is that this helps us computing $x$ using the last equation above. Your equation $x=(kG)(G^{-1})$ makes no sense. Is $G$ your basepoint from an elliptic curve? What is $k$ in your equation? Anyways, let us write $G^{-1}$ as $-G$ (as you write the group additively) and what you get is: $kG-G=(k-1)G$. That doesn't help you. $\endgroup$
    – DrLecter
    Commented Jan 16, 2017 at 8:30
  • $\begingroup$ I figured out what I was doing wrong last night. I am not used to some of the quirks of EC notation. $kG$ is actually a different operation than say $kx$. Finding $G^{-1}$ would break discrete log, finding $k^{-1}$ is trivial. $\endgroup$
    – Ethan Heilman
    Commented Jan 16, 2017 at 16:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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