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?

up vote 8 down vote accepted

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.

  • You are confusing $p$ with $n$ (order of the largest prime order subgroup). All valid private keys are in $\mathbb{ Z}_n^*$. – Ruggero Nov 3 '15 at 9:46
  • Sorry, I should have said that I'm using curve secp256k1. – Thomas Von Panom Nov 3 '15 at 10:07
  • 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. – Fozi Sep 11 '17 at 15:22
  • @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. – fgrieu Sep 11 '17 at 15:30
  • @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. – Squeamish Ossifrage Sep 11 '17 at 18:28

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.
  • 2
    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. – fgrieu Nov 3 '15 at 10:27
  • @fgrieu, yeah, just noticed. I had the one for P-256 first, but changed when I saw the comment. – otus Nov 3 '15 at 10:28

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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