Botan  2.12.1
Crypto and TLS for C++11
bigint.cpp
Go to the documentation of this file.
1 /*
2 * BigInt Base
3 * (C) 1999-2011,2012,2014,2019 Jack Lloyd
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/rounding.h>
11 #include <botan/internal/bit_ops.h>
12 #include <botan/internal/ct_utils.h>
13 #include <botan/loadstor.h>
14 
15 namespace Botan {
16 
17 BigInt::BigInt(const word words[], size_t length)
18  {
19  m_data.set_words(words, length);
20  }
21 
22 /*
23 * Construct a BigInt from a regular number
24 */
25 BigInt::BigInt(uint64_t n)
26  {
27  if(n > 0)
28  {
29 #if BOTAN_MP_WORD_BITS == 32
30  m_data.set_word_at(0, static_cast<word>(n));
31  m_data.set_word_at(1, static_cast<word>(n >> 32));
32 #else
33  m_data.set_word_at(0, n);
34 #endif
35  }
36 
37  }
38 
39 /*
40 * Construct a BigInt of the specified size
41 */
42 BigInt::BigInt(Sign s, size_t size)
43  {
44  m_data.set_size(size);
45  m_signedness = s;
46  }
47 
48 /*
49 * Construct a BigInt from a string
50 */
51 BigInt::BigInt(const std::string& str)
52  {
53  Base base = Decimal;
54  size_t markers = 0;
55  bool negative = false;
56 
57  if(str.length() > 0 && str[0] == '-')
58  {
59  markers += 1;
60  negative = true;
61  }
62 
63  if(str.length() > markers + 2 && str[markers ] == '0' &&
64  str[markers + 1] == 'x')
65  {
66  markers += 2;
67  base = Hexadecimal;
68  }
69 
70  *this = decode(cast_char_ptr_to_uint8(str.data()) + markers,
71  str.length() - markers, base);
72 
73  if(negative) set_sign(Negative);
74  else set_sign(Positive);
75  }
76 
77 BigInt::BigInt(const uint8_t input[], size_t length)
78  {
79  binary_decode(input, length);
80  }
81 
82 /*
83 * Construct a BigInt from an encoded BigInt
84 */
85 BigInt::BigInt(const uint8_t input[], size_t length, Base base)
86  {
87  *this = decode(input, length, base);
88  }
89 
90 BigInt::BigInt(const uint8_t buf[], size_t length, size_t max_bits)
91  {
92  const size_t max_bytes = std::min(length, (max_bits + 7) / 8);
93  binary_decode(buf, max_bytes);
94 
95  const size_t b = this->bits();
96  if(b > max_bits)
97  {
98  *this >>= (b - max_bits);
99  }
100  }
101 
102 /*
103 * Construct a BigInt from an encoded BigInt
104 */
105 BigInt::BigInt(RandomNumberGenerator& rng, size_t bits, bool set_high_bit)
106  {
107  randomize(rng, bits, set_high_bit);
108  }
109 
110 uint8_t BigInt::byte_at(size_t n) const
111  {
112  return get_byte(sizeof(word) - (n % sizeof(word)) - 1,
113  word_at(n / sizeof(word)));
114  }
115 
116 int32_t BigInt::cmp_word(word other) const
117  {
118  if(is_negative())
119  return -1; // other is positive ...
120 
121  const size_t sw = this->sig_words();
122  if(sw > 1)
123  return 1; // must be larger since other is just one word ...
124 
125  return bigint_cmp(this->data(), sw, &other, 1);
126  }
127 
128 /*
129 * Comparison Function
130 */
131 int32_t BigInt::cmp(const BigInt& other, bool check_signs) const
132  {
133  if(check_signs)
134  {
135  if(other.is_positive() && this->is_negative())
136  return -1;
137 
138  if(other.is_negative() && this->is_positive())
139  return 1;
140 
141  if(other.is_negative() && this->is_negative())
142  return (-bigint_cmp(this->data(), this->size(),
143  other.data(), other.size()));
144  }
145 
146  return bigint_cmp(this->data(), this->size(),
147  other.data(), other.size());
148  }
149 
150 bool BigInt::is_equal(const BigInt& other) const
151  {
152  if(this->sign() != other.sign())
153  return false;
154 
155  return bigint_ct_is_eq(this->data(), this->sig_words(),
156  other.data(), other.sig_words()).is_set();
157  }
158 
159 bool BigInt::is_less_than(const BigInt& other) const
160  {
161  if(this->is_negative() && other.is_positive())
162  return true;
163 
164  if(this->is_positive() && other.is_negative())
165  return false;
166 
167  if(other.is_negative() && this->is_negative())
168  {
169  return !bigint_ct_is_lt(other.data(), other.sig_words(),
170  this->data(), this->sig_words(), true).is_set();
171  }
172 
173  return bigint_ct_is_lt(this->data(), this->sig_words(),
174  other.data(), other.sig_words()).is_set();
175  }
176 
177 void BigInt::encode_words(word out[], size_t size) const
178  {
179  const size_t words = sig_words();
180 
181  if(words > size)
182  throw Encoding_Error("BigInt::encode_words value too large to encode");
183 
184  clear_mem(out, size);
185  copy_mem(out, data(), words);
186  }
187 
188 size_t BigInt::Data::calc_sig_words() const
189  {
190  const size_t sz = m_reg.size();
191  size_t sig = sz;
192 
193  word sub = 1;
194 
195  for(size_t i = 0; i != sz; ++i)
196  {
197  const word w = m_reg[sz - i - 1];
198  sub &= ct_is_zero(w);
199  sig -= sub;
200  }
201 
202  /*
203  * This depends on the data so is poisoned, but unpoison it here as
204  * later conditionals are made on the size.
205  */
206  CT::unpoison(sig);
207 
208  return sig;
209  }
210 
211 /*
212 * Return bits {offset...offset+length}
213 */
214 uint32_t BigInt::get_substring(size_t offset, size_t length) const
215  {
216  if(length == 0 || length > 32)
217  throw Invalid_Argument("BigInt::get_substring invalid substring length");
218 
219  const size_t byte_offset = offset / 8;
220  const size_t shift = (offset % 8);
221  const uint32_t mask = 0xFFFFFFFF >> (32 - length);
222 
223  const uint8_t b0 = byte_at(byte_offset);
224  const uint8_t b1 = byte_at(byte_offset + 1);
225  const uint8_t b2 = byte_at(byte_offset + 2);
226  const uint8_t b3 = byte_at(byte_offset + 3);
227  const uint8_t b4 = byte_at(byte_offset + 4);
228  const uint64_t piece = make_uint64(0, 0, 0, b4, b3, b2, b1, b0);
229 
230  return static_cast<uint32_t>((piece >> shift) & mask);
231  }
232 
233 /*
234 * Convert this number to a uint32_t, if possible
235 */
236 uint32_t BigInt::to_u32bit() const
237  {
238  if(is_negative())
239  throw Encoding_Error("BigInt::to_u32bit: Number is negative");
240  if(bits() > 32)
241  throw Encoding_Error("BigInt::to_u32bit: Number is too big to convert");
242 
243  uint32_t out = 0;
244  for(size_t i = 0; i != 4; ++i)
245  out = (out << 8) | byte_at(3-i);
246  return out;
247  }
248 
249 /*
250 * Set bit number n
251 */
252 void BigInt::conditionally_set_bit(size_t n, bool set_it)
253  {
254  const size_t which = n / BOTAN_MP_WORD_BITS;
255  const word mask = static_cast<word>(set_it) << (n % BOTAN_MP_WORD_BITS);
256  m_data.set_word_at(which, word_at(which) | mask);
257  }
258 
259 /*
260 * Clear bit number n
261 */
262 void BigInt::clear_bit(size_t n)
263  {
264  const size_t which = n / BOTAN_MP_WORD_BITS;
265 
266  if(which < size())
267  {
268  const word mask = ~(static_cast<word>(1) << (n % BOTAN_MP_WORD_BITS));
269  m_data.set_word_at(which, word_at(which) & mask);
270  }
271  }
272 
273 size_t BigInt::bytes() const
274  {
275  return round_up(bits(), 8) / 8;
276  }
277 
278 size_t BigInt::top_bits_free() const
279  {
280  const size_t words = sig_words();
281 
282  const word top_word = word_at(words - 1);
283  const size_t bits_used = high_bit(top_word);
284  CT::unpoison(bits_used);
285  return BOTAN_MP_WORD_BITS - bits_used;
286  }
287 
288 size_t BigInt::bits() const
289  {
290  const size_t words = sig_words();
291 
292  if(words == 0)
293  return 0;
294 
295  const size_t full_words = (words - 1) * BOTAN_MP_WORD_BITS;
296  const size_t top_bits = BOTAN_MP_WORD_BITS - top_bits_free();
297 
298  return full_words + top_bits;
299  }
300 
301 /*
302 * Calcluate the size in a certain base
303 */
304 size_t BigInt::encoded_size(Base base) const
305  {
306  static const double LOG_2_BASE_10 = 0.30102999566;
307 
308  if(base == Binary)
309  return bytes();
310  else if(base == Hexadecimal)
311  return 2*bytes();
312  else if(base == Decimal)
313  return static_cast<size_t>((bits() * LOG_2_BASE_10) + 1);
314  else
315  throw Invalid_Argument("Unknown base for BigInt encoding");
316  }
317 
318 /*
319 * Return the negation of this number
320 */
322  {
323  BigInt x = (*this);
324  x.flip_sign();
325  return x;
326  }
327 
329  {
330  if(p.is_negative() || this->is_negative())
331  throw Invalid_Argument("BigInt::reduce_below both values must be positive");
332 
333  const size_t p_words = p.sig_words();
334 
335  if(size() < p_words + 1)
336  grow_to(p_words + 1);
337 
338  if(ws.size() < p_words + 1)
339  ws.resize(p_words + 1);
340 
341  clear_mem(ws.data(), ws.size());
342 
343  size_t reductions = 0;
344 
345  for(;;)
346  {
347  word borrow = bigint_sub3(ws.data(), data(), p_words + 1, p.data(), p_words);
348  if(borrow)
349  break;
350 
351  ++reductions;
352  swap_reg(ws);
353  }
354 
355  return reductions;
356  }
357 
358 void BigInt::ct_reduce_below(const BigInt& mod, secure_vector<word>& ws, size_t bound)
359  {
360  if(mod.is_negative() || this->is_negative())
361  throw Invalid_Argument("BigInt::ct_reduce_below both values must be positive");
362 
363  const size_t mod_words = mod.sig_words();
364 
365  grow_to(mod_words);
366 
367  const size_t sz = size();
368 
369  ws.resize(sz);
370 
371  clear_mem(ws.data(), sz);
372 
373  for(size_t i = 0; i != bound; ++i)
374  {
375  word borrow = bigint_sub3(ws.data(), data(), sz, mod.data(), mod_words);
376 
377  CT::Mask<word>::is_zero(borrow).select_n(mutable_data(), ws.data(), data(), sz);
378  }
379  }
380 
381 /*
382 * Return the absolute value of this number
383 */
385  {
386  BigInt x = (*this);
387  x.set_sign(Positive);
388  return x;
389  }
390 
391 void BigInt::binary_encode(uint8_t buf[]) const
392  {
393  this->binary_encode(buf, bytes());
394  }
395 
396 /*
397 * Encode this number into bytes
398 */
399 void BigInt::binary_encode(uint8_t output[], size_t len) const
400  {
401  const size_t full_words = len / sizeof(word);
402  const size_t extra_bytes = len % sizeof(word);
403 
404  for(size_t i = 0; i != full_words; ++i)
405  {
406  const word w = word_at(i);
407  store_be(w, output + (len - (i+1)*sizeof(word)));
408  }
409 
410  if(extra_bytes > 0)
411  {
412  const word w = word_at(full_words);
413 
414  for(size_t i = 0; i != extra_bytes; ++i)
415  {
416  output[extra_bytes - i - 1] = get_byte(sizeof(word) - i - 1, w);
417  }
418  }
419  }
420 
421 /*
422 * Set this number to the value in buf
423 */
424 void BigInt::binary_decode(const uint8_t buf[], size_t length)
425  {
426  clear();
427 
428  const size_t full_words = length / sizeof(word);
429  const size_t extra_bytes = length % sizeof(word);
430 
431  secure_vector<word> reg((round_up(full_words + (extra_bytes > 0 ? 1 : 0), 8)));
432 
433  for(size_t i = 0; i != full_words; ++i)
434  {
435  reg[i] = load_be<word>(buf + length - sizeof(word)*(i+1), 0);
436  }
437 
438  if(extra_bytes > 0)
439  {
440  for(size_t i = 0; i != extra_bytes; ++i)
441  reg[full_words] = (reg[full_words] << 8) | buf[i];
442  }
443 
444  m_data.swap(reg);
445  }
446 
447 void BigInt::ct_cond_swap(bool predicate, BigInt& other)
448  {
449  const size_t max_words = std::max(size(), other.size());
450  grow_to(max_words);
451  other.grow_to(max_words);
452 
453  bigint_cnd_swap(predicate, this->mutable_data(), other.mutable_data(), max_words);
454  }
455 
456 void BigInt::cond_flip_sign(bool predicate)
457  {
458  // This code is assuming Negative == 0, Positive == 1
459 
460  const auto mask = CT::Mask<uint8_t>::expand(predicate);
461 
462  const uint8_t current_sign = static_cast<uint8_t>(sign());
463 
464  const uint8_t new_sign = mask.select(current_sign ^ 1, current_sign);
465 
466  set_sign(static_cast<Sign>(new_sign));
467  }
468 
469 void BigInt::ct_cond_assign(bool predicate, const BigInt& other)
470  {
471  const size_t t_words = size();
472  const size_t o_words = other.size();
473 
474  if(o_words < t_words)
475  grow_to(o_words);
476 
477  const size_t r_words = std::max(t_words, o_words);
478 
479  const auto mask = CT::Mask<word>::expand(predicate);
480 
481  for(size_t i = 0; i != r_words; ++i)
482  {
483  const word o_word = other.word_at(i);
484  const word t_word = this->word_at(i);
485  this->set_word_at(i, mask.select(o_word, t_word));
486  }
487 
488  if(sign() != other.sign())
489  {
490  cond_flip_sign(predicate);
491  }
492  }
493 
494 #if defined(BOTAN_HAS_VALGRIND)
495 void BigInt::const_time_poison() const
496  {
497  CT::poison(m_data.const_data(), m_data.size());
498  }
499 
500 void BigInt::const_time_unpoison() const
501  {
502  CT::unpoison(m_data.const_data(), m_data.size());
503  }
504 #endif
505 
507  const std::vector<BigInt>& vec,
508  size_t idx)
509  {
510  const size_t words = output.size();
511 
512  clear_mem(output.data(), output.size());
513 
514  CT::poison(&idx, sizeof(idx));
515 
516  for(size_t i = 0; i != vec.size(); ++i)
517  {
518  BOTAN_ASSERT(vec[i].size() >= words,
519  "Word size as expected in const_time_lookup");
520 
521  const auto mask = CT::Mask<word>::is_equal(i, idx);
522 
523  for(size_t w = 0; w != words; ++w)
524  {
525  const word viw = vec[i].word_at(w);
526  output[w] = mask.if_set_return(viw);
527  }
528  }
529 
530  CT::unpoison(idx);
531  CT::unpoison(output.data(), output.size());
532  }
533 
534 }
bool is_negative() const
Definition: bigint.h:525
static void const_time_lookup(secure_vector< word > &output, const std::vector< BigInt > &vec, size_t idx)
Definition: bigint.cpp:506
void store_be(uint16_t in, uint8_t out[2])
Definition: loadstor.h:438
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 randomize(RandomNumberGenerator &rng, size_t bitsize, bool set_high_bit=true)
Definition: big_rand.cpp:17
int32_t cmp(const BigInt &n, bool check_signs=true) const
Definition: bigint.cpp:131
void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:111
Sign sign() const
Definition: bigint.h:537
constexpr uint8_t get_byte(size_t byte_num, T input)
Definition: loadstor.h:41
const uint8_t * cast_char_ptr_to_uint8(const char *s)
Definition: mem_ops.h:164
constexpr uint64_t make_uint64(uint8_t i0, uint8_t i1, uint8_t i2, uint8_t i3, uint8_t i4, uint8_t i5, uint8_t i6, uint8_t i7)
Definition: loadstor.h:87
word * mutable_data()
Definition: bigint.h:612
void swap_reg(secure_vector< word > &reg)
Definition: bigint.h:165
void poison(const T *p, size_t n)
Definition: ct_utils.h:48
word bigint_sub3(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:342
void binary_encode(uint8_t buf[]) const
Definition: bigint.cpp:391
word word_at(size_t n) const
Definition: bigint.h:506
uint32_t get_substring(size_t offset, size_t length) const
Definition: bigint.cpp:214
BigInt operator-() const
Definition: bigint.cpp:321
const word * data() const
Definition: bigint.h:618
#define BOTAN_ASSERT(expr, assertion_made)
Definition: assert.h:55
uint8_t byte_at(size_t n) const
Definition: bigint.cpp:110
void const_time_poison() const
Definition: bigint.h:732
static Mask< T > expand(T v)
Definition: ct_utils.h:123
void encode_words(word out[], size_t size) const
Definition: bigint.cpp:177
bool is_less_than(const BigInt &n) const
Definition: bigint.cpp:159
void ct_cond_swap(bool predicate, BigInt &other)
Definition: bigint.cpp:447
void bigint_cnd_swap(word cnd, word x[], word y[], size_t size)
Definition: mp_core.h:29
T ct_is_zero(T x)
Definition: bit_ops.h:32
int32_t cmp_word(word n) const
Definition: bigint.cpp:116
CT::Mask< word > bigint_ct_is_eq(const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:611
size_t size() const
Definition: bigint.h:578
size_t high_bit(T n)
Definition: bit_ops.h:55
void copy_mem(T *out, const T *in, size_t n)
Definition: mem_ops.h:122
Definition: alg_id.cpp:13
size_t sig_words() const
Definition: bigint.h:584
size_t bytes() const
Definition: bigint.cpp:273
void clear()
Definition: bigint.h:364
void conditionally_set_bit(size_t n, bool set_it)
Definition: bigint.cpp:252
void cond_flip_sign(bool predicate)
Definition: bigint.cpp:456
void const_time_unpoison() const
Definition: bigint.h:733
CT::Mask< word > bigint_ct_is_lt(const word x[], size_t x_size, const word y[], size_t y_size, bool lt_or_equal=false)
Definition: mp_core.h:574
static BigInt decode(const uint8_t buf[], size_t length)
Definition: bigint.h:798
void grow_to(size_t n) const
Definition: bigint.h:634
size_t encoded_size(Base base=Binary) const
Definition: bigint.cpp:304
BigInt abs() const
Definition: bigint.cpp:384
size_t reduce_below(const BigInt &mod, secure_vector< word > &ws)
Definition: bigint.cpp:328
void set_word_at(size_t i, word w)
Definition: bigint.h:511
uint32_t to_u32bit() const
Definition: bigint.cpp:236
void binary_decode(const uint8_t buf[], size_t length)
Definition: bigint.cpp:424
void unpoison(const T *p, size_t n)
Definition: ct_utils.h:59
void ct_reduce_below(const BigInt &mod, secure_vector< word > &ws, size_t bound)
Definition: bigint.cpp:358
BigInt()=default
size_t top_bits_free() const
Definition: bigint.cpp:278
std::vector< T, secure_allocator< T > > secure_vector
Definition: secmem.h:65
void flip_sign()
Definition: bigint.h:552
void clear_bit(size_t n)
Definition: bigint.cpp:262
static Mask< T > is_zero(T x)
Definition: ct_utils.h:141
size_t round_up(size_t n, size_t align_to)
Definition: rounding.h:21
void set_sign(Sign sign)
Definition: bigint.h:561
static Mask< T > is_equal(T x, T y)
Definition: ct_utils.h:149
bool is_positive() const
Definition: bigint.h:531
void ct_cond_assign(bool predicate, const BigInt &other)
Definition: bigint.cpp:469
bool is_equal(const BigInt &n) const
Definition: bigint.cpp:150