ECC in Libraries

This page collects information about ECC implementations in open-source software. It was extracted by source code analysis (i.e. we looked at the code and tried really hard to name what we see), so it may or may not match the reality (whether due to a mistake or due to different naming choices).

We restricted ourselves to ECDH/ECDSA (on prime field curves) and x25519/Ed25519. In case libraries contain multiple implementations we tried to document them clearly, along with the rules on how they pick one (e.g. curve-based/architecture-based). Naming of scalar multipliers is tricky. Naming of coordinate systems and formulas is taken from the EFD.

BouncyCastle

Version: 1.76 (tag r1rv76)
Repository: https://github.com/bcgit/bc-java/
Docs: https://bouncycastle.org/docs/docs1.8on/index.html

Primitives

Supports short-Weierstrass curves for the usual (ECDSA, ECDH). Supports X25519, Ed25519. Also more exotic stuff like ECMQV, GOST key exchange and signatures and lots of others.

Lots of scalarmults available:
Several coordinate systems supported:

  • Affine

  • Projective (Homogenous)

  • Jaobian

  • Jacobian-Chudnovsky

  • Jacobian-Modified

  • Lambda-Affine? (binary-field curves only)

  • Lambda-Projective? (binary-field curves only)

  • Skewed? (binary-field curves only)

Some curve-custom code in: https://github.com/bcgit/bc-java/tree/r1rv76/core/src/main/java/org/bouncycastle/math/ec/custom/sec Specifically, fast-prime modular reduction for SECG curves, and (weirdly) a short-Weierstrass implementation of Curve25519.

Ed25519 based on Mike Hamburg’s work.

ECDH

KeyGen:
Derive:

  • Short-Weierstrass

  • GLV if possible, else Window NAF via ECDHBasicAgreement.calculateAgreement -> ECPoint.multiply -> ECCurve.getMultiplier -> ECCurve.createDefaultMultiplier.

  • Jacobian-Modified via ECCurve.FP_DEFAULT_COORDS. SECP curves use Jacobian, SECT curves use Lambda-Projective.

  • Formulas same as KeyGen.

ECDSA

KeyGen:

  • Short-Weierstrass

  • Comb via ECKeyPairGenerator.generateKeyPair -> ECKeyPairGenerator.createBasePointMultiplier.

  • Jacobian-Modified via ECCurve.FP_DEFAULT_COORDS. SECP curves use Jacobian, SECT curves use Lambda-Projective.

  • Formulas same as KeyGen.

Sign:

  • Short-Weierstrass

  • Comb via ECDSASigner.generateSignature -> ECDSASigner.createBasePointMultiplier.

  • Jacobian-Modified via ECCurve.FP_DEFAULT_COORDS. SECP curves use Jacobian, SECT curves use Lambda-Projective.

  • Formulas same as KeyGen.

Verify:

X25519

KeyGen:

  • Twisted-Edwards

  • Comb via X25519.generatePublicKey -> X25519.scalarMultBase -> Ed25519.scalarMultBaseYZ -> Ed25519.scalarMultBase.

  • Many coordinate systems: Extended, half-Niels, affine.

  • Some HWCD formulas are used.

Derive:

Ed25519

KeyGen:

  • Twisted-Edwards

  • Comb via Ed25519.generatePublicKey -> Ed25519.scalarMultBaseEncoded -> Ed25519.scalarMultBase.

  • Many coordinate systems: Extended, half-Niels, affine.

  • Some HWCD formulas are used.

Sign:

  • Twisted-Edwards

  • Comb via Ed25519.sign -> Ed25519.implSign -> Ed25519.scalarMultBaseEncoded -> Ed25519.scalarMultBase.

  • Many coordinate systems: Extended, half-Niels, affine.

  • Some HWCD formulas are used.

Verify:

BoringSSL

Version: bfa8369 (commit bfa8369)
Repository: https://github.com/google/boringssl/
Docs: https://commondatastorage.googleapis.com/chromium-boringssl-docs/headers.html

Primitives

Supports P-224, P-256, P-384 and P-521. Also Curve25519. Uses fiat-crypto for the SECP curve field arithmetic and x25519.

P-224

P-256

P-384

  • Uses defaults (described below).

P-521

  • Uses defaults (described below).

ECDH

KeyGen:
Derive:

ECDSA

KeyGen:
Sign:
Verify:

X25519

KeyGen:

  • Twisted-Edwards

  • ?? via X25519_keypair -> X25519_public_from_private -> x25519_ge_scalarmult_base.

  • Has multiple coordinate systems: projective, extended, completed, Duif

  • Unknown formulas. dbl, add

