From 33f4ceb178adf291109926fefc679949c8037404 Mon Sep 17 00:00:00 2001
From: Jack Lloyd <jack@randombit.net>
Date: Thu, 19 Apr 2018 21:52:21 -0400
Subject: 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
---
 src/lib/pubkey/ec_group/curve_gfp.cpp | 72 +++++++++++++++++++++++++++++++++++
 1 file changed, 72 insertions(+)

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
 
 /**
-- 
cgit v1.2.3