Are all possible EC private keys valid?

Question

I usually generate a key pair using OpenSSL or Bouncy Castle.

I'm using curve secp256k1.

The 256bit private keys look fairly random.

Do all values of "private key" have a corresponding public key?

If so, can the public key be found for all arbitrary 256bit values, when treated as if they were private keys?

If not, is there a way to tell whether a 256bit value could be a private key?

Answer 1

I'll consider that you are using a 256-bit curve per ANS X9.62:2005.

Not all 256-bit bitstrings are a formally valid private key; when using big-endian conventions, these must represent a strictly positive integer less than $n$, the order of the largest prime order subgroup. Quoting the normative A.4.1 Preliminaries in the standard:

An elliptic curve key pair for given elliptic curve domain parameters is a pair $(d, Q)$, where $d$ is an integer in $[1, n – 1]$, and Q is a point on the curve such that $Q = d\,G$.

For the Koblitz curve secp256k1 of SEC 2,
$n=2^{256}-\mathtt{14551231950b75fc4402da1732fc9bebf}_{16}$.
For P-256 (also known as secp256r1),
$n=2^{256}-2^{224}+2^{192}-\mathtt{4319055258e8617b0c46353d039cdaaf}_{16}$.

The all-zero bitstring, and the bitstrings representing $n$ or more in big-endian convention, have no corresponding public key per the standard. They are in a proportion about $2^{-128}$ for secp256k1, $2^{-32}$ for P-256.

Note: we could reduce modulo $n$ bitstrings representing more than $n$, but that would be non-standard, and would still leave two bitstring (corresponding to $0$ and $n$) without a public key. $k\gets((k+n-2)\bmod(n-1))+1$ would do better, but the distribution would not be uniform unless $k$ is drawn at random from an interval much larger than $n$.

Note: This answer disregards the ASN.1 representation of a private key.

Answer 2

There are three ways to look at it:

1. The mathematics. An elliptic curve key pair is defined as $s, s \cdot G$, where $s$ is an integer, $G$ is the base point and $\cdot$ is elliptic curve point multiplication (scalar multiplication). There is no requirement for $s$ to be smaller than the order of the base point, so you could allow the private key to be however large you like.
2. The standards. I'm not sure what the IEEE standard that TLS follows says, but at least SEC 1 says that the private key should be a random number from $[1, n-1]$, where $n$ is the order of $G$. In the case of secp256k1 $n$ would be FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141, in hex.
3. The software. This part is a bit off topic here, but software may or may not follow the standard to the letter, and I could easily imagine one that allows larger values, since the scalar multiplication should work just fine.

Answer 3

On curve secp256k1 which is a finite range equal to $2^{256}-2^{32}-{2^9}-2^{8}-2^{7}-2^{6}-2^{4}-1$, the number of valid keys denoted as n would be any 256-bit value between 1 and n-1, where n is equal to 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 and thus all 256-bit values in that particular range are valid private keys which each has a distinct public-key. And while I didn't see recommendations on what the size the private key should be as per this guide from the SECG, I've noticed common libraries automatically check that the private key is smaller than n (see below examples).

Note: While g is part of the calculation together with the private key (${s \cdot G}$), I don't consider g to be part of the keypair, as it is a public universal number that doesn't change (constant), while the secret exponent s chosen from the range of n must be kept secret (and chosen in a cryptographically-secure manner, in order to be feasibly unpredictable and maintain its maximum potential security in terms of entropy bits).

Some software may contain error-checking to test whether the private key is less than the value of n and return an error if it is not.

For example, using the Python library eth-keys (available via "pip install eth-keys" on terminal) which is part of the official Github repository belonging to the Ethereum Foundation, the following error generates if you try to paste a private key larger than n by 1 (i.e. n+1 which is 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364142):

