Questions about generating a random number for ECDSA

Question

One of the component of making of SECP256K1 signatures, is a random number that is later multiplied by the generator point in order to be used in further computations.

If we imagine that k - is the random nonce number and G - is the generator point, then:

What's the length of k (random number), in bytes, bits?

However, I am trying to find the answer in the Bitcoin core source code, but it's kind of hard to read and could find an answer to it there.

    /* Generate an ECDSA signature `noncefp` and `ndata` 
allows you to pass a * custom nonce function, passing `NULL` 
will use the RFC-6979 safe default. * Signing with a valid context, 
verified secret key * and the default nonce function should never fail. */
    
    return_val = secp256k1_ecdsa_sign(ctx, &sig, msg_hash, seckey, NULL, NULL);
    
    assert(return_val);

I am not sure where is k located in the code.

Also curious about other things:

Has anyone successfully replicated, mimicked the k for signatures, where k is not known?

Has anyone successfully "mined", or brute forced a k for signatures?

Is it possible to brute force the k by randomly generating random number with the function/algorithm being implemented in bitcoin core? (I suppose it is RFC-6979 or something)

Answer 1

What's the length of k (random number), in bytes, bits?

256 bits.

The number k (also called the nonce) in ECDSA must be an unpredictable value, indistinguishable from uniformly random among the set of all valid private keys. For secp256k1, that range is from 0x1 to 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364140, inclusive. Since the lower bound is so close to 0, and the upper bound is so close to 2²⁵⁶, just using a uniform 256-bit value will always be valid k, except with negligible probability.

Has anyone successfully replicated, mimicked the k for signatures, where k is not known?

If you can successfully guess the k value used in a signature, you can compute its private key. For correctly-functioning wallet software, this is hopefully impossible to third parties.

Has anyone successfully "mined", or brute forced a k for signatures?

Brute forcing will only work against badly-generated nonces that are chosen from a very small range, which is probably fairly rare. There are other misuses of nonce creation however, which have occurred in practice, and have been exploited.

One of them is reusing the same nonce value twice with the same private key, for different messages. When identified, this allows computing the private key as well. This was used to attack the PlayStation 3 security (where every signature used the same k value).

More subtle nonce crimes, and a fairly advanced attack against them, is described in this paper.

Is it possible to brute force the k by randomly generating random number with the function/algorithm being implemented in bitcoin core? (I suppose it is RFC-6979 or something)

RFC6979 describes a derandomized nonce generation algorithm. Somewhat simplified, what it suggests is akin to using Hash(private_key || message) as nonce. This has the property that it is unpredictable to third parties (since they don't know the private key), and will never result in reuse for distinct messages under the same private key.

When nonces are generated this way, and you don't know the private key, trying to brute force is hopeless. Computing the private key from the public key using an algorithm like Pollard's Rho, and then solving for the nonce, would be many orders of magnitude faster than trying to brute force the nonce directly.