Re: [Cfrg] E-521 vs. numsp512t1

[Mike Hamburg <[e-mail]>]

On 10/22/2014 04:42 PM, Ilari Liusvaara wrote:
> On Wed, Oct 22, 2014 at 07:19:44PM -0400, David Leon Gil wrote:
>> On Wed, Oct 22, 2014 at 5:34 PM, D. J. Bernstein <[e-mail]> wrote:
>>> Rob Granger and Mike Scott have posted a new paper "Faster ECC over
>>> \F_{2^521-1}" (https://eprint.iacr.org/2014/852) reporting ECC speeds
>>> mod 2^521-1, and in particular the first (as far as I know) serious
>>> implementation of E-521.
>> The implementation djb mentions is available on their website:
>>
>> http://indigo.ie/~mscott/{ed521,ws521}.cpp
>>
>
> Watch out (from ed521.cpp):
>
>
> void mul(int *w,ECp *P)
> {
> 	ECp W[33],Q;
> 	precomp(P,W);
>
> 	copy(&W[w[86]],P);
> 	for (int i=85;i>=0;i--)
> 	{
> 		if (w[i]>=0) copy(&W[w[i]],&Q);
> 		else         neg(&W[-w[i]],&Q);
> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> 		window(&Q,P);
> 	}
> 	norm(P);
> }
>
>
> That does not look constant-time...
>
>
> -Ilari
>
Also, on curves at moderncrypto dot org, Samuel Neves is reporting (and 
I can confirm) that the performance numbers do not account for 
TurboBoost.  He measured a slower but still impressive ~884kcy.

That said, the Granger-Scott implementation does not take advantage of 
vectorization or assembly optimizations, even to the degree that 
Goldilocks does (asm wide multiply and accumulate, mostly there to 
constrain the scheduler and register allocator).  It would be 
interesting to check its performance with more optimization.

On a related note, one of the numbers I reported for Goldilocks (~480k 
Haswell cycles) also did not account for TurboBoost.  DJB's Titan0 
SUPERCOP measurement of 529kcy on Haswell is accurate.  It turns out 
that on Ubuntu at least (Linux 3.13.0-29), disabling HyperThreading 
re-enables TurboBoost, so be careful what order you do it in.

Cheers,
-- Mike