[curves] XEdDSA specification

[Andy Isaacson]

On Thu, Oct 20, 2016 at 07:37:41PM -0400, Trevor Perrin wrote:
>I'm happy to announce that a spec for the "XEd25519" signature
>algorithm used in Signal is available at [1].
>
>Feedback is welcome, ...

Thanks for all your work on this, Trevor.

Is the source markup for this document in git somewhere?  I'd put up 
pull requests for these suggestions if it were.

Having two different values named A makes the document excessively 
confusing to the non-expert.  We can avoid some confusion if we rename 
one of them, for example keep $A$ for the curve constant and use `Ak` 
for the twisted Edwards point representation of the public key.  (This 
will be somewhat confusing with the `kB` notation used for 
multiplication in `calculate_key_pair` so perhaps this also demands 
writing multiplication `k * B`, which is unfortunate but perhaps not a 
blocker.)

I'd be more comfortable if the pseudocode explicitly called out the 
bytes-to-integer and integer-to-bytes conversion that's defined in 2.4; 
as it stands, the document can only be read sequentially starting at the  
beginnning, every time I need to refer to it, because the implicit 
conversions are critical to understanding section 3 and xeddsa_verify.

Having one spec defining four different functions (XEd25519, VXEd25519, 
XEd448, VXEd448) makes some of the definitions general enough to be hard 
for the non-specialist reader to make concrete.  I'd have an easier time 
understanding XEd25519 in a standalone spec.  But there's a tradeoff, 
the symmetry in the specs is worth preserving, so maybe this spec should 
remain general and once the standards are finalized, a more concrete 
implementor's guide can be written.

There aren't any test vectors in the spec, and only one in 
curve25519-java/android/jni/ed25519/tests/tests.c that I've found so 
far.  A few more wouldn't hurt.

It'd also be nice to have fully worked examples, but that definitely 
doesn't belong in the spec; I'll see if I can generate an appropriate 
document as part of my current project.

-andy