Botan  2.13.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  *this *= static_cast<word>(y);
147  this->reduce_below(mod, ws);
148  return (*this);
149  }
150 
151 BigInt& BigInt::rev_sub(const word y[], size_t y_sw, secure_vector<word>& ws)
152  {
153  if(this->sign() != BigInt::Positive)
154  throw Invalid_State("BigInt::sub_rev requires this is positive");
155 
156  const size_t x_sw = this->sig_words();
157 
158  ws.resize(std::max(x_sw, y_sw));
159  clear_mem(ws.data(), ws.size());
160 
161  const int32_t relative_size = bigint_sub_abs(ws.data(), data(), x_sw, y, y_sw);
162 
163  this->cond_flip_sign(relative_size > 0);
164  this->swap_reg(ws);
165 
166  return (*this);
167  }
168 
169 /*
170 * Multiplication Operator
171 */
173  {
175  return this->mul(y, ws);
176  }
177 
179  {
180  const size_t x_sw = sig_words();
181  const size_t y_sw = y.sig_words();
182  set_sign((sign() == y.sign()) ? Positive : Negative);
183 
184  if(x_sw == 0 || y_sw == 0)
185  {
186  clear();
188  }
189  else if(x_sw == 1 && y_sw)
190  {
191  grow_to(y_sw + 1);
192  bigint_linmul3(mutable_data(), y.data(), y_sw, word_at(0));
193  }
194  else if(y_sw == 1 && x_sw)
195  {
196  word carry = bigint_linmul2(mutable_data(), x_sw, y.word_at(0));
197  set_word_at(x_sw, carry);
198  }
199  else
200  {
201  const size_t new_size = x_sw + y_sw + 1;
202  ws.resize(new_size);
203  secure_vector<word> z_reg(new_size);
204 
205  bigint_mul(z_reg.data(), z_reg.size(),
206  data(), size(), x_sw,
207  y.data(), y.size(), y_sw,
208  ws.data(), ws.size());
209 
210  this->swap_reg(z_reg);
211  }
212 
213  return (*this);
214  }
215 
217  {
218  const size_t sw = sig_words();
219 
220  secure_vector<word> z(2*sw);
221  ws.resize(z.size());
222 
223  bigint_sqr(z.data(), z.size(),
224  data(), size(), sw,
225  ws.data(), ws.size());
226 
227  swap_reg(z);
229 
230  return (*this);
231  }
232 
234  {
235  if(y == 0)
236  {
237  clear();
239  }
240 
241  const word carry = bigint_linmul2(mutable_data(), size(), y);
242  set_word_at(size(), carry);
243 
244  return (*this);
245  }
246 
247 /*
248 * Division Operator
249 */
251  {
252  if(y.sig_words() == 1 && is_power_of_2(y.word_at(0)))
253  (*this) >>= (y.bits() - 1);
254  else
255  (*this) = (*this) / y;
256  return (*this);
257  }
258 
259 /*
260 * Modulo Operator
261 */
263  {
264  return (*this = (*this) % mod);
265  }
266 
267 /*
268 * Modulo Operator
269 */
270 word BigInt::operator%=(word mod)
271  {
272  if(mod == 0)
273  throw BigInt::DivideByZero();
274 
275  word remainder = 0;
276 
277  if(is_power_of_2(mod))
278  {
279  remainder = (word_at(0) & (mod - 1));
280  }
281  else
282  {
283  const size_t sw = sig_words();
284  for(size_t i = sw; i > 0; --i)
285  remainder = bigint_modop(remainder, word_at(i-1), mod);
286  }
287 
288  if(remainder && sign() == BigInt::Negative)
289  remainder = mod - remainder;
290 
291  m_data.set_to_zero();
292  m_data.set_word_at(0, remainder);
294  return remainder;
295  }
296 
297 /*
298 * Left Shift Operator
299 */
301  {
302  const size_t shift_words = shift / BOTAN_MP_WORD_BITS;
303  const size_t shift_bits = shift % BOTAN_MP_WORD_BITS;
304  const size_t size = sig_words();
305 
306  const size_t bits_free = top_bits_free();
307 
308  const size_t new_size = size + shift_words + (bits_free < shift_bits);
309 
310  m_data.grow_to(new_size);
311 
312  bigint_shl1(m_data.mutable_data(), new_size, size, shift_words, shift_bits);
313 
314  return (*this);
315  }
316 
317 /*
318 * Right Shift Operator
319 */
321  {
322  const size_t shift_words = shift / BOTAN_MP_WORD_BITS;
323  const size_t shift_bits = shift % BOTAN_MP_WORD_BITS;
324 
325  bigint_shr1(m_data.mutable_data(), m_data.size(), shift_words, shift_bits);
326 
327  if(is_negative() && is_zero())
329 
330  return (*this);
331  }
332 
333 }
void bigint_shr1(word x[], size_t x_size, size_t word_shift, size_t bit_shift)
Definition: mp_core.h:427
void bigint_sub2_rev(word x[], const word y[], size_t y_size)
Definition: mp_core.h:324
bool is_negative() const
Definition: bigint.h:525
void carry(int64_t &h0, int64_t &h1)
BigInt & operator*=(const BigInt &y)
Definition: big_ops2.cpp:172
word BOTAN_WARN_UNUSED_RESULT bigint_linmul2(word x[], size_t x_size, word y)
Definition: mp_core.h:487
int32_t bigint_cmp(const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:523
size_t bits() const
Definition: bigint.cpp:288
void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:112
word bigint_sub2(word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:300
word bigint_add3_nc(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:250
Sign sign() const
Definition: bigint.h:537
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:419
word * mutable_data()
Definition: bigint.h:612
void swap_reg(secure_vector< word > &reg)
Definition: bigint.h:165
word bigint_sub3(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:342
word word_at(size_t n) const
Definition: bigint.h:506
BigInt & operator<<=(size_t shift)
Definition: big_ops2.cpp:300
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:618
BigInt & operator>>=(size_t shift)
Definition: big_ops2.cpp:320
void bigint_linmul3(word z[], const word x[], size_t x_size, word y)
Definition: mp_core.h:502
BigInt & operator%=(const BigInt &y)
Definition: big_ops2.cpp:262
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:409
#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:377
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:578
void set_words(const word w[], size_t len)
Definition: bigint.h:516
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:216
size_t sig_words() const
Definition: bigint.h:584
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:250
BigInt & mod_mul(uint8_t y, const BigInt &mod, secure_vector< word > &ws)
Definition: big_ops2.cpp:139
void clear()
Definition: bigint.h:364
void cond_flip_sign(bool predicate)
Definition: bigint.cpp:456
void grow_to(size_t n) const
Definition: bigint.h:634
size_t reduce_below(const BigInt &mod, secure_vector< word > &ws)
Definition: bigint.cpp:328
void bigint_add2(word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:280
void set_word_at(size_t i, word w)
Definition: bigint.h:511
size_t top_bits_free() const
Definition: bigint.cpp:278
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:178
void set_sign(Sign sign)
Definition: bigint.h:561
void bigint_mod_sub(word t[], const word s[], const word mod[], size_t mod_sw, word ws[])
Definition: mp_core.h:685
BigInt & rev_sub(const word y[], size_t y_words, secure_vector< word > &ws)
Definition: big_ops2.cpp:151
word bigint_modop(word n1, word n0, word d)
Definition: mp_core.h:753