Add field inversion for P-521

ECDSA sign about 10% faster, ECDSA verify and ECDH about 5% faster.

1 files changed, 68 insertions, 0 deletions

diff --git a/src/lib/pubkey/ec_group/curve_gfp.cpp b/src/lib/pubkey/ec_group/curve_gfp.cpp
index abd541912..b9ff7caaa 100644
--- a/src/lib/pubkey/ec_group/curve_gfp.cpp
+++ b/src/lib/pubkey/ec_group/curve_gfp.cpp
@@ -458,8 +458,76 @@ class CurveGFp_P521 final : public CurveGFp_NIST
       const BigInt& get_p() const override { return prime_p521(); }
    private:
       void redc(BigInt& x, secure_vector<word>& ws) const override { redc_p521(x, ws); }
+      BigInt invert_element(const BigInt& x, secure_vector<word>& ws) const override;
    };
 
+BigInt CurveGFp_P521::invert_element(const BigInt& x, secure_vector<word>& ws) const
+   {
+   BigInt r;
+   BigInt rl;
+   BigInt a7;
+   BigInt tmp;
+
+   curve_sqr(r, x, ws);
+   curve_mul_tmp(r, x, tmp, ws);
+
+   curve_sqr_tmp(r, tmp, ws);
+   curve_mul_tmp(r, x, tmp, ws);
+
+   rl = r;
+
+   for(size_t i = 0; i != 3; ++i)
+      curve_sqr_tmp(r, tmp, ws);
+   curve_mul_tmp(r, rl, tmp, ws);
+
+   curve_sqr_tmp(r, tmp, ws);
+   curve_mul_tmp(r, x, tmp, ws);
+   a7 = r; // need this value later
+
+   curve_sqr_tmp(r, tmp, ws);
+   curve_mul_tmp(r, x, tmp, ws);
+
+   rl = r;
+   for(size_t i = 0; i != 8; ++i)
+      curve_sqr_tmp(r, tmp, ws);
+   curve_mul_tmp(r, rl, tmp, ws);
+
+   rl = r;
+   for(size_t i = 0; i != 16; ++i)
+      curve_sqr_tmp(r, tmp, ws);
+   curve_mul_tmp(r, rl, tmp, ws);
+
+    rl = r;
+    for(size_t i = 0; i != 32; ++i)
+        curve_sqr_tmp(r, tmp, ws);
+    curve_mul_tmp(r, rl, tmp, ws);
+
+    rl = r;
+    for(size_t i = 0; i != 64; ++i)
+        curve_sqr_tmp(r, tmp, ws);
+    curve_mul_tmp(r, rl, tmp, ws);
+
+    rl = r;
+    for(size_t i = 0; i != 128; ++i)
+        curve_sqr_tmp(r, tmp, ws);
+    curve_mul_tmp(r, rl, tmp, ws);
+
+    rl = r;
+    for(size_t i = 0; i != 256; ++i)
+        curve_sqr_tmp(r, tmp, ws);
+    curve_mul_tmp(r, rl, tmp, ws);
+
+    for(size_t i = 0; i != 7; ++i)
+        curve_sqr_tmp(r, tmp, ws);
+    curve_mul_tmp(r, a7, 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;
+   }
+
 }
 
 std::shared_ptr<CurveGFp_Repr>