Derive:

  • Montgomery

  • Ladder via X25519 -> x25519_scalar_mult -> x25519_NEON/x25519_scalar_mult_adx/x25519_scalar_mult_generic

  • xz.

  • Unknown formula: ladd-boringssl-x25519 from fiat-crypto.

Ed25519

Based on ref10 of Ed25519.

KeyGen:

  • Twisted-Edwards

  • ?? via ED25519_keypair -> ED25519_keypair_from_seed -> x25519_ge_scalarmult_base.

  • Has multiple coordinate systems: projective, extended, completed, Duif

  • Unknown formulas. dbl, add

Sign:

  • Twisted-Edwards

  • ?? via ED25519_sign -> ED25519_keypair_from_seed -> x25519_ge_scalarmult_base.

  • Has multiple coordinate systems: projective, extended, completed, Duif

  • Unknown formulas. dbl, add

Verify:

  • Twisted-Edwards

  • Sliding window (signed) with interleaving? via ED25519_verify -> ge_double_scalarmult_vartime.

  • Has multiple coordinate systems: projective, extended, completed, Duif

  • Unknown formulas. dbl, add

Botan

Version: 3.2.0 (tag 3.2.0)
Repository: https://github.com/randombit/botan/
Docs: https://botan.randombit.net/handbook/

Primitives

Has coordinate and scalar blinding,

ECDH

KeyGen:
Derive:

ECDSA

KeyGen:
Sign:
Verify:

X25519

Based on curve25519_donna.

  • Montgomery

  • Montgomery ladder (unrolled several iterations)

  • xz

  • Unknown formula: ladd-botan-x25519

Ed25519

Based on ref10 of Ed25519. See BoringSSL.

SymCrypt

Version: 103.1.0 (tag v103.1.0)
Repository: https://github.com/microsoft/SymCrypt
Docs:

Primitives

Supports ECDH and ECDSA with NIST curves (192, 224, 256, 384, 521) and Twisted Edwards NUMS curves (NumsP256t1, NumsP384t1, NumsP512t1). Also custom curves. Supports X25519.

ECDH

KeyGen:
Derive:

ECDSA

KeyGen:
Sign:
Verify:

X25519

KeyGen:

  • Montgomery

  • Ladder via SymCryptMontgomeryPointScalarMul.

  • xz.

  • ladd-1987-m-3 via SymCryptMontgomeryDoubleAndAdd.

Derive:

  • Same as Keygen.

fastecdsa

Version: v2.3.1
Repository: https://github.com/AntonKueltz/fastecdsa/
Docs: https://fastecdsa.readthedocs.io/en/latest/index.html

Primitives

Offers only ECDSA. Supported curves: all SECP curves (8) for 192-256 bits, all (7) Brainpool curves as well as custom curves.

ECDSA

KeyGen:

  • Short-Weierstrass

  • Ladder via get_public_key -> pointZZ_pMul.

  • Affine and schoolbook add and double.

Sign:

  • Short-Weierstrass

  • Same ladder as Keygen via sign.

Verify:

micro-ecc

Version: v1.1
Repository: https://github.com/kmackay/micro-ecc/
Docs:

Primitives

Offers ECDH and ECDSA on secp160r1, secp192r1, secp224r1, secp256r1, and secp256k1.

ECDH

KeyGen:
Derive:

  • Short-Weierstrass

  • Ladder (coZ, with subtraction) via uECC_shared_secret -> EccPoint_compute_public_key -> EccPoint_mult (also has coordinate randomization).

  • Same coords and formulas as KeyGen.

ECDSA

Keygen:

  • Same as ECDH.

Sign:

  • Short-Weierstrass

  • Ladder (coZ, with subtraction) via uECC_sign -> uECC_sign_with_k_internal -> EccPoint_mult (also has coordinate randomization).

  • Same coords and formulas as KeyGen.

Verify:

  • Short-Weierstrass

  • Shamir’s trick via uECC_verify.

  • Same coords and formulas as KeyGen.

Intel IPP cryptography

Version: 2021.9.0
Repository: https://github.com/intel/ipp-crypto/
Docs: https://www.intel.com/content/www/us/en/docs/ipp-crypto/developer-reference/2021-8/overview.html

Primitives

Supports “ECC (NIST curves), ECDSA, ECDH, EC-SM2”. Also ECNR.

ECDH

KeyGen:
Derive:

  • Short-Weierstrass

  • (signed, Booth) Fixed Window (width = 5) via ippsGFpECSharedSecretDH -> gfec_MulPoint -> gfec_point_mul.

  • Has special functions for NIST curves, but those implement the same scalarmult.

  • Same coordinates and formulas as KeyGen.

ECDSA

KeyGen:

  • Same as ECDH.

Sign:
Verify:

x25519

