Re: [Cfrg] On relative performance of Edwards v.s. Montgomery Curve25519, variable base

[Mike Hamburg <[e-mail]>]

On 01/05/2015 12:26 AM, Andrey Jivsov wrote:
>
> I was expecting that a Montgomery ladder will be faster. Which brings 
> the question how much faster should we expect Montgomery ladder to be 
> for p ~= 2^256 x86 or other architecture? I don't see it on x86 in my 
> quick tests.
>
> Also, I saw a remark in 
> https://www.ietf.org/mail-archive/web/cfrg/current/msg05712.html "At 
> the 128-bit security level the ladder can be faster. At the > 200-bit+ 
> security levels the ladder is slower."
Hi Andrey,

I don't know about Donna, but I have fairly comprehensive benchmarks on 
a 252-bit curve (Ed252-MontgomeryStation) and the Goldilocks curves.

Ed252 runs a shared secret computation in 133k cycles on my 3.6GHz 
i7-4790 machine (TB off, HT off).  The microbenchmark breaks this down 
as 120k cycles of constant-time Montgomery laddering, about 13k cycles 
compression, and about 1300 cycles unaccounted.

Constant-time windowed Edwards would replace the ladder with 126k 
cycles.  Variable-time wNAF Edwards takes 112k cycles. So variable-time 
Edwards is 7% faster, and constant-time Edwards is 5% slower, than the 
Montgomery ladder, not counting the final compression.  But the 
Montgomery ladder takes compressed points as input.  Decompression takes 
13.4k  cycles to Edwards, or about 11% of the ladder.  So if you're 
operating on compressed points throughout, the Montgomery ladder is 
about 16% faster (and the whole ECDH about 14-15% faster) than 
constant-time Edwards.


For Ed448, it's a little closer.  The Montgomery ladder and compression 
take 529kcy, and the Edwards consttime window and compression (but not 
decompression) take 540kcy.  The compression function itself is about 
48kcy for either, and decompression is 49kcy.  So with no decompression, 
Montgomery is 2% faster, and with decompression it's 11% faster.

However, replace that Edwards with a fixed-window with cache-vulnerable 
indexing, and it goes down to 503kcy.  Replace it with wNAF and it goes 
down to 490kcy.  At that point it's still slower than the Montgomery 
ladder on compressed points, but only by 2%.

This ratio should be affected by the S/M/m ratio of the field 
arithmetic, the speed of constant-time lookup and condswap, and the size 
of the scalars.  Montgomery does more S,m, and Edwards does more M, 
except that the decompression is also S heavy.  As the curve gets 
larger, the windows can get larger which favors Edwards.  But Edwards 
also burns some 7-8% of its time on constant-time lookups on Ed448, and 
that's with AVX2 to speed them up.

Microsoft's benchmarks on Ed-384-mers, and even some of my earlier Ed448 
numbers disagree with the Ed448 data above.  My earlier numbers were 
about 6% less favorable to Montgomery, and Microsoft's numbers were 
about 10-15% less favorable to Montgomery.  I don't know why my latest 
tests are more favorable to Montgomery than my earlier ones; it may be 
machine or compiler-dependent, or it may have been caused by source 
changes since then.  I tried to hash out the discrepancy between my 
numbers and Microsoft's with Patrick Longa Pierola, but that's as close 
as we got.

So, for larger primes, the Montgomery ladder is probably slightly faster 
than Edwards when operating on compressed points, and slower or the same 
otherwise.


Cheers,
-- Mike