Botan  2.19.1
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

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

Definition at line 54 of file point_mul.cpp.

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

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

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

Definition at line 109 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().

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