The compression of the elliptic curve point coordinates

Question

Some time ago I faced the problem of the unexpected format compression of the points on elliptic curve. I used ECDH procedure with a third party service on the base of the $\mathbb({F}_{2^m})$ curve in the polynomial $(m,k_3,k_2,k_1) = (431,5,3,1)$ representation.

As response I received a compressed point in the following format:

03 39000436 + "108 other digits"  

My confusion was that I expected to see the compression format corresponding to X9.62 standard: Public Key Cryptography For The Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA)

I expected to see 03 + "108 digits". Here 03 is a sign of the compression format and 108 is the size of the $X$ and $Y$ coordinates (54 bytes each) for $(431,5,3,1)$ curve.

Could you please help me to understand what does this 39000436 mean?

Answer 1

In this case the 03 is not a sign of the compression format. It's a DER encoding of an ASN.1 BIT STRING, with a length of 39 hex (57 bytes). 00 means that all the bits in the remaining 56 bytes are used; this is rather common. 00 itself is not part of the encoded value.

Within this BIT STRING there is a value starting with 04 36. Here 04 is not an uncompressed point, but it is an ASN.1 OCTET STRING. Again, 36 is the length, in this case 54 bytes (the previous 57 bytes with an additional overhead of 00 04 36).

---

A BIT STRING is often used to be able to use any key or data format within it. The OCTET STRING is probably used to wrap the coordinate(s) within it. Because the BIT STRING doesn't indicate that there is an ASN.1 encoding within it (it contains a primitive value rather than a constructed value), decoding is a two step process. In this case the OCTET STRING is spurious, but it may be different for other structures that consist of a SEQUENCE of elements.

---

The 54 bytes of the value of the OCTET STRING are the minimum number of bytes to store a single 431-bit coordinate: $\big\lceil 431 / 8 \big\rceil = 54$. This could be the X coordinate that is the result of an ECDH calculation. If it was a point representing a public key you'd expect a compressed or uncompressed point, which would take one byte in addition to the 54 bytes given.