5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Doesn't need to start with 04. Points are encoded according to section 5.1.2 in RFC 8032: 255 bits for y-coordinate and 1 bit for x coordinate. Coordinates on Curve25519 are mod $p$ with $p= 2^{255} - 19$ so 32 bytes are needed for one coordinate. $\endgroup$ – corpsfini Jul 24 at 11:05
8
$\begingroup$

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.
$\endgroup$
9
$\begingroup$

(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.

$\endgroup$
  • $\begingroup$ Thanks a lot! This is exactly what I needed. So the 32bytes I see above is really the Y coordinate, and I can recover X with that formula to get both. I love Minisign, it's really fab. Can I ask you, is it possible to output the raw private key (just for learning), or manually decrypt it? $\endgroup$ – Woodstock Jul 24 at 11:44
  • 1
    $\begingroup$ Keys are encoded in little-endian format, GnuPG being the only implementation I'm aware of that uses big-endian for Ed25519. So y as an integer is (0xf7)*2^0 + (0x59)*2^8 ... (0x0d)*2^252 = 6059360325038685432335429159867106683431817502499950464645549794044379486711 and x = 33942739095931203280835016784239364197415773456702966128992901549564140435446 $\endgroup$ – Frank Denis Jul 24 at 12:00
  • $\begingroup$ Wonderful thanks Frank. Is decryption of the private key possible if I manually follow the description of its form, or is there a way to extract the raw key in an easier fashion? $\endgroup$ – Woodstock Jul 24 at 12:06
  • $\begingroup$ The format of the private key is described here: jedisct1.github.io/minisign/#secret-key-format - The KDF is used to generate the key steam. If you don't want to do this yourself, the easiest way to go is probably to modify the code to print the key after decryption. Or use libsodium (or any other Ed25519 implementation) directly. $\endgroup$ – Frank Denis Jul 24 at 12:11
  • $\begingroup$ Thanks Frank! <3 $\endgroup$ – Woodstock Jul 24 at 12:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.