[curves] new 25519 measurements of formally verified implementations

[Armando Faz Hernández]

Quoting "Jason A. Donenfeld" <Jason at zx2c4.com>:
> 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.
>

The rfc7748_precomputed library is now released under LGPLv2.1.
We are happy to see our code integrated in more projects.

Quoting "Jason A. Donenfeld" <Jason at zx2c4.com>:
> - It looks like the precomputation implementation is failing some unit
> tests! Perhaps it's not properly reducing incoming public points?
>
> 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.

Thanks, for this observation. The code was missing to handle some carry bits,
producing incorrect outputs for numbers between 2p and 2^256. Now, I have
rewritten some operations for GF(2^255-19) considering all of these cases.
More tests were added and fuzz test against HACL implementation.

Code is available at:
   https://github.com/armfazh/rfc7748_precomputed  (commit c79ca5e...)

*Disclaimer: More test and work is needed for the GF(2^448-2^224-1)  
arithmetic.

> 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".

Due to the bug's corrections, a slight loss of performance was observed;
however, other operations were optimized too counteracting the losses.
Let us know about your new measurements.



--
Armando Faz Hernández, PhD Candidate.
Instituto de Computação, Unicamp.
Campinas, Brasil.