KeyGen:
Derive:

  • Montgomery

  • ? via mbx_x25519 -> x25519_scalar_mul_dual

  • xz

  • Unknown formulas.

Ed25519

KeyGen:

  • Twisted-Edwards

  • Fixed window with full precomputation? (width = 4) via mbx_ed25519_public_key -> ifma_ed25519_mul_basepoint

  • Mixes coordinate models:

    homogeneous: (X:Y:Z) satisfying x=X/Z, y=Y/Z
extended homogeneous: (X:Y:Z:T) satisfying x=X/Z, y=Y/Z, XY=ZT
completed: (X:Y:Z:T) satisfying x=X/Z, y=Y/T
scalar precomputed group element: (y-x:y+x:2*t*d), t=x*y
mb precomputed group element: (y-x:y+x:2*t*d), t=x*y
projective flavor of the mb precomputed: (Y-X:Y+X:2*T*d:Z), T=X*Y

Add:

fe52_add(r->X, p->Y, p->X);      // X3 = Y1+X1
fe52_sub(r->Y, p->Y, p->X);      // Y3 = Y1-X1
fe52_mul(r->Z, r->X, q->yaddx);  // Z3 = X3*yplusx2
fe52_mul(r->Y, r->Y, q->ysubx);  // Y3 = Y3*yminisx2
fe52_mul(r->T, q->t2d, p->T);    // T3 = T1*xy2d2
fe52_add(t0, p->Z, p->Z);        // t0 = Z1+Z1
fe52_sub(r->X, r->Z, r->Y);      // X3 = Z3-Y3 = X3*yplusx2 - Y3*yminisx2 = (Y1+X1)*yplusx2 - (Y1-X1)*yminisx2
fe52_add(r->Y, r->Z, r->Y);      // Y3 = Z3+Y3 = X3*yplusx2 + Y3*yminisx2 = (Y1+X1)*yplusx2 + (Y1-X1)*yminisx2
fe52_add(r->Z, t0, r->T);        // Z3 = 2*Z1 + T1*xy2d2
fe52_sub(r->T, t0, r->T);        // T3 = 2*Z1 - T1*xy2d2

Dbl:

fe52_sqr(r->X, p->X);
fe52_sqr(r->Z, p->Y);
fe52_sqr(r->T, p->Z);
fe52_add(r->T, r->T, r->T);
fe52_add(r->Y, p->X, p->Y);
fe52_sqr(t0, r->Y);
fe52_add(r->Y, r->Z, r->X);
fe52_sub(r->Z, r->Z, r->X);
fe52_sub(r->X, t0, r->Y);
fe52_sub(r->T, r->T, r->Z);
Sign:
Verify:

  • Twisted-Edwards

  • Fixed window with full precomputation? (width = 4) for base point mult, then just Fixed window (width = 4) for the other mult, all via mbx_ed25519_verify -> ifma_ed25519_prod_point -> ifma_ed25519_mul_point + ifma_ed25519_mul_basepoint

  • Same as KeyGen.

LibreSSL

Version: v3.8.2
Repository: https://github.com/libressl/portable
Docs:

Primitives

Supports ECDH, ECDSA as well as x25519 and Ed25519.

ECDH

KeyGen:

  • Short-Weierstrass

  • Simple Ladder via kmethod.keygen -> ec_key_gen -> EC_POINT_mul -> method.mul_generator_ct -> ec_GFp_simple_mul_generator_ct -> ec_GFp_simple_mul_ct. Also does coordinate blinding and fixes scalar bit-length.

  • Jacobian coordinates.

  • Unknown formulas: add-libressl-v382, dbl-libressl-v382

Derive:

  • Short-Weierstrass

  • Simple Ladder via kmethod.compute_key -> ecdh_compute_key -> EC_POINT_mul -> method.mul_single_ct -> ec_GFp_simple_mul_single_ct -> ec_GFp_simple_mul_ct. Also does coordinate blinding and fixes scalar bit-length.

  • Same as KeyGen.

ECDSA

KeyGen:

  • Same as ECDH.

Sign:

  • Short-Weierstrass

  • Simple Ladder via ECDSA_sign -> kmethod.sign -> ecdsa_sign -> ECDSA_do_sign -> kmethod.sign_sig -> ecdsa_sign_sig -> ECDSA_sign_setup -> kmethod.sign_setup -> ecdsa_sign_setup -> EC_POINT_mul -> method.mul_generator_ct -> ec_GFp_simple_mul_generator_ct -> ec_GFp_simple_mul_ct.

  • Same as ECDH.

Verify:

X25519

Based on ref10 of Ed25519. See BoringSSL. Not exactly the same.

Ed25519

Based on ref10 of Ed25519. See BoringSSL. Not exactly the same.

libtomcrypt

