Botan  2.7.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_sw, Sign y_sign)
16  {
17  const size_t x_sw = sig_words();
18 
19  if(sign() == y_sign)
20  {
21  const size_t reg_size = std::max(x_sw, y_sw) + 1;
22 
23  if(m_reg.size() < reg_size)
24  grow_to(reg_size);
25 
26  bigint_add2(mutable_data(), reg_size - 1, y, y_sw);
27  }
28  else
29  {
30  const int32_t relative_size = bigint_cmp(data(), x_sw, y, y_sw);
31 
32  if(relative_size < 0)
33  {
34  const size_t reg_size = std::max(x_sw, y_sw);
35  grow_to(reg_size);
36  bigint_sub2_rev(mutable_data(), y, y_sw);
37  set_sign(y_sign);
38  }
39  else if(relative_size == 0)
40  {
41  zeroise(m_reg);
43  }
44  else if(relative_size > 0)
45  {
46  bigint_sub2(mutable_data(), x_sw, y, y_sw);
47  }
48  }
49 
50  return (*this);
51  }
52 
54  {
55  return add(y.data(), y.sig_words(), y.sign());
56  }
57 
59  {
60  return add(&y, 1, Positive);
61  }
62 
63 BigInt& BigInt::sub(const word y[], size_t y_sw, Sign y_sign)
64  {
65  const size_t x_sw = sig_words();
66 
67  int32_t relative_size = bigint_cmp(data(), x_sw, y, y_sw);
68 
69  const size_t reg_size = std::max(x_sw, y_sw) + 1;
70  grow_to(reg_size);
71 
72  if(relative_size < 0)
73  {
74  if(sign() == y_sign)
75  bigint_sub2_rev(mutable_data(), y, y_sw);
76  else
77  bigint_add2(mutable_data(), reg_size - 1, y, y_sw);
78 
79  set_sign(y_sign == Positive ? Negative : Positive);
80  }
81  else if(relative_size == 0)
82  {
83  if(sign() == y_sign)
84  {
85  clear();
87  }
88  else
89  bigint_shl1(mutable_data(), x_sw, 0, 1);
90  }
91  else if(relative_size > 0)
92  {
93  if(sign() == y_sign)
94  bigint_sub2(mutable_data(), x_sw, y, y_sw);
95  else
96  bigint_add2(mutable_data(), reg_size - 1, y, y_sw);
97  }
98 
99  return (*this);
100  }
101 
103  {
104  return sub(y.data(), y.sig_words(), y.sign());
105  }
106 
108  {
109  return sub(&y, 1, Positive);
110  }
111 
113  {
114  if(this->is_negative() || s.is_negative() || mod.is_negative())
115  throw Invalid_Argument("BigInt::mod_add expects all arguments are positive");
116 
117  // TODO add optimized version of this
118  *this += s;
119  this->reduce_below(mod, ws);
120 
121  return (*this);
122  }
123 
125  {
126  if(this->is_negative() || s.is_negative() || mod.is_negative())
127  throw Invalid_Argument("BigInt::mod_sub expects all arguments are positive");
128 
129  const size_t t_sw = sig_words();
130  const size_t s_sw = s.sig_words();
131  const size_t mod_sw = mod.sig_words();
132 
133  if(t_sw > mod_sw || s_sw > mod_sw)
134  throw Invalid_Argument("BigInt::mod_sub args larger than modulus");
135 
136  BOTAN_DEBUG_ASSERT(*this < mod);
137  BOTAN_DEBUG_ASSERT(s < mod);
138 
139  int32_t relative_size = bigint_cmp(data(), t_sw, s.data(), s_sw);
140 
141  if(relative_size >= 0)
142  {
143  // this >= s in which case just subtract
144  bigint_sub2(mutable_data(), t_sw, s.data(), s_sw);
145  }
146  else
147  {
148  // Otherwise we must sub s and then add p (or add (p - s) as here)
149 
150  if(ws.size() < mod_sw)
151  ws.resize(mod_sw);
152 
153  word borrow = bigint_sub3(ws.data(), mod.data(), mod_sw, s.data(), s_sw);
154  BOTAN_ASSERT_NOMSG(borrow == 0);
155 
156  if(m_reg.size() < mod_sw)
157  grow_to(mod_sw);
158 
159  word carry = bigint_add2_nc(mutable_data(), m_reg.size(), ws.data(), mod_sw);
161  }
162 
163  return (*this);
164  }
165 
166 BigInt& BigInt::rev_sub(const word y[], size_t y_sw, secure_vector<word>& ws)
167  {
168  /*
169  *this = BigInt(y, y_sw) - *this;
170  return *this;
171  */
172  if(this->sign() != BigInt::Positive)
173  throw Invalid_State("BigInt::sub_rev requires this is positive");
174 
175  const size_t x_sw = this->sig_words();
176 
177  const int32_t relative_size = bigint_cmp(y, y_sw, this->data(), x_sw);
178 
179  ws.resize(std::max(y_sw, x_sw) + 1);
180  clear_mem(ws.data(), ws.size());
181 
182  if(relative_size < 0)
183  {
184  bigint_sub3(ws.data(), this->data(), x_sw, y, y_sw);
185  this->flip_sign();
186  }
187  else if(relative_size == 0)
188  {
189  ws.clear();
190  }
191  else if(relative_size > 0)
192  {
193  bigint_sub3(ws.data(), y, y_sw, this->data(), x_sw);
194  }
195 
196  m_reg.swap(ws);
197 
198  return (*this);
199  }
200 
201 /*
202 * Multiplication Operator
203 */
205  {
207  return this->mul(y, ws);
208  }
209 
211  {
212  const size_t x_sw = sig_words();
213  const size_t y_sw = y.sig_words();
214  set_sign((sign() == y.sign()) ? Positive : Negative);
215 
216  if(x_sw == 0 || y_sw == 0)
217  {
218  clear();
220  }
221  else if(x_sw == 1 && y_sw)
222  {
223  grow_to(y_sw + 1);
224  bigint_linmul3(mutable_data(), y.data(), y_sw, word_at(0));
225  }
226  else if(y_sw == 1 && x_sw)
227  {
228  grow_to(x_sw + 1);
229  bigint_linmul2(mutable_data(), x_sw, y.word_at(0));
230  }
231  else
232  {
233  const size_t new_size = x_sw + y_sw + 1;
234  ws.resize(new_size);
235  secure_vector<word> z_reg(new_size);
236 
237  bigint_mul(z_reg.data(), z_reg.size(),
238  data(), size(), x_sw,
239  y.data(), y.size(), y_sw,
240  ws.data(), ws.size());
241 
242  z_reg.swap(m_reg);
243  }
244 
245  return (*this);
246  }
247 
249  {
250  const size_t sw = sig_words();
251 
252  secure_vector<word> z(2*sw);
253  ws.resize(z.size());
254 
255  bigint_sqr(z.data(), z.size(),
256  data(), size(), sw,
257  ws.data(), ws.size());
258 
259  swap_reg(z);
261 
262  return (*this);
263  }
264 
266  {
267  if(y == 0)
268  {
269  clear();
271  }
272 
273  const size_t x_sw = sig_words();
274 
275  if(size() < x_sw + 1)
276  grow_to(x_sw + 1);
277  bigint_linmul2(mutable_data(), x_sw, y);
278 
279  return (*this);
280  }
281 
282 /*
283 * Division Operator
284 */
286  {
287  if(y.sig_words() == 1 && is_power_of_2(y.word_at(0)))
288  (*this) >>= (y.bits() - 1);
289  else
290  (*this) = (*this) / y;
291  return (*this);
292  }
293 
294 /*
295 * Modulo Operator
296 */
298  {
299  return (*this = (*this) % mod);
300  }
301 
302 /*
303 * Modulo Operator
304 */
305 word BigInt::operator%=(word mod)
306  {
307  if(mod == 0)
308  throw BigInt::DivideByZero();
309 
310  if(is_power_of_2(mod))
311  {
312  word result = (word_at(0) & (mod - 1));
313  clear();
314  grow_to(2);
315  m_reg[0] = result;
316  return result;
317  }
318 
319  word remainder = 0;
320 
321  for(size_t j = sig_words(); j > 0; --j)
322  remainder = bigint_modop(remainder, word_at(j-1), mod);
323  clear();
324  grow_to(2);
325 
326  if(remainder && sign() == BigInt::Negative)
327  m_reg[0] = mod - remainder;
328  else
329  m_reg[0] = remainder;
330 
332 
333  return word_at(0);
334  }
335 
336 /*
337 * Left Shift Operator
338 */
340  {
341  if(shift)
342  {
343  const size_t shift_words = shift / BOTAN_MP_WORD_BITS,
344  shift_bits = shift % BOTAN_MP_WORD_BITS,
345  words = sig_words();
346 
347  /*
348  * FIXME - if shift_words == 0 && the top shift_bits of the top word
349  * are zero then we know that no additional word is needed and can
350  * skip the allocation.
351  */
352  const size_t needed_size = words + shift_words + (shift_bits ? 1 : 0);
353 
354  if(m_reg.size() < needed_size)
355  grow_to(needed_size);
356 
357  bigint_shl1(mutable_data(), words, shift_words, shift_bits);
358  }
359 
360  return (*this);
361  }
362 
363 /*
364 * Right Shift Operator
365 */
367  {
368  if(shift)
369  {
370  const size_t shift_words = shift / BOTAN_MP_WORD_BITS,
371  shift_bits = shift % BOTAN_MP_WORD_BITS;
372 
373  bigint_shr1(mutable_data(), sig_words(), shift_words, shift_bits);
374 
375  if(is_zero())
377  }
378 
379  return (*this);
380  }
381 
382 }
void bigint_shr1(word x[], size_t x_size, size_t word_shift, size_t bit_shift)
Definition: mp_core.cpp:359
void bigint_sub2_rev(word x[], const word y[], size_t y_size)
Definition: mp_core.cpp:227
bool is_negative() const
Definition: bigint.h:460
void carry(int64_t &h0, int64_t &h1)
BigInt & operator*=(const BigInt &y)
Definition: big_ops2.cpp:204
int32_t bigint_cmp(const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.cpp:456
size_t bits() const
Definition: bigint.cpp:228
void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:97
word bigint_sub2(word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.cpp:204
void bigint_linmul2(word x[], size_t x_size, word y)
Definition: mp_core.cpp:300
Sign sign() const
Definition: bigint.h:472
BigInt & mod_sub(const BigInt &y, const BigInt &mod, secure_vector< word > &ws)
Definition: big_ops2.cpp:124
bool is_zero() const
Definition: bigint.h:355
word * mutable_data()
Definition: bigint.h:545
void swap_reg(secure_vector< word > &reg)
Definition: bigint.h:156
#define BOTAN_ASSERT_NOMSG(expr)
Definition: assert.h:56
word bigint_sub3(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.cpp:276
word word_at(size_t n) const
Definition: bigint.h:440
BigInt & operator<<=(size_t shift)
Definition: big_ops2.cpp:339
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:352
const word * data() const
Definition: bigint.h:551
BigInt & operator>>=(size_t shift)
Definition: big_ops2.cpp:366
void bigint_linmul3(word z[], const word x[], size_t x_size, word y)
Definition: mp_core.cpp:318
BigInt & operator%=(const BigInt &y)
Definition: big_ops2.cpp:297
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:111
BigInt & mod_add(const BigInt &y, const BigInt &mod, secure_vector< word > &ws)
Definition: big_ops2.cpp:112
BigInt & sub(const word y[], size_t y_words, Sign sign)
Definition: big_ops2.cpp:63
size_t size() const
Definition: bigint.h:513
word bigint_add2_nc(word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.cpp:138
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:248
size_t sig_words() const
Definition: bigint.h:519
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:293
BigInt & operator/=(const BigInt &y)
Definition: big_ops2.cpp:285
void clear()
Definition: bigint.h:314
BigInt & operator-=(const BigInt &y)
Definition: big_ops2.cpp:102
void bigint_shl1(word x[], size_t x_size, size_t word_shift, size_t bit_shift)
Definition: mp_core.cpp:336
void grow_to(size_t n)
Definition: bigint.cpp:302
void bigint_add2(word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.cpp:186
void reduce_below(const BigInt &mod, secure_vector< word > &ws)
Definition: bigint.cpp:266
std::vector< T, secure_allocator< T > > secure_vector
Definition: secmem.h:88
BigInt & mul(const BigInt &y, secure_vector< word > &ws)
Definition: big_ops2.cpp:210
void flip_sign()
Definition: bigint.h:487
BigInt & rev_sub(const word y[], size_t y_size, secure_vector< word > &ws)
Definition: big_ops2.cpp:166
void set_sign(Sign sign)
Definition: bigint.h:496
BigInt & operator+=(const BigInt &y)
Definition: big_ops2.cpp:53
word bigint_modop(word n1, word n0, word d)
Definition: mp_core.cpp:515
bool is_power_of_2(T arg)
Definition: bit_ops.h:25
void zeroise(std::vector< T, Alloc > &vec)
Definition: secmem.h:183