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?

  • $\begingroup$ Or maybe, how many standards do exist to code the points of the elliptic curve besides x9.62? $\endgroup$ – Rotvik Knuzich Jul 12 '18 at 13:30

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.

  • $\begingroup$ @Cryptostase D'oh! Could you check the new text? Thanks! $\endgroup$ – Maarten Bodewes Jul 13 '18 at 13:19
  • $\begingroup$ So If i get it correct i should make my decision about the EC point format on the base of the length of the octet string. In my case it is X coordinate with 54 bytes so I have compressed format. Right? $\endgroup$ – Rotvik Knuzich Jul 18 '18 at 12:44
  • $\begingroup$ No, it's just the (or at least a) X-coordinate. You'd need a 02 or 03 in front of it for it to be compressed format. $\endgroup$ – Maarten Bodewes Jul 18 '18 at 13:05

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.