<p>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 <code>k</code> 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 <code>k</code> parameter was chosen. </p>

<p>Gregory Maxwell made a comment about the use of deterministic <code>k</code> values <a href="http://permalink.gmane.org/gmane.comp.bitcoin.devel/2734" rel="noreferrer">here</a>:</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>The new <a href="https://github.com/bitcoin/secp256k1" rel="noreferrer">libsecp256k1</a> library by Pieter Wuille actually uses deterministic generation of <code>k</code>.</p>

<p>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 <code>k</code> value <a href="https://bitcoin.stackexchange.com/questions/35848/recovering-private-key-when-someone-uses-the-same-k-twice-in-ecdsa-signatures">instantly leaks your private key</a>. A similar attack can also be exploited if the PRNG is weak enough to determine the relationship between different <code>k</code> values used when signing the same piece of data. Since the <code>k</code> 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. </p>

CC BY-SA 3.0
2015-02-20T06:27:16.537Z
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
CC BY-SA 3.0
2015-02-20T08:03:54.533Z
Signing the same data twice with different 'k' values is safe.
amaclin
CC BY-SA 3.0
2015-02-20T08:51:15.007Z
@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
CC BY-SA 3.0
2015-02-20T13:07:08.903Z
@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](http://bitcoin.stackexchange.com/questions/35848/recovering-private-key-when-someone-uses-the-same-k-twice-in-ecdsa-signatures).
morsecoder
CC BY-SA 3.0
2015-02-20T19:52:21.367Z
@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
CC BY-SA 3.0
2015-02-21T02:41:40.727Z
@PieterWuille Can you illuminate me? Dont we just concatenate the private key and the hashed message as the HMAC nonce?
abeikverdi
CC BY-SA 3.0
2015-02-21T08:29:05.557Z
@abeikverdi Read RFC6979 and try to implement it, you'll see.
Pieter Wuille
CC BY-SA 3.0
2015-02-22T06:19:12.470Z
@PieterWuille I have already read RFC6979. Never tried to implement that though. Is this 10% overhead time that you are referring to, you personal experience? or its scientific?
abeikverdi
CC BY-SA 3.0
2015-02-22T14:42:27.803Z
I benchmarked it. Can't get more scientific than that.
Pieter Wuille
CC BY-SA 3.0
2015-02-22T15:51:12.773Z
@StephenM347 Wouldn't this RFC 6979 generates the same k twice? HMAC_DBGA(private key d || H(m)) generates the same k for the same hashed message since the private key is constant. Doesn't it? Isn't that a problem?
abeikverdi
CC BY-SA 3.0
2015-02-22T17:04:35.400Z
@abeikverdi, Not really, that's exactly why it's useful is because it produces the same signature for the same data. It only uses the same k twice for the same message. It's only when you sign different data with the same k value that it leaks your private key. Using the same k for the same data doesn't give any new information.
morsecoder
CC BY-SA 3.0
2015-02-22T17:11:03.130Z
@StephenM347 the data that you are referring which is the hashed message is the hash of transaction?
abeikverdi
CC BY-SA 3.0
2015-02-22T17:19:53.787Z
@abeikverdi, essentially, yes, the data being signed is a hash of the transaction which has been cleared of all inputs (you don't sign other signatures). There's one more little nuance, that the previous scriptPubKey of the output being spent is inserted in the scriptSig before double SHA256 hashing.
morsecoder
CC BY-SA 3.0
2015-02-22T17:27:00.960Z
@StephenM347 Thanks a lot! I totally got it now!
abeikverdi
CC BY-SA 3.0
2015-02-20T05:13:49.750Z
2015-02-20T17:06:25.103Z
2017-04-13T12:47:34.187Z
morsecoder
<p>Generating random number <code>k</code> in elliptic curve is crucial and in any transactions signature in Bitcoin, random number <code>k</code> is required to compute a point <code>k*G</code>. If this <code>k</code> is chosen not randomly, it instantly leaks the private key. <br/>
Therefore, they came up with an idea of deterministic generation of ECDSA which is described in <a href="https://www.rfc-editor.org/rfc/rfc6979" rel="nofollow noreferrer">RFC6979</a>. Basically they concatenate the private key with the hashed message and use an HMAC function and generate a pseudo random <code>k</code>. <br/>
This method seems simple and easy.</p>
<ul>
<li>Does it introduce any overhead?</li>
<li>If yes, is this overhead negligible?</li>
</ul>
<p>Or generally is there any inefficiencies or problem with this method and why do we still see non-deterministic implementation of ECDSA?</p>

<signature><cryptography><ecdsa>
Problems with deterministic ECDSA based on RFC6979 in Bitcoin
abeikverdi
# Problems with deterministic ECDSA based on RFC6979 in Bitcoin

(Asked by: username_0 on 2015-02-19)

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](https://www.rfc-editor.org/rfc/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?

**Tags:** signature, cryptography, ecdsa


---

## 1 answers

### Answer by username_1 on 2015-02-20. Score: 11 | Accepted answer

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](http://permalink.gmane.org/gmane.comp.bitcoin.devel/2734):

> 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](https://github.com/bitcoin/secp256k1) library by username_3 username_3 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](https://bitcoin.stackexchange.com/questions/35848/recovering-private-key-when-someone-uses-the-same-k-twice-in-ecdsa-signatures). 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.

> **Comments:**
> **username_0**: 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.  
> **username_2**: Signing the same data twice with different 'k' values is safe.  
> **username_3**: @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.  
> **username_1**: @username_3 Thanks, I have updated my answer. I had confused the different-ks-same-data attack with the different-data-same-ks attack mentioned [here](http://bitcoin.stackexchange.com/questions/35848/recovering-private-key-when-someone-uses-the-same-k-twice-in-ecdsa-signatures).  
> **username_3**: @username_0 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.  
> **username_0**: @username_3 Can you illuminate me? Dont we just concatenate the private key and the hashed message as the HMAC nonce?  
> **username_3**: @username_0 Read RFC6979 and try to implement it, you'll see.  
> **username_0**: @username_3 I have already read RFC6979. Never tried to implement that though. Is this 10% overhead time that you are referring to, you personal experience? or its scientific?  
> **username_3**: I benchmarked it. Can't get more scientific than that.  
> **username_0**: @StephenM347 Wouldn't this RFC 6979 generates the same k twice? HMAC_DBGA(private key d || H(m)) generates the same k for the same hashed message since the private key is constant. Doesn't it? Isn't that a problem?  
> **username_1**: @username_0, Not really, that's exactly why it's useful is because it produces the same signature for the same data. It only uses the same k twice for the same message. It's only when you sign different data with the same k value that it leaks your private key. Using the same k for the same data doesn't give any new information.  
> **username_0**: @StephenM347 the data that you are referring which is the hashed message is the hash of transaction?  
> **username_1**: @username_0, essentially, yes, the data being signed is a hash of the transaction which has been cleared of all inputs (you don't sign other signatures). There's one more little nuance, that the previous scriptPubKey of the output being spent is inserted in the scriptSig before double SHA256 hashing.  
> **username_0**: @StephenM347 Thanks a lot! I totally got it now!  

---

