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

[Andrey Jivsov <[e-mail]>]

On 01/12/2015 11:30 AM, Watson Ladd wrote:
> On Mon, Jan 12, 2015 at 9:59 AM, Michael Hamburg <[e-mail]> wrote:
>>
>> On Jan 12, 2015, at 7:28 AM, Watson Ladd <[e-mail]> wrote:
>> The table is filled with a cost of 8M for additions and 4M+4S for
>> doublings so 2^(w-2)*8M+2^(w-2)*(4M+4S). Then we proceed for
>> ceil(255/w)-1steps, each step consisting of (w-1) 3M+4S doublings, and
>> 1 4M+4S doubling. Ergo the total cost becomes
>> 2^(w-2)*(12M+4S)+(ceil(255/w)-1)*(w*(3M+4S)+1M).
>>
>>
>> Don’t you need to do some additions at some point as well?  Or do the
>> additions only cost 1M?
>
> Doing the calculation correctly, it's effectively 9M for an addition
> after a 3M+4S doubling. The best window is 5, with 1296*M + 1032*S,
> and tossing in the inversion gives 1307*M + 1286*S, vs 1285*M + 1265*S
> for Montgomery form. Note that here I'm neglecting the multiplications
> by constants, which is why the speeds are coming out slightly
> differently.

For extended twisted Edwards coordinates (thanks, Mike) I get very 
similar result. I agree with your operation count (according to 
http://eprint.iacr.org/2008/522.pdf):

n=255; w=5; 2^(w-2)*(8*M) + 2^(w-2)*(4*M+4*S) + 
w*(ceil(n/w)-1)*(3*M+4*S)+(ceil(n/w)-1)*(9*M)+11*M + 245*S =
1307*M + 1277*S

v.s. Montgomery

n=255; n*(5*M+4*S+M/4)+11*M + 245*S=1350*M + 1265*S =
1350*M + 1265*S

I believe I properly accounted for constants (d in t.Ed is large, would 
costs D=M, a=-1 D=0). The table will include points in extended twisted 
Edwards coordinates. Interestingly, the d is not used in any calculation.

The extended twisted Edwards coordinates, despite having to deal with 
large d, are slightly better (~1.5%) with a simple window exponentiation 
method.

The comb method doesn't seem to be better.

>
> But the bottom line is that Montgomery ladder is competitive with the
> best known alternative methods at 255 bits, in terms of operation
> counts, and this difference can be wiped out by the need for side
> channel protection: none of the various models are saying anything too
> different.

Yes, looks like this, if my calculations are correct. The paper mentions 
additional "caching", though.

One argument remains, though. If you plan to do anything beyond ECDH, 
there is a benefit to have the same code that does ECDH, and, say, signing.