Re: [Cfrg] E-521 vs. numsp512t1

[Andy Lutomirski <[e-mail]>]

On Thu, Oct 23, 2014 at 10:06 AM, Mike Hamburg <[e-mail]> wrote:
>
>
> 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.
>

I haven't tried it for these types of tests, but something like:

$ perf stat ./whatever_benchmark

will count cycles directly.  As long as the benchmark isn't too
memory-heavy and as long as it runs enough loops to wash out the
startup time, it might be a much simpler way to do this kind of
benchmarking.

--Andy