Using the terminology of the ECDSA wikipedia page, ECDSA (and DSA) signatures re

Question

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?

Explanation / Answer

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

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.