Version: v1.18.2
Repository: https://github.com/libtom/libtomcrypt/
Docs:

Primitives

Offers ECDH and ECDSA on the curves: SECP112r1, SECP128r1, SECP160r1, P-192, P-224, P-256, P-384, P-521.

ECDH

KeyGen:

  • Short-Weierstrass

  • Simple ladder via ecc_make_key -> ecc_make_key_ex -> ecc_ptmul -> ltc_ecc_mulmod_timing.

  • jacobian, dbl-1998-hnm via ltc_ecc_projective_dbl_point

  • jacobian, add-1998-hnm via ltc_ecc_projective_add_point

Derive:

  • Same as Keygen via ecc_shared_secret -> ecc_ptmul -> ltc_ecc_mulmod_timing.

ECDSA

Keygen:

  • Same as ECDH.

Sign:

  • Same as Keygen via ecc_sign_hash -> _ecc_sign_hash -> ecc_make_key_ex.

Verify:

  • Shamir’s trick via ecc_verify_hash -> _ecc_verify_hash -> ecc_mul2add or two separate sliding windows.

  • Same coords and formulas as KeyGen.

wolfSSL

OpenSSL

Version: 3.1.4
Repository: https://github.com/openssl/openssl
Docs: https://www.openssl.org/docs/

Primitives

ECDH, ECDSA on standard and custom curves. x25519, x448 and Ed25519, Ed448. Also SM2 specific methods.

The ladder methods have coordinate randomization and fix scalar bit-length.

Has several EC_METHODs.

  • EC_GFp_simple_method

  • EC_GFp_mont_method

  • EC_GFp_nist_method

  • EC_GFp_nistp224_method

  • EC_GFp_nistp256_method

  • EC_GFp_nistz256_method

  • EC_GFp_nistp521_method

ossl_ec_GFp_simple_ladder_pre:

  • Short-Weierstrass

  • xz

  • dbl-2002-it-2

ossl_ec_GFp_simple_ladder_step:

  • Short-Weierstrass

  • xz

  • mladd-2002-it-4

ossl_ec_GFp_simple_ladder_post:

  • Short-Weierstrass

  • xz to y-recovery

ECDH

KeyGen:

  • Short-Weierstrass

  • ? via EVP_EC_gen -> EVP_PKEY_Q_keygen -> evp_pkey_keygen -> EVP_PKEY_generate -> evp_keymgmt_util_gen -> evp_keymgmt_gen -> EC_KEYMGMT.gen -> ec_gen -> EC_KEY_generate_key -> ec_method.keygen  -> ossl_ec_key_simple_generate_key -> EC_POINT_mul(k, G, NULL, NULL) all methods then either ec_method.mul or ossl_ec_wNAF_mul

    • EC_GFp_simple_method -> ossl_ec_wNAF_mul -> ossl_ec_scalar_mul_ladder (Lopez-Dahab ladder) for [k]G and [k]P. Otherwise multi-scalar wNAF with interleaving?

    • EC_GFp_mont_method -> ossl_ec_wNAF_mul -> ossl_ec_scalar_mul_ladder (Lopez-Dahab ladder) for [k]G and [k]P. Otherwise multi-scalar wNAF with interleaving?

    • EC_GFp_nist_method -> ossl_ec_wNAF_mul -> ossl_ec_scalar_mul_ladder (Lopez-Dahab ladder) for [k]G and [k]P. Otherwise multi-scalar wNAF with interleaving?

      • ec_point_ladder_pre -> ec_method.ladder_pre or EC_POINT_dbl

      • ec_point_ladder_step -> ec_method.ladder_step or EC_POINT_add + EC_POINT_dbl

      • ec_point_ladder_post -> ec_method.ladder_post

      • the methods all use ossl_ec_GFp_simple_ladder_* functions as ladder_*.

    • EC_GFp_nistp224_method -> ossl_ec_GFp_nistp224_points_mul -> Comb for generator, (signed, Booth) Fixed Window (width = 5) for other points.

    • EC_GFp_nistp256_method -> ossl_ec_GFp_nistp256_points_mul -> Comb for generator, (signed, Booth) Fixed Window (width = 5) for other points.

    • EC_GFp_nistz256_method -> ecp_nistz256_points_mul -> (signed, Booth) Fixed Window (width = 7) with full precomputation from [SG14].

    • EC_GFp_nistp521_method -> ossl_ec_GFp_nistp521_points_mul -> Comb for generator, (signed, Booth) Fixed Window (width = 5) for other points.

  • Jacobian (or Jacobian-3 for NIST)

  • Formulas:

    • EC_GFp_simple_method -> LibreSSL add and LibreSSL dbl

    • EC_GFp_mont_method -> LibreSSL add and LibreSSL dbl

    • EC_GFp_nist_method -> LibreSSL add and LibreSSL dbl

    • EC_GFp_nistp224_method -> BoringSSL P-224 add and dbl

    • EC_GFp_nistp256_method -> add-2007-bl, dbl-2001-b

    • EC_GFp_nistz256_method -> Unknown: add-openssl-z256, add-openssl-z256a

    • EC_GFp_nistp521_method -> add-2007-bl, dbl-2001-b

