5079590438

Committed 25 May 2023 12:28PM UTC coverage: 92.228% (+0.5%) from 91.723%

Build # 5079590438

Build Type

Pull #3502

github

Pull Request Pull Request #3502: Apply clang-format to the codebase

Run Details

75589 of 81959 relevant lines covered (92.23%)

12139530.51 hits per line

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

96.17

/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; }

}

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().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;
   }
}

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)
      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;
}

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

   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()) {
      BigInt& mask = ws[0];
      BigInt& mask2 = ws[1];
      BigInt& mask3 = ws[2];
      BigInt& new_x = ws[3];
      BigInt& new_y = ws[4];
      BigInt& new_z = ws[5];
      secure_vector<word>& tmp = ws[6].get_word_vector();

      const CurveGFp& curve = U[0].get_curve();

      const size_t p_bits = curve.get_p().bits();

      // Skipping zero point since it can't be randomized
      for(size_t i = 1; i != U.size(); ++i) {
         mask.randomize(rng, p_bits - 1, false);
         // Easy way of ensuring mask != 0
         mask.set_bit(0);

         curve.sqr(mask2, mask, tmp);
         curve.mul(mask3, mask, mask2, tmp);

         curve.mul(new_x, U[i].get_x(), mask2, tmp);
         curve.mul(new_y, U[i].get_y(), mask3, tmp);
         curve.mul(new_z, U[i].get_z(), mask, tmp);

         U[i].swap_coords(new_x, new_y, new_z);
      }
   }

   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 mask(rng, blinding_size(group_order), false);
   const BigInt scalar = k + group_order * mask;

   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_DEBUG_ASSERT(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;
}

}

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) { return (group_order.bits() + 1) / 2; }	860✔
19
20	}
21
22	EC_Point multi_exponentiate(const EC_Point& x, const BigInt& z1, const EC_Point& y, const BigInt& z2) {	×
23	EC_Point_Multi_Point_Precompute xy_mul(x, y);	×
24	return xy_mul.multi_exp(z1, z2);	×
25	}	×
26
27	EC_Point_Base_Point_Precompute::EC_Point_Base_Point_Precompute(const EC_Point& base, const Modular_Reducer& mod_order) :	860✔
28	m_base_point(base), m_mod_order(mod_order), m_p_words(base.get_curve().get_p().sig_words()) {	860✔
29	std::vector<BigInt> ws(EC_Point::WORKSPACE_SIZE);	860✔
30
31	const size_t p_bits = base.get_curve().get_p().bits();	860✔
32
33	/*
34	* Some of the curves (eg secp160k1) have an order slightly larger than
35	* the size of the prime modulus. In all cases they are at most 1 bit
36	* longer. The +1 compensates for this.
37	*/
38	const size_t T_bits = round_up(p_bits + blinding_size(mod_order.get_modulus()) + 1, WINDOW_BITS) / WINDOW_BITS;	860✔
39
40	std::vector<EC_Point> T(WINDOW_SIZE * T_bits);	860✔
41
42	EC_Point g = base;	860✔
43	EC_Point g2, g4;	860✔
44
45	for(size_t i = 0; i != T_bits; i++) {	131,183✔
46	g2 = g;	130,323✔
47	g2.mult2(ws);	130,323✔
48	g4 = g2;	130,323✔
49	g4.mult2(ws);	130,323✔
50
51	T[7 * i + 0] = g;	130,323✔
52	T[7 * i + 1] = std::move(g2);	130,323✔
53	T[7 * i + 2] = T[7 * i + 1].plus(T[7 * i + 0], ws); // g2+g	390,969✔
54	T[7 * i + 3] = g4;	130,323✔
55	T[7 * i + 4] = T[7 * i + 3].plus(T[7 * i + 0], ws); // g4+g	390,969✔
56	T[7 * i + 5] = T[7 * i + 3].plus(T[7 * i + 1], ws); // g4+g2	390,969✔
57	T[7 * i + 6] = T[7 * i + 3].plus(T[7 * i + 2], ws); // g4+g2+g	390,969✔
58
59	g.swap(g4);	130,323✔
60	g.mult2(ws);	130,323✔
61	}
62
63	EC_Point::force_all_affine(T, ws[0].get_word_vector());	860✔
64
65	m_W.resize(T.size() * 2 * m_p_words);	860✔
66
67	word* p = &m_W[0];	860✔
68	for(size_t i = 0; i != T.size(); ++i) {	913,121✔
69	T[i].get_x().encode_words(p, m_p_words);	912,261✔
70	p += m_p_words;	912,261✔
71	T[i].get_y().encode_words(p, m_p_words);	912,261✔
72	p += m_p_words;	912,261✔
73	}
74	}	860✔
75
76	EC_Point EC_Point_Base_Point_Precompute::mul(const BigInt& k,	2,897✔
77	RandomNumberGenerator& rng,
78	const BigInt& group_order,
79	std::vector<BigInt>& ws) const {
80	if(k.is_negative())	2,897✔
81	throw Invalid_Argument("EC_Point_Base_Point_Precompute scalar must be positive");	×
82
83	// Instead of reducing k mod group order should we alter the mask size??
84	BigInt scalar = m_mod_order.reduce(k);	2,897✔
85
86	if(rng.is_seeded()) {	2,897✔
87	// Choose a small mask m and use k' = k + m*order (Coron's 1st countermeasure)
88	const BigInt mask(rng, blinding_size(group_order));	2,865✔
89	scalar += group_order * mask;	5,730✔
90	} else {	2,865✔
91	/*
92	When we don't have an RNG we cannot do scalar blinding. Instead use the
93	same trick as OpenSSL and add one or two copies of the order to normalize
94	the length of the scalar at order.bits()+1. This at least ensures the loop
95	bound does not leak information about the high bits of the scalar.
96	*/
97	scalar += group_order;	32✔
98	if(scalar.bits() == group_order.bits())	32✔
99	scalar += group_order;	8✔
100	BOTAN_DEBUG_ASSERT(scalar.bits() == group_order.bits() + 1);	2,897✔
101	}
102
103	const size_t windows = round_up(scalar.bits(), WINDOW_BITS) / WINDOW_BITS;	2,897✔
104
105	const size_t elem_size = 2 * m_p_words;	2,897✔
106
107	BOTAN_ASSERT(windows <= m_W.size() / (3 * elem_size), "Precomputed sufficient values for scalar mult");	2,897✔
108
109	EC_Point R = m_base_point.zero();	2,897✔
110
111	if(ws.size() < EC_Point::WORKSPACE_SIZE)	2,897✔
112	ws.resize(EC_Point::WORKSPACE_SIZE);	1,963✔
113
114	// the precomputed multiples are not secret so use std::vector
115	std::vector<word> Wt(elem_size);	2,897✔
116
117	for(size_t i = 0; i != windows; ++i) {	453,739✔
118	const size_t window = windows - i - 1;	450,842✔
119	const size_t base_addr = (WINDOW_SIZE * window) * elem_size;	450,842✔
120
121	const word w = scalar.get_substring(WINDOW_BITS * window, WINDOW_BITS);	450,842✔
122
123	const auto w_is_1 = CT::Mask<word>::is_equal(w, 1);	450,842✔
124	const auto w_is_2 = CT::Mask<word>::is_equal(w, 2);	450,842✔
125	const auto w_is_3 = CT::Mask<word>::is_equal(w, 3);	450,842✔
126	const auto w_is_4 = CT::Mask<word>::is_equal(w, 4);	450,842✔
127	const auto w_is_5 = CT::Mask<word>::is_equal(w, 5);	450,842✔
128	const auto w_is_6 = CT::Mask<word>::is_equal(w, 6);	450,842✔
129	const auto w_is_7 = CT::Mask<word>::is_equal(w, 7);	450,842✔
130
131	for(size_t j = 0; j != elem_size; ++j) {	5,465,594✔
132	const word w1 = w_is_1.if_set_return(m_W[base_addr + 0 * elem_size + j]);	5,014,752✔
133	const word w2 = w_is_2.if_set_return(m_W[base_addr + 1 * elem_size + j]);	5,014,752✔
134	const word w3 = w_is_3.if_set_return(m_W[base_addr + 2 * elem_size + j]);	5,014,752✔
135	const word w4 = w_is_4.if_set_return(m_W[base_addr + 3 * elem_size + j]);	5,014,752✔
136	const word w5 = w_is_5.if_set_return(m_W[base_addr + 4 * elem_size + j]);	5,014,752✔
137	const word w6 = w_is_6.if_set_return(m_W[base_addr + 5 * elem_size + j]);	5,014,752✔
138	const word w7 = w_is_7.if_set_return(m_W[base_addr + 6 * elem_size + j]);	5,014,752✔
139
140	Wt[j] = w1 \| w2 \| w3 \| w4 \| w5 \| w6 \| w7;	5,014,752✔
141	}
142
143	R.add_affine(&Wt[0], m_p_words, &Wt[m_p_words], m_p_words, ws);	450,842✔
144
145	if(i == 0 && rng.is_seeded()) {	450,842✔
146	/*
147	* Since we start with the top bit of the exponent we know the
148	* first window must have a non-zero element, and thus R is
149	* now a point other than the point at infinity.
150	*/
151	BOTAN_DEBUG_ASSERT(w != 0);	2,865✔
152	R.randomize_repr(rng, ws[0].get_word_vector());	2,865✔
153	}
154	}
155
156	BOTAN_DEBUG_ASSERT(R.on_the_curve());	2,897✔
157
158	return R;	2,897✔
159	}	5,794✔
160
161	EC_Point_Var_Point_Precompute::EC_Point_Var_Point_Precompute(const EC_Point& point,	2,797✔
162	RandomNumberGenerator& rng,
163	std::vector<BigInt>& ws) :	2,797✔
164	m_curve(point.get_curve()), m_p_words(m_curve.get_p().sig_words()), m_window_bits(4) {	2,797✔
165	if(ws.size() < EC_Point::WORKSPACE_SIZE)	2,797✔
166	ws.resize(EC_Point::WORKSPACE_SIZE);	584✔
167
168	std::vector<EC_Point> U(static_cast<size_t>(1) << m_window_bits);	2,797✔
169	U[0] = point.zero();	5,594✔
170	U[1] = point;	2,797✔
171
172	for(size_t i = 2; i < U.size(); i += 2) {	22,376✔
173	U[i] = U[i / 2].double_of(ws);	58,737✔
174	U[i + 1] = U[i].plus(point, ws);	58,737✔
175	}
176
177	// Hack to handle Blinded_Point_Multiply
178	if(rng.is_seeded()) {	2,797✔
179	BigInt& mask = ws[0];	2,795✔
180	BigInt& mask2 = ws[1];	2,795✔
181	BigInt& mask3 = ws[2];	2,795✔
182	BigInt& new_x = ws[3];	2,795✔
183	BigInt& new_y = ws[4];	2,795✔
184	BigInt& new_z = ws[5];	2,795✔
185	secure_vector<word>& tmp = ws[6].get_word_vector();	2,795✔
186
187	const CurveGFp& curve = U[0].get_curve();	2,795✔
188
189	const size_t p_bits = curve.get_p().bits();	2,795✔
190
191	// Skipping zero point since it can't be randomized
192	for(size_t i = 1; i != U.size(); ++i) {	44,720✔
193	mask.randomize(rng, p_bits - 1, false);	41,925✔
194	// Easy way of ensuring mask != 0
195	mask.set_bit(0);	41,925✔
196
197	curve.sqr(mask2, mask, tmp);	41,925✔
198	curve.mul(mask3, mask, mask2, tmp);	41,925✔
199
200	curve.mul(new_x, U[i].get_x(), mask2, tmp);	41,925✔
201	curve.mul(new_y, U[i].get_y(), mask3, tmp);	41,925✔
202	curve.mul(new_z, U[i].get_z(), mask, tmp);	41,925✔
203
204	U[i].swap_coords(new_x, new_y, new_z);	41,925✔
205	}
206	}
207
208	m_T.resize(U.size() * 3 * m_p_words);	2,797✔
209
210	word* p = &m_T[0];	2,797✔
211	for(size_t i = 0; i != U.size(); ++i) {	47,549✔
212	U[i].get_x().encode_words(p, m_p_words);	44,752✔
213	U[i].get_y().encode_words(p + m_p_words, m_p_words);	44,752✔
214	U[i].get_z().encode_words(p + 2 * m_p_words, m_p_words);	44,752✔
215	p += 3 * m_p_words;	44,752✔
216	}
217	}	2,797✔
218
219	EC_Point EC_Point_Var_Point_Precompute::mul(const BigInt& k,	2,797✔
220	RandomNumberGenerator& rng,
221	const BigInt& group_order,
222	std::vector<BigInt>& ws) const {
223	if(k.is_negative())	2,797✔
224	throw Invalid_Argument("EC_Point_Var_Point_Precompute scalar must be positive");	×
225	if(ws.size() < EC_Point::WORKSPACE_SIZE)	2,797✔
226	ws.resize(EC_Point::WORKSPACE_SIZE);	×
227
228	// Choose a small mask m and use k' = k + m*order (Coron's 1st countermeasure)
229	const BigInt mask(rng, blinding_size(group_order), false);	2,797✔
230	const BigInt scalar = k + group_order * mask;	2,797✔
231
232	const size_t elem_size = 3 * m_p_words;	2,797✔
233	const size_t window_elems = static_cast<size_t>(1) << m_window_bits;	2,797✔
234
235	size_t windows = round_up(scalar.bits(), m_window_bits) / m_window_bits;	2,797✔
236	EC_Point R(m_curve);	2,797✔
237	secure_vector<word> e(elem_size);	2,797✔
238
239	if(windows > 0) {	2,797✔
240	windows--;	2,797✔
241
242	const uint32_t w = scalar.get_substring(windows * m_window_bits, m_window_bits);	2,797✔
243
244	clear_mem(e.data(), e.size());	2,797✔
245	for(size_t i = 1; i != window_elems; ++i) {	44,752✔
246	const auto wmask = CT::Mask<word>::is_equal(w, i);	41,955✔
247
248	for(size_t j = 0; j != elem_size; ++j) {	647,430✔
249	e[j] \|= wmask.if_set_return(m_T[i * elem_size + j]);	605,475✔
250	}
251	}
252
253	R.add(&e[0], m_p_words, &e[m_p_words], m_p_words, &e[2 * m_p_words], m_p_words, ws);	2,797✔
254
255	/*
256	Randomize after adding the first nibble as before the addition R
257	is zero, and we cannot effectively randomize the point
258	representation of the zero point.
259	*/
260	R.randomize_repr(rng, ws[0].get_word_vector());	2,797✔
261	}
262
263	while(windows) {	313,642✔
264	R.mult2i(m_window_bits, ws);	310,845✔
265
266	const uint32_t w = scalar.get_substring((windows - 1) * m_window_bits, m_window_bits);	310,845✔
267
268	clear_mem(e.data(), e.size());	310,845✔
269	for(size_t i = 1; i != window_elems; ++i) {	4,973,520✔
270	const auto wmask = CT::Mask<word>::is_equal(w, i);	4,662,675✔
271
272	for(size_t j = 0; j != elem_size; ++j) {	81,125,325✔
273	e[j] \|= wmask.if_set_return(m_T[i * elem_size + j]);	76,462,650✔
274	}
275	}
276
277	R.add(&e[0], m_p_words, &e[m_p_words], m_p_words, &e[2 * m_p_words], m_p_words, ws);	310,845✔
278
279	windows--;
280	}
281
282	BOTAN_DEBUG_ASSERT(R.on_the_curve());	2,797✔
283
284	return R;	2,797✔
285	}	8,391✔
286
287	EC_Point_Multi_Point_Precompute::EC_Point_Multi_Point_Precompute(const EC_Point& x, const EC_Point& y) {	10,015✔
288	if(x.on_the_curve() == false \|\| y.on_the_curve() == false) {	10,015✔
289	m_M.push_back(x.zero());	1✔
290	return;	1✔
291	}
292
293	std::vector<BigInt> ws(EC_Point::WORKSPACE_SIZE);	10,014✔
294
295	EC_Point x2 = x;	10,014✔
296	x2.mult2(ws);	10,014✔
297
298	const EC_Point x3(x2.plus(x, ws));	10,014✔
299
300	EC_Point y2 = y;	10,014✔
301	y2.mult2(ws);	10,014✔
302
303	const EC_Point y3(y2.plus(y, ws));	10,014✔
304
305	m_M.reserve(15);	10,014✔
306
307	m_M.push_back(x);	10,014✔
308	m_M.push_back(x2);	10,014✔
309	m_M.push_back(x3);	10,014✔
310
311	m_M.push_back(y);	10,014✔
312	m_M.push_back(y.plus(x, ws));	20,028✔
313	m_M.push_back(y.plus(x2, ws));	20,028✔
314	m_M.push_back(y.plus(x3, ws));	20,028✔
315
316	m_M.push_back(y2);	10,014✔
317	m_M.push_back(y2.plus(x, ws));	20,028✔
318	m_M.push_back(y2.plus(x2, ws));	20,028✔
319	m_M.push_back(y2.plus(x3, ws));	20,028✔
320
321	m_M.push_back(y3);	10,014✔
322	m_M.push_back(y3.plus(x, ws));	20,028✔
323	m_M.push_back(y3.plus(x2, ws));	20,028✔
324	m_M.push_back(y3.plus(x3, ws));	20,028✔
325
326	bool no_infinity = true;	10,014✔
327	for(auto& pt : m_M) {	160,224✔
328	if(pt.is_zero())	280,245✔
329	no_infinity = false;	150✔
330	}
331
332	if(no_infinity) {	10,014✔
333	EC_Point::force_all_affine(m_M, ws[0].get_word_vector());	9,964✔
334	}
335
336	m_no_infinity = no_infinity;	10,014✔
337	}	10,014✔
338
339	EC_Point EC_Point_Multi_Point_Precompute::multi_exp(const BigInt& z1, const BigInt& z2) const {	12,758✔
340	if(m_M.size() == 1)	12,758✔
341	return m_M[0];	1✔
342
343	std::vector<BigInt> ws(EC_Point::WORKSPACE_SIZE);	12,757✔
344
345	const size_t z_bits = round_up(std::max(z1.bits(), z2.bits()), 2);	17,101✔
346
347	EC_Point H = m_M[0].zero();	12,757✔
348
349	for(size_t i = 0; i != z_bits; i += 2) {	1,993,680✔
350	if(i > 0) {	1,980,923✔
351	H.mult2i(2, ws);	1,968,166✔
352	}
353
354	const uint32_t z1_b = z1.get_substring(z_bits - i - 2, 2);	1,980,923✔
355	const uint32_t z2_b = z2.get_substring(z_bits - i - 2, 2);	1,980,923✔
356
357	const uint32_t z12 = (4 * z2_b) + z1_b;	1,980,923✔
358
359	// This function is not intended to be const time
360	if(z12) {	1,980,923✔
361	if(m_no_infinity)	1,841,332✔
362	H.add_affine(m_M[z12 - 1], ws);	1,833,229✔
363	else
364	H.add(m_M[z12 - 1], ws);	8,103✔
365	}
366	}
367
368	if(z1.is_negative() != z2.is_negative())	12,757✔
369	H.negate();	×
370
371	return H;	12,757✔
372	}	12,757✔
373
374	}

randombit / botan / 5079590438

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