`from eth_keys import keys

>>> bytes.fromhex('fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364142') 
b'\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xfe\xba\xae\xdc\xe6\xafH\xa0;\xbf\xd2^\x8c\xd06AB'
>>> keys.PrivateKey(b'\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xfe\xba\xae\xdc\xe6\xafH\xa0;\xbf\xd2^\x8c\xd06AB').public_key

Traceback (most recent call last):
  File "<pyshell#321>", line 1, in <module>
    keys.PrivateKey(b'\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xfe\xba\xae\xdc\xe6\xafH\xa0;\xbf\xd2^\x8c\xd06AB').public_key
  File "/Library/Frameworks/Python.framework/Versions/3.7/lib/python3.7/site-packages/eth_keys/datatypes.py", line 256, in __init__
    self.public_key = self.backend.private_key_to_public_key(self)
  File "/Library/Frameworks/Python.framework/Versions/3.7/lib/python3.7/site-packages/eth_keys/backends/native/main.py", line 53, in private_key_to_public_key
    public_key_bytes = private_key_to_public_key(private_key.to_bytes())
  File "/Library/Frameworks/Python.framework/Versions/3.7/lib/python3.7/site-packages/eth_keys/backends/native/ecdsa.py", line 56, in private_key_to_public_key
    raise Exception("Invalid privkey")
Exception: Invalid privkey

Whereas, using the value n-1 is accepted as a valid private key (although no one should ever use that as it is not secure and just here as an example to generate a public-key without error):

`from eth_keys import keys
>>> bytes.fromhex('fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364140')

b'\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xfe\xba\xae\xdc\xe6\xafH\xa0;\xbf\xd2^\x8c\xd06A@'
>>> keys.PrivateKey(b'\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xfe\xba\xae\xdc\xe6\xafH\xa0;\xbf\xd2^\x8c\xd06A@').public_key

'0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798b7c52588d95c3b9aa25b0403f1eef75702e84bb7597aabe663b82f6f04ef2777'
>>>`

Using a different Python library called ecdsa (short for the elliptic curve digital signature algorithm, and available via pip install ecdsa from terminal), we arrive at a similar but more descriptive error message for the same invalid key showing the secret exponent is less than n (secexp < n) as seen below:

import ecdsa
from ecdsa import SigningKey, SECP256k1

>>> private_key=ecdsa.SigningKey.from_string(b'\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xfe\xba\xae\xdc\xe6\xafH\xa0;\xbf\xd2^\x8c\xd06AB', curve=ecdsa.SECP256k1)

Traceback (most recent call last):
  File "<pyshell#342>", line 1, in <module>
    private_key=ecdsa.SigningKey.from_string(b'\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xfe\xba\xae\xdc\xe6\xafH\xa0;\xbf\xd2^\x8c\xd06AB', curve=ecdsa.SECP256k1)
  File "/Library/Frameworks/Python.framework/Versions/3.7/lib/python3.7/site-packages/ecdsa/keys.py", line 151, in from_string
    return klass.from_secret_exponent(secexp, curve, hashfunc)
  File "/Library/Frameworks/Python.framework/Versions/3.7/lib/python3.7/site-packages/ecdsa/keys.py", line 137, in from_secret_exponent
    assert 1 <= secexp < n
AssertionError
>>> 

Whereas in the same ecdsa library with the above example valid key the same public address is returned:

```
>>> import ecdsa

>>> from ecdsa import SigningKey, SECP256k1

>>> private_key=ecdsa.SigningKey.from_string(b'\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xfe\xba\xae\xdc\xe6\xafH\xa0;\xbf\xd2^\x8c\xd06A@', curve=ecdsa.SECP256k1)

>>> public_key = private_key.get_verifying_key().to_string()

>>> print(public_key)

b"y\xbef~\xf9\xdc\xbb\xacU\xa0b\x95\xce\x87\x0b\x07\x02\x9b\xfc\xdb-\xce(\xd9Y\xf2\x81[\x16\xf8\x17\x98\xb7\xc5%\x88\xd9\\;\x9a\xa2[\x04\x03\xf1\xee\xf7W\x02\xe8K\xb7Yz\xab\xe6c\xb8/o\x04\xef'w"

>>> b"y\xbef~\xf9\xdc\xbb\xacU\xa0b\x95\xce\x87\x0b\x07\x02\x9b\xfc\xdb-\xce(\xd9Y\xf2\x81[\x16\xf8\x17\x98\xb7\xc5%\x88\xd9\\;\x9a\xa2[\x04\x03\xf1\xee\xf7W\x02\xe8K\xb7Yz\xab\xe6c\xb8/o\x04\xef'w".hex()

'79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798b7c52588d95c3b9aa25b0403f1eef75702e84bb7597aabe663b82f6f04ef2777'```

Thanks to error-checking, in the above examples two of the same invalid keys where not usable across both programs, whereas two of the same valid keys were accepted and produced matching public keys, across the same programs.