Botan  2.11.0
Crypto and TLS for C++11
big_ops2.cpp
Go to the documentation of this file.
1 /*
2 * (C) 1999-2007,2018 Jack Lloyd
3 * 2016 Matthias Gierlings
4 *
5 * Botan is released under the Simplified BSD License (see license.txt)
6 */
7 
8 #include <botan/bigint.h>
9 #include <botan/internal/mp_core.h>
10 #include <botan/internal/bit_ops.h>
11 #include <algorithm>
12 
13 namespace Botan {
14 
15 BigInt& BigInt::add(const word y[], size_t y_words, Sign y_sign)
16  {
17  const size_t x_sw = sig_words();
18 
19  grow_to(std::max(x_sw, y_words) + 1);
20 
21  if(sign() == y_sign)
22  {
23  bigint_add2(mutable_data(), size() - 1, y, y_words);
24  }
25  else
26  {
27  const int32_t relative_size = bigint_cmp(data(), x_sw, y, y_words);
28 
29  if(relative_size >= 0)
30  {
31  // *this >= y
32  bigint_sub2(mutable_data(), x_sw, y, y_words);
33  }
34  else
35  {
36  // *this < y
37  bigint_sub2_rev(mutable_data(), y, y_words);
38  }
39 
40  //this->sign_fixup(relative_size, y_sign);
41  if(relative_size < 0)
42  set_sign(y_sign);
43  else if(relative_size == 0)
45  }
46 
47  return (*this);
48  }
49 
51  {
52  if(this->is_negative() || s.is_negative() || mod.is_negative())
53  throw Invalid_Argument("BigInt::mod_add expects all arguments are positive");
54 
55  BOTAN_DEBUG_ASSERT(*this < mod);
56  BOTAN_DEBUG_ASSERT(s < mod);
57 
58  /*
59  t + s or t + s - p == t - (p - s)
60 
61  So first compute ws = p - s
62 
63  Then compute t + s and t - ws
64 
65  If t - ws does not borrow, then that is the correct valued
66  */
67 
68  const size_t mod_sw = mod.sig_words();
69  BOTAN_ARG_CHECK(mod_sw > 0, "BigInt::mod_add modulus must be positive");
70 
71  this->grow_to(mod_sw);
72  s.grow_to(mod_sw);
73 
74  // First mod_sw for p - s, 2*mod_sw for bigint_addsub workspace
75  if(ws.size() < 3*mod_sw)
76  ws.resize(3*mod_sw);
77 
78  word borrow = bigint_sub3(&ws[0], mod.data(), mod_sw, s.data(), mod_sw);
79  BOTAN_DEBUG_ASSERT(borrow == 0);
80 
81  // Compute t - ws
82  borrow = bigint_sub3(&ws[mod_sw], this->data(), mod_sw, &ws[0], mod_sw);
83 
84  // Compute t + s
85  bigint_add3_nc(&ws[mod_sw*2], this->data(), mod_sw, s.data(), mod_sw);
86 
87  CT::conditional_copy_mem(borrow, &ws[0], &ws[mod_sw*2], &ws[mod_sw], mod_sw);
88  set_words(&ws[0], mod_sw);
89 
90  return (*this);
91  }
92 
94  {
95  if(this->is_negative() || s.is_negative() || mod.is_negative())
96  throw Invalid_Argument("BigInt::mod_sub expects all arguments are positive");
97 
98  // We are assuming in this function that *this and s are no more than mod_sw words long
99  BOTAN_DEBUG_ASSERT(*this < mod);
100  BOTAN_DEBUG_ASSERT(s < mod);
101 
102  const size_t mod_sw = mod.sig_words();
103 
104  this->grow_to(mod_sw);
105  s.grow_to(mod_sw);
106 
107  if(ws.size() < mod_sw)
108  ws.resize(mod_sw);
109 
110 #if 0
111  //Faster but not const time:
112 
113  // Compute t - s
114  word borrow = bigint_sub3(ws.data(), data(), mod_sw, s.data(), mod_sw);
115 
116  if(borrow)
117  {
118  // If t < s, instead compute p - (s - t)
119  bigint_sub2_rev(mutable_data(), s.data(), mod_sw);
120  bigint_sub2_rev(mutable_data(), mod.data(), mod_sw);
121  }
122  else
123  {
124  // No borrow so we already have the result we need
125  swap_reg(ws);
126  }
127 #else
128  if(mod_sw == 4)
129  bigint_mod_sub_n<4>(mutable_data(), s.data(), mod.data(), ws.data());
130  else if(mod_sw == 6)
131  bigint_mod_sub_n<6>(mutable_data(), s.data(), mod.data(), ws.data());
132  else
133  bigint_mod_sub(mutable_data(), s.data(), mod.data(), mod_sw, ws.data());
134 #endif
135 
136  return (*this);
137  }
138 
139 BigInt& BigInt::mod_mul(uint8_t y, const BigInt& mod, secure_vector<word>& ws)
140  {
141  BOTAN_ARG_CHECK(this->is_negative() == false, "*this must be positive");
142  BOTAN_ARG_CHECK(y < 16, "y too large");
143 
144  BOTAN_DEBUG_ASSERT(*this < mod);
145 
146  switch(y)
147  {
148  case 2:
149  *this <<= 1;
150  break;
151  case 4:
152  *this <<= 2;
153  break;
154  case 8:
155  *this <<= 3;
156  break;
157  default:
158  *this *= static_cast<word>(y);
159  break;
160  }
161 
162  this->reduce_below(mod, ws);
163  return (*this);
164  }
165 
166 BigInt& BigInt::rev_sub(const word y[], size_t y_sw, secure_vector<word>& ws)
167  {
168  if(this->sign() != BigInt::Positive)
169  throw Invalid_State("BigInt::sub_rev requires this is positive");
170 
171  const size_t x_sw = this->sig_words();
172 
173  ws.resize(std::max(x_sw, y_sw));
174  clear_mem(ws.data(), ws.size());
175 
176  const int32_t relative_size = bigint_sub_abs(ws.data(), data(), x_sw, y, y_sw);
177 
178  this->cond_flip_sign(relative_size > 0);
179  this->swap_reg(ws);
180 
181  return (*this);
182  }
183 
184 /*
185 * Multiplication Operator
186 */
188  {
190  return this->mul(y, ws);
191  }
192 
194  {
195  const size_t x_sw = sig_words();
196  const size_t y_sw = y.sig_words();
197  set_sign((sign() == y.sign()) ? Positive : Negative);
198 
199  if(x_sw == 0 || y_sw == 0)
200  {
201  clear();
203  }
204  else if(x_sw == 1 && y_sw)
205  {
206  grow_to(y_sw + 1);
207  bigint_linmul3(mutable_data(), y.data(), y_sw, word_at(0));
208  }
209  else if(y_sw == 1 && x_sw)
210  {
211  grow_to(x_sw + 1);
212  bigint_linmul2(mutable_data(), x_sw, y.word_at(0));
213  }
214  else
215  {
216  const size_t new_size = x_sw + y_sw + 1;
217  ws.resize(new_size);
218  secure_vector<word> z_reg(new_size);
219 
220  bigint_mul(z_reg.data(), z_reg.size(),
221  data(), size(), x_sw,
222  y.data(), y.size(), y_sw,
223  ws.data(), ws.size());
224 
225  this->swap_reg(z_reg);
226  }
227 
228  return (*this);
229  }
230 
232  {
233  const size_t sw = sig_words();
234 
235  secure_vector<word> z(2*sw);
236  ws.resize(z.size());
237 
238  bigint_sqr(z.data(), z.size(),
239  data(), size(), sw,
240  ws.data(), ws.size());
241 
242  swap_reg(z);
244 
245  return (*this);
246  }
247 
249  {
250  if(y == 0)
251  {
252  clear();
254  }
255 
256  const size_t x_sw = sig_words();
257 
258  if(size() < x_sw + 1)
259  grow_to(x_sw + 1);
260  bigint_linmul2(mutable_data(), x_sw, y);
261 
262  return (*this);
263  }
264 
265 /*
266 * Division Operator
267 */
269  {
270  if(y.sig_words() == 1 && is_power_of_2(y.word_at(0)))
271  (*this) >>= (y.bits() - 1);
272  else
273  (*this) = (*this) / y;
274  return (*this);
275  }
276 
277 /*
278 * Modulo Operator
279 */
281  {
282  return (*this = (*this) % mod);
283  }
284 
285 /*
286 * Modulo Operator
287 */
288 word BigInt::operator%=(word mod)
289  {
290  if(mod == 0)
291  throw BigInt::DivideByZero();
292 
293  word remainder = 0;
294 
295  if(is_power_of_2(mod))
296  {
297  remainder = (word_at(0) & (mod - 1));
298  }
299  else
300  {
301  const size_t sw = sig_words();
302  for(size_t i = sw; i > 0; --i)
303  remainder = bigint_modop(remainder, word_at(i-1), mod);
304  }
305 
306  if(remainder && sign() == BigInt::Negative)
307  remainder = mod - remainder;
308 
309  m_data.set_to_zero();
310  m_data.set_word_at(0, remainder);
312  return remainder;
313  }
314 
315 /*
316 * Left Shift Operator
317 */
319  {
320  const size_t shift_words = shift / BOTAN_MP_WORD_BITS;
321  const size_t shift_bits = shift % BOTAN_MP_WORD_BITS;
322  const size_t size = sig_words();
323 
324  const size_t bits_free = top_bits_free();
325 
326  const size_t new_size = size + shift_words + (bits_free < shift);
327 
328  m_data.grow_to(new_size);
329 
330  bigint_shl1(m_data.mutable_data(), new_size, size, shift_words, shift_bits);
331 
332  return (*this);
333  }
334 
335 /*
336 * Right Shift Operator
337 */
339  {
340  const size_t shift_words = shift / BOTAN_MP_WORD_BITS;
341  const size_t shift_bits = shift % BOTAN_MP_WORD_BITS;
342 
343  bigint_shr1(m_data.mutable_data(), m_data.size(), shift_words, shift_bits);
344 
345  if(is_negative() && is_zero())
347 
348  return (*this);
349  }
350 
351 }
void bigint_shr1(word x[], size_t x_size, size_t word_shift, size_t bit_shift)
Definition: mp_core.h:429
void bigint_sub2_rev(word x[], const word y[], size_t y_size)
Definition: mp_core.h:326
bool is_negative() const
Definition: bigint.h:530
BigInt & operator*=(const BigInt &y)
Definition: big_ops2.cpp:187
int32_t bigint_cmp(const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:525
size_t bits() const
Definition: bigint.cpp:281
void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:111
word bigint_sub2(word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:302
void bigint_linmul2(word x[], size_t x_size, word y)
Definition: mp_core.h:489
word bigint_add3_nc(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:252
Sign sign() const
Definition: bigint.h:542
BigInt & mod_sub(const BigInt &y, const BigInt &mod, secure_vector< word > &ws)
Definition: big_ops2.cpp:93
bool is_zero() const
Definition: bigint.h:420
word * mutable_data()
Definition: bigint.h:617
void swap_reg(secure_vector< word > &reg)
Definition: bigint.h:166
word bigint_sub3(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:344
word word_at(size_t n) const
Definition: bigint.h:511
BigInt & operator<<=(size_t shift)
Definition: big_ops2.cpp:318
void bigint_sqr(word z[], size_t z_size, const word x[], size_t x_size, size_t x_sw, word workspace[], size_t ws_size)
Definition: mp_karat.cpp:357
const word * data() const
Definition: bigint.h:623
BigInt & operator>>=(size_t shift)
Definition: big_ops2.cpp:338
void bigint_linmul3(word z[], const word x[], size_t x_size, word y)
Definition: mp_core.h:504
BigInt & operator%=(const BigInt &y)
Definition: big_ops2.cpp:280
void bigint_shl1(word x[], size_t x_size, size_t x_words, size_t word_shift, size_t bit_shift)
Definition: mp_core.h:411
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:123
CT::Mask< word > bigint_sub_abs(word z[], const word x[], const word y[], size_t N, word ws[])
Definition: mp_core.h:379
constexpr bool is_power_of_2(T arg)
Definition: bit_ops.h:43
BigInt & mod_add(const BigInt &y, const BigInt &mod, secure_vector< word > &ws)
Definition: big_ops2.cpp:50
size_t size() const
Definition: bigint.h:583
void set_words(const word w[], size_t len)
Definition: bigint.h:521
BigInt & add(const word y[], size_t y_words, Sign sign)
Definition: big_ops2.cpp:15
Definition: alg_id.cpp:13
BigInt & square(secure_vector< word > &ws)
Definition: big_ops2.cpp:231
size_t sig_words() const
Definition: bigint.h:589
Mask< T > conditional_copy_mem(T cnd, T *to, const T *from0, const T *from1, size_t elems)
Definition: ct_utils.h:339
#define BOTAN_ARG_CHECK(expr, msg)
Definition: assert.h:37
void bigint_mul(word z[], size_t z_size, const word x[], size_t x_size, size_t x_sw, const word y[], size_t y_size, size_t y_sw, word workspace[], size_t ws_size)
Definition: mp_karat.cpp:298
BigInt & operator/=(const BigInt &y)
Definition: big_ops2.cpp:268
BigInt & mod_mul(uint8_t y, const BigInt &mod, secure_vector< word > &ws)
Definition: big_ops2.cpp:139
void clear()
Definition: bigint.h:365
void cond_flip_sign(bool predicate)
Definition: bigint.cpp:449
void grow_to(size_t n) const
Definition: bigint.h:639
size_t reduce_below(const BigInt &mod, secure_vector< word > &ws)
Definition: bigint.cpp:321
void bigint_add2(word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:282
size_t top_bits_free() const
Definition: bigint.cpp:271
std::vector< T, secure_allocator< T > > secure_vector
Definition: secmem.h:65
BigInt & mul(const BigInt &y, secure_vector< word > &ws)
Definition: big_ops2.cpp:193
void set_sign(Sign sign)
Definition: bigint.h:566
void bigint_mod_sub(word t[], const word s[], const word mod[], size_t mod_sw, word ws[])
Definition: mp_core.h:686
BigInt & rev_sub(const word y[], size_t y_words, secure_vector< word > &ws)
Definition: big_ops2.cpp:166
word bigint_modop(word n1, word n0, word d)
Definition: mp_core.h:754