Re: [TLS] PKIX drafts on EdDSA/Ed25519 and Curve25519/Curve448

[Ilari Liusvaara <[e-mail]>]

On Tue, Jun 30, 2015 at 12:02:39AM +0200, Simon Josefsson wrote:
> 
> A couple of people suggested to define encodings for Curve25519/Curve448
> (the CFRG curves) public keys.  I didn't see that this necessarily had
> to be in the above document, so I put it in a separate document.  I'm
> not entirely sure how useful this is, or if I may have completely
> misunderstood what people had in mind. 

Well, EdDSA-like scheme (obtained by dropping constraints on curve
and hash[1] and generation of a and seed[2])  would be:

(a and seed generated from secret)
r = h(seed || M)
R = rB
A = aB
s = (r + h(encode_p(R) || encode_p(A) || M) * a) mod l
signature = encode_p(R) || encode_s(s)
public key = encode_p(A)

(Multiply equation for s to get verification equation:
sB = R + h(encode_p(R) || encode_p(A) || M) * A )

(One can obtain Ed25519 from this by substituting suitable a / seed
generation, B and functions h, encode_p and encode_a.)


And since encode_p(X) is inside hash, one must pin it down for the
scheme to work (interoperate between signers and verifiers), along
with the hash function h to use.

Edwards curves are always constant or quadric in x for in every
term of curve equation. Which means that x can be compressed to
a single LSB bit (Ed25519 paper is somewhat unclearly worded IMO,
but this is what it does for prime curves[3][4]).

There's also encode_s(x), but it is straightforward (can just use
little-endian base-256 integer encoding.


[1] Enabling it to work on curves other than very few ones, especially
with standard-issue hashes.

[2] Since hash function length is insufficient for the method used in
Ed25519 without using exotic hashes.

[3] There are other possibilities, but LSB bit (even/odd) seems to be
the easiest to extract and to compare.

[4] For Ed448 there is also encoding from Ed448-Goldilocks, which is
56 bytes (448 bits) instead of 57 bytes (449 bits). But it is fair
bit more complicated (slow) than straightforward point compression.


-Ilari