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)?

up vote 4 down vote accepted

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

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".

  • in the second paragraph, given $x$ we can encode $y$ in a single bit. Which means $y$ is always 0 or 1? – kelalaka Dec 2 at 9:48
  • $y$ is not 0 or 1, $y$ is still a number from the field ($[0, N-1]$). For any $x$, there exist only two possible $y$. So it is unnecessary to use 255 bits for $y$, since there are only two options. And encoding "two options" can be done in one single bit, which corresponds to the sign ($+$ or $-$) of the $y$-coordinate. – Ruben De Smet Dec 3 at 8:38

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.

  • 1
    You know better; coordinates are in the underlying field [0,p-1] for F_p and equivalent to [0,2^m-1] for F_2^m. Per Hasse the curve order #E is near the underlying field order, but not the same -- and though not asked, the subgroup order n (of the generator G) used for the privatekey and signatures is less than #E if that is not prime. – dave_thompson_085 Dec 2 at 12:22

Your Answer

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.