Add Fermat based inversion of P-384 field elements

Cuts about 100K cycles from the inversion, improving ECDSA sign by 10%
and ECDH by ~2%

Addition chain from https://briansmith.org/ecc-inversion-addition-chains-01

GH #1479

1 files changed, 72 insertions, 0 deletions

diff --git a/src/lib/pubkey/ec_group/curve_gfp.cpp b/src/lib/pubkey/ec_group/curve_gfp.cpp
index b9ff7caaa..112213d6c 100644
--- a/src/lib/pubkey/ec_group/curve_gfp.cpp
+++ b/src/lib/pubkey/ec_group/curve_gfp.cpp
@@ -444,8 +444,80 @@ class CurveGFp_P384 final : public CurveGFp_NIST
       const BigInt& get_p() const override { return prime_p384(); }
    private:
       void redc(BigInt& x, secure_vector<word>& ws) const override { redc_p384(x, ws); }
+      BigInt invert_element(const BigInt& x, secure_vector<word>& ws) const override;
    };
 
+BigInt CurveGFp_P384::invert_element(const BigInt& x, secure_vector<word>& ws) const
+   {
+   BigInt r, x2, x3, x15, x30, tmp, rl;
+
+   r = x;
+   curve_sqr_tmp(r, tmp, ws);
+   curve_mul_tmp(r, x, tmp, ws);
+   x2 = r;
+
+   curve_sqr_tmp(r, tmp, ws);
+   curve_mul_tmp(r, x, tmp, ws);
+
+   x3 = r;
+
+   for(size_t i = 0; i != 3; ++i)
+      curve_sqr_tmp(r, tmp, ws);
+   curve_mul_tmp(r, x3, tmp, ws);
+
+   rl = r;
+   for(size_t i = 0; i != 6; ++i)
+      curve_sqr_tmp(r, tmp, ws);
+   curve_mul_tmp(r, rl, tmp, ws);
+
+   for(size_t i = 0; i != 3; ++i)
+      curve_sqr_tmp(r, tmp, ws);
+   curve_mul_tmp(r, x3, tmp, ws);
+
+   x15 = r;
+   for(size_t i = 0; i != 15; ++i)
+      curve_sqr_tmp(r, tmp, ws);
+   curve_mul_tmp(r, x15, tmp, ws);
+
+   x30 = r;
+   for(size_t i = 0; i != 30; ++i)
+      curve_sqr_tmp(r, tmp, ws);
+   curve_mul_tmp(r, x30, tmp, ws);
+
+   rl = r;
+   for(size_t i = 0; i != 60; ++i)
+      curve_sqr_tmp(r, tmp, ws);
+   curve_mul_tmp(r, rl, tmp, ws);
+
+   rl = r;
+   for(size_t i = 0; i != 120; ++i)
+      curve_sqr_tmp(r, tmp, ws);
+   curve_mul_tmp(r, rl, tmp, ws);
+
+   for(size_t i = 0; i != 15; ++i)
+      curve_sqr_tmp(r, tmp, ws);
+   curve_mul_tmp(r, x15, tmp, ws);
+
+   for(size_t i = 0; i != 31; ++i)
+      curve_sqr_tmp(r, tmp, ws);
+   curve_mul_tmp(r, x30, tmp, ws);
+
+   for(size_t i = 0; i != 2; ++i)
+      curve_sqr_tmp(r, tmp, ws);
+   curve_mul_tmp(r, x2, tmp, ws);
+
+   for(size_t i = 0; i != 94; ++i)
+      curve_sqr_tmp(r, tmp, ws);
+   curve_mul_tmp(r, x30, tmp, ws);
+
+   for(size_t i = 0; i != 2; ++i)
+      curve_sqr_tmp(r, tmp, ws);
+
+   curve_mul_tmp(r, x, tmp, ws);
+
+   return r;
+   }
+
 #endif
 
 /**