Derive:
  • Same as KeyGen, except for:

    • nistp{224,256,521} methods, where the Fixed Window branch of the scalar multiplier is taken,

    • nistz256 where a (signed, Booth) Fixed Window (width = 5) is taken.

ECDSA

KeyGen:

  • Same as ECDH.

Sign:

  • Same as KeyGen.

Verify:

  • Short-Weierstrass

  • EC_GFp_simple_method, EC_GFp_mont_method, EC_GFp_nist_method: Interleaved multi-scalar wNAF via ec_method.verify_sig -> ossl_ecdsa_simple_verify_sig -> EC_POINT_mul -> ossl_ec_wNAF_mul.

  • EC_GFp_nistp224_method, EC_GFp_nistp256_method, EC_GFp_nistp521_method: Interleaved Comb for G and (signed, Booth) Fixed Window (width = 5) for other point.

  • EC_GFp_nistz256_method: Same as KeyGen for G and same as ECDH Derive for other point.

x25519

Taken from ref10 of Ed25519. See BoringSSL.

KeyGen:

  • Twisted-Edwards

  • Pippenger via ossl_x25519_public_from_private -> ge_scalarmult_base.

  • Mixes coordinate models:

    ge_p2 (projective): (X:Y:Z) satisfying x=X/Z, y=Y/Z
ge_p3 (extended): (X:Y:Z:T) satisfying x=X/Z, y=Y/Z, XY=ZT
ge_p1p1 (completed): ((X:Z),(Y:T)) satisfying x=X/Z, y=Y/T
ge_precomp (Duif): (y+x,y-x,2dxy)
Derive:

  • Montgomery

  • Montgomery ladder via ossl_x25519 -> x25519_scalar_mult

  • xz coords

  • Unknown ladder formula: ladd-openssl-x25519

Ed25519

Taken from ref10 of Ed25519. See BoringSSL.

KeyGen:

  • Same as x25519 KeyGen via ossl_ed25519_public_from_private -> ge_scalarmult_base.

Sign:

  • Same as x25519 KeyGen via ossl_ed25519_sign -> ge_scalarmult_base.

Verify:

  • Sliding window (signed) with interleaving? via ossl_ed25519_verify -> ge_double_scalarmult_vartime.

  • Otherwise same mixed coordinates and formulas.

NSS

Version: 3.94
Repository: https://hg.mozilla.org/projects/nss
Docs:

Primitives

ECDH, ECDSA (only standard curves P-256, P-384, P-521), also x25519.

Two ECMethods:
  • Curve25519

    • 32-bit -> own impl

    • 64-bit -> HACL*

  • P-256 from HACL*

Several ECGroups:

  • generic ECGroup_consGFp

  • Montgomery arithmetic ECGroup_consGFp_mont

  • P-256

  • P-384 from ECCkiila

  • P-521 from ECCkiila

The ECMethods override the scalarmult of the ECGroups in:

  • ec_NewKey via ec_get_method_from_name and then calling the method.mul.

  • EC_ValidatePublicKey via ec_get_method_from_name and then calling the method.validate.

  • ECDH_Derive via ec_get_method_from_name and then calling the method.mul.

  • ECDSA_SignDigest and ECDSA_SignDigestWithSeed via ec_SignDigestWithSeed, then ec_get_method_from_name and then calling the method.mul.

P-256 from HACL*

KeyGen:

  • Short-Weierstrass

  • Fixed Window (width = 4)? points to https://eprint.iacr.org/2013/816.pdf? via ec_secp256r1_pt_mul -> (Hacl*) Hacl_P256_dh_initiator -> point_mul_g

  • projective-3 coords.

  • add-2015-rcb, dbl-2015-rcb-3

Derive:

  • Same as KeyGen.

Sign:

  • Same as Keygen.

Verify:

  • Short-Weierstrass

  • Multi-scalar simultaneous Fixed Window

  • Same coords and formulas as KeyGen.

P-384

KeyGen:

  • Short-Weierstrass

  • Comb from ecckiila: EC_NewKeyFromSeed -> ec_NewKey -> ec_points_mul -> ECPoints_mul -> ecgroup.points_mul -> point_mul_two_secp384r1_wrap -> point_mul_g_secp384r1_wrap -> point_mul_g_secp384r1 -> fixed_smul_cmb.

  • projective-3 coords.

  • dbl-2015-rcb-3, madd-2015-rcb-3 also add-2015-rcb in point_add_proj.

