Botan  2.13.0
Crypto and TLS for C++11
Public Member Functions | List of all members
Botan::PointGFp_Base_Point_Precompute Class Referencefinal

#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

◆ PointGFp_Base_Point_Precompute()

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.

51  :
52  m_base_point(base),
53  m_mod_order(mod_order),
54  m_p_words(base.get_curve().get_p().sig_words()),
55  m_T_size(base.get_curve().get_p().bits() + PointGFp_SCALAR_BLINDING_BITS + 1)
56  {
57  std::vector<BigInt> ws(PointGFp::WORKSPACE_SIZE);
58 
59  const size_t p_bits = base.get_curve().get_p().bits();
60 
61  /*
62  * Some of the curves (eg secp160k1) have an order slightly larger than
63  * the size of the prime modulus. In all cases they are at most 1 bit
64  * longer. The +1 compensates for this.
65  */
66  const size_t T_bits = round_up(p_bits + PointGFp_SCALAR_BLINDING_BITS + 1, WINDOW_BITS) / WINDOW_BITS;
67 
68  std::vector<PointGFp> T(WINDOW_SIZE*T_bits);
69 
70  PointGFp g = base;
71  PointGFp g2, g4;
72 
73  for(size_t i = 0; i != T_bits; i++)
74  {
75  g2 = g;
76  g2.mult2(ws);
77  g4 = g2;
78  g4.mult2(ws);
79 
80  T[7*i+0] = g;
81  T[7*i+1] = std::move(g2);
82  T[7*i+2] = T[7*i+1].plus(T[7*i+0], ws); // g2+g
83  T[7*i+3] = g4;
84  T[7*i+4] = T[7*i+3].plus(T[7*i+0], ws); // g4+g
85  T[7*i+5] = T[7*i+3].plus(T[7*i+1], ws); // g4+g2
86  T[7*i+6] = T[7*i+3].plus(T[7*i+2], ws); // g4+g2+g
87 
88  g.swap(g4);
89  g.mult2(ws);
90  }
91 
92  PointGFp::force_all_affine(T, ws[0].get_word_vector());
93 
94  m_W.resize(T.size() * 2 * m_p_words);
95 
96  word* p = &m_W[0];
97  for(size_t i = 0; i != T.size(); ++i)
98  {
99  T[i].get_x().encode_words(p, m_p_words);
100  p += m_p_words;
101  T[i].get_y().encode_words(p, m_p_words);
102  p += m_p_words;
103  }
104  }
static void force_all_affine(std::vector< PointGFp > &points, secure_vector< word > &ws)
Definition: point_gfp.cpp:420
fe T
Definition: ge.cpp:37
size_t round_up(size_t n, size_t align_to)
Definition: rounding.h:21

Member Function Documentation

◆ mul()

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

110  {
111  if(k.is_negative())
112  throw Invalid_Argument("PointGFp_Base_Point_Precompute scalar must be positive");
113 
114  // Instead of reducing k mod group order should we alter the mask size??
115  BigInt scalar = m_mod_order.reduce(k);
116 
117  if(rng.is_seeded())
118  {
119  // Choose a small mask m and use k' = k + m*order (Coron's 1st countermeasure)
120  const BigInt mask(rng, PointGFp_SCALAR_BLINDING_BITS);
121  scalar += group_order * mask;
122  }
123  else
124  {
125  /*
126  When we don't have an RNG we cannot do scalar blinding. Instead use the
127  same trick as OpenSSL and add one or two copies of the order to normalize
128  the length of the scalar at order.bits()+1. This at least ensures the loop
129  bound does not leak information about the high bits of the scalar.
130  */
131  scalar += group_order;
132  if(scalar.bits() == group_order.bits())
133  scalar += group_order;
134  BOTAN_DEBUG_ASSERT(scalar.bits() == group_order.bits() + 1);
135  }
136 
137  const size_t windows = round_up(scalar.bits(), WINDOW_BITS) / WINDOW_BITS;
138 
139  const size_t elem_size = 2*m_p_words;
140 
141  BOTAN_ASSERT(windows <= m_W.size() / (3*elem_size),
142  "Precomputed sufficient values for scalar mult");
143 
144  PointGFp R = m_base_point.zero();
145 
146  if(ws.size() < PointGFp::WORKSPACE_SIZE)
147  ws.resize(PointGFp::WORKSPACE_SIZE);
148 
149  // the precomputed multiples are not secret so use std::vector
150  std::vector<word> Wt(elem_size);
151 
152  for(size_t i = 0; i != windows; ++i)
153  {
154  const size_t window = windows - i - 1;
155  const size_t base_addr = (WINDOW_SIZE*window)*elem_size;
156 
157  const word w = scalar.get_substring(WINDOW_BITS*window, WINDOW_BITS);
158 
159  const auto w_is_1 = CT::Mask<word>::is_equal(w, 1);
160  const auto w_is_2 = CT::Mask<word>::is_equal(w, 2);
161  const auto w_is_3 = CT::Mask<word>::is_equal(w, 3);
162  const auto w_is_4 = CT::Mask<word>::is_equal(w, 4);
163  const auto w_is_5 = CT::Mask<word>::is_equal(w, 5);
164  const auto w_is_6 = CT::Mask<word>::is_equal(w, 6);
165  const auto w_is_7 = CT::Mask<word>::is_equal(w, 7);
166 
167  for(size_t j = 0; j != elem_size; ++j)
168  {
169  const word w1 = w_is_1.if_set_return(m_W[base_addr + 0*elem_size + j]);
170  const word w2 = w_is_2.if_set_return(m_W[base_addr + 1*elem_size + j]);
171  const word w3 = w_is_3.if_set_return(m_W[base_addr + 2*elem_size + j]);
172  const word w4 = w_is_4.if_set_return(m_W[base_addr + 3*elem_size + j]);
173  const word w5 = w_is_5.if_set_return(m_W[base_addr + 4*elem_size + j]);
174  const word w6 = w_is_6.if_set_return(m_W[base_addr + 5*elem_size + j]);
175  const word w7 = w_is_7.if_set_return(m_W[base_addr + 6*elem_size + j]);
176 
177  Wt[j] = w1 | w2 | w3 | w4 | w5 | w6 | w7;
178  }
179 
180  R.add_affine(&Wt[0], m_p_words, &Wt[m_p_words], m_p_words, ws);
181 
182  if(i == 0 && rng.is_seeded())
183  {
184  /*
185  * Since we start with the top bit of the exponent we know the
186  * first window must have a non-zero element, and thus R is
187  * now a point other than the point at infinity.
188  */
189  BOTAN_DEBUG_ASSERT(w != 0);
190  R.randomize_repr(rng, ws[0].get_word_vector());
191  }
192  }
193 
194  BOTAN_DEBUG_ASSERT(R.on_the_curve());
195 
196  return R;
197  }
#define BOTAN_ASSERT(expr, assertion_made)
Definition: assert.h:55
PointGFp zero() const
Definition: point_gfp.h:319
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:123
BigInt reduce(const BigInt &x) const
Definition: reducer.cpp:37
size_t round_up(size_t n, size_t align_to)
Definition: rounding.h:21
static Mask< T > is_equal(T x, T y)
Definition: ct_utils.h:149

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