Botan::EC_Point_Base_Point_Precompute Class Reference

#include <point_mul.h>

Public Member Functions
	EC_Point_Base_Point_Precompute (const EC_Point &base_point, const Modular_Reducer &mod_order)
EC_Point	mul (const BigInt &k, RandomNumberGenerator &rng, const BigInt &group_order, std::vector< BigInt > &ws) const

Detailed Description

Definition at line 16 of file point_mul.h.

Constructor & Destructor Documentation

EC_Point_Base_Point_Precompute()

Botan::EC_Point_Base_Point_Precompute::EC_Point_Base_Point_Precompute	(	const EC_Point &	base_point,
		const Modular_Reducer &	mod_order )

Definition at line 29 of file point_mul.cpp.

                                                                                                                     :
      m_base_point(base), m_mod_order(mod_order), m_p_words(base.get_curve().get_p().sig_words()) {
   std::vector<BigInt> ws(EC_Point::WORKSPACE_SIZE);
 
   const size_t p_bits = base.get_curve().get_p().bits();
 
   /*
   * Some of the curves (eg secp160k1) have an order slightly larger than
   * the size of the prime modulus. In all cases they are at most 1 bit
   * longer. The +1 compensates for this.
   */
   const size_t T_bits = round_up(p_bits + blinding_size(mod_order.get_modulus()) + 1, WINDOW_BITS) / WINDOW_BITS;
 
   std::vector<EC_Point> T(WINDOW_SIZE * T_bits);
 
   EC_Point g = base;
   EC_Point g2, g4;
 
   for(size_t i = 0; i != T_bits; i++) {
      g2 = g;
      g2.mult2(ws);
      g4 = g2;
      g4.mult2(ws);
 
      T[7 * i + 0] = g;
      T[7 * i + 1] = std::move(g2);
      T[7 * i + 2] = T[7 * i + 1].plus(T[7 * i + 0], ws);  // g2+g
      T[7 * i + 3] = g4;
      T[7 * i + 4] = T[7 * i + 3].plus(T[7 * i + 0], ws);  // g4+g
      T[7 * i + 5] = T[7 * i + 3].plus(T[7 * i + 1], ws);  // g4+g2
      T[7 * i + 6] = T[7 * i + 3].plus(T[7 * i + 2], ws);  // g4+g2+g
 
      g.swap(g4);
      g.mult2(ws);
   }
 
   EC_Point::force_all_affine(T, ws[0].get_word_vector());
 
   m_W.resize(T.size() * 2 * m_p_words);
 
   word* p = &m_W[0];
   for(size_t i = 0; i != T.size(); ++i) {
      T[i].get_x().encode_words(p, m_p_words);
      p += m_p_words;
      T[i].get_y().encode_words(p, m_p_words);
      p += m_p_words;
   }
}

References Botan::BigInt::bits(), Botan::EC_Point::force_all_affine(), Botan::EC_Point::get_curve(), Botan::Modular_Reducer::get_modulus(), Botan::CurveGFp::get_p(), Botan::EC_Point::mult2(), Botan::EC_Point::plus(), Botan::round_up(), Botan::EC_Point::swap(), T, and Botan::EC_Point::WORKSPACE_SIZE.

Member Function Documentation

mul()

EC_Point Botan::EC_Point_Base_Point_Precompute::mul	(	const BigInt &	k,
		RandomNumberGenerator &	rng,
		const BigInt &	group_order,
		std::vector< BigInt > &	ws ) const

