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