Subject: [Cfrg] Signature performance using Montgomery curves

From: Evgeny Alekseev <[email-masked]>
Date: Tue, 17 Mar 2015 12:43:17 +0300

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

---

From: Mike Hamburg <[email-masked]>
Date: Tue, 17 Mar 2015 10:08:48 -0700

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:
> (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) .
>
> 256 14929                                                   9971
> 512 3558                                                     1988
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

---

From: Ilari Liusvaara <[email-masked]>
Date: Tue, 17 Mar 2015 19:23:24 +0200

On Tue, Mar 17, 2015 at 10:08:48AM -0700, Mike Hamburg wrote:
> scalar math because it's not a bottleneck in Schnorr signatures.  But it is
> a major bottleneck in ECDSA.

>From RFC5832:

Signing:
- Fixed scalarmult
- 2x Mul (mod l)
- Add (mod l)  [note: Adds multiply results from above]

Verification:
- ^-1 (mod l)  [inversion]
- 2x Mul (mod l)
- Double scalarmult

-Ilari

---

From: Mike Hamburg <[email-masked]>
Date: Tue, 17 Mar 2015 10:32:51 -0700

> - ^-1 (mod l)  [inversion]

Ah, thanks Ilari.  And it looks like verif is the same type of double 
scalarmult as for Schnorr.  So the signing should be the same ~20k/s 
(actually, I looked at keygen instead of sign, so 19455/s) as the 
regular Goldilocks signing, but the verif will be slower as in my 
earlier post.

-- Mike

---

From: Mike Hamburg <[email-masked]>
Date: Tue, 17 Mar 2015 10:36:53 -0700

On 03/17/2015 10:08 AM, Mike Hamburg wrote:
>
> Your Core i5-4570 has a huge boost ratio, from 2 GHz to 3.2 GHz.
Wait, no it doesn't, that's a 4750HQ.  The 4570 is 3.2-3.6 GHz (unless 
it's an S or T), so TB still matters but not as much.

Pardon my fat googlyfingers,
-- Mike