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

[Michael Hamburg <[e-mail]>]

Thanks for your analysis!  However, please note that with lazy extended homogeneous coordinates on a twisted Edwards curve with a=-1, the cost of an Edwards addition to an accumulator is 8M and not 10M+1S, and the cost of a doubling is still 3M+4S, perhaps with an additional 1M to convert from this form to a suitable one for the window table.

Furthermore, the multiplication by a constant in the Montgomery curve is not negligible, but neither is the cost of a constant-time lookup in the Edwards window table.

Cheers,
— Mike

> On Jan 11, 2015, at 4:31 PM, Andrey Jivsov <[e-mail]> wrote:
> 
> Counting multiplications (M) and squares (S) in F(p), ECC formulas use at least 5% more operations v.s. Montgomery.
> 
> The lowest non-Montgomery count is reached with twisted Edwards, signed window, w=5, which yields 6%/5.5% more M/S.
> 
> I pasted my notes below.
> 
> It's possible that my initial results in this thread are due to the difference in F(p) operations between the two implementations.
> 
> See also http://www.ietf.org/mail-archive/web/cfrg/current/msg05857.html
> 
> Thanks to Mike and Watson for pointers and comments.
> 
> 
> -----------------------------------------------------------------
> Montgomery method:
> -----------------------------------------------------------------
> 
> From http://hyperelliptic.org/EFD/g1p/auto-montgom-xz.html (8.2M for differential addition and doubling) with Z1=1: 5M+4S.
> 
> 256*(5*M+4*S)=1275*M + 1020*S
> Inverse: 11*M + 245*S
> 
> (also checked curve25519-donna-c64.c)
> 
> Total: 1285*M + 1265*S
> 
> -----------------------------------------------------------------
> t.Edwards window method:
> -----------------------------------------------------------------
> 
> Write the windows size as w and n-bit E(F(p)) curve (e.g. n=255). 2^(w-1) signed elements need to be calculated.
> 
> The half of 2^(w-1) is filled with doubles, half with additions
> 
> 2^(w-2) additions, 2^(w-2) doubles, z!=1
> 
> addition: 10M+1S
> double: 3M+4S
> from http://hyperelliptic.org/EFD/g1p/auto-twisted-projective.html
> 
> Window filling:
> 2^(w-2)*(10*M+S) + 2^(w-2)*(3*M+4*S)
> 
> For windowed scalar multiplication there are w(ceil(n/w)-1) doubles and ceil(255/w)-1 additions
> 
> w*(ceil(n/w)-1)*(3*M+4*S)+(ceil(n/w)-1)*(10*M+S)
> 
> The formula is 2^(w-2)*(10*M+S) + 2^(w-2)*(3*M+4*S) + w*(ceil(n/w)-1)*(3*M+4*S)+(ceil(n/w)-1)*(10*M+S)
> 
> w=3: 1622*M + 1102*S
> w=4: 1438*M + 1091*S
> w=5: 1354*M + 1090*S
> w=6: 1384*M + 1130*S
> 
> Inverse: 11*M + 245*S
> 
> Total (w=5) with inverse:
> 1354*M + 1090*S +11*M + 245*S = 1365*M + 1335*S
> 
> So we have
> 
> Montgomery (M):     1285*M + 1265*S
> t.Edwards w=5 (tE): 1365*M + 1335*S
> ( tE needs 6% more M, 5.5% more S )
> 
> Unifying S+M, this is:
> 
> for S=M cost:
> M: 2550*M
> tE: 2700*M
> 
> for S=0.625M cost:
> M: 2075M
> E: 2200M
> 
> Watson's estimate is:
> Montgomery: 2491M
> t.Edwards w=5: 2714M
> 
> -----------------------------------------------------------------
> "Jacobian coordinates with a4=0 for short Weierstrass curves", window method
> -----------------------------------------------------------------
> http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html
> 
> doubling: 2M+5S
> addition:  11M+5S
> 
> 2^(w-2)*(11*M+5*S) + 2^(w-2)*(2*M+5*S) + w*(ceil(n/w)-1)*(2*M+5*S)+(ceil(n/w)-1)*(11*M+5*S) + 11*M + 245*S
> 
> w=5: 1165*M + 1825*S
> 
> for S=M cost
> 2990*M
> 
> for S=0.625M cost
> 2305*M
> 
> -----------------------------------------------------------------
> variable curve size n, window method
> -----------------------------------------------------------------
> 
> Hand-waive (extrapolate from Curve25519) the inverse as
> 0.95*n*S+0.05*n*M
> 
> Montgomery:
> (n+1)*(5*M+4*S)+0.95*n*S+0.05*n*M
> 
> t.Edwards:
> F=2^(w-2)*(10*M+S) + 2^(w-2)*(3*M+4*S) + w*(ceil(n/w)-1)*(3*M+4*S)+(ceil(n/w)-1)*(10*M+S)+ 0.95*n*S+0.05*n*M
> 
> n=384:
> M: 1944*M + 1904*S
> w=5:
> tE: 2023*M + 2000*S
> w=6:
> tE: 1991*M + 2019*S
> 
> n=255, w=5  (compare to the actual, above):
> M: 1292*M + 1266*S
> tE: 1366*M + 1332*S
> 
> n=400:
> M: 2025*M + 1984*S
> w=5:
> tE: 2099*M + 2079*S
> w=6:
> tE: 2076*M + 2110.*S
> w=7:
> tE: 2203*M + 2193*S
> 
> n=512:
> M: 2590*M + 2538*S
> w=5:
> tE: 2679*M + 2668*S
> w=6:
> tE: 2613*M + 2691*S
> 
> -----------------------------------------------------------------
> Comb method
> -----------------------------------------------------------------
> The method is described here: http://eprint.iacr.org/2005/222.pdf, but always add O:
> 
> precomp: (w-1)*ceil(n/w)(3M+4S) + ((2^w)-w-1)*(10M+1S)
> mult: (ceil(n/w)-1)*(3M+4S+10M+1S)
> inverse (n=255): 11*M + 245*S
> 
> total: (w-1)*ceil(n/w)*(3*M+4*S) + ((2^(w-1))-w-1)*(10*M+S) + (ceil(n/w)-1)*(3*M+4*S+10*M+S)+11*M + 245*S
> 
> n=255:
> w=3:
> 1653*M + 1349*S
> w=4:
> 1516*M + 1339*S
> w=5:
> 1533*M + 1337*S
> w=6:
> 1772*M + 1372*S
> 
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> http://www.irtf.org/mailman/listinfo/cfrg