[curves] Finalizing XEdDSA

[Brian Smith]

Trevor Perrin <trevp at trevp.net> wrote:

> On Wed, Nov 2, 2016 at 3:00 PM, Brian Smith <brian at briansmith.org> wrote:

> It seems worth expanding on what exactly compatibility and incompatibility
>
> is intended. It's unclear to me.
>
> XEd25519 signatures are intended to be equivalent to Ed25519
> signatures, just with the public keys converted.  So we need to
> calculate "h" the exact same way, i.e. h = HASH(R || A || M).
>
> Agreed this should be explained, somewhere.
>
> (XEd448 may not be identical to the CFRG's version of Ed448, because
> they're not using the equivalent curve to X448, but that's a separate
> issue).
>

Yes, I found (and find) it confusing that XEd448 is different than Ed448 in
obvious ways, but yet a of XEdDSA is to be co,[compatible with EdDSA in
some way. More on the equivalence of Ed25519 and XEd25119 below.



> Nice - That works well, another reason for moving Z earlier.
>
> So you're thinking of similarly factoring out h and s computation into
> a helper function, with V and Rv moved to a prefix?
>

Yes. Basically, I'm simply trying to understand make make plain the
differences between these three functions. Also, I'm suspicious of trivial
but unnecessary differences between the functions in general.

Assuming I didn't make a huge mistake, here's another factoring of the
logic that shows that XEd22519 signing can be used with either XEd25519
keys or Ed25519 keys. In particular, the randomization of the nonce and the
derivation of an Ed25519 key from an X25519 key are orthogonal and XEd25519
signing is equivalent to Ed25519 signing with a nonce that has a fixed ||
random || fixed prefix.

xed25519_precompute(k):
    A, a = calculate_key_pair(k)
    prefix = domain_separator(1) || a
    return (A, a, prefix)

ed25519_precompute(k):
    A, seed = k.split_at(32)
    a', prefix = hash(seed).split_at(32)
    a = a' & 248 & 63 | 64
    return (A, a, prefix)

xed25519_sign((A, a, prefix), M, Z):
    pad = ""
    randomized_prefix = prefix || Z || pad
    return ed25519_sign((A, a, prefix), M)

# Uses naming from draft-irtf-cfrg-eddsa-05
ed25519_sign((A, a, prefix), M):
    r = hash(prefix || M) (mod L)
    R = rB
    k = hash(R || A || M) (mod L)
    S = r + k * a (mod L)
    return R || S

I've not bothered to do VXEd25519 yet.

Cheers,
Brian
-- 
https://briansmith.org/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20161102/471c3bcc/attachment.html>