0

I read that the private key pk has to be any number between 1 and n, where n is almost 10^77. Since pk' s function is practically to be used as a scalar for multiplying the generator point G, why does it have to be strictly less than n?

I've thought that is because the math behind secp256k: inside a order-n group, if I multiply times x a number A (with x > n), it's equivalent to multiply the same number A times y, with y = x % n. So y will be extremely less than x, making A easier to be discovered. Is this argument correct?

7

You're right, there is no strict requirement that the private key is strictly less than the group order.

However, it is required that the resulting public key is uniform, which implies that (x % n) must be uniformly distributed between 1 and n-1 inclusive (or at least indistinguishably close to uniform). The easiest way to accomplish this is by saying that the private key must be picked directly uniformly between its bounds. However, you could just as well say you pick a private key uniformly between 1 and 1337*n-1 (except no multiple of n).

To elaborate on "indistinguishably close to uniform": specifically for the secp256k1 curve (which is used in Bitcoin's signatures), the curve order is very close to 2^256, and in general you won't ever generate a 256-bit number that is >= n. This is not the case for all elliptic curves however, and biasing private keys can actually threaten security.

  • For size, n is approximately 2^32 shy of 2^256 – Anonymous Mar 27 at 0:12
  • 1
    @Anonymous That's the field size. The group order is around 2^256 - 1.27*2^128. – Pieter Wuille Mar 27 at 0:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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