10
$\begingroup$

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?

$\endgroup$
10
$\begingroup$

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 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 then $n$, but that would be non-standard, and would still leave two bitstrings (corresponding to $0$ and $n$) without a public key.

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

$\endgroup$
  • 1
    $\begingroup$ You are confusing $p$ with $n$ (order of the largest prime order subgroup). All valid private keys are in $\mathbb{ Z}_n^*$. $\endgroup$ – Ruggero Nov 3 '15 at 9:46
  • $\begingroup$ Sorry, I should have said that I'm using curve secp256k1. $\endgroup$ – Thomas Von Panom Nov 3 '15 at 10:07
  • $\begingroup$ So would you say that 1 is a valid key? Is it a good key? What would be the minimal number that you would consider a "good" key? I'm asking because our key derivation function can (theoretically) produce those keys. $\endgroup$ – Fozi Sep 11 '17 at 15:22
  • $\begingroup$ @Fozi: The question (as I read it) is not about "good" key, but about "valid" key. New questions in comment are frowned at. What would be the minimal number that you would consider a "good" key? is an interesting question; I can't immediately find a duplicate; why not ask it as an independent question after double-check? The variant if we put an alert threshold on low key, what are odds of false positive as a function of number of uses, key width and type? has a quantitative answer, and it might help answer your question. $\endgroup$ – fgrieu Sep 11 '17 at 15:30
  • $\begingroup$ @Fozi: 1 is neither better or worse than 0x3b6ddba1f4b325cee4505084bc507d2019e86539f8d4be027004b69f9aa0bc74, as long as they have equal probability of occurring, namely $1/n$ or about ${\sim}1/2^{256}$, so that the adversary has no better probability of success by guessing one or the other first. Note that the probability of getting either one of them individually is negligible, just like any other possible secret scalar. $\endgroup$ – Squeamish Ossifrage Sep 11 '17 at 18:28
8
$\begingroup$

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.
$\endgroup$
  • 2
    $\begingroup$ Your $n$ seems to be that of secp256k1, which is what the question is turns out to be about; but that's not P-256, wich is secp256r1. Oh man these numbers are confusing. $\endgroup$ – fgrieu Nov 3 '15 at 10:27
  • $\begingroup$ @fgrieu, yeah, just noticed. I had the one for P-256 first, but changed when I saw the comment. $\endgroup$ – otus Nov 3 '15 at 10:28
1
$\begingroup$

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.

$\endgroup$

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.