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)
44  set_sign(Positive);
45  }
46 
47  return (*this);
48  }
49 
50 BigInt& BigInt::mod_add(const BigInt& s, const BigInt& mod, secure_vector<word>& ws)
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);
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 
93 BigInt& BigInt::mod_sub(const BigInt& s, const BigInt& mod, secure_vector<word>& ws)
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 */
187 BigInt& BigInt::operator*=(const BigInt& y)
188  {
189  secure_vector<word> ws;
190  return this->mul(y, ws);
191  }
192 
193 BigInt& BigInt::mul(const BigInt& y, secure_vector<word>& ws)
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();
202  set_sign(Positive);
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 
231 BigInt& BigInt::square(secure_vector<word>& ws)
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);
243  set_sign(BigInt::Positive);
244 
245  return (*this);
246  }
247 
248 BigInt& BigInt::operator*=(word y)
249  {
250  if(y == 0)
251  {
252  clear();
253  set_sign(Positive);
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 */
268 BigInt& BigInt::operator/=(const BigInt& y)
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 */
280 BigInt& BigInt::operator%=(const BigInt& mod)
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);
311  set_sign(BigInt::Positive);
312  return remainder;
313  }
314 
315 /*
316 * Left Shift Operator
317 */
318 BigInt& BigInt::operator<<=(size_t shift)
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 */
338 BigInt& BigInt::operator>>=(size_t shift)
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())
346  set_sign(Positive);
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
int32_t bigint_cmp(const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:525
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
secure_vector< word > & ws
Definition: curve_nistp.h:24
word bigint_sub3(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:344
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
botan_mp_t remainder
Definition: ffi.h:831
void bigint_linmul3(word z[], const word x[], size_t x_size, word y)
Definition: mp_core.h:504
BigInt const BigInt & mod
Definition: numthry.h:103
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 square(const BigInt &x)
Definition: mp_numth.cpp:19
const botan_mp_t size_t shift
Definition: ffi.h:859
Definition: alg_id.cpp:13
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
void bigint_add2(word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:282
const OctetString & y
Definition: symkey.h:126
void bigint_mod_sub(word t[], const word s[], const word mod[], size_t mod_sw, word ws[])
Definition: mp_core.h:686
word bigint_modop(word n1, word n0, word d)
Definition: mp_core.h:754