1

Context about the ECDSA nonce: Questions about generating a random number for ECDSA

Are these nonce values public or private? I understand that they are generated to be different every transaction and never reused, but unless I'm mistaken I cannot find any reference to them being a public part of a bitcoin transaction. Because of this, I don't understand how a transaction could be verified if a secret nonce was used, would this not obscure a large part of the message being signed and create un-verifiable data from someone who doesn't own the private key? Or is it that the value is in fact public, if public where are they in a transaction? If it is private how are verifications accomplished?

Michael Folkson
  • 14,337
  • 3
  • 11
  • 45
Poseidon
  • 599
  • 2
  • 20

1 Answers1

2

Are these nonce values public or private?

Yes and no.

For every signature, a new, secret, unpredictable, private nonce is generated. It is never revealed, just like the private key is never revealed. If the term "ECDSA nonce" is used without qualifications, it usually refers to this private nonce.

Then the corresponding public nonce is computed. It's effectively the same computation as is done to go from private key to public key. This public nonce is part of the signature, and necessary to verify it. This is usually not talked about in superficial descriptions of ECDSA, as all of this is just internal to the algorithm. For users of ECDSA, it suffices to think of the signature as a single black box that ought to be passed around from the signer to the verifier unmodified.

I'll try to explain how ECDSA works in a bit more detail, though you have to be aware that there isn't all that much of an "insight" that makes one understand why it is secure; ultimately all of that boils down to many people having tried to break it, and fail.

  • Let m be the message, and z = hash(m) the hash of the message.
  • Let d be the private key, a number in range [1,n-1], where n is a constant, close to 2256.
  • Let E be the function that turns private keys into public keys, which takes as input a number, and returns a "point".
    • E has the property that for any a and b, it holds that E(a) ⊕ E(b) = E(a + b), where ⊕ is an addition-like operation between points.
    • E also has the property that for any a and b, it holds that aⓧE(b) = E(ab), where ⓧ is a multiplication-like operation between numbers and points, returning a point.
    • E has the property that given E(d), it's hard to find d.
  • Let Q be the public key, Q = E(d).

ECDSA signing of message m with private key d is then roughly:

  • Generate a random nonce k.
  • Compute the public nonce R = E(k).
  • Turn R into a number, r.
  • Compute s = k-1(z + dr).
  • Return the signature (r, s).

Someone seeing the signature can't figure out k or d, because it's hard to go from R = E(k) to k, and without k, the equation s = (z + dr) / k has two unknowns (k and d). Note that this is just an intuition for why it's hard; it's not a proof.

However, it is possible to verify the signature!

  • We know s = k-1(z + dr).
  • Bring k to the other side: sk = z + dr.
  • Apply E() to both sides of the equation: E(sk) = E(z + dr).
  • Then use the multiplication and addition rules: sⓧE(k) = E(z)⊕(rⓧE(d)).
  • Using R = E(k) and Q = E(d) we get: sⓧR = E(z)⊕(rⓧQ).
  • This is an equation the verifier can check, since they have s, z, r, Q, and can find R from r.

In actual ECDSA, the ⓧ and ⊕ operations are elliptic curve point multiplication and addition, and E() is multiplication with the curve generator. Those are implementation details however, and the scheme works just as well for other kinds of mathematical structures that permit such operations, and have the property that E() is hard to invert.

Pieter Wuille
  • 98,249
  • 9
  • 183
  • 287
  • Is the private nonce **(k)** range same as the pvtkey range: `a number in range [1,n-1], where n is a constant, close to 2^256` ? We use the same function **E()** to generate the public nonce and the public ECDSA key. I am using the rust secp256k wrapper: [secp256kRust](https://docs.rs/secp256k1/latest/secp256k1/) in order to generate my public key from my private key. It expects something like the output of a sha256 hash for the private key arg, is the private random integer value sha256'd before running **E(k)** to get the public one? If not how can I run the pubkey gen fn **E()** on it? – Poseidon Jan 08 '23 at 23:26
  • There's some functions that are not demonstrated in this crate that seem to reference **RFC6979** [signEcdsaRecoverable](https://docs.rs/secp256k1/latest/secp256k1/struct.Secp256k1.html#method.sign_ecdsa_recoverable) but the docs [docs](https://docs.rs/secp256k1/latest/secp256k1/) seem to use a function (`sign_ecdsa`) that does not use the nonce? – Poseidon Jan 08 '23 at 23:49
  • My explanation above is very abstract! This is not how practical implementations work. I just wanted to give an intuition for how it works, not going into details. – Pieter Wuille Jan 09 '23 at 00:14
  • But to answer your question: the nonce k is in the same range as private keys, from 1 to n-1 inclusive (where n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141); the nonce k is usually generated using RFC6979 (which effectively computes it as a function of the private key and the message). The private key is generally not a SHA256 hash, but it can be; many Bitcoin wallets these days use BIP32 for generating private keys. – Pieter Wuille Jan 09 '23 at 00:17
  • The documentation for that crate seems outdated. None of the libsecp256k1 functions accept you passing in your own nonce; the nonce is always generated by the library, because it's so easy to screw up if you do it yourself. – Pieter Wuille Jan 09 '23 at 00:18
  • Is this function [low_r](https://docs.rs/secp256k1/latest/secp256k1/struct.Secp256k1.html#method.sign_ecdsa_low_r) using the RFC6979 a you described: a function of the private key and the message? I am sort-of confused because I assume that if there is a random number being selected upon signing, then the signature output should change upon each signature, even if the message stays the same. Using the sign_ecdsa_low_r function produces the same output every time, which means it is not adding a random value right? Or is it producing the same deterministic value based on the pvt key and message? – Poseidon Jan 09 '23 at 00:50
  • `k` in practice is not random; it is merely unpredictable to anyone who does not know the private key. RFC6979 specifies determining `k` as a function of the private key and the message, which suffices - it'll be different for every message, and unpredictable without access to the private key. – Pieter Wuille Jan 09 '23 at 01:22
  • This is very clear and helps me understand the underlying mechanism, however I'm still trying to apply this to confirm if the Rust crate is correctly using this `k` value? I understand that it would be a **different** `k` for every **different message**, but does that mean that the `k` value is **the same** for every **identical message** assuming same private key? – Poseidon Jan 09 '23 at 18:51
  • libsecp256k1, and by extension rust-secp256k1, deals with nonces internally. You don't need to do anything. Yes, without additional randomness, if the message and private key are identical, the nonce and hence the entire signature will be identical too. – Pieter Wuille Jan 09 '23 at 19:17
  • If you have further questions about the rust-secp256k1 crate, or libsecp256k1, please open another question, as that all seems unrelated to the question being discussed here. – Pieter Wuille Jan 09 '23 at 19:22