Botan  2.11.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 18 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 44 of file point_mul.cpp.

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

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