Botan  2.15.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 53 of file point_mul.cpp.

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

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