1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
|
/*
* BigInt
* (C) 1999-2008,2012 Jack Lloyd
* 2007 FlexSecure
*
* Botan is released under the Simplified BSD License (see license.txt)
*/
#ifndef BOTAN_BIGINT_H_
#define BOTAN_BIGINT_H_
#include <botan/types.h>
#include <botan/secmem.h>
#include <botan/exceptn.h>
#include <botan/loadstor.h>
#include <iosfwd>
namespace Botan {
class RandomNumberGenerator;
/**
* Arbitrary precision integer
*/
class BOTAN_PUBLIC_API(2,0) BigInt final
{
public:
/**
* Base enumerator for encoding and decoding
*/
enum Base { Decimal = 10, Hexadecimal = 16, Binary = 256 };
/**
* Sign symbol definitions for positive and negative numbers
*/
enum Sign { Negative = 0, Positive = 1 };
/**
* DivideByZero Exception
*/
class BOTAN_PUBLIC_API(2,0) DivideByZero final : public Exception
{
public:
DivideByZero() : Exception("BigInt divide by zero") {}
};
/**
* Create empty BigInt
*/
BigInt() = default;
/**
* Create BigInt from 64 bit integer
* @param n initial value of this BigInt
*/
BigInt(uint64_t n);
/**
* Copy Constructor
* @param other the BigInt to copy
*/
BigInt(const BigInt& other);
/**
* Create BigInt from a string. If the string starts with 0x the
* rest of the string will be interpreted as hexadecimal digits.
* Otherwise, it will be interpreted as a decimal number.
*
* @param str the string to parse for an integer value
*/
explicit BigInt(const std::string& str);
/**
* Create a BigInt from an integer in a byte array
* @param buf the byte array holding the value
* @param length size of buf
*/
BigInt(const uint8_t buf[], size_t length);
/**
* Create a BigInt from an integer in a byte array
* @param buf the byte array holding the value
* @param length size of buf
* @param base is the number base of the integer in buf
*/
BigInt(const uint8_t buf[], size_t length, Base base);
/**
* Create a BigInt from an array of words
* @param words the words
* @param length number of words
*/
BigInt(const word words[], size_t length);
/**
* \brief Create a random BigInt of the specified size
*
* @param rng random number generator
* @param bits size in bits
* @param set_high_bit if true, the highest bit is always set
*
* @see randomize
*/
BigInt(RandomNumberGenerator& rng, size_t bits, bool set_high_bit = true);
/**
* Create BigInt of specified size, all zeros
* @param sign the sign
* @param n size of the internal register in words
*/
BigInt(Sign sign, size_t n);
/**
* Move constructor
*/
BigInt(BigInt&& other)
{
this->swap(other);
}
/**
* Move assignment
*/
BigInt& operator=(BigInt&& other)
{
if(this != &other)
this->swap(other);
return (*this);
}
/**
* Copy assignment
*/
BigInt& operator=(const BigInt&) = default;
/**
* Swap this value with another
* @param other BigInt to swap values with
*/
void swap(BigInt& other)
{
m_reg.swap(other.m_reg);
std::swap(m_signedness, other.m_signedness);
}
void swap_reg(secure_vector<word>& reg)
{
m_reg.swap(reg);
}
/**
* += operator
* @param y the BigInt to add to this
*/
BigInt& operator+=(const BigInt& y);
/**
* -= operator
* @param y the BigInt to subtract from this
*/
BigInt& operator-=(const BigInt& y);
/**
* *= operator
* @param y the BigInt to multiply with this
*/
BigInt& operator*=(const BigInt& y);
/**
* *= operator
* @param y the word to multiply with this
*/
BigInt& operator*=(word y);
/**
* /= operator
* @param y the BigInt to divide this by
*/
BigInt& operator/=(const BigInt& y);
/**
* Modulo operator
* @param y the modulus to reduce this by
*/
BigInt& operator%=(const BigInt& y);
/**
* Modulo operator
* @param y the modulus (word) to reduce this by
*/
word operator%=(word y);
/**
* Left shift operator
* @param shift the number of bits to shift this left by
*/
BigInt& operator<<=(size_t shift);
/**
* Right shift operator
* @param shift the number of bits to shift this right by
*/
BigInt& operator>>=(size_t shift);
/**
* Increment operator
*/
BigInt& operator++() { return (*this += 1); }
/**
* Decrement operator
*/
BigInt& operator--() { return (*this -= 1); }
/**
* Postfix increment operator
*/
BigInt operator++(int) { BigInt x = (*this); ++(*this); return x; }
/**
* Postfix decrement operator
*/
BigInt operator--(int) { BigInt x = (*this); --(*this); return x; }
/**
* Unary negation operator
* @return negative this
*/
BigInt operator-() const;
/**
* ! operator
* @return true iff this is zero, otherwise false
*/
bool operator !() const { return (!is_nonzero()); }
/**
* Multiply this with y
* @param y the BigInt to multiply with this
* @param ws a temp workspace
*/
BigInt& mul(const BigInt& y, secure_vector<word>& ws);
/**
* Set *this to y - *this
* @param y the BigInt to subtract from
* @param ws a temp workspace
*/
BigInt& rev_sub(const word y[], size_t y_size, secure_vector<word>& ws);
/**
* Return *this below mod
*
* Assumes that *this is (if anything) only slightly larger than
* mod and performs repeated subtractions. It should not be used if
* *this is much larger than mod, instead of modulo operator.
*/
void reduce_below(const BigInt& mod, secure_vector<word> &ws);
/**
* Zeroize the BigInt. The size of the underlying register is not
* modified.
*/
void clear() { zeroise(m_reg); }
/**
* Compare this to another BigInt
* @param n the BigInt value to compare with
* @param check_signs include sign in comparison?
* @result if (this<n) return -1, if (this>n) return 1, if both
* values are identical return 0 [like Perl's <=> operator]
*/
int32_t cmp(const BigInt& n, bool check_signs = true) const;
/**
* Test if the integer has an even value
* @result true if the integer is even, false otherwise
*/
bool is_even() const { return (get_bit(0) == 0); }
/**
* Test if the integer has an odd value
* @result true if the integer is odd, false otherwise
*/
bool is_odd() const { return (get_bit(0) == 1); }
/**
* Test if the integer is not zero
* @result true if the integer is non-zero, false otherwise
*/
bool is_nonzero() const { return (!is_zero()); }
/**
* Test if the integer is zero
* @result true if the integer is zero, false otherwise
*/
bool is_zero() const
{
const size_t sw = sig_words();
for(size_t i = 0; i != sw; ++i)
if(m_reg[i])
return false;
return true;
}
/**
* Set bit at specified position
* @param n bit position to set
*/
void set_bit(size_t n);
/**
* Clear bit at specified position
* @param n bit position to clear
*/
void clear_bit(size_t n);
/**
* Clear all but the lowest n bits
* @param n amount of bits to keep
*/
void mask_bits(size_t n)
{
if(n == 0) { clear(); return; }
const size_t top_word = n / BOTAN_MP_WORD_BITS;
const word mask = (static_cast<word>(1) << (n % BOTAN_MP_WORD_BITS)) - 1;
if(top_word < size())
{
const size_t len = size() - (top_word + 1);
if (len > 0)
{
clear_mem(&m_reg[top_word+1], len);
}
m_reg[top_word] &= mask;
}
}
/**
* Return bit value at specified position
* @param n the bit offset to test
* @result true, if the bit at position n is set, false otherwise
*/
bool get_bit(size_t n) const
{
return ((word_at(n / BOTAN_MP_WORD_BITS) >> (n % BOTAN_MP_WORD_BITS)) & 1);
}
/**
* Return (a maximum of) 32 bits of the complete value
* @param offset the offset to start extracting
* @param length amount of bits to extract (starting at offset)
* @result the integer extracted from the register starting at
* offset with specified length
*/
uint32_t get_substring(size_t offset, size_t length) const;
/**
* Convert this value into a uint32_t, if it is in the range
* [0 ... 2**32-1], or otherwise throw an exception.
* @result the value as a uint32_t if conversion is possible
*/
uint32_t to_u32bit() const;
/**
* @param n the offset to get a byte from
* @result byte at offset n
*/
uint8_t byte_at(size_t n) const
{
return get_byte(sizeof(word) - (n % sizeof(word)) - 1,
word_at(n / sizeof(word)));
}
/**
* Return the word at a specified position of the internal register
* @param n position in the register
* @return value at position n
*/
word word_at(size_t n) const
{ return ((n < size()) ? m_reg[n] : 0); }
void set_word_at(size_t i, word w)
{
if(i >= m_reg.size())
grow_to(i + 1);
m_reg[i] = w;
}
/**
* Tests if the sign of the integer is negative
* @result true, iff the integer has a negative sign
*/
bool is_negative() const { return (sign() == Negative); }
/**
* Tests if the sign of the integer is positive
* @result true, iff the integer has a positive sign
*/
bool is_positive() const { return (sign() == Positive); }
/**
* Return the sign of the integer
* @result the sign of the integer
*/
Sign sign() const { return (m_signedness); }
/**
* @result the opposite sign of the represented integer value
*/
Sign reverse_sign() const
{
if(sign() == Positive)
return Negative;
return Positive;
}
/**
* Flip the sign of this BigInt
*/
void flip_sign()
{
set_sign(reverse_sign());
}
/**
* Set sign of the integer
* @param sign new Sign to set
*/
void set_sign(Sign sign)
{
if(is_zero())
m_signedness = Positive;
else
m_signedness = sign;
}
/**
* @result absolute (positive) value of this
*/
BigInt abs() const;
/**
* Give size of internal register
* @result size of internal register in words
*/
size_t size() const { return m_reg.size(); }
/**
* Return how many words we need to hold this value
* @result significant words of the represented integer value
*/
size_t sig_words() const
{
const word* x = m_reg.data();
size_t sig = m_reg.size();
while(sig && (x[sig-1] == 0))
sig--;
return sig;
}
/**
* Give byte length of the integer
* @result byte length of the represented integer value
*/
size_t bytes() const;
/**
* Get the bit length of the integer
* @result bit length of the represented integer value
*/
size_t bits() const;
/**
* Return a mutable pointer to the register
* @result a pointer to the start of the internal register
*/
word* mutable_data() { return m_reg.data(); }
/**
* Return a const pointer to the register
* @result a pointer to the start of the internal register
*/
const word* data() const { return m_reg.data(); }
secure_vector<word>& get_word_vector() { return m_reg; }
const secure_vector<word>& get_word_vector() const { return m_reg; }
/**
* Increase internal register buffer to at least n words
* @param n new size of register
*/
void grow_to(size_t n);
/**
* Resize the vector to the minimum word size to hold the integer, or
* min_size words, whichever is larger
*/
void shrink_to_fit(size_t min_size = 0);
/**
* Fill BigInt with a random number with size of bitsize
*
* If \p set_high_bit is true, the highest bit will be set, which causes
* the entropy to be \a bits-1. Otherwise the highest bit is randomly chosen
* by the rng, causing the entropy to be \a bits.
*
* @param rng the random number generator to use
* @param bitsize number of bits the created random value should have
* @param set_high_bit if true, the highest bit is always set
*/
void randomize(RandomNumberGenerator& rng, size_t bitsize, bool set_high_bit = true);
/**
* Store BigInt-value in a given byte array
* @param buf destination byte array for the integer value
*/
void binary_encode(uint8_t buf[]) const;
/**
* Read integer value from a byte array with given size
* @param buf byte array buffer containing the integer
* @param length size of buf
*/
void binary_decode(const uint8_t buf[], size_t length);
/**
* Read integer value from a byte array (secure_vector<uint8_t>)
* @param buf the array to load from
*/
void binary_decode(const secure_vector<uint8_t>& buf)
{
binary_decode(buf.data(), buf.size());
}
/**
* @param base the base to measure the size for
* @return size of this integer in base base
*/
size_t encoded_size(Base base = Binary) const;
/**
* Place the value into out, zero-padding up to size words
* Throw if *this cannot be represented in size words
*/
void encode_words(word out[], size_t size) const;
/**
* @param rng a random number generator
* @param min the minimum value
* @param max the maximum value
* @return random integer in [min,max)
*/
static BigInt random_integer(RandomNumberGenerator& rng,
const BigInt& min,
const BigInt& max);
/**
* Create a power of two
* @param n the power of two to create
* @return bigint representing 2^n
*/
static BigInt power_of_2(size_t n)
{
BigInt b;
b.set_bit(n);
return b;
}
/**
* Encode the integer value from a BigInt to a std::vector of bytes
* @param n the BigInt to use as integer source
* @param base number-base of resulting byte array representation
* @result secure_vector of bytes containing the integer with given base
*/
static std::vector<uint8_t> encode(const BigInt& n, Base base = Binary);
/**
* Encode the integer value from a BigInt to a secure_vector of bytes
* @param n the BigInt to use as integer source
* @param base number-base of resulting byte array representation
* @result secure_vector of bytes containing the integer with given base
*/
static secure_vector<uint8_t> encode_locked(const BigInt& n,
Base base = Binary);
/**
* Encode the integer value from a BigInt to a byte array
* @param buf destination byte array for the encoded integer
* value with given base
* @param n the BigInt to use as integer source
* @param base number-base of resulting byte array representation
*/
static void encode(uint8_t buf[], const BigInt& n, Base base = Binary);
/**
* Create a BigInt from an integer in a byte array
* @param buf the binary value to load
* @param length size of buf
* @param base number-base of the integer in buf
* @result BigInt representing the integer in the byte array
*/
static BigInt decode(const uint8_t buf[], size_t length,
Base base = Binary);
/**
* Create a BigInt from an integer in a byte array
* @param buf the binary value to load
* @param base number-base of the integer in buf
* @result BigInt representing the integer in the byte array
*/
static BigInt decode(const secure_vector<uint8_t>& buf,
Base base = Binary)
{
return BigInt::decode(buf.data(), buf.size(), base);
}
/**
* Create a BigInt from an integer in a byte array
* @param buf the binary value to load
* @param base number-base of the integer in buf
* @result BigInt representing the integer in the byte array
*/
static BigInt decode(const std::vector<uint8_t>& buf,
Base base = Binary)
{
return BigInt::decode(buf.data(), buf.size(), base);
}
/**
* Encode a BigInt to a byte array according to IEEE 1363
* @param n the BigInt to encode
* @param bytes the length of the resulting secure_vector<uint8_t>
* @result a secure_vector<uint8_t> containing the encoded BigInt
*/
static secure_vector<uint8_t> encode_1363(const BigInt& n, size_t bytes);
static void encode_1363(uint8_t out[], size_t bytes, const BigInt& n);
/**
* Encode two BigInt to a byte array according to IEEE 1363
* @param n1 the first BigInt to encode
* @param n2 the second BigInt to encode
* @param bytes the length of the encoding of each single BigInt
* @result a secure_vector<uint8_t> containing the concatenation of the two encoded BigInt
*/
static secure_vector<uint8_t> encode_fixed_length_int_pair(const BigInt& n1, const BigInt& n2, size_t bytes);
/**
* Set output = vec[idx].m_reg in constant time
* All words of vec must have the same size
*/
static void const_time_lookup(
secure_vector<word>& output,
const std::vector<BigInt>& vec,
size_t idx);
private:
secure_vector<word> m_reg;
Sign m_signedness = Positive;
};
/*
* Arithmetic Operators
*/
BigInt BOTAN_PUBLIC_API(2,0) operator+(const BigInt& x, const BigInt& y);
BigInt BOTAN_PUBLIC_API(2,0) operator-(const BigInt& x, const BigInt& y);
BigInt BOTAN_PUBLIC_API(2,0) operator*(const BigInt& x, const BigInt& y);
BigInt BOTAN_PUBLIC_API(2,0) operator/(const BigInt& x, const BigInt& d);
BigInt BOTAN_PUBLIC_API(2,0) operator%(const BigInt& x, const BigInt& m);
word BOTAN_PUBLIC_API(2,0) operator%(const BigInt& x, word m);
BigInt BOTAN_PUBLIC_API(2,0) operator<<(const BigInt& x, size_t n);
BigInt BOTAN_PUBLIC_API(2,0) operator>>(const BigInt& x, size_t n);
/*
* Comparison Operators
*/
inline bool operator==(const BigInt& a, const BigInt& b)
{ return (a.cmp(b) == 0); }
inline bool operator!=(const BigInt& a, const BigInt& b)
{ return (a.cmp(b) != 0); }
inline bool operator<=(const BigInt& a, const BigInt& b)
{ return (a.cmp(b) <= 0); }
inline bool operator>=(const BigInt& a, const BigInt& b)
{ return (a.cmp(b) >= 0); }
inline bool operator<(const BigInt& a, const BigInt& b)
{ return (a.cmp(b) < 0); }
inline bool operator>(const BigInt& a, const BigInt& b)
{ return (a.cmp(b) > 0); }
/*
* I/O Operators
*/
BOTAN_PUBLIC_API(2,0) std::ostream& operator<<(std::ostream&, const BigInt&);
BOTAN_PUBLIC_API(2,0) std::istream& operator>>(std::istream&, BigInt&);
}
namespace std {
template<>
inline void swap<Botan::BigInt>(Botan::BigInt& x, Botan::BigInt& y)
{
x.swap(y);
}
}
#endif
|