Subject: [Cfrg] performance comparisons

From: Paul Lambert <[email-masked]>
Date: Thu, 5 Feb 2015 13:14:04 -0800

I¹m presenting Curve25519 for possible adoption to a non-IETF forum.
It would be very valuable to have a good performance comparison information
of Curve25519 versus NIST-P256 where the comparison includes the
Validation required.
I find interesting numbers at:
 http://cr.yp.to/ecdh/reports.html
But P256 is not included.

Could someone kindly provide or point to an appropriate reference.

Thanks in advance,

Paul

---

From: Michael Hamburg <[email-masked]>
Date: Thu, 5 Feb 2015 13:28:46 -0800

Hi Paul,

Surely if the point is given in uncompressed format, the validation takes negligible time.  You just have to remember to do it.  And if it’s given in compressed format but then decompressed, then again the decompression routine should fail if the point is not on the curve.

The only case where you might need a complicated validation routine is if you’re trying to use a subgroup of a curve with cofactor, which is pretty uncommon in my experience.

The numbers you cited are 14 years old.  Newer results are available depending on platform.  One source would be https://eprint.iacr.org/2013/816.pdf <https://eprint.iacr.org/2013/816.pdf>, though that only covers Intel Sandy Bridge and Haswell.  I vaguely recall there being an erratum on this paper… you might want to find their actual OpenSSL patch and test it to make sure the performance is the same in the release version.

Anyway, that would put NIST-P256 at ECDH at 374k Sandy Bridge cycles vs 194k for Curve25519, and at 291k Haswell cycles vs  162k for Curve25519.

I think results on other platforms, particularly ARM NEON, may be less favorable to NIST-P256, but I don’t have any on hand.

Cheers,
— Mike

> On Feb 5, 2015, at 1:14 PM, Paul Lambert <[email-masked]> wrote:
> 
> 
> 
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

---

From: Andrey Jivsov <[email-masked]>
Date: Thu, 05 Feb 2015 13:38:25 -0800

> Could someone kindly provide or point to an appropriate reference.
...

Here are my timings.

http://www.ietf.org/mail-archive/web/cfrg/current/msg05219.html (most 
optimized Curve25519 v.s. P-256 on x86 that I know of is 65% faster)

Also: http://www.ietf.org/mail-archive/web/cfrg/current/msg05251.html

Point validation is a few F(p) muls, adds, and should not show up in the 
scalarmult results.

---

From: Paul Lambert <[email-masked]>
Date: Thu, 5 Feb 2015 14:04:06 -0800

Hi Mike,

Many thanks for the quick answers.

Surely if the point is given in uncompressed format, the validation takes negligible time.  You just have to remember to do it.  And if it’s given in compressed format but then decompressed, then again the decompression routine should fail if the point is not on the curve.
Yes.  Either the decompression or a point validation needs to be included.

The numbers you cited are 14 years old.  Newer results are available depending on platform.  One source would be https://eprint.iacr.org/2013/816.pdf, though that only covers Intel Sandy Bridge and Haswell.  I vaguely recall there being an erratum on this paper… you might want to find their actual OpenSSL patch and test it to make sure the performance is the same in the release version.

Very nice reference – thank you.  It’s a good place to start to say why ECC should be used.

However … it does not mention Curve25519.

It’s also very SSL specific giving numbers for the specific handshake.  I’m working on something else, and need to show a direct comparison of Curve25519 versus P256.

Anyway, that would put NIST-P256 at ECDH at 374k Sandy Bridge cycles vs 194k for Curve25519, and at 291k Haswell cycles vs  162k for Curve25519.
Perfect.  So this is a 80% to 93%+ performance improvement.   I’ll use these numbers.

I think results on other platforms, particularly ARM NEON, may be less favorable to NIST-P256, but I don’t have any on hand.
Comparisons on ‘small’ processor would be very interesting also.

Many thanks for the help,

Paul

Cheers,
— Mike

On Feb 5, 2015, at 1:14 PM, Paul Lambert <[email-masked]<mailto:[email-masked]>> wrote:

Thanks in advance,

Paul

_______________________________________________
Cfrg mailing list
[email-masked]<mailto:[email-masked]>
http://www.irtf.org/mailman/listinfo/cfrg