# Can ECDSA signatures be safely made “deterministic”?

Using the terminology of the ECDSA wikipedia page, ECDSA (and DSA) signatures require a random k value for each signature which ensures that the signature is different each time even if the message and key are the same. For some applications a "constant" signature may be desirable.

It seems to me that there would be no harm in implementing "constant" ECDSA by setting the "random" k value to be the x-coordinate of the message hash z (converted to a curve point in some arbitrary fashion) multiplied by the private key. Obviously the method translates back to DSA.

This scheme might be useful for implementations which do not have access to a source of random numbers.

Are there any problems with this? Is there a faster way of generating a suitable k than a point multiplication?

ByteCoin

-
I don't see why you want to include the private key in the generation of $k$. –  Paŭlo Ebermann Sep 29 '11 at 10:33
@Paulo: if you guess $k$ then you can recompute the private key from the signature. $k$ MUST be hidden from any attacker; hence, its generation must include some secret data. The private key is some secret data. –  Thomas Pornin Sep 29 '11 at 12:28
@ThomasPornin Ah, thanks. Looks like I mixed $k$ and $r$. –  Paŭlo Ebermann Sep 29 '11 at 12:38
Related blog entry: Surviving a bad RNG Scroll down to ECDSA signatures –  CodesInChaos Jul 22 '12 at 15:56

There is a draft RFC which describes a way to implement deterministic (EC)DSA (with test vectors). In this draft, both $h(m)$ (the hash of the message) and $x$ are used as input to a deterministic PRNG which uses HMAC (that's HMAC-DRBG as specified by NIST); the PRNG output is used to yield $k$. I am not sure your simple multiplication with $x$ would be enough to guarantee security; ideally, a random oracle should be used, and HMAC-DRBG is the closest to a practical random oracle that I could find.

Note that $k$ must be generated uniformly in the $[1, q-1]$ range (where $q$ is the subgroup order). Any information on $k$, even partial (such as: values between $1$ and $2^{160}-q$ are twice as probable than values between $2^{160}-q$ and $q$), can be exploited by the attacker.

(There will be a new draft version with a few text changes in the draft -- but the same test vectors -- as soon as I find the time to do it.)

Edit: the RFC is now published as RFC 6979.

-
What a coincidence that you're the author of the relevant RFC! It's "expired" - what happened to it? You make a good point about wanting not to have to worry about detecting bad quality random numbers. –  ByteCoin Sep 29 '11 at 22:53
Can you give a reference for a technique which would exploit such weak partial information on k? I think I recall seeing an attack which required several bits fixed. –  ByteCoin Sep 29 '11 at 23:05
@ByteCoin: drafts expire after 6 months -- that's why they are called drafts. I submitted it as "independent submission" (i.e. not from an IETF committee) and got a few remarks; the new draft will be up as soon as I spend a few hours on it. As for the technique with partial information on $k$, it was found by Bleichenbacher; in this article, Serge Vaudenay says that it was a "private communication", hence not really published anywhere. –  Thomas Pornin Sep 30 '11 at 0:44

In their 1998 SAC paper, M'Raihi et al showed how to use hash functions to turn Schnorr signatures (quite similar to (EC)DSA) deterministic, and proved that if the original signature scheme (with randomness) is secure, so is the deterministic one.

Bernstein et al's recent EdDSA signature scheme uses the same technique to avoid randomness.

-
Thanks for the references. The EdDSA paper refers to setting k as the hash of the message and private key which for many applications would be faster and superior to my original proposal. –  ByteCoin Sep 29 '11 at 12:52
This doesn't work. If a hash collision is found then the two messages have the same hash $z$. In my scheme, this results in the same $k$ and hence the signature is identical and hence the secret key is not revealed. –  ByteCoin Jan 23 '12 at 14:45