Is there a 1:1 mapping between private and public EC keys?

Question

After asking: Are all possible EC private keys valid? I learned that all 32 byte (256 bit) values greater than 0 and less than n are all valid private keys. This means that 99% of all 256 bit values are valid private keys. (This was a revelation to me.)

The public key space is 257 bits, as it includes X and the sign bit of Y.

Is there an exact 1:1 mapping between private and public keys?

Is there a way of telling whether a 257 bit value is a valid public key? (i.e. that a private key maps to it, as slightly more than half of all 257 bit values must not be valid public keys, if there is a 1:1 mapping.)

(I'm using secp256k1.)

---

Thanks for your answers.

My mental model, for an imaginary curve with n = 5, a 3 bit private key and 4 bit public key now looks like this:

private              public
0x0    +-----------> 0x0
0x1 ---+             0x1
0x2 -----------+     0x2
0x3 ---------+ |     0x3
0x4 ---+     +-|---> 0x4
0x5    |       |     0x5
0x6    |       |     0x6
0x7    |       |     0x7
       |       |     0x8
       |       +---> 0x9
       |             0xa
       |             0xb
       |             0xc
       |             0xd
       |             0xe
       +-----------> 0xf

Answer 1

Points on secp256k1 fulfill the equation:

$$ y^2=x^3+7 \pmod p$$

Your 257 bit compressed point consists of the sign* of $y$ and the value of $x$. You probably want to restrict $x$ to $0 \leq x < p$ as a canonical representation.

Since $y^2$ is obviously a square, we need to look at $x^3+7$ to see if it's a square as well:

• If $x^3+7$ is a square, then there are two points for that $x$ which only differ by the sign of $y$, which is why the compressed point contains the sign of $y$.

• If $x^3+7$ is zero, there is only one solution, since $y=-y$.

• If $x^3+7$ is a non-square, then there are no solutions.

Not counting $0$, exactly half the elements of the finite field are square and the other half is non-square. $x^3+7$ complicates matters a bit, so approximately half of the possible $x$ values are square. Hasse's theorem on elliptic curves quantifies this approximation.

You can efficiently check if a field element is square, and thus verify if it is a valid $x$ value of a point on the curve.

---

* field-elements don't actually have a sign. But since the least significant bit of non-zero values differs between $+y$ and $-y$, we can use it as sign. See Determine if a public key point y is negative or positive, odd or even? for a longer explanation.

Answer 2

Yes, there is an exact mapping between valid private and public key. The public key is essentially a representation of a point of the curve (not at infinity), obtained as the private key's representative integer times the generating point. All the points on the curve (not at infinity) are obtained for some public key, and are a valid public key.

Depending on if point compression is used or not, a public key for secp256k1 is 257-bit or 512-bit. Testing if an alleged public key is valid amounts to checking if it lies on the curve, which can be made efficiently. Without point compression, we merely need to check if the curve's equation is verified. CodesInChaos's answer beats me at explaining how to do this with point compression.

Answer 3

The answer to the question in the title is yes, provided you define "valid keys" appropriately. Since you also do not name a specific cryptosystem you had in mind, I will assume a common denominator: instances of the elliptic-curve discrete logarithm problem. This leads to the following definitions

• Public parameters: an elliptic curve $E$ and a point $G$ of order $n$. (That is, such that $n$ is the smallest positive integer such that $nG = \infty$.)
• Private key: a uniformly chosen integer $s \in \{0,\dots,n-1\}$. Any integer in that range is a valid private key.
• Public key: the point $H = sG$. Any point which is a multiple of $G$ is a valid public key.

Then the mapping between the set of private keys to the set of public keys is simply $k \mapsto kG$, I claim that this mapping is a bijection.

It is an injection, because if $kG = k'G$, then $kG-k'G = (k-k')G = \infty$. Assuming without loss of generality that $k \ge k'$, $k-k'$ is a non-negative integer smaller than $n$ such that $(k-k')G = \infty$, which implies $k-k' = 0$ since $n$ is the smallest positive integer such that $nG = \infty$.

To show that it is a surjection, we first observe that by definition a private key $H$ is a multiple of $G$, meaning there is an integer $k$ such that $H = kG$. We must show that there always exists such an integer which is a private key, i.e., an integer in $\{0,\dots,n-1\}$. Let $k = nq+r$ be the Euclidean division of $k$ by $n$. Then $H = kG = qnG+rG = q\infty+rG = rG$, so $rG = H$ and since $r \in \{0,\dots,n-1\}$ by definition of the Euclidean division, it is the private key associated with the public key $H$.