[curves] new 25519 measurements of formally verified implementations

[Jason A. Donenfeld]

Hi Armando,

I've started importing your precomputation implementation into kernel
space for use in kbench9000 (and in WireGuard and the kernel crypto
library too, of course).

- The first problem remains the license. The kernel requires
GPLv2-compatible code. GPLv3 isn't compatible with GPLv2. This isn't
up to me at all, unfortunately, so this stuff will have to be licensed
differently in order to be useful.

- It looks like the precomputation implementation is failing some unit
tests! Perhaps it's not properly reducing incoming public points?

{
.private = { 1 },
.public = { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff
},
.result = { 0xb3, 0x2d, 0x13, 0x62, 0xc2, 0x48, 0xd6, 0x2f, 0xe6,
0x26, 0x19, 0xcf, 0xf0, 0x4d, 0xd4, 0x3d, 0xb7, 0x3f, 0xfc, 0x1b,
0x63, 0x8, 0xed, 0xe3, 0xb, 0x78, 0xd8, 0x73, 0x80, 0xf1, 0xe8, 0x34 }
}

[ 8855.567043] Expected: b3 2d 13 62 c2 48 d6 2f e6 26 19 cf f0 4d d4
3d  .-.b.H./.&...M.=
[ 8855.567044] Expected: b7 3f fc 1b 63 08 ed e3 0b 78 d8 73 80 f1 e8
34  .?..c....x.s...4
[ 8855.567046] Actual: eb 1b 2b df 13 6a 3e bc 30 9f a4 f7 a1 95 a7 08
 ..+..j>.0.......
[ 8855.567047] Actual: 11 7f 7c e4 6e 65 a4 44 48 22 4d 00 78 54 70 5b
 ..|.ne.DH"M.xTp[
[ 8855.567048] kbench9000: precomp self-test 4: FAIL

There's the vector if you'd like to play with it. The other test
vectors I have do pass, though, which is good I suppose.

On the plus side, the implementation is super fast:

With turbo on, on my E3-1505Mv5, I'm getting:

donna64: 121793 cycles per call
 hacl64: 109793 cycles per call
 fiat64: 108937 cycles per call
sandy2x: 103003 cycles per call
  amd64: 108688 cycles per call
precomp: 83391 cycles per call
 fiat32: 232835 cycles per call
donna32: 411511 cycles per call

The benchmark of your precomputation implementation has what's
referred to by medical doctors as "less digits".

Regards,
Jason