Botan::PointGFp_Base_Point_Precompute Class Reference

#include <point_mul.h>

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

Detailed Description

Definition at line 16 of file point_mul.h.

Constructor & Destructor Documentation

Botan::PointGFp_Base_Point_Precompute::PointGFp_Base_Point_Precompute	(	const PointGFp &	base_point,
		const Modular_Reducer &	mod_order
	)

Definition at line 50 of file point_mul.cpp.

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

                                                                                                 :
   m_base_point(base),
   m_mod_order(mod_order),
   m_p_words(base.get_curve().get_p().sig_words()),
   m_T_size(base.get_curve().get_p().bits() + PointGFp_SCALAR_BLINDING_BITS + 1)
   {
   std::vector<BigInt> ws(PointGFp::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 + PointGFp_SCALAR_BLINDING_BITS + 1, WINDOW_BITS) / WINDOW_BITS;

   std::vector<PointGFp> T(WINDOW_SIZE*T_bits);

   PointGFp g = base;
   PointGFp 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);
      }

   PointGFp::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;
      }
   }

Member Function Documentation

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

Definition at line 106 of file point_mul.cpp.

References Botan::PointGFp::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::PointGFp::on_the_curve(), Botan::PointGFp::randomize_repr(), Botan::Modular_Reducer::reduce(), Botan::round_up(), Botan::PointGFp::WORKSPACE_SIZE, and Botan::PointGFp::zero().

   {
   if(k.is_negative())
      throw Invalid_Argument("PointGFp_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, PointGFp_SCALAR_BLINDING_BITS);
      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");

   PointGFp R = m_base_point.zero();

   if(ws.size() < PointGFp::WORKSPACE_SIZE)
      ws.resize(PointGFp::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;
   }

---

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