Definition at line 78 of file point_mul.cpp.

                                                                          {
   if(k.is_negative()) {
      throw Invalid_Argument("EC_Point_Base_Point_Precompute scalar must be positive");
   }
 
   // Instead of reducing k mod group order should we alter the mask size??
   BigInt scalar = m_mod_order.reduce(k);
 
   if(rng.is_seeded()) {
      // Choose a small mask m and use k' = k + m*order (Coron's 1st countermeasure)
      const BigInt mask(rng, blinding_size(group_order));
      scalar += group_order * mask;
   } else {
      /*
      When we don't have an RNG we cannot do scalar blinding. Instead use the
      same trick as OpenSSL and add one or two copies of the order to normalize
      the length of the scalar at order.bits()+1. This at least ensures the loop
      bound does not leak information about the high bits of the scalar.
      */
      scalar += group_order;
      if(scalar.bits() == group_order.bits()) {
         scalar += group_order;
      }
      BOTAN_DEBUG_ASSERT(scalar.bits() == group_order.bits() + 1);
   }
 
   const size_t windows = round_up(scalar.bits(), WINDOW_BITS) / WINDOW_BITS;
 
   const size_t elem_size = 2 * m_p_words;
 
   BOTAN_ASSERT(windows <= m_W.size() / (3 * elem_size), "Precomputed sufficient values for scalar mult");
 
   EC_Point R = m_base_point.zero();
 
   if(ws.size() < EC_Point::WORKSPACE_SIZE) {
      ws.resize(EC_Point::WORKSPACE_SIZE);
   }
 
   // the precomputed multiples are not secret so use std::vector
   std::vector<word> Wt(elem_size);
 
   for(size_t i = 0; i != windows; ++i) {
      const size_t window = windows - i - 1;
      const size_t base_addr = (WINDOW_SIZE * window) * elem_size;
 
      const word w = scalar.get_substring(WINDOW_BITS * window, WINDOW_BITS);
 
      const auto w_is_1 = CT::Mask<word>::is_equal(w, 1);
      const auto w_is_2 = CT::Mask<word>::is_equal(w, 2);
      const auto w_is_3 = CT::Mask<word>::is_equal(w, 3);
      const auto w_is_4 = CT::Mask<word>::is_equal(w, 4);
      const auto w_is_5 = CT::Mask<word>::is_equal(w, 5);
      const auto w_is_6 = CT::Mask<word>::is_equal(w, 6);
      const auto w_is_7 = CT::Mask<word>::is_equal(w, 7);
 
      for(size_t j = 0; j != elem_size; ++j) {
         const word w1 = w_is_1.if_set_return(m_W[base_addr + 0 * elem_size + j]);
         const word w2 = w_is_2.if_set_return(m_W[base_addr + 1 * elem_size + j]);
         const word w3 = w_is_3.if_set_return(m_W[base_addr + 2 * elem_size + j]);
         const word w4 = w_is_4.if_set_return(m_W[base_addr + 3 * elem_size + j]);
         const word w5 = w_is_5.if_set_return(m_W[base_addr + 4 * elem_size + j]);
         const word w6 = w_is_6.if_set_return(m_W[base_addr + 5 * elem_size + j]);
         const word w7 = w_is_7.if_set_return(m_W[base_addr + 6 * elem_size + j]);
 
         Wt[j] = w1 | w2 | w3 | w4 | w5 | w6 | w7;
      }
 
      R.add_affine(&Wt[0], m_p_words, &Wt[m_p_words], m_p_words, ws);
 
      if(i == 0 && rng.is_seeded()) {
         /*
         * Since we start with the top bit of the exponent we know the
         * first window must have a non-zero element, and thus R is
         * now a point other than the point at infinity.
         */
         BOTAN_DEBUG_ASSERT(w != 0);
         R.randomize_repr(rng, ws[0].get_word_vector());
      }
   }
 
   BOTAN_DEBUG_ASSERT(R.on_the_curve());
 
   return R;
}

References Botan::EC_Point::add_affine(), Botan::BigInt::bits(), BOTAN_ASSERT, BOTAN_DEBUG_ASSERT, Botan::BigInt::get_substring(), Botan::CT::Mask< T >::is_equal(), Botan::BigInt::is_negative(), Botan::RandomNumberGenerator::is_seeded(), Botan::EC_Point::on_the_curve(), Botan::EC_Point::randomize_repr(), Botan::Modular_Reducer::reduce(), Botan::round_up(), Botan::EC_Point::WORKSPACE_SIZE, and Botan::EC_Point::zero().

---

The documentation for this class was generated from the following files:

• src/lib/pubkey/ec_group/point_mul.h
• src/lib/pubkey/ec_group/point_mul.cpp