Precompute for multiexponentation when verifying ECC signatures

ECDSA already did this. Improves repeated ECGDSA, ECKCDSA, SM2,
and GOST signature verification by 10-15%

5 files changed, 22 insertions, 15 deletions

diff --git a/news.rst b/news.rst
index 6a86833ce..f970bd8f4 100644
--- a/news.rst
+++ b/news.rst
@@ -13,6 +13,9 @@ Version 2.7.0, Not Yet Released
 * Optimized elliptic point doubling for curves with an ``a`` parameter
   of zero or negative three. (GH #1534)
 
+* Improved performance of signature verification in ECGDSA, ECKCDSA,
+  SM2 and GOST by 10-15%.
+
 * Allow the year to be up to 2200 in ASN.1 time objects. Previously this
   was limited to 2100. (GH #1536)
 
diff --git a/src/lib/pubkey/ecgdsa/ecgdsa.cpp b/src/lib/pubkey/ecgdsa/ecgdsa.cpp
index 062bb524d..192d999a8 100644
--- a/src/lib/pubkey/ecgdsa/ecgdsa.cpp
+++ b/src/lib/pubkey/ecgdsa/ecgdsa.cpp
@@ -10,6 +10,7 @@
 #include <botan/keypair.h>
 #include <botan/reducer.h>
 #include <botan/internal/pk_ops_impl.h>
+#include <botan/internal/point_mul.h>
 
 namespace Botan {
 
@@ -86,7 +87,7 @@ class ECGDSA_Verification_Operation final : public PK_Ops::Verification_with_EMS
                                    const std::string& emsa) :
          PK_Ops::Verification_with_EMSA(emsa),
          m_group(ecgdsa.domain()),
-         m_public_point(ecgdsa.public_point())
+         m_gy_mul(m_group.get_base_point(), ecgdsa.public_point())
          {
          }
 
@@ -98,7 +99,7 @@ class ECGDSA_Verification_Operation final : public PK_Ops::Verification_with_EMS
                   const uint8_t sig[], size_t sig_len) override;
    private:
       const EC_Group m_group;
-      const PointGFp& m_public_point;
+      const PointGFp_Multi_Point_Precompute m_gy_mul;
    };
 
 bool ECGDSA_Verification_Operation::verify(const uint8_t msg[], size_t msg_len,
@@ -119,7 +120,7 @@ bool ECGDSA_Verification_Operation::verify(const uint8_t msg[], size_t msg_len,
 
    const BigInt u1 = m_group.multiply_mod_order(e, w);
    const BigInt u2 = m_group.multiply_mod_order(s, w);
-   const PointGFp R = m_group.point_multiply(u1, m_public_point, u2);
+   const PointGFp R = m_gy_mul.multi_exp(u1, u2);
 
    if(R.is_zero())
       return false;
diff --git a/src/lib/pubkey/eckcdsa/eckcdsa.cpp b/src/lib/pubkey/eckcdsa/eckcdsa.cpp
index f16fb027e..90716228a 100644
--- a/src/lib/pubkey/eckcdsa/eckcdsa.cpp
+++ b/src/lib/pubkey/eckcdsa/eckcdsa.cpp
@@ -8,6 +8,7 @@
 
 #include <botan/eckcdsa.h>
 #include <botan/internal/pk_ops_impl.h>
+#include <botan/internal/point_mul.h>
 #include <botan/keypair.h>
 #include <botan/reducer.h>
 #include <botan/emsa.h>
@@ -113,11 +114,11 @@ class ECKCDSA_Verification_Operation final : public PK_Ops::Verification_with_EM
                                    const std::string& emsa) :
          PK_Ops::Verification_with_EMSA(emsa),
          m_group(eckcdsa.domain()),
-         m_public_point(eckcdsa.public_point()),
+         m_gy_mul(m_group.get_base_point(), eckcdsa.public_point()),
          m_prefix()
          {
-         const BigInt public_point_x = m_public_point.get_affine_x();
-         const BigInt public_point_y = m_public_point.get_affine_y();
+         const BigInt public_point_x = eckcdsa.public_point().get_affine_x();
+         const BigInt public_point_y = eckcdsa.public_point().get_affine_y();
 
          m_prefix.resize(public_point_x.bytes() + public_point_y.bytes());
          public_point_x.binary_encode(&m_prefix[0]);
@@ -136,7 +137,7 @@ class ECKCDSA_Verification_Operation final : public PK_Ops::Verification_with_EM
                   const uint8_t sig[], size_t sig_len) override;
    private:
       const EC_Group m_group;
-      const PointGFp& m_public_point;
+      const PointGFp_Multi_Point_Precompute m_gy_mul;
       secure_vector<uint8_t> m_prefix;
    };
 
