Re: [Cfrg] Timing of libsodium, curve25519-donna, MSR ECCLib, and openssl-master

[Andrey Jivsov <[e-mail]>]

On 10/08/2014 10:05 PM, Watson Ladd wrote:
>> was 14131.5/5231.7=2.7 (reported on 09/03/2013)
>> >now: 14251.3/11105.2=1.27
>> >(apparently due to Montgomery-style assembler code specialized for P-256
>> >prime)
>> >
>> >This is even more interesting. These performance improvements apparently
>> >cover most of x86 CPUs in use today, clients and servers.
> Wouldn't the speedups from reducing the number of field operations by
> changing the curve shape stack on top of these? I don't really see the
> relevance to picking which wire format to use.
>
Just to be clear, I was saying that the apparent factor of ~2 
improvement of P-256 on non-AVX2 machine appears to be due to highly 
tuned Montgomery modulo prime reduction code, hardcoded for P-256 prime.

Montgomery curve has fewer underlying filed operations. The performance 
benefit will be lower than due to prime reduction/hardware/instruction 
assistance. However, given that the numbers are fairly close now, we can 
expect change in leadership depending on the mix of features. For 
example,  a hypothetical mix of the P-256 underlying field operations 
found in the code that I timed and a Montgomery curve on top would 
probably move such an implementation into the lead in the tests I performed.

P-256 has an advantage that it's in standards, widely deployed, can do 
point additions (without penalty of coordinate conversion), and you can 
get X.509 certs with it. It would have been easier to argue on its 
disadvantages if it had worse performance than it appears to have. I am 
aware of other disadvantages of P-256.

In your other e-mail, Watson, regarding AVX2/vector operations + X25519, 
it's an interesting question. The issues here are:
* will this hide some benefits of the 2^n-1 prime?
* increase code complexity?
* it seems that this is of no use to mobile devices (in the near future 
anyway)
* but servers will benefit from this.