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

[Michael Hamburg <[e-mail]>]

> On Jun 30, 2015, at 1:20 AM, Ilari Liusvaara <[e-mail]> wrote:
> 
> 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

To clarify, the encoding in Ed448-Goldilocks, and its successor “decaf”,
are more complicated than straightforward point compression but not
significantly slower.

There is also the alternative of (low bit of x is 0) ? y : -y, with the identity
(0,1) mapped arbitrarily to 1.

As for hash functions, the hash function used to produce the challenge
doesn’t have to be uniform.  It doesn’t even have to output a number as
big as the curve — half as big is good enough — but most schemes use
the full length for extra conservatism.  Also, if the curve order is close to
a power of 2 (i.e. 2^bleh +- O(2^(bleh/2))), then a hash the same length
as the order is good enough for choosing the seed.  You only need a
longer seed if the curve is not close enough to a power of 2, eg P256 or
Brainpool.  But it is nice to be able to choose the same hash function for
every curve of the same size.

Cheers,
— Mike