Derive:

  • Short-Weierstrass

  • Regular Window NAF (width = 5) from ecckiila: ECDH_Derive -> ec_points_mul -> ECPoints_mul -> ecgroup.points_mul -> point_mul_secp384r1_wrap -> point_mul_secp384r1 -> var_smul_rwnaf.

  • projective-3 coords.

  • dbl-2015-rcb-3, add-2015-rcb.

Sign:

  • Same as KeyGen.

Verify:

  • Short-Weierstrass

  • Interleaved multi-scalar window NAF (width = 5) with Shamir’s trick from ecckiila: ECDSA_SignDigest -> ECDSA_SignDigestWithSeed -> ec_SignDigestWithSeed -> ec_points_mul -> ECPoints_mul -> ecgroup.points_mul -> point_mul_two_secp384r1_wrap -> point_mul_two_secp384r1 -> var_smul_wnaf_two

  • projective-3 coords.

  • dbl-2015-rcb-3, madd-2015-rcb-3 also add-2015-rcb in point_add_proj.

P-521

Same as P-384.

x25519

KeyGen:
Derive:

  • Same as KeyGen.

libsecp256k1

Version: v0.4.0
Repository: https://github.com/bitcoin-core/secp256k1
Docs:

Primitives

Supports ECDSA, ECDH and Schnorr signatures over secp256k1.

ECDH

KeyGen:
Derive:

ECDSA

Keygen:

  • Same as ECDH.

Sign:

  • Same as Keygen via secp256k1_ecdsa_sign -> secp256k1_ecdsa_sign_inner -> secp256k1_ecdsa_sig_sign -> secp256k1_ecmult_gen.

Verify:

  • Split both scalars using GLV and then interleaving with width-5 NAFS on 4 scalars via secp256k1_ecdsa_verify -> secp256k1_ecdsa_sig_verify -> secp256k1_ecmult -> secp256k1_ecmult_strauss_wnaf.

  • DBL same as in ECDH DERIVE. Two formulas for addition are implemented. For the generator part, same addition as in Keygen is used. For public key, the following:

    assume iZ2 = 1/Z2
az = Z_1*iZ2
Z12 = az^2
u1 = X1
u2 = X2*Z12
s1 = Y1
s2 = Y2*Z12
s2 = s2*az
h = -u1
h = h+u2
i = -s2
i = i+s1
Z3 = Z1*h
h2 = h^2
h2 = -h2
h3 = h2*h
t = u1*h2
X3 = i^2
X3 = X3+h3
X3 = X3+t
X3 = X3+t
t = t+X3
Y3 = t*i
h3 = h3*s1
Y3 = Y3+h3

  • Before the addition the Jacobian coordinates are mapped to an isomorphic curve.

Nettle

Version: 3.9.1
Repository: https://git.lysator.liu.se/nettle/nettle
Docs: https://www.lysator.liu.se/~nisse/nettle/nettle.html

Primitives

ECDSA on P192, P224, P256, P384 and P521, also EdDSA on Curve25519, Curve448.

Pippenger parameters

Curve

K

C

P192

8

6

P224

16

7

P256

11

6

P384

32

6

P521

44

6

Curve25519

11

6

ECDSA

KeyGen:
Sign:

  • Short-Weierstrass

  • Pippenger via ecc_ecdsa_sign -> ecc_mul_g.

  • Same as KeyGen.

Verify:

Ed25519

KeyGen:
Sign:

  • Twisted Edwards

  • Pippenger via ed25519_sha512_sign -> _eddsa_sign -> ecc_curve.mul_g -> ecc_mul_g_eh.

  • Same as KeyGen.

Verify:

  • Twisted Edwards

  • Pippenger and 4-bit Fixed Window via ed25519_sha512_verify -> _eddsa_verify -> ecc_curve.mul + ecc_curve.mul_g.

  • Same as KeyGen.

mbedTLS

Version: 3.5.1
Repository: https://github.com/Mbed-TLS/mbedtls
Docs: https://mbed-tls.readthedocs.io/en/latest/index.html

Primitives

ECDH and ECDSA on P192, P224, P256, P384, P521 (their R and K variants) as well as x25519 and x448.

x25519 has two implementations, and mbedTLS one (described below) and one from Project Everest.

ECDH

KeyGen:

  • Short-Weierstrass

  • Comb via mbedtls_ecdh_gen_public -> ecdh_gen_public_restartable -> mbedtls_ecp_mul_restartable -> ecp_mul_restartable_internal -> ecp_mul_comb. w = 5 for curves < 384 bits, then w = 6.

  • Jacobian coords with coordinate randomization.

  • add-gecc-322 [GECC]_ algorithm 3.22, dbl-1998-cmo-2. Also has alternative impl (_ALT).

