3 ms·

> They also added the PCLMULQDQ instruction to efficiently implement ECC. Isn't this more typically used in GHASH implementations? Maybe it's applicable to bot

• pbsd 11y ago
  PCLMULQDQ is a godsend to both (GCM and binary elliptic curves), since both rely heavily on multiplication performance over F_{2^n}. The current fastest elliptic curve implementations are over binary fields using this instruction: http://eprint.iacr.org/2013/131 http://eprint.iacr.org/2013/131.
  • sdevlin 11y ago
    Ah, interesting - so this applies in particular to elliptic curves over binary fields. I may have missed this, but did they note how performance fared in the absence of hardware support? Also, have binary curves (this or the NIST ones or any others) seen widespread deployment anywhere? I was under the impression that prime field curves were more widely used.
    • pbsd 11y ago
      As far as I know they didn't try to make a good implementation without CLMUL. However, the older endomorphism-free curve2251 implementation [2, 3] is eye-opening: - the SSSE3 implementation is ~2.7 times slower than with CLMUL - the generic (using mpfq, which should actually be pretty good) implementation is 5-6 times slower than with CLMUL Binary curves used to be a lot more popular than they are now, before we all had fat multipliers in CPUs. The patent situation is worse for binary fields too, I think. That said, I'm pretty sure there are deployments somewhere using them; Dan Boneh's TLS survey [1] shows an overwhelming 96% of TLS clients using NIST's P-256, but the second most popular curve is NIST's B-233, at 3.6%. I would guess that this is due to hardware accelerators. [1] http://www.w2spconf.com/2014/papers/TLS.pdf http://www.w2spconf.com/2014/papers/TLS.pdf [2] http://bench.cr.yp.to/web-impl/amd64-titan0-crypto_dh.html http://bench.cr.yp.to/web-impl/amd64-titan0-crypto_dh.html [3] https://eprint.iacr.org/2011/170 https://eprint.iacr.org/2011/170
      • sdevlin 11y ago
        Great info - thanks!