11531243697

Committed 26 Oct 2024 10:56AM UTC coverage: 91.133% (-0.003%) from 91.136%

Build # 11531243697

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #4408 from randombit/jack/odd-blinding

When scalar blinding use an odd blinding factor

Run Details

91076 of 99937 relevant lines covered (91.13%)

9383597.46 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

93.94

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

/*
* (C) 2015,2018 Jack Lloyd
*
* Botan is released under the Simplified BSD License (see license.txt)
*/

#include <botan/internal/point_mul.h>

#include <botan/reducer.h>
#include <botan/rng.h>
#include <botan/internal/ct_utils.h>
#include <botan/internal/rounding.h>

namespace Botan {

namespace {

size_t blinding_size(const BigInt& group_order) {
   return (group_order.bits() + 1) / 2;
}

BigInt blinding_mask(const BigInt& group_order, RandomNumberGenerator& rng) {
   BigInt mask(rng, blinding_size(group_order));
   mask.set_bit(0);
   return mask;
}

}  // namespace

EC_Point multi_exponentiate(const EC_Point& x, const BigInt& z1, const EC_Point& y, const BigInt& z2) {
   EC_Point_Multi_Point_Precompute xy_mul(x, y);
   return xy_mul.multi_exp(z1, z2);
}

EC_Point_Base_Point_Precompute::EC_Point_Base_Point_Precompute(const EC_Point& base, const Modular_Reducer& mod_order) :
      m_base_point(base), m_mod_order(mod_order), m_p_words(base.get_curve().get_p_words()) {
   std::vector<BigInt> ws(EC_Point::WORKSPACE_SIZE);

   const size_t order_bits = mod_order.get_modulus().bits();

   const size_t T_bits = round_up(order_bits + blinding_size(mod_order.get_modulus()), 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;
   }
}

EC_Point EC_Point_Base_Point_Precompute::mul(const BigInt& k,
                                             RandomNumberGenerator& rng,
                                             const BigInt& group_order,
                                             std::vector<BigInt>& ws) const {
   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)
      scalar += group_order * blinding_mask(group_order, rng);
   } 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;
}

EC_Point_Var_Point_Precompute::EC_Point_Var_Point_Precompute(const EC_Point& ipoint,
                                                             RandomNumberGenerator& rng,
                                                             std::vector<BigInt>& ws) :
      m_curve(ipoint.get_curve()), m_p_words(m_curve.get_p_words()), m_window_bits(4) {
   if(ws.size() < EC_Point::WORKSPACE_SIZE) {
      ws.resize(EC_Point::WORKSPACE_SIZE);
   }

   auto point = ipoint;
   point.randomize_repr(rng);

   std::vector<EC_Point> U(static_cast<size_t>(1) << m_window_bits);
   U[0] = point.zero();
   U[1] = point;

   for(size_t i = 2; i < U.size(); i += 2) {
      U[i] = U[i / 2].double_of(ws);
      U[i + 1] = U[i].plus(point, ws);
   }

   // Hack to handle Blinded_Point_Multiply
   if(rng.is_seeded()) {
      // Skipping zero point since it can't be randomized
      for(size_t i = 1; i != U.size(); ++i) {
         U[i].randomize_repr(rng);
      }
   }

   m_T.resize(U.size() * 3 * m_p_words);

   word* p = &m_T[0];
   for(size_t i = 0; i != U.size(); ++i) {
      U[i].get_x().encode_words(p, m_p_words);
      U[i].get_y().encode_words(p + m_p_words, m_p_words);
      U[i].get_z().encode_words(p + 2 * m_p_words, m_p_words);
      p += 3 * m_p_words;
   }
}

