Botan  2.4.0
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 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 
14 namespace Botan {
15 
16 /*
17 * Construct a BigInt from a regular number
18 */
19 BigInt::BigInt(uint64_t n)
20  {
21  if(n == 0)
22  return;
23 
24  const size_t limbs_needed = sizeof(uint64_t) / sizeof(word);
25 
26  m_reg.resize(4*limbs_needed);
27  for(size_t i = 0; i != limbs_needed; ++i)
28  m_reg[i] = ((n >> (i*MP_WORD_BITS)) & MP_WORD_MASK);
29  }
30 
31 /*
32 * Construct a BigInt of the specified size
33 */
35  {
36  m_reg.resize(round_up(size, 8));
37  m_signedness = s;
38  }
39 
40 /*
41 * Copy constructor
42 */
43 BigInt::BigInt(const BigInt& other)
44  {
45  m_reg = other.m_reg;
46  m_signedness = other.m_signedness;
47  }
48 
49 /*
50 * Construct a BigInt from a string
51 */
52 BigInt::BigInt(const std::string& str)
53  {
54  Base base = Decimal;
55  size_t markers = 0;
56  bool negative = false;
57 
58  if(str.length() > 0 && str[0] == '-')
59  {
60  markers += 1;
61  negative = true;
62  }
63 
64  if(str.length() > markers + 2 && str[markers ] == '0' &&
65  str[markers + 1] == 'x')
66  {
67  markers += 2;
68  base = Hexadecimal;
69  }
70 
71  *this = decode(cast_char_ptr_to_uint8(str.data()) + markers,
72  str.length() - markers, base);
73 
74  if(negative) set_sign(Negative);
75  else set_sign(Positive);
76  }
77 
78 /*
79 * Construct a BigInt from an encoded BigInt
80 */
81 BigInt::BigInt(const uint8_t input[], size_t length, Base base)
82  {
83  *this = decode(input, length, base);
84  }
85 
86 /*
87 * Construct a BigInt from an encoded BigInt
88 */
89 BigInt::BigInt(RandomNumberGenerator& rng, size_t bits, bool set_high_bit)
90  {
91  randomize(rng, bits, set_high_bit);
92  }
93 
94 /*
95 * Comparison Function
96 */
97 int32_t BigInt::cmp(const BigInt& other, bool check_signs) const
98  {
99  if(check_signs)
100  {
101  if(other.is_positive() && this->is_negative())
102  return -1;
103 
104  if(other.is_negative() && this->is_positive())
105  return 1;
106 
107  if(other.is_negative() && this->is_negative())
108  return (-bigint_cmp(this->data(), this->sig_words(),
109  other.data(), other.sig_words()));
110  }
111 
112  return bigint_cmp(this->data(), this->sig_words(),
113  other.data(), other.sig_words());
114  }
115 
116 /*
117 * Return bits {offset...offset+length}
118 */
119 uint32_t BigInt::get_substring(size_t offset, size_t length) const
120  {
121  if(length > 32)
122  throw Invalid_Argument("BigInt::get_substring: Substring size too big");
123 
124  uint64_t piece = 0;
125  for(size_t i = 0; i != 8; ++i)
126  {
127  const uint8_t part = byte_at((offset / 8) + (7-i));
128  piece = (piece << 8) | part;
129  }
130 
131  const uint64_t mask = (static_cast<uint64_t>(1) << length) - 1;
132  const size_t shift = (offset % 8);
133 
134  return static_cast<uint32_t>((piece >> shift) & mask);
135  }
136 
137 /*
138 * Convert this number to a uint32_t, if possible
139 */
140 uint32_t BigInt::to_u32bit() const
141  {
142  if(is_negative())
143  throw Encoding_Error("BigInt::to_u32bit: Number is negative");
144  if(bits() > 32)
145  throw Encoding_Error("BigInt::to_u32bit: Number is too big to convert");
146 
147  uint32_t out = 0;
148  for(size_t i = 0; i != 4; ++i)
149  out = (out << 8) | byte_at(3-i);
150  return out;
151  }
152 
153 /*
154 * Set bit number n
155 */
156 void BigInt::set_bit(size_t n)
157  {
158  const size_t which = n / MP_WORD_BITS;
159  const word mask = static_cast<word>(1) << (n % MP_WORD_BITS);
160  if(which >= size()) grow_to(which + 1);
161  m_reg[which] |= mask;
162  }
163 
164 /*
165 * Clear bit number n
166 */
167 void BigInt::clear_bit(size_t n)
168  {
169  const size_t which = n / MP_WORD_BITS;
170  const word mask = static_cast<word>(1) << (n % MP_WORD_BITS);
171  if(which < size())
172  m_reg[which] &= ~mask;
173  }
174 
175 size_t BigInt::bytes() const
176  {
177  return round_up(bits(), 8) / 8;
178  }
179 
180 /*
181 * Count how many bits are being used
182 */
183 size_t BigInt::bits() const
184  {
185  const size_t words = sig_words();
186 
187  if(words == 0)
188  return 0;
189 
190  const size_t full_words = words - 1;
191  return (full_words * MP_WORD_BITS + high_bit(word_at(full_words)));
192  }
193 
194 /*
195 * Calcluate the size in a certain base
196 */
197 size_t BigInt::encoded_size(Base base) const
198  {
199  static const double LOG_2_BASE_10 = 0.30102999566;
200 
201  if(base == Binary)
202  return bytes();
203  else if(base == Hexadecimal)
204  return 2*bytes();
205  else if(base == Decimal)
206  return static_cast<size_t>((bits() * LOG_2_BASE_10) + 1);
207  else
208  throw Invalid_Argument("Unknown base for BigInt encoding");
209  }
210 
211 /*
212 * Set the sign
213 */
215  {
216  if(is_zero())
217  m_signedness = Positive;
218  else
219  m_signedness = s;
220  }
221 
222 /*
223 * Reverse the value of the sign flag
224 */
226  {
228  }
229 
230 /*
231 * Return the opposite value of the current sign
232 */
234  {
235  if(sign() == Positive)
236  return Negative;
237  return Positive;
238  }
239 
240 /*
241 * Return the negation of this number
242 */
244  {
245  BigInt x = (*this);
246  x.flip_sign();
247  return x;
248  }
249 
250 /*
251 * Return the absolute value of this number
252 */
254  {
255  BigInt x = (*this);
256  x.set_sign(Positive);
257  return x;
258  }
259 
260 void BigInt::grow_to(size_t n)
261  {
262  if(n > size())
263  m_reg.resize(round_up(n, 8));
264  }
265 
266 /*
267 * Encode this number into bytes
268 */
269 void BigInt::binary_encode(uint8_t output[]) const
270  {
271  const size_t sig_bytes = bytes();
272  for(size_t i = 0; i != sig_bytes; ++i)
273  output[sig_bytes-i-1] = byte_at(i);
274  }
275 
276 /*
277 * Set this number to the value in buf
278 */
279 void BigInt::binary_decode(const uint8_t buf[], size_t length)
280  {
281  const size_t WORD_BYTES = sizeof(word);
282 
283  clear();
284  m_reg.resize(round_up((length / WORD_BYTES) + 1, 8));
285 
286  for(size_t i = 0; i != length / WORD_BYTES; ++i)
287  {
288  const size_t top = length - WORD_BYTES*i;
289  for(size_t j = WORD_BYTES; j > 0; --j)
290  m_reg[i] = (m_reg[i] << 8) | buf[top - j];
291  }
292 
293  for(size_t i = 0; i != length % WORD_BYTES; ++i)
294  m_reg[length / WORD_BYTES] = (m_reg[length / WORD_BYTES] << 8) | buf[i];
295  }
296 
298  {
299  m_reg.resize(sig_words());
300  }
301 
303  const std::vector<BigInt>& vec,
304  size_t idx)
305  {
306  const size_t words = output.size();
307 
308  clear_mem(output.data(), output.size());
309 
310  CT::poison(&idx, sizeof(idx));
311 
312  for(size_t i = 0; i != vec.size(); ++i)
313  {
314  BOTAN_ASSERT(vec[i].size() >= words,
315  "Word size as expected in const_time_lookup");
316 
317  for(size_t w = 0; w != words; ++w)
318  output[w] |= CT::select<word>(CT::is_equal(i, idx), vec[i].word_at(w), 0);
319  }
320 
321  CT::unpoison(idx);
322  CT::unpoison(output.data(), output.size());
323  }
324 
325 }
Sign reverse_sign() const
Definition: bigint.cpp:233
bool is_negative() const
Definition: bigint.h:353
static void const_time_lookup(secure_vector< word > &output, const std::vector< BigInt > &vec, size_t idx)
Definition: bigint.cpp:302
int32_t bigint_cmp(const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.cpp:378
size_t bits() const
Definition: bigint.cpp:183
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:97
void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:86
void set_bit(size_t n)
Definition: bigint.cpp:156
Sign sign() const
Definition: bigint.h:365
const uint8_t * cast_char_ptr_to_uint8(const char *s)
Definition: mem_ops.h:120
bool is_zero() const
Definition: bigint.h:255
void poison(const T *p, size_t n)
Definition: ct_utils.h:46
void binary_encode(uint8_t buf[]) const
Definition: bigint.cpp:269
word word_at(size_t n) const
Definition: bigint.h:340
uint32_t get_substring(size_t offset, size_t length) const
Definition: bigint.cpp:119
BigInt operator-() const
Definition: bigint.cpp:243
T is_equal(T x, T y)
Definition: ct_utils.h:124
const word * data() const
Definition: bigint.h:430
#define BOTAN_ASSERT(expr, assertion_made)
Definition: assert.h:29
uint8_t byte_at(size_t n) const
Definition: bigint.h:329
size_t size() const
Definition: bigint.h:392
size_t high_bit(T n)
Definition: bit_ops.h:37
Definition: alg_id.cpp:13
size_t sig_words() const
Definition: bigint.h:398
size_t bytes() const
Definition: bigint.cpp:175
void clear()
Definition: bigint.h:222
const word MP_WORD_MASK
Definition: mp_types.h:27
void grow_to(size_t n)
Definition: bigint.cpp:260
size_t encoded_size(Base base=Binary) const
Definition: bigint.cpp:197
BigInt abs() const
Definition: bigint.cpp:253
uint32_t to_u32bit() const
Definition: bigint.cpp:140
void binary_decode(const uint8_t buf[], size_t length)
Definition: bigint.cpp:279
void unpoison(const T *p, size_t n)
Definition: ct_utils.h:57
BigInt()=default
std::vector< T, secure_allocator< T > > secure_vector
Definition: secmem.h:88
void shrink_to_fit()
Definition: bigint.cpp:297
void flip_sign()
Definition: bigint.cpp:225
void clear_bit(size_t n)
Definition: bigint.cpp:167
size_t round_up(size_t n, size_t align_to)
Definition: rounding.h:21
void set_sign(Sign sign)
Definition: bigint.cpp:214
bool is_positive() const
Definition: bigint.h:359
static BigInt decode(const uint8_t buf[], size_t length, Base base=Binary)
Definition: big_code.cpp:114
const size_t MP_WORD_BITS
Definition: mp_core.h:22