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

[Andrey Jivsov <[e-mail]>]

I timed the EdDSA using the code recommended in 
http://www.ietf.org/mail-archive/web/cfrg/current/msg05034.html

To my surprise the performance of the verification v.s. variable base 
ECDH are about the same on a (non-Haswell) i5-3550 CPU @ 3.30GHz CPU ( 
the same I used before in prior reports).

git clone https://github.com/brainhub/curve25519-donna.git
$ make speed-curve25519-donna-c64 && ./speed-curve25519-donna-c64
71 us, 14063.8 op/s, 234115 cycles/op

git clone https://github.com/floodyberry/ed25519-donna && cd ed25519-donna
$ gcc ed25519.c -m64 -O3 -c  && gcc test.c ed25519.o -l crypto -o _ && ./_
61965 ticks/public key generation
65268 ticks/signature
223425 ticks/signature verification
60219 ticks/curve25519 basepoint scalarmult
failed to generate expected result
want: 
51,e7,68,e0,f7,a1,88,45,de,a1,cb,d9,37,d4,78,53,1b,95,db,be,66,59,29,3b,94,51,2f,bc,0d,66,ba,3f,
got : 
a9,62,ab,6a,f7,93,6c,52,a6,4e,68,34,04,1c,db,6b,47,7d,5e,f8,14,c0,fc,5c,1d,99,98,1b,b5,c5,05,53,
diff: f8,85,c3,8a, 
,32,e4,17,78,ef,a3,ed,33,c8,a3,38,5c,e8,85,46,72,99,d5,67,89,c8,b7,a7,b8,a3,bf,6c,

110063 ticks/verification (batch)

(I commented out exit(1) in test.c due to tests failing and added 
"batch" above).

I then changed the ge25519_double_scalarmult_vartime, which is doing 
"[s1]p1 + [s2]basepoint" to only do [s1]p1, making sure that the piece 
that takes window values from the precomputed static const 
ge25519_double_scalarmult_vartime is disabled.

This resulted in:
...
202080 ticks/signature verification
...

We have ECDH performance: 234115,  a relevant portion of signature 
verification: 202080.

This shows that the performance of Montgomery ladder v.s. Edwards 
variable base scalar multiplication for p ~= 2^256 is about 15% faster. 
The table for the window values is only 40*4*2^3=1280 bytes. This is 
with 64-bit C code in both cases.


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."