EC_Point EC_Point_Var_Point_Precompute::mul(const BigInt& k,
                                            RandomNumberGenerator& rng,
                                            const BigInt& group_order,
                                            std::vector<BigInt>& ws) const {
   if(k.is_negative()) {
      throw Invalid_Argument("EC_Point_Var_Point_Precompute scalar must be positive");
   }
   if(ws.size() < EC_Point::WORKSPACE_SIZE) {
      ws.resize(EC_Point::WORKSPACE_SIZE);
   }

   // Choose a small mask m and use k' = k + m*order (Coron's 1st countermeasure)
   const BigInt scalar = k + group_order * blinding_mask(group_order, rng);

   const size_t elem_size = 3 * m_p_words;
   const size_t window_elems = static_cast<size_t>(1) << m_window_bits;

   size_t windows = round_up(scalar.bits(), m_window_bits) / m_window_bits;
   EC_Point R(m_curve);
   secure_vector<word> e(elem_size);

   if(windows > 0) {
      windows--;

      const uint32_t w = scalar.get_substring(windows * m_window_bits, m_window_bits);

      clear_mem(e.data(), e.size());
      for(size_t i = 1; i != window_elems; ++i) {
         const auto wmask = CT::Mask<word>::is_equal(w, i);

         for(size_t j = 0; j != elem_size; ++j) {
            e[j] |= wmask.if_set_return(m_T[i * elem_size + j]);
         }
      }

      R.add(&e[0], m_p_words, &e[m_p_words], m_p_words, &e[2 * m_p_words], m_p_words, ws);

      /*
      Randomize after adding the first nibble as before the addition R
      is zero, and we cannot effectively randomize the point
      representation of the zero point.
      */
      R.randomize_repr(rng, ws[0].get_word_vector());
   }

   while(windows) {
      R.mult2i(m_window_bits, ws);

      const uint32_t w = scalar.get_substring((windows - 1) * m_window_bits, m_window_bits);

      clear_mem(e.data(), e.size());
      for(size_t i = 1; i != window_elems; ++i) {
         const auto wmask = CT::Mask<word>::is_equal(w, i);

         for(size_t j = 0; j != elem_size; ++j) {
            e[j] |= wmask.if_set_return(m_T[i * elem_size + j]);
         }
      }

      R.add(&e[0], m_p_words, &e[m_p_words], m_p_words, &e[2 * m_p_words], m_p_words, ws);

      windows--;
   }

   BOTAN_ASSERT_NOMSG(R.on_the_curve());

   return R;
}

EC_Point_Multi_Point_Precompute::EC_Point_Multi_Point_Precompute(const EC_Point& x, const EC_Point& y) {
   if(x.on_the_curve() == false || y.on_the_curve() == false) {
      m_M.push_back(x.zero());
      return;
   }

   std::vector<BigInt> ws(EC_Point::WORKSPACE_SIZE);

   EC_Point x2 = x;
   x2.mult2(ws);

   const EC_Point x3(x2.plus(x, ws));

   EC_Point y2 = y;
   y2.mult2(ws);

   const EC_Point y3(y2.plus(y, ws));

   m_M.reserve(15);

   m_M.push_back(x);
   m_M.push_back(x2);
   m_M.push_back(x3);

   m_M.push_back(y);
   m_M.push_back(y.plus(x, ws));
   m_M.push_back(y.plus(x2, ws));
   m_M.push_back(y.plus(x3, ws));

   m_M.push_back(y2);
   m_M.push_back(y2.plus(x, ws));
   m_M.push_back(y2.plus(x2, ws));
   m_M.push_back(y2.plus(x3, ws));

   m_M.push_back(y3);
   m_M.push_back(y3.plus(x, ws));
   m_M.push_back(y3.plus(x2, ws));
   m_M.push_back(y3.plus(x3, ws));

   bool no_infinity = true;
   for(auto& pt : m_M) {
      if(pt.is_zero()) {
         no_infinity = false;
      }
   }

   if(no_infinity) {
      EC_Point::force_all_affine(m_M, ws[0].get_word_vector());
   }

   m_no_infinity = no_infinity;
}

EC_Point EC_Point_Multi_Point_Precompute::multi_exp(const BigInt& z1, const BigInt& z2) const {
   if(m_M.size() == 1) {
      return m_M[0];
   }

   std::vector<BigInt> ws(EC_Point::WORKSPACE_SIZE);

   const size_t z_bits = round_up(std::max(z1.bits(), z2.bits()), 2);

   EC_Point H = m_M[0].zero();

   for(size_t i = 0; i != z_bits; i += 2) {
      if(i > 0) {
         H.mult2i(2, ws);
      }

      const uint32_t z1_b = z1.get_substring(z_bits - i - 2, 2);
      const uint32_t z2_b = z2.get_substring(z_bits - i - 2, 2);

      const uint32_t z12 = (4 * z2_b) + z1_b;

      // This function is not intended to be const time
      if(z12) {
         if(m_no_infinity) {
            H.add_affine(m_M[z12 - 1], ws);
         } else {
            H.add(m_M[z12 - 1], ws);
         }
      }
   }

   if(z1.is_negative() != z2.is_negative()) {
      H.negate();
   }

   return H;
}

}  // namespace Botan

