11

Generating random number k in elliptic curve is crucial and in any transactions signature in Bitcoin, random number k is required to compute a point k*G. If this k is chosen not randomly, it instantly leaks the private key.
Therefore, they came up with an idea of deterministic generation of ECDSA which is described in RFC6979. Basically they concatenate the private key with the hashed message and use an HMAC function and generate a pseudo random k.
This method seems simple and easy.

  • Does it introduce any overhead?
  • If yes, is this overhead negligible?

Or generally is there any inefficiencies or problem with this method and why do we still see non-deterministic implementation of ECDSA?

Improve this question

1 Answer 1

Reset to default
11

Not any serious efficiency concerns. Signing is done fairly infrequently for any particular client (only a few signatures per transaction usually). While possible that the signing might take slightly longer to generate the k value, it would not be noticeable, especially considering how infrequently it is used by any one particular client. It's the verification of all the signatures that is the CPU bottleneck for block verification in bitcoin, because all full nodes have to verify the signatures of all the transactions on the network, and this takes the same time regardless of how the k parameter was chosen.

Gregory Maxwell made a comment about the use of deterministic k values here:

The primary arguments in most spaces against derandomizing DSA are FIPS conformance (irrelevant for us) and reasonable concerns about the risks of using a (less) reviewed cryptographic construct. With widespread motion towards derandomized DSA this latter concern is less of an issue.

The new libsecp256k1 library by Pieter Wuille actually uses deterministic generation of k.

Also note that one of the key benefits of using this construction is that you need not worry about a weakness in your PRNG being exploited in the signing process. For example, signing different pieces of data with the same k value instantly leaks your private key. A similar attack can also be exploited if the PRNG is weak enough to determine the relationship between different k values used when signing the same piece of data. Since the k is deterministically generated from the data you are signing (and the private key), these concerns about the PRNG are no longer as relevant, as you will always produce the same signature for the same piece of data. This also makes writing ECDSA unit tests easier.

Improve this answer
14
  • As you mentioned the verification process is the same and adding couple of extra HMAC computation to the client side doesn't really affect the signature process.
    – abeikverdi
    Feb 20, 2015 at 6:27
  • Signing the same data twice with different 'k' values is safe.
    – amaclin
    Feb 20, 2015 at 8:03
  • 4
    @adaclin Only if an attacker cannot determine the relation between the two k values used. If for example one k is known to be equal to the other plus one, it instantly leaks your private key.
    – Pieter Wuille
    Feb 20, 2015 at 8:51
  • 1
    @PieterWuille Thanks, I have updated my answer. I had confused the different-ks-same-data attack with the different-data-same-ks attack mentioned here.
    – morsecoder
    Feb 20, 2015 at 13:07
  • @abeikverdi Actually, generating a nonce using RFC6979 with SHA256 requires 22 invocations of the SHA256 compression function, which takes in the order of 10% of the whole signing time.
    – Pieter Wuille
    Feb 20, 2015 at 19:52

Your Answer

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

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