For elliptic-curve cryptography, does a 256-bit key imply that $x$ and $y$ are each 256-bits or 128-bits?

Question

In the wikipedia article, the claim is made that "256-bit elliptic curve public key should provide comparable security to a 3072-bit RSA public key". Since, in ECC, the public-key consists of a point $(x, y)$, when they say a "256-bit public key", does that imply both $x$ and $y$ are each 256-bits? Or that, together, they are 256 bits (meaning that each would be 128 bits)?

Answer 1

In ECC, the xxx-bit curve implies the modulus length. Also, this implies the length of each coordinate in $(x,y)$. Therefore, $x$ and $y$ are each 256-bit

Answer 2

I'll take as example Curve25519. The order of the field is $N=2^{255}-19$. This means that the coordinates of a curve point $(x,y)$ both are a number $[0, N-1]$. Encoding such a number takes $\log_2{N}=254.99...$ bits, which is almost 255 bits (practically 255 bits).

However, we are storing redundant information if we naively encode both $x$ and $y$! Our curve is symmetric over the x-axis, and the curve equation $y^2 = x^3 + 486662x^2 + x$ has only two solutions given an $x$. This means, given $x$, we can encode $y$ in a single bit (the sign of the solution to the equation).

So, in total, we can encode $x$ in 255 bits, and $y$ in a single bit, totalling 256 bits. This neatly fits 32 bytes! And this is indeed called more or less "a 256-bits curve".

Answer 3

The X and Y coordinates are numbers in the range 1 to N-1 where N is the order of the curve. That does mean that the minimum encoding of the bits may be smaller than the order of the curve, which determines the key size for Elliptic Curve crypto. The chance that they will be 128 bits is negligible though, as the there are at least $2^{127}$ more numbers that are higher than 128 bits then there are numbers of 128 bits or lower. So yeah, they are both numbers of 256 bits or a few bits and possibly even bytes less.

Quite often the coordinates they will be stored in an array of 32 bytes. This is certainly the case if they are encoded as uncompressed point: 04 <32 bytes of X> <32 bytes of Y>. However, the coordinates may also be stored as compressed point, in which case a specific Y coordinate is calculated from the X and the least significant bit of the compressed point indicator: 02 <32 bytes of X> or 03 <32 bytes of X>. This is just to indicate that the encoding of the coordinates may differ, both at rest / on disk and in memory.

Also note that sometimes curve calculations are even performed using a different coordinate system internally. Each coordinate would still have about the same size though.