1	/*
2	* (C) 2015,2018 Jack Lloyd
3	*
4	* Botan is released under the Simplified BSD License (see license.txt)
5	*/
6
7	#include <botan/internal/point_mul.h>
8
9	#include <botan/reducer.h>
10	#include <botan/rng.h>
11	#include <botan/internal/ct_utils.h>
12	#include <botan/internal/rounding.h>
13
14	namespace Botan {
15
16	namespace {
17
18	size_t blinding_size(const BigInt& group_order) {	9,090✔
19	return (group_order.bits() + 1) / 2;	252✔
20	}
21
22	BigInt blinding_mask(const BigInt& group_order, RandomNumberGenerator& rng) {	8,838✔
23	BigInt mask(rng, blinding_size(group_order));	8,838✔
24	mask.set_bit(0);	8,838✔
25	return mask;	8,838✔
26	}	×
27
28	} // namespace
29
30	EC_Point multi_exponentiate(const EC_Point& x, const BigInt& z1, const EC_Point& y, const BigInt& z2) {	×
31	EC_Point_Multi_Point_Precompute xy_mul(x, y);	×
32	return xy_mul.multi_exp(z1, z2);	×
33	}	×
34
35	EC_Point_Base_Point_Precompute::EC_Point_Base_Point_Precompute(const EC_Point& base, const Modular_Reducer& mod_order) :	252✔
36	m_base_point(base), m_mod_order(mod_order), m_p_words(base.get_curve().get_p_words()) {	252✔
37	std::vector<BigInt> ws(EC_Point::WORKSPACE_SIZE);	252✔
38
39	const size_t order_bits = mod_order.get_modulus().bits();	252✔
40
41	const size_t T_bits = round_up(order_bits + blinding_size(mod_order.get_modulus()), WINDOW_BITS) / WINDOW_BITS;	252✔
42
43	std::vector<EC_Point> T(WINDOW_SIZE * T_bits);	252✔
44
45	EC_Point g = base;	252✔
46	EC_Point g2, g4;	252✔
47
48	for(size_t i = 0; i != T_bits; i++) {	26,991✔
49	g2 = g;	26,739✔
50	g2.mult2(ws);	26,739✔
51	g4 = g2;	26,739✔
52	g4.mult2(ws);	26,739✔
53
54	T[7 * i + 0] = g;	26,739✔
55	T[7 * i + 1] = std::move(g2);	26,739✔
56	T[7 * i + 2] = T[7 * i + 1].plus(T[7 * i + 0], ws); // g2+g	80,217✔
57	T[7 * i + 3] = g4;	26,739✔
58	T[7 * i + 4] = T[7 * i + 3].plus(T[7 * i + 0], ws); // g4+g	80,217✔
59	T[7 * i + 5] = T[7 * i + 3].plus(T[7 * i + 1], ws); // g4+g2	80,217✔
60	T[7 * i + 6] = T[7 * i + 3].plus(T[7 * i + 2], ws); // g4+g2+g	80,217✔
61
62	g.swap(g4);	26,739✔
63	g.mult2(ws);	26,739✔
64	}
65
66	EC_Point::force_all_affine(T, ws[0].get_word_vector());	252✔
67
68	m_W.resize(T.size() * 2 * m_p_words);	252✔
69
70	word* p = &m_W[0];	252✔
71	for(size_t i = 0; i != T.size(); ++i) {	187,425✔
72	T[i].get_x().encode_words(p, m_p_words);	187,173✔
73	p += m_p_words;	187,173✔
74	T[i].get_y().encode_words(p, m_p_words);	187,173✔
75	p += m_p_words;	187,173✔
76	}
77	}	252✔
78
79	EC_Point EC_Point_Base_Point_Precompute::mul(const BigInt& k,	4,941✔
80	RandomNumberGenerator& rng,
81	const BigInt& group_order,
82	std::vector<BigInt>& ws) const {
83	if(k.is_negative()) {	4,941✔
84	throw Invalid_Argument("EC_Point_Base_Point_Precompute scalar must be positive");	×
85	}
86
87	// Instead of reducing k mod group order should we alter the mask size??
88	BigInt scalar = m_mod_order.reduce(k);	4,941✔
89
90	if(rng.is_seeded()) {	4,941✔
91	// Choose a small mask m and use k' = k + m*order (Coron's 1st countermeasure)
92	scalar += group_order * blinding_mask(group_order, rng);	14,796✔
93	} else {
94	/*
95	When we don't have an RNG we cannot do scalar blinding. Instead use the
96	same trick as OpenSSL and add one or two copies of the order to normalize
97	the length of the scalar at order.bits()+1. This at least ensures the loop
98	bound does not leak information about the high bits of the scalar.
99	*/
100	scalar += group_order;	9✔
101	if(scalar.bits() == group_order.bits()) {	9✔
102	scalar += group_order;	8✔
103	}
104	BOTAN_DEBUG_ASSERT(scalar.bits() == group_order.bits() + 1);	4,941✔
105	}
106
107	const size_t windows = round_up(scalar.bits(), WINDOW_BITS) / WINDOW_BITS;	4,941✔
108
109	const size_t elem_size = 2 * m_p_words;	4,941✔
110
111	BOTAN_ASSERT(windows <= m_W.size() / (3 * elem_size), "Precomputed sufficient values for scalar mult");	4,941✔
112
113	EC_Point R = m_base_point.zero();	4,941✔
114
115	if(ws.size() < EC_Point::WORKSPACE_SIZE) {	4,941✔
116	ws.resize(EC_Point::WORKSPACE_SIZE);	3,480✔
117	}
118
119	// the precomputed multiples are not secret so use std::vector
120	std::vector<word> Wt(elem_size);	4,941✔
121
122	for(size_t i = 0; i != windows; ++i) {	571,219✔
123	const size_t window = windows - i - 1;	566,278✔
124	const size_t base_addr = (WINDOW_SIZE * window) * elem_size;	566,278✔
125
126	const word w = scalar.get_substring(WINDOW_BITS * window, WINDOW_BITS);	566,278✔
127
128	const auto w_is_1 = CT::Mask<word>::is_equal(w, 1);	566,278✔
129	const auto w_is_2 = CT::Mask<word>::is_equal(w, 2);	566,278✔
130	const auto w_is_3 = CT::Mask<word>::is_equal(w, 3);	566,278✔
131	const auto w_is_4 = CT::Mask<word>::is_equal(w, 4);	566,278✔
132	const auto w_is_5 = CT::Mask<word>::is_equal(w, 5);	566,278✔
133	const auto w_is_6 = CT::Mask<word>::is_equal(w, 6);	566,278✔
134	const auto w_is_7 = CT::Mask<word>::is_equal(w, 7);	566,278✔
135
136	for(size_t j = 0; j != elem_size; ++j) {	5,378,774✔
137	const word w1 = w_is_1.if_set_return(m_W[base_addr + 0 * elem_size + j]);	4,812,496✔
138	const word w2 = w_is_2.if_set_return(m_W[base_addr + 1 * elem_size + j]);	4,812,496✔
139	const word w3 = w_is_3.if_set_return(m_W[base_addr + 2 * elem_size + j]);	4,812,496✔
140	const word w4 = w_is_4.if_set_return(m_W[base_addr + 3 * elem_size + j]);	4,812,496✔
141	const word w5 = w_is_5.if_set_return(m_W[base_addr + 4 * elem_size + j]);	4,812,496✔
142	const word w6 = w_is_6.if_set_return(m_W[base_addr + 5 * elem_size + j]);	4,812,496✔
143	const word w7 = w_is_7.if_set_return(m_W[base_addr + 6 * elem_size + j]);	4,812,496✔
144
145	Wt[j] = w1 \| w2 \| w3 \| w4 \| w5 \| w6 \| w7;	4,812,496✔
146	}
147
148	R.add_affine(&Wt[0], m_p_words, &Wt[m_p_words], m_p_words, ws);	566,278✔
149
150	if(i == 0 && rng.is_seeded()) {	566,278✔
151	/*
152	* Since we start with the top bit of the exponent we know the
153	* first window must have a non-zero element, and thus R is
154	* now a point other than the point at infinity.
155	*/
156	BOTAN_DEBUG_ASSERT(w != 0);	4,932✔
157	R.randomize_repr(rng, ws[0].get_word_vector());	4,932✔
158	}
159	}
160
161	BOTAN_DEBUG_ASSERT(R.on_the_curve());	4,941✔
162
163	return R;	9,882✔
164	}	9,882✔
165
166	EC_Point_Var_Point_Precompute::EC_Point_Var_Point_Precompute(const EC_Point& ipoint,	3,906✔
167	RandomNumberGenerator& rng,
168	std::vector<BigInt>& ws) :	3,906✔
169	m_curve(ipoint.get_curve()), m_p_words(m_curve.get_p_words()), m_window_bits(4) {	3,906✔
170	if(ws.size() < EC_Point::WORKSPACE_SIZE) {	3,906✔
171	ws.resize(EC_Point::WORKSPACE_SIZE);	3,337✔
172	}
173
174	auto point = ipoint;	3,906✔
175	point.randomize_repr(rng);	3,906✔
176
177	std::vector<EC_Point> U(static_cast<size_t>(1) << m_window_bits);	3,906✔
178	U[0] = point.zero();	7,812✔
179	U[1] = point;	3,906✔
180
181	for(size_t i = 2; i < U.size(); i += 2) {	31,248✔
182	U[i] = U[i / 2].double_of(ws);	82,026✔
183	U[i + 1] = U[i].plus(point, ws);	82,026✔
184	}
185
186	// Hack to handle Blinded_Point_Multiply
187	if(rng.is_seeded()) {	3,906✔
188	// Skipping zero point since it can't be randomized
189	for(size_t i = 1; i != U.size(); ++i) {	62,496✔
190	U[i].randomize_repr(rng);	58,590✔
191	}
192	}
193
194	m_T.resize(U.size() * 3 * m_p_words);	3,906✔
195
196	word* p = &m_T[0];	3,906✔
197	for(size_t i = 0; i != U.size(); ++i) {	66,402✔
198	U[i].get_x().encode_words(p, m_p_words);	62,496✔
199	U[i].get_y().encode_words(p + m_p_words, m_p_words);	62,496✔
200	U[i].get_z().encode_words(p + 2 * m_p_words, m_p_words);	62,496✔
201	p += 3 * m_p_words;	62,496✔
202	}
203	}	3,906✔
204
205	EC_Point EC_Point_Var_Point_Precompute::mul(const BigInt& k,	3,906✔
206	RandomNumberGenerator& rng,
207	const BigInt& group_order,
208	std::vector<BigInt>& ws) const {
209	if(k.is_negative()) {	3,906✔
210	throw Invalid_Argument("EC_Point_Var_Point_Precompute scalar must be positive");	×
211	}
212	if(ws.size() < EC_Point::WORKSPACE_SIZE) {	3,906✔
213	ws.resize(EC_Point::WORKSPACE_SIZE);	×
214	}
215
216	// Choose a small mask m and use k' = k + m*order (Coron's 1st countermeasure)
217	const BigInt scalar = k + group_order * blinding_mask(group_order, rng);	7,812✔
218
219	const size_t elem_size = 3 * m_p_words;	3,906✔
220	const size_t window_elems = static_cast<size_t>(1) << m_window_bits;	3,906✔
221
222	size_t windows = round_up(scalar.bits(), m_window_bits) / m_window_bits;	3,906✔
223	EC_Point R(m_curve);	3,906✔
224	secure_vector<word> e(elem_size);	3,906✔
225
226	if(windows > 0) {	3,906✔
227	windows--;	3,906✔
228
229	const uint32_t w = scalar.get_substring(windows * m_window_bits, m_window_bits);	3,906✔
230
231	clear_mem(e.data(), e.size());	3,906✔
232	for(size_t i = 1; i != window_elems; ++i) {	62,496✔
233	const auto wmask = CT::Mask<word>::is_equal(w, i);	58,590✔
234
235	for(size_t j = 0; j != elem_size; ++j) {	721,890✔
236	e[j] \|= wmask.if_set_return(m_T[i * elem_size + j]);	663,300✔
237	}
238	}
239
240	R.add(&e[0], m_p_words, &e[m_p_words], m_p_words, &e[2 * m_p_words], m_p_words, ws);	3,906✔
241
242	/*
243	Randomize after adding the first nibble as before the addition R
244	is zero, and we cannot effectively randomize the point
245	representation of the zero point.
246	*/
247	R.randomize_repr(rng, ws[0].get_word_vector());	3,906✔
248	}
249
250	while(windows) {	333,644✔
251	R.mult2i(m_window_bits, ws);	329,738✔
252
253	const uint32_t w = scalar.get_substring((windows - 1) * m_window_bits, m_window_bits);	329,738✔
254
255	clear_mem(e.data(), e.size());	329,738✔
256	for(size_t i = 1; i != window_elems; ++i) {	5,275,808✔
257	const auto wmask = CT::Mask<word>::is_equal(w, i);	4,946,070✔
258
259	for(size_t j = 0; j != elem_size; ++j) {	67,454,490✔
260	e[j] \|= wmask.if_set_return(m_T[i * elem_size + j]);	62,508,420✔
261	}
262	}
263
264	R.add(&e[0], m_p_words, &e[m_p_words], m_p_words, &e[2 * m_p_words], m_p_words, ws);	329,738✔
265
266	windows--;
267	}
268
269	BOTAN_ASSERT_NOMSG(R.on_the_curve());	3,906✔
270
271	return R;	3,906✔
272	}	7,812✔
273
274	EC_Point_Multi_Point_Precompute::EC_Point_Multi_Point_Precompute(const EC_Point& x, const EC_Point& y) {	1,177✔
275	if(x.on_the_curve() == false \|\| y.on_the_curve() == false) {	1,177✔
276	m_M.push_back(x.zero());	×
277	return;	×
278	}
279
280	std::vector<BigInt> ws(EC_Point::WORKSPACE_SIZE);	1,177✔
281
282	EC_Point x2 = x;	1,177✔
283	x2.mult2(ws);	1,177✔
284
285	const EC_Point x3(x2.plus(x, ws));	1,177✔
286
287	EC_Point y2 = y;	1,177✔
288	y2.mult2(ws);	1,177✔
289
290	const EC_Point y3(y2.plus(y, ws));	1,177✔
291
292	m_M.reserve(15);	1,177✔
293
294	m_M.push_back(x);	1,177✔
295	m_M.push_back(x2);	1,177✔
296	m_M.push_back(x3);	1,177✔
297
298	m_M.push_back(y);	1,177✔
299	m_M.push_back(y.plus(x, ws));	2,354✔
300	m_M.push_back(y.plus(x2, ws));	2,354✔
301	m_M.push_back(y.plus(x3, ws));	2,354✔
302
303	m_M.push_back(y2);	1,177✔
304	m_M.push_back(y2.plus(x, ws));	2,354✔
305	m_M.push_back(y2.plus(x2, ws));	2,354✔
306	m_M.push_back(y2.plus(x3, ws));	2,354✔
307
308	m_M.push_back(y3);	1,177✔
309	m_M.push_back(y3.plus(x, ws));	2,354✔
310	m_M.push_back(y3.plus(x2, ws));	2,354✔
311	m_M.push_back(y3.plus(x3, ws));	2,354✔
312
313	bool no_infinity = true;	1,177✔
314	for(auto& pt : m_M) {	18,832✔
315	if(pt.is_zero()) {	32,938✔
316	no_infinity = false;	18✔
317	}
318	}
319
320	if(no_infinity) {	1,177✔
321	EC_Point::force_all_affine(m_M, ws[0].get_word_vector());	1,171✔
322	}
323
324	m_no_infinity = no_infinity;	1,177✔
325	}	1,177✔
326
327	EC_Point EC_Point_Multi_Point_Precompute::multi_exp(const BigInt& z1, const BigInt& z2) const {	5,387✔
328	if(m_M.size() == 1) {	5,387✔
329	return m_M[0];	×
330	}
331
332	std::vector<BigInt> ws(EC_Point::WORKSPACE_SIZE);	5,387✔
333
334	const size_t z_bits = round_up(std::max(z1.bits(), z2.bits()), 2);	7,207✔
335
336	EC_Point H = m_M[0].zero();	5,387✔
337
338	for(size_t i = 0; i != z_bits; i += 2) {	631,345✔
339	if(i > 0) {	625,958✔
340	H.mult2i(2, ws);	620,571✔
341	}
342
343	const uint32_t z1_b = z1.get_substring(z_bits - i - 2, 2);	625,958✔
344	const uint32_t z2_b = z2.get_substring(z_bits - i - 2, 2);	625,958✔
345
346	const uint32_t z12 = (4 * z2_b) + z1_b;	625,958✔
347
348	// This function is not intended to be const time
349	if(z12) {	625,958✔
350	if(m_no_infinity) {	586,308✔
351	H.add_affine(m_M[z12 - 1], ws);	585,823✔
352	} else {
353	H.add(m_M[z12 - 1], ws);	485✔
354	}
355	}
356	}
357
358	if(z1.is_negative() != z2.is_negative()) {	5,387✔
359	H.negate();	×
360	}
361
362	return H;	5,387✔
363	}	5,387✔
364
365	} // namespace Botan

randombit / botan / 11531243697

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous