Re: [Cfrg] Signature performance using Montgomery curves

Hi Evgeny,

Does the Russian standard require an inversion mod the curve order? 
Goldilocks doesn't implement this, and has very little optimization for 
scalar math because it's not a bottleneck in Schnorr signatures.  But it 
is a major bottleneck in ECDSA.

Without that step, the Goldilocks code base can do about 20000 
signatures or 6100 verifies per second on a Core i7-4790.  This is on 
one core of four, HT off, TB off, 3.6GHz, with IIRC a 15 kiB precomputed 
table.  What were the settings for your benchmark?  Your Core i5-4570 
has a huge boost ratio, from 2 GHz to 3.2 GHz.

Since I don't have optimized scalar math, I can only ballpark how long 
the inversion step would take, though perhaps you could share your 
numbers for 512?  With the mostly unoptimized scalar montmul code in the 
Decaf branch, a double montmul (to multiply two scalars and correct for 
the Montgomery factor) takes 263ns.  So about 448*1.25 montmuls would 
take 73us, dropping speeds to just over 8000 signatures or 4200 verifies 
per second, again on a 3.6GHz core.

A more optimized FLT inverse might take half the time (with optimized 
montmul, dedicated squaring, an addition chain etc), which would raise 
speeds to ~11000 signs or 5000 verifies / core second. I don't know how 
fast blinded EGCD is at this size, but it's probably considerably faster 
than FLT at the cost of some complexity.

Cheers,
-- Mike

On 03/17/2015 02:43 AM, Evgeny Alekseev wrote:
>
> Dear all,
>
> we studied performance of Russian national digital signature standard 
> (which is, in fact, very similar to ECDSA) using Montgomery curves  
> over F(p) with p1 = 2^512 - 569 and p2 = 2^256-617 and got the 
> following result (for Intel Core i5-4570) .
>
> Field size, bits             Signatures per second                  
> Verifications per second
>
> 256 14929                                                   9971
>
> 512 3558                                                     1988
>
>
> Could anyone tell, please, if there is such a performance analysis of 
> ECDSA, using Montgomery curves over F(p) with p = 2^448 - 2^224 - 1?
>
>
> Kind regards, Evgeny Alekseev, PhD
> Moscow State University, Faculty of Computational Mathematics and Cybernetics
>
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg