Botan  2.15.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);
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(mod_sw == 4)
111  bigint_mod_sub_n<4>(mutable_data(), s.data(), mod.data(), ws.data());
112  else if(mod_sw == 6)
113  bigint_mod_sub_n<6>(mutable_data(), s.data(), mod.data(), ws.data());
114  else
115  bigint_mod_sub(mutable_data(), s.data(), mod.data(), mod_sw, ws.data());
116 
117  return (*this);
118  }
119 
121  {
122  BOTAN_ARG_CHECK(this->is_negative() == false, "*this must be positive");
123  BOTAN_ARG_CHECK(y < 16, "y too large");
124 
125  BOTAN_DEBUG_ASSERT(*this < mod);
126 
127  *this *= static_cast<word>(y);
128  this->reduce_below(mod, ws);
129  return (*this);
130  }
131 
132 BigInt& BigInt::rev_sub(const word y[], size_t y_sw, secure_vector<word>& ws)
133  {
134  if(this->sign() != BigInt::Positive)
135  throw Invalid_State("BigInt::sub_rev requires this is positive");
136 
137  const size_t x_sw = this->sig_words();
138 
139  ws.resize(std::max(x_sw, y_sw));
140  clear_mem(ws.data(), ws.size());
141 
142  const int32_t relative_size = bigint_sub_abs(ws.data(), data(), x_sw, y, y_sw);
143 
144  this->cond_flip_sign(relative_size > 0);
145  this->swap_reg(ws);
146 
147  return (*this);
148  }
149 
150 /*
151 * Multiplication Operator
152 */
154  {
156  return this->mul(y, ws);
157  }
158 
160  {
161  const size_t x_sw = sig_words();
162  const size_t y_sw = y.sig_words();
163  set_sign((sign() == y.sign()) ? Positive : Negative);
164 
165  if(x_sw == 0 || y_sw == 0)
166  {
167  clear();
169  }
170  else if(x_sw == 1 && y_sw)
171  {
172  grow_to(y_sw + 1);
173  bigint_linmul3(mutable_data(), y.data(), y_sw, word_at(0));
174  }
175  else if(y_sw == 1 && x_sw)
176  {
177  word carry = bigint_linmul2(mutable_data(), x_sw, y.word_at(0));
178  set_word_at(x_sw, carry);
179  }
180  else
181  {
182  const size_t new_size = x_sw + y_sw + 1;
183  ws.resize(new_size);
184  secure_vector<word> z_reg(new_size);
185 
186  bigint_mul(z_reg.data(), z_reg.size(),
187  data(), size(), x_sw,
188  y.data(), y.size(), y_sw,
189  ws.data(), ws.size());
190 
191  this->swap_reg(z_reg);
192  }
193 
194  return (*this);
195  }
196 
198  {
199  const size_t sw = sig_words();
200 
201  secure_vector<word> z(2*sw);
202  ws.resize(z.size());
203 
204  bigint_sqr(z.data(), z.size(),
205  data(), size(), sw,
206  ws.data(), ws.size());
207 
208  swap_reg(z);
210 
211  return (*this);
212  }
213 
215  {
216  if(y == 0)
217  {
218  clear();
220  }
221 
222  const word carry = bigint_linmul2(mutable_data(), size(), y);
223  set_word_at(size(), carry);
224 
225  return (*this);
226  }
227 
228 /*
229 * Division Operator
230 */
232  {
233  if(y.sig_words() == 1 && is_power_of_2(y.word_at(0)))
234  (*this) >>= (y.bits() - 1);
235  else
236  (*this) = (*this) / y;
237  return (*this);
238  }
239 
240 /*
241 * Modulo Operator
242 */
244  {
245  return (*this = (*this) % mod);
246  }
247 
248 /*
249 * Modulo Operator
250 */
252  {
253  if(mod == 0)
254  throw BigInt::DivideByZero();
255 
256  word remainder = 0;
257 
258  if(is_power_of_2(mod))
259  {
260  remainder = (word_at(0) & (mod - 1));
261  }
262  else
263  {
264  const size_t sw = sig_words();
265  for(size_t i = sw; i > 0; --i)
266  remainder = bigint_modop(remainder, word_at(i-1), mod);
267  }
268 
269  if(remainder && sign() == BigInt::Negative)
270  remainder = mod - remainder;
271 
272  m_data.set_to_zero();
273  m_data.set_word_at(0, remainder);
275  return remainder;
276  }
277 
278 /*
279 * Left Shift Operator
280 */
282  {
283  const size_t shift_words = shift / BOTAN_MP_WORD_BITS;
284  const size_t shift_bits = shift % BOTAN_MP_WORD_BITS;
285  const size_t size = sig_words();
286 
287  const size_t bits_free = top_bits_free();
288 
289  const size_t new_size = size + shift_words + (bits_free < shift_bits);
290 
291  m_data.grow_to(new_size);
292 
293  bigint_shl1(m_data.mutable_data(), new_size, size, shift_words, shift_bits);
294 
295  return (*this);
296  }
297 
298 /*
299 * Right Shift Operator
300 */
302  {
303  const size_t shift_words = shift / BOTAN_MP_WORD_BITS;
304  const size_t shift_bits = shift % BOTAN_MP_WORD_BITS;
305 
306  bigint_shr1(m_data.mutable_data(), m_data.size(), shift_words, shift_bits);
307 
308  if(is_negative() && is_zero())
310 
311  return (*this);
312  }
313 
314 }
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:527
void carry(int64_t &h0, int64_t &h1)
BigInt & operator*=(const BigInt &y)
Definition: big_ops2.cpp:153
word BOTAN_WARN_UNUSED_RESULT bigint_linmul2(word x[], size_t x_size, word y)
Definition: mp_core.h:489
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:297
void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:115
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:539
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:421
word * mutable_data()
Definition: bigint.h:614
void swap_reg(secure_vector< word > &reg)
Definition: bigint.h:167
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:508
BigInt & operator<<=(size_t shift)
Definition: big_ops2.cpp:281
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:620
BigInt & operator>>=(size_t shift)
Definition: big_ops2.cpp:301
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:243
BigInt const BigInt & mod
Definition: numthry.h:105
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:580
void set_words(const word w[], size_t len)
Definition: bigint.h:518
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:197
size_t sig_words() const
Definition: bigint.h:586
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:231
BigInt & mod_mul(uint8_t y, const BigInt &mod, secure_vector< word > &ws)
Definition: big_ops2.cpp:120
void clear()
Definition: bigint.h:366
void cond_flip_sign(bool predicate)
Definition: bigint.cpp:476
void grow_to(size_t n) const
Definition: bigint.h:636
size_t reduce_below(const BigInt &mod, secure_vector< word > &ws)
Definition: bigint.cpp:337
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:513
size_t top_bits_free() const
Definition: bigint.cpp:287
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:159
void set_sign(Sign sign)
Definition: bigint.h:563
void bigint_mod_sub(word t[], const word s[], const word mod[], size_t mod_sw, word ws[])
Definition: mp_core.h:687
BigInt & rev_sub(const word y[], size_t y_words, secure_vector< word > &ws)
Definition: big_ops2.cpp:132
word bigint_modop(word n1, word n0, word d)
Definition: mp_core.h:755