Derive:

  • Short-Weierstrass

  • Comb via mbedtls_ecdh_compute_shared -> ecdh_compute_shared_restartable -> mbedtls_ecp_mul_restartable -> ecp_mul_restartable_internal -> ecp_mul_comb. w = 4 for curves < 384 bits, then w = 5. The width is smaller by 1 than the case when the generator point is used (in KeyGen).

  • Same coords and formulas as KeyGen.

ECDSA

KeyGen:

  • Short-Weierstrass

  • Comb via mbedtls_ecdsa_genkey -> mbedtls_ecp_gen_keypair -> mbedtls_ecp_gen_keypair_base -> mbedtls_ecp_mul -> mbedtls_ecp_mul_restartable -> ecp_mul_restartable_internal -> ecp_mul_comb.

  • Same as ECDH (KeyGen).

Sign:

  • Short-Weierstrass

  • Comb via mbedtls_ecdsa_sign -> mbedtls_ecdsa_sign_restartable -> mbedtls_ecp_mul_restartable -> ecp_mul_restartable_internal -> ecp_mul_comb.

  • Same as ECDH (KeyGen).

Verify:

  • Short-Weierstrass

  • Comb + Comb via mbedtls_ecdsa_verify -> mbedtls_ecdsa_verify_restartable -> mbedtls_ecp_muladd_restartable -> mbedtls_ecp_mul_shortcuts + mbedtls_ecp_mul_shortcuts -> ecp_mul_restartable_internal -> ecp_mul_comb.

  • Same as ECDH (KeyGen, Derive).

x25519

KeyGen:

  • Montgomery

  • Montgomery Ladder via mbedtls_ecdh_gen_public -> ecdh_gen_public_restartable -> mbedtls_ecp_mul_restartable -> ecp_mul_restartable_internal -> ecp_mul_mxz.

  • xz coords.

  • mladd-1987-m.

Derive:

  • Montgomery

  • Montgomery Ladder via mbedtls_ecdh_compute_shared -> ecdh_compute_shared_restartable -> mbedtls_ecp_mul_restartable -> ecp_mul_restartable_internal -> ecp_mul_mxz.

  • Same as KeyGen.

SunEC

Version: jdk-21-ga (JDK 21)
Repository: https://github.com/openjdk/jdk/
Docs:

Primitives

ECDH, ECDSA, x25519, Ed25519

P-256

The only special thing is the generator scalarmult, Secp256R1GeneratorMultiplier which is a Comb.

ECDH

KeyGen:

  • Short-Weierstrass

  • Fixed Window (width = 4) via ECKeyPairGenerator.generateKeyPair -> ECKeyPairGenerator.generateKeyPairImpl -> ECPrivateKeyImpl.calculatePublicKey -> ECOperations.multiply -> Default(PointMultiplier).pointMultiply

  • projective-3 coords

  • RCB-based formulas: add-sunec-v21, dbl-sunec-v21,

Derive:

  • Same as KeyGen.

ECDSA

Same as ECDH.

x25519

KeyGen:

  • Montgomery

  • Montgomery ladder

  • xz

  • Ladder formula from RFC 7748

Derive:

  • Same as KeyGen.

Ed25519

KeyGen:
Sign:

  • Same as KeyGen.

Verify:

  • Same as KeyGen.

Go

Version: go1.21.4
Repository: https://github.com/golang/go
Docs:

Primitives

ECDH, ECDSA over P-224, P-256, P-384 and P-521. Ed25519, X25519

ECDH

KeyGen:
Derive:

  • Short-Weierstrass

  • Fixed window (w=4) via ecdh -> ScalarMult.

  • Same formulas as in Keygen.

Also supports constant-time, 64-bit assembly implementation of P256 described in https://eprint.iacr.org/2013/816.pdf

ECDSA

KeyGen:

  • Same as ECDH KeyGen via ecdsa.go:GenerateKey -> generateNISTEC -> randomPoint -> ScalarBaseMult.

Sign:

  • Same as KeyGen via ecdsa.go:SignASN1 -> signNISTEC -> randomPoint -> ScalarBaseMult.

Verify:

  • Two separate scalar multiplications ScalarBaseMult (same as KeyGen) and ScalarMult (same as ECDH Derive) via ecdsa.go:VerifyASN1 -> verifyNISTEC.

X25519

KeyGen:

  • Montgomery

  • Ladder via privateKeyToPublicKey -> x25519ScalarMult.

  • xz

  • Unknown formula: ladd-go-1214

Derive:

  • Same as KeyGen via x25519.go:ecdh -> x25519ScalarMult.

