[curves] new 25519 measurements of formally verified implementations

Armando Faz Hernández armfazh at ic.unicamp.br
Fri Feb 23 12:08:46 PST 2018

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)  

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

More information about the Curves mailing list