Raw curve25519 public key points

Question

I'm trying to understand curve25519, and ECC public points.

I'm playing with Minisign, to better understand the fundamentals of ECC.

Minisign uses curve25519 and outputs public keys as base64 encoded strings in the following format:

base64(<signature_algorithm> || <key_id> || <public_key>)

signature_algorithm: Ed

key_id: 8 random bytes

public_key: Ed25519 public key

As an example, my public key is:

RWRxmbgCt+0wPvdZ0alM7J46oqsOBTtud4E8zRznnCT0q0u7X971eWUN

Decoding this Base64 to Hex we get:

45 64 71 99 b8 02 b7 ed 30 3e f7 59 d1 a9 4c ec 9e 3a a2 ab 0e 05 3b 6e 77 81 3c cd 1c e7 9c 24 f4 ab 4b bb 5f de f5 79 65 0d

This makes sense... 45 64 == Ed

Next eight random bytes... 71 99 b8 02 b7 ed 30 3e

Then, if I'm correct, the public key... f7 59 d1 a9 4c ec 9e 3a a2 ab 0e 05 3b 6e 77 81 3c cd 1c e7 9c 24 f4 ab 4b bb 5f de f5 79 65 0d

Now this is what I'm trying to understand!

The public key is the right size (32 bytes/256 bits), however isn't it supposed to start with 04?

Also is it possible to take the public key and break it into it's X,Y co-ordinates as integers?

Is 16 bytes enough to represent a curve25519 X or Y component?

Thanks for the help.

Answer 1

The leading 04 byte is specified by the SEC standard (which is based on the ANSI X9.62 standard). It indicates that the public key point is not compressed. If the key is compressed, it uses 02 or 03 as leading byte depending on the lower bit of the y coordinate.

EdDSA public keys do not use this byte for two reasons:

• It always uses compressed points; there is one additional bit depending on the y coordinate, but it's bitwise concatenated directly to the x coordinate (it's not the lower bit of y like in SEC, but on whether x or p-x is larger). Since the x coordinate in Ed25519 has 255 bits, with the additional bit it fits nicely in 256 bits.
• It doesn't need compatibility with older ECC implementations, since it's a new signature algorithm over a new curve which are not in the SEC standard.

Answer 2

(minisign author here)

As noted by corpsfini, keys encode the Y coordinate. The X coordinate is recovered using the curve equation: X = sqrt((Y^2 - 1) / (d Y^2 + 1)).

The square root has two solutions, so we need to encode the sign of x as well. Since coordinates only require 255 bits, we have a extra bit, used to encode the sign.

X and Y ∈ [0; 2^255-19[, so 16 bytes wouldn't be enough to encode them.