[curves] Input validation for genus 2 scalar multiplication

[D. J. Bernstein]

Robert Ransom writes:
> * The paper does not even mention the equation which input points must
>   satisfy.

It's 4EE xyzt == (F(xt+yz)+G(xz+yt)+H(xy+zt)-x^2-y^2-z^2-t^2)^2; i.e.,
put S = x^2+y^2+z^2+t^2 and check EE ((x+y)^2-x^2-y^2) ((z+t)^2-z^2-t^2) ==
((F/2)((x+t)^2+(y+z)^2-S)+(G/2)((x+z)^2+(y+t)^2-S)+(H/2)((x+y)^2+(z+t)^2-S)-S)^2.

I'm not sure whether checking this would violate validation patent
7257709. Using the same equation for decompression is safer but of
course more complicated.

We've instead been working on a completely different network format that
very easily supports much faster key generation. People who need
faster-than-Curve25519 speeds will want to use the new format (and
people who don't need faster-than-Curve25519 speeds should just use
Curve25519). This started as an appendix to the same paper but turned
into a big enough project that we split it into a separate paper:

   http://cr.yp.to/papers.html#hyperand

More software for the hyperand paper will be online soon. In particular,
the new format requires generating new "hyper-and-elliptic" curves, and
we're currently doing this for 2^127-1. This is much less expensive than
the Gaudry--Schost computation (and scales much more smoothly to higher
security levels) but it's still not instantaneous.

Btw, if you're imagining what SafeCurves would look like if it were
extended beyond the case of prime-field ECC, take a look at the
ted127glv4 curve: the twist has an impressively low security level.
Fortunately the ted127glv4 software also isn't available, so there's no
real risk for users. :-)

---Dan