Ed25519

KeyGen:

  • Twisted-Edwards

  • Pippenger’s signed 4-bit method with precomputation via ed25519.go:GenerateKey -> NewKeyFromSeed -> newKeyFromSeed -> ScalarBaseMult.

  • Extended coordinates mixed with y-x,y+x,2dxy coordinates

  • AddAffine (and similar SubAffine):

    YplusX.Add(&p.y, &p.x)
YminusX.Subtract(&p.y, &p.x)

PP.Multiply(&YplusX, &q.YplusX)
MM.Multiply(&YminusX, &q.YminusX)
TT2d.Multiply(&p.t, &q.T2d)

Z2.Add(&p.z, &p.z)

v.X.Subtract(&PP, &MM)
v.Y.Add(&PP, &MM)
v.Z.Add(&Z2, &TT2d)
v.T.Subtract(&Z2, &TT2d)
Sign:

  • Same as Keygen via ed25519.go: Sign -> sign ->  ScalarBaseMult.

Verify:

  • Bos-Coster method via ed25519.go: Verify -> verify -> VarTimeDoubleScalarBaseMult.

  • Same coordinates and formulas as in Keygen.

libgcrypt

Version: 1.10.2
Repository: https://git.gnupg.org/
Docs: https://gnupg.org/documentation/manuals/gcrypt/

Primitives

Supports ECDH, X25519 and EdDSA on C25519, X448, Ed25519, Ed448, NIST curves, Brainpool curves and secp256k1. Also supports GOST and SM2 signatures.

ECDH

KeyGen:
Derive:

  • Same as Keygen via gcry_pk_encrypt -> _gcry_pk_encrypt -> generate -> ecc_encrypt_raw -> _gcry_mpi_ec_mul_point.

ECDSA

Keygen:

  • Same as ECDH.

Sign:

  • Same as Keygen via gcry_ecc_ecdsa_sign -> _gcry_ecc_ecdsa_sign -> _gcry_mpi_ec_mul_point.

Verify:

  • Two separate scalar multiplications via gcry_ecc_ecdsa_verify -> _gcry_ecc_ecdsa_verify.

EdDSA

Keygen:
Sign:

  • Same as Keygen via gcry_ecc_eddsa_sign -> _gcry_ecc_eddsa_sign -> _gcry_mpi_ec_mul_point.

Verify:

  • Two separate scalar multiplications via gcry_ecc_eddsa_verify -> _gcry_ecc_eddsa_verify.

X25519

KeyGen:

  • Montgomery

  • Montgomery ladder via gcry_pk_genkey -> _gcry_pk_genkey -> generate -> ecc_generate -> nist_generate_key -> _gcry_mpi_ec_mul_point.

  • xz coordinates with a shuffled version of ladd-1987-m-3

Derive:

  • Same as Keygen via gcry_pk_encrypt -> _gcry_pk_encrypt -> generate -> ecc_encrypt_raw -> _gcry_mpi_ec_mul_point.

BearSSL

Version: v0.6
Repository: https://bearssl.org/gitweb/?p=BearSSL;a=summary
Docs: https://bearssl.org/index.html

Primitives

Supports SECG prime field curves, as well as Brainpool and Curve25519, Curve448. Has API functions for ECDSA, but does ECDH only implicitly in its TLS implementation (no public API exposed). Unclear whether Ed25519 is supported.

ECDH

KeyGen:

  • Short-Weierstrass

  • (width=2) Fixed Window via br_ec_compute_pub -> impl.mulgen -> impl.mul, but (width=4) Fixed Window via br_ec_compute_pub -> impl.mulgen for special (P-256) curves.

  • Jacobian coordinates

  • Unknown formulas: add-bearssl-v06, dbl-bearssl-v06,

Derive:

  • Short-Weierstrass

  • (width=2) Fixed Window via impl.mul.

  • Coordinates and formulas same as in KeyGen.

ECDSA

KeyGen:

  • Same as ECDH.

Sign:

  • Short-Weierstrass

  • (width=2) Fixed Window via br_ecdsa_*_sign_raw -> impl.mulgen -> impl.mul, but (width=4) Fixed Window via br_ecdsa_*_sign_raw -> impl.mulgen for special (P-256) curves.

  • Coordinates and formulas same as in KeyGen.

Verify:

  • Short-Weierstrass

  • Simple scalarmult then add via br_ecdsa_*_verify_raw -> impl.muladd -> impl.mul + add

  • Coordinates and formulas same as in KeyGen.

x25519

KeyGen:

  • Montgomery

  • Montgomery ladder via br_ec_compute_pub -> impl.mulgen -> impl.mul.

  • xz coordinates

  • ladd-rfc7748

Derive:

  • Same as KeyGen.