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?

Improve this question

1 Answer 1

Reset to default
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.

Improve this answer
10
  • 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 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 8 at 23:26
  • There's some functions that are not demonstrated in this crate that seem to reference RFC6979 signEcdsaRecoverable but the docs docs seem to use a function (sign_ecdsa) that does not use the nonce?
    – Poseidon
    Jan 8 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 9 at 0: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 9 at 0: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 9 at 0:18

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.