ECC Public Key length differs from bit representation

Question

A 256 Bit ECC key-pair (256 Bit is supposed to be the length of the public key) generated with OpenSSL using this command from the manual:

openssl ecparam -name secp256k1 -genkey -noout -out key.pem

and the corresponding public key with:

openssl ec -in key.pem -out public.pem -pubout

The public.pem file contains a base64 encoded string, for example:

-----BEGIN PUBLIC KEY-----
MFYwEAYHKoZIzj0CAQYFK4EEAAoDQgAEdPzYnkmkF8oy+R+FcByIbyPBE2l6HHOJ
mfZWtAaFZyIx9WPSzZTdyjmWlFqLvwaFlHu9OX9e7Snslfw7nneDIw==
-----END PUBLIC KEY-----

The public key consists of a point(x and y coordinate) and the curve used.

When decoded, each coordinate is a 256 bit-long number and the key itself is by no means 256 Bit long. Is this correct?

I'm aiming for the shortest possible public key length while preserving secuirty in my application and i don't understand why a suggested "256 bit public key" is more then double the size in reality.

Answer 1

An elliptic curve is defined over a finite field of size q for some integer q. Each curve element is a point and has two coordinates X and Y, which are curve elements.

The "size" of the curve, which is the important parameter for its cryptographic strength, is close to q. It can be shown that the total curve size n is such that |n - (q + 1)| ≤ 2*sqrt(q) (that's Hasse's theorem). So if you want a "256-bit curve" you will need a 256-bit field.

However, a public key is a curve point, represented by two coordinates. So you end up with two 256-bit values, hence the public key size. Moreover, standard public key formats also include some parameters which specify that the public key is of the "elliptic curve" type, and reference the actual curve from which the point is part. We still call it a "256-bit public key" because that number relates to the cryptographic strength of the key, not to the actual encoded size.

---

If we dig a bit further, we may note that all curve points must, by definition, fulfil the curve equation, usually Y² = X³ + aX + b for two constants a and b (these constants actually define the curve). It follows that, if you know X, then you can compute Y² by using the curve equation. Since we are working in a field, an element has at most two square roots in that field, so from Y² you can get Y and -Y. This allows point compression: a representation of a point (X,Y) as only X, plus one bit of Y (which is enough to distinguish between Y and -Y). With point compression, a 256-bit EC public key fits in 257 bits (assuming that the information about the used curve is transmitted through some other way).

Unfortunately, point compression, while nifty, appears to have been patented at some point, so a lot of existing implementations don't support it, even though it would be "standard" (it is described in ANS X9.62-2005). From the "RFC" point of view, support of point compression is optional. Therefore, using it incurs a risk of loss of interoperability.

(I don't know if OpenSSL supports point compression. It should be tested.)