Representation of generated Public Key

[sergio-domingues]

Hello, I'm using sect163k1 elliptic curve and in order to generate the public key I'm executing the following code:

int ecdh_generate_keys(uint8_t* public, uint8_t* private);

Is the result following a standard specification (compressed / uncompressed / hybrid) format defined in SEC1v2?

Thanks in advance!

[kokke]

Hi @sergio-domingues and thanks for your interest :)

I am not sure I understand your question. The keys are generated in a standard fashion.

From the comments in the top of ecdh_example.c.

1. Alice picks a (secret) random natural number 'a', calculates P = a * G and sends P to Bob. 'a' is Alice's private key. 'P' is Alice's public key.

The coordinates are represented as uncompressed raw points, which to my knowledge is a standard representation.

Does that answer your question?

[sergio-domingues]

According to the standards defined in that NIST specification, shouldn't the uncompressed format begin with 0x04? I know If it's better for my needs I can just add that initial byte, just wanted to clarify what standard is being used. Thanks again :)

[kokke]

When exchanging points etc. using bit-strings, yes there is a convention to add 04 if uncompressed, 02 or 03 if compressed.

From RFC 5480:

  o The first octet of the OCTET STRING indicates whether the key is
    compressed or uncompressed.  The uncompressed form is indicated
    by 0x04 and the compressed form is indicated by either 0x02 or
    0x03 (see 2.3.3 in [SEC1]).  The public key MUST be rejected if
    any other value is included in the first octet.

I am by no way an expert on this standard, but I interpreted that paragraph to only regard parameter exchanges in textual format (bit-string / octet string). I think I read some of the same in 2.3.3 in the SEC-document you linked to.

EDIT:

An aside: The reason I am not compressing the points, is that I think point-compression is still a patent-encumbered technology.

[sergio-domingues]

Ok, it makes sense. Thank you for the clarification!

[kokke]

I think it mostly means something if you exchange curve parameters using a standard format like X.509 or something similar (ASN.1?).

I will close this issue, but feel free to continue the discussion if you have further questions or comments :)

[sergio-domingues]

Hi again @kokke, I also noticed that a 3 byte (0x00) is being added after X and Y, is it supposed to work like a separator?

[kokke]

Hi @sergio-domingues - I'm not sure what you are referring to, can you give me a link to some code or copy/paste the parts you are referring to ? :)

[sergio-domingues]

Testing for a K=1 with curves sec163k1, sect233k1 adds bytes between coordinates (3 bytes and 2 bytes respectively). For example for the k233, when generating public key:

[kokke]

That is just a coincidence. An artifact of how the numbers are placed in memory.

For the case sect163k1, think of the key as two 163 bits numbers put next to each other (the x and y coordinate).

We allocate in 8 bit chunks (8 bit pr byte), so that leaves at least 5 unused bits after the first coordinate. Unless the y coordinate uses the MSB, every bit unused, will leave an extra 0-bit between the numbers.

It is not unthinkable that there could be 20-25 clear bits between the numbers.

[sergio-domingues]

Yeah I understand that the public key is represented by the concatenation of x and y.

Following the logic on your reply the unused bytes will be in the 0-30 byte range (233 bits), as you can see in the image every time I generate a public key for that curve a 2 byte (0x00) is added between x and y in the [30,31] indexes, making it look like: [x-coord][0x0][0x0][y-coord] and the y-coord is missing the 2 bytes because of that spacing.

Could you pelase execute the public key computation for that curve in your side in order to verify this issue?