Is there a 1:1 mapping between private and public EC keys? 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    +-----------&gt; 0x0
0x1 ---+             0x1
0x2 -----------+     0x2
0x3 ---------+ |     0x3
0x4 ---+     +-|---&gt; 0x4
0x5    |       |     0x5
0x6    |       |     0x6
0x7    |       |     0x7
       |       |     0x8
       |       +---&gt; 0x9
       |             0xa
       |             0xb
       |             0xc
       |             0xd
       |             0xe
       +-----------&gt; 0xf
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 &lt; 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.