@@ -169,7 +170,7 @@ bool ECKCDSA_Verification_Operation::verify(const uint8_t msg[], size_t,
    BigInt w(r_xor_e.data(), r_xor_e.size());
    w = m_group.mod_order(w);
 
-   const PointGFp q = m_group.point_multiply(w, m_public_point, s);
+   const PointGFp q = m_gy_mul.multi_exp(w, s);
    const BigInt q_x = q.get_affine_x();
    secure_vector<uint8_t> c(q_x.bytes());
    q_x.binary_encode(c.data());
diff --git a/src/lib/pubkey/gost_3410/gost_3410.cpp b/src/lib/pubkey/gost_3410/gost_3410.cpp
index 0fcca1b8d..b0c94fb7e 100644
--- a/src/lib/pubkey/gost_3410/gost_3410.cpp
+++ b/src/lib/pubkey/gost_3410/gost_3410.cpp
@@ -9,6 +9,7 @@
 
 #include <botan/gost_3410.h>
 #include <botan/internal/pk_ops_impl.h>
+#include <botan/internal/point_mul.h>
 #include <botan/reducer.h>
 #include <botan/der_enc.h>
 #include <botan/ber_dec.h>
@@ -151,7 +152,7 @@ class GOST_3410_Verification_Operation final : public PK_Ops::Verification_with_
                                        const std::string& emsa) :
          PK_Ops::Verification_with_EMSA(emsa),
          m_group(gost.domain()),
-         m_public_point(gost.public_point())
+         m_gy_mul(m_group.get_base_point(), gost.public_point())
          {}
 
       size_t max_input_bits() const override { return m_group.get_order_bits(); }
@@ -162,7 +163,7 @@ class GOST_3410_Verification_Operation final : public PK_Ops::Verification_with_
                   const uint8_t sig[], size_t sig_len) override;
    private:
       const EC_Group m_group;
-      const PointGFp& m_public_point;
+      const PointGFp_Multi_Point_Precompute m_gy_mul;
    };
 
 bool GOST_3410_Verification_Operation::verify(const uint8_t msg[], size_t msg_len,
@@ -189,7 +190,7 @@ bool GOST_3410_Verification_Operation::verify(const uint8_t msg[], size_t msg_le
    const BigInt z1 = m_group.multiply_mod_order(s, v);
    const BigInt z2 = m_group.multiply_mod_order(-r, v);
 
-   const PointGFp R = m_group.point_multiply(z1, m_public_point, z2);
+   const PointGFp R = m_gy_mul.multi_exp(z1, z2);
 
    if(R.is_zero())
      return false;
diff --git a/src/lib/pubkey/sm2/sm2.cpp b/src/lib/pubkey/sm2/sm2.cpp
index 4b5610c85..95fe28f14 100644
--- a/src/lib/pubkey/sm2/sm2.cpp
+++ b/src/lib/pubkey/sm2/sm2.cpp
@@ -8,6 +8,7 @@
 
 #include <botan/sm2.h>
 #include <botan/internal/pk_ops_impl.h>
+#include <botan/internal/point_mul.h>
 #include <botan/numthry.h>
 #include <botan/keypair.h>
 #include <botan/hash.h>
@@ -136,11 +137,11 @@ class SM2_Verification_Operation final : public PK_Ops::Verification
                                  const std::string& ident,
                                  const std::string& hash) :
          m_group(sm2.domain()),
-         m_public_point(sm2.public_point()),
+         m_gy_mul(m_group.get_base_point(), sm2.public_point()),
          m_hash(HashFunction::create_or_throw(hash))
          {
          // ZA=H256(ENTLA || IDA || a || b || xG || yG || xA || yA)
-         m_za = sm2_compute_za(*m_hash, ident, m_group, m_public_point);
+         m_za = sm2_compute_za(*m_hash, ident, m_group, sm2.public_point());
          m_hash->update(m_za);
          }
 
@@ -152,7 +153,7 @@ class SM2_Verification_Operation final : public PK_Ops::Verification
       bool is_valid_signature(const uint8_t sig[], size_t sig_len) override;
    private:
       const EC_Group m_group;
-      const PointGFp& m_public_point;
+      const PointGFp_Multi_Point_Precompute m_gy_mul;
       std::vector<uint8_t> m_za;
       std::unique_ptr<HashFunction> m_hash;
    };
@@ -178,7 +179,7 @@ bool SM2_Verification_Operation::is_valid_signature(const uint8_t sig[], size_t
    if(t == 0)
       return false;
 
-   const PointGFp R = m_group.point_multiply(s, m_public_point, t);
+   const PointGFp R = m_gy_mul.multi_exp(s, t);
 
    // ???
    if(R.is_zero())