Botan
1.11.15
|
00001 /* 00002 * BigInt 00003 * (C) 1999-2008,2012 Jack Lloyd 00004 * 2007 FlexSecure 00005 * 00006 * Botan is released under the Simplified BSD License (see license.txt) 00007 */ 00008 00009 #ifndef BOTAN_BIGINT_H__ 00010 #define BOTAN_BIGINT_H__ 00011 00012 #include <botan/rng.h> 00013 #include <botan/secmem.h> 00014 #include <botan/mp_types.h> 00015 #include <botan/get_byte.h> 00016 #include <iosfwd> 00017 00018 namespace Botan { 00019 00020 /** 00021 * Arbitrary precision integer 00022 */ 00023 class BOTAN_DLL BigInt 00024 { 00025 public: 00026 /** 00027 * Base enumerator for encoding and decoding 00028 */ 00029 enum Base { Decimal = 10, Hexadecimal = 16, Binary = 256 }; 00030 00031 /** 00032 * Sign symbol definitions for positive and negative numbers 00033 */ 00034 enum Sign { Negative = 0, Positive = 1 }; 00035 00036 /** 00037 * DivideByZero Exception 00038 */ 00039 struct BOTAN_DLL DivideByZero : public Exception 00040 { DivideByZero() : Exception("BigInt divide by zero") {} }; 00041 00042 /** 00043 * Create empty BigInt 00044 */ 00045 BigInt() { m_signedness = Positive; } 00046 00047 /** 00048 * Create BigInt from 64 bit integer 00049 * @param n initial value of this BigInt 00050 */ 00051 BigInt(u64bit n); 00052 00053 /** 00054 * Copy Constructor 00055 * @param other the BigInt to copy 00056 */ 00057 BigInt(const BigInt& other); 00058 00059 /** 00060 * Create BigInt from a string. If the string starts with 0x the 00061 * rest of the string will be interpreted as hexadecimal digits. 00062 * Otherwise, it will be interpreted as a decimal number. 00063 * 00064 * @param str the string to parse for an integer value 00065 */ 00066 BigInt(const std::string& str); 00067 00068 /** 00069 * Create a BigInt from an integer in a byte array 00070 * @param buf the byte array holding the value 00071 * @param length size of buf 00072 * @param base is the number base of the integer in buf 00073 */ 00074 BigInt(const byte buf[], size_t length, Base base = Binary); 00075 00076 /** 00077 * Create a random BigInt of the specified size 00078 * @param rng random number generator 00079 * @param bits size in bits 00080 */ 00081 BigInt(RandomNumberGenerator& rng, size_t bits); 00082 00083 /** 00084 * Create BigInt of specified size, all zeros 00085 * @param sign the sign 00086 * @param n size of the internal register in words 00087 */ 00088 BigInt(Sign sign, size_t n); 00089 00090 /** 00091 * Move constructor 00092 */ 00093 BigInt(BigInt&& other) 00094 { 00095 this->swap(other); 00096 } 00097 00098 /** 00099 * Move assignment 00100 */ 00101 BigInt& operator=(BigInt&& other) 00102 { 00103 if(this != &other) 00104 this->swap(other); 00105 00106 return (*this); 00107 } 00108 00109 /** 00110 * Copy assignment 00111 */ 00112 BigInt& operator=(const BigInt&) = default; 00113 00114 /** 00115 * Swap this value with another 00116 * @param other BigInt to swap values with 00117 */ 00118 void swap(BigInt& other) 00119 { 00120 m_reg.swap(other.m_reg); 00121 std::swap(m_signedness, other.m_signedness); 00122 } 00123 00124 void swap_reg(secure_vector<word>& reg) 00125 { 00126 m_reg.swap(reg); 00127 } 00128 00129 /** 00130 * += operator 00131 * @param y the BigInt to add to this 00132 */ 00133 BigInt& operator+=(const BigInt& y); 00134 00135 /** 00136 * -= operator 00137 * @param y the BigInt to subtract from this 00138 */ 00139 BigInt& operator-=(const BigInt& y); 00140 00141 /** 00142 * *= operator 00143 * @param y the BigInt to multiply with this 00144 */ 00145 BigInt& operator*=(const BigInt& y); 00146 00147 /** 00148 * /= operator 00149 * @param y the BigInt to divide this by 00150 */ 00151 BigInt& operator/=(const BigInt& y); 00152 00153 /** 00154 * Modulo operator 00155 * @param y the modulus to reduce this by 00156 */ 00157 BigInt& operator%=(const BigInt& y); 00158 00159 /** 00160 * Modulo operator 00161 * @param y the modulus (word) to reduce this by 00162 */ 00163 word operator%=(word y); 00164 00165 /** 00166 * Left shift operator 00167 * @param shift the number of bits to shift this left by 00168 */ 00169 BigInt& operator<<=(size_t shift); 00170 00171 /** 00172 * Right shift operator 00173 * @param shift the number of bits to shift this right by 00174 */ 00175 BigInt& operator>>=(size_t shift); 00176 00177 /** 00178 * Increment operator 00179 */ 00180 BigInt& operator++() { return (*this += 1); } 00181 00182 /** 00183 * Decrement operator 00184 */ 00185 BigInt& operator--() { return (*this -= 1); } 00186 00187 /** 00188 * Postfix increment operator 00189 */ 00190 BigInt operator++(int) { BigInt x = (*this); ++(*this); return x; } 00191 00192 /** 00193 * Postfix decrement operator 00194 */ 00195 BigInt operator--(int) { BigInt x = (*this); --(*this); return x; } 00196 00197 /** 00198 * Unary negation operator 00199 * @return negative this 00200 */ 00201 BigInt operator-() const; 00202 00203 /** 00204 * ! operator 00205 * @return true iff this is zero, otherwise false 00206 */ 00207 bool operator !() const { return (!is_nonzero()); } 00208 00209 /** 00210 * Zeroize the BigInt. The size of the underlying register is not 00211 * modified. 00212 */ 00213 void clear() { zeroise(m_reg); } 00214 00215 /** 00216 * Compare this to another BigInt 00217 * @param n the BigInt value to compare with 00218 * @param check_signs include sign in comparison? 00219 * @result if (this<n) return -1, if (this>n) return 1, if both 00220 * values are identical return 0 [like Perl's <=> operator] 00221 */ 00222 s32bit cmp(const BigInt& n, bool check_signs = true) const; 00223 00224 /** 00225 * Test if the integer has an even value 00226 * @result true if the integer is even, false otherwise 00227 */ 00228 bool is_even() const { return (get_bit(0) == 0); } 00229 00230 /** 00231 * Test if the integer has an odd value 00232 * @result true if the integer is odd, false otherwise 00233 */ 00234 bool is_odd() const { return (get_bit(0) == 1); } 00235 00236 /** 00237 * Test if the integer is not zero 00238 * @result true if the integer is non-zero, false otherwise 00239 */ 00240 bool is_nonzero() const { return (!is_zero()); } 00241 00242 /** 00243 * Test if the integer is zero 00244 * @result true if the integer is zero, false otherwise 00245 */ 00246 bool is_zero() const 00247 { 00248 const size_t sw = sig_words(); 00249 00250 for(size_t i = 0; i != sw; ++i) 00251 if(m_reg[i]) 00252 return false; 00253 return true; 00254 } 00255 00256 /** 00257 * Set bit at specified position 00258 * @param n bit position to set 00259 */ 00260 void set_bit(size_t n); 00261 00262 /** 00263 * Clear bit at specified position 00264 * @param n bit position to clear 00265 */ 00266 void clear_bit(size_t n); 00267 00268 /** 00269 * Clear all but the lowest n bits 00270 * @param n amount of bits to keep 00271 */ 00272 void mask_bits(size_t n) 00273 { 00274 if(n == 0) { clear(); return; } 00275 00276 const size_t top_word = n / BOTAN_MP_WORD_BITS; 00277 const word mask = (static_cast<word>(1) << (n % BOTAN_MP_WORD_BITS)) - 1; 00278 00279 if(top_word < size()) 00280 { 00281 clear_mem(&m_reg[top_word+1], size() - (top_word + 1)); 00282 m_reg[top_word] &= mask; 00283 } 00284 } 00285 00286 /** 00287 * Return bit value at specified position 00288 * @param n the bit offset to test 00289 * @result true, if the bit at position n is set, false otherwise 00290 */ 00291 bool get_bit(size_t n) const 00292 { 00293 return ((word_at(n / BOTAN_MP_WORD_BITS) >> (n % BOTAN_MP_WORD_BITS)) & 1); 00294 } 00295 00296 /** 00297 * Return (a maximum of) 32 bits of the complete value 00298 * @param offset the offset to start extracting 00299 * @param length amount of bits to extract (starting at offset) 00300 * @result the integer extracted from the register starting at 00301 * offset with specified length 00302 */ 00303 u32bit get_substring(size_t offset, size_t length) const; 00304 00305 /** 00306 * Convert this value into a u32bit, if it is in the range 00307 * [0 ... 2**32-1], or otherwise throw an exception. 00308 * @result the value as a u32bit if conversion is possible 00309 */ 00310 u32bit to_u32bit() const; 00311 00312 /** 00313 * @param n the offset to get a byte from 00314 * @result byte at offset n 00315 */ 00316 byte byte_at(size_t n) const 00317 { 00318 return get_byte(sizeof(word) - (n % sizeof(word)) - 1, 00319 word_at(n / sizeof(word))); 00320 } 00321 00322 /** 00323 * Return the word at a specified position of the internal register 00324 * @param n position in the register 00325 * @return value at position n 00326 */ 00327 word word_at(size_t n) const 00328 { return ((n < size()) ? m_reg[n] : 0); } 00329 00330 void set_word_at(size_t i, word w) 00331 { 00332 grow_to(i + 1); 00333 m_reg[i] = w; 00334 } 00335 00336 /** 00337 * Tests if the sign of the integer is negative 00338 * @result true, iff the integer has a negative sign 00339 */ 00340 bool is_negative() const { return (sign() == Negative); } 00341 00342 /** 00343 * Tests if the sign of the integer is positive 00344 * @result true, iff the integer has a positive sign 00345 */ 00346 bool is_positive() const { return (sign() == Positive); } 00347 00348 /** 00349 * Return the sign of the integer 00350 * @result the sign of the integer 00351 */ 00352 Sign sign() const { return (m_signedness); } 00353 00354 /** 00355 * @result the opposite sign of the represented integer value 00356 */ 00357 Sign reverse_sign() const; 00358 00359 /** 00360 * Flip the sign of this BigInt 00361 */ 00362 void flip_sign(); 00363 00364 /** 00365 * Set sign of the integer 00366 * @param sign new Sign to set 00367 */ 00368 void set_sign(Sign sign); 00369 00370 /** 00371 * @result absolute (positive) value of this 00372 */ 00373 BigInt abs() const; 00374 00375 /** 00376 * Give size of internal register 00377 * @result size of internal register in words 00378 */ 00379 size_t size() const { return m_reg.size(); } 00380 00381 /** 00382 * Return how many words we need to hold this value 00383 * @result significant words of the represented integer value 00384 */ 00385 size_t sig_words() const 00386 { 00387 const word* x = &m_reg[0]; 00388 size_t sig = m_reg.size(); 00389 00390 while(sig && (x[sig-1] == 0)) 00391 sig--; 00392 return sig; 00393 } 00394 00395 /** 00396 * Give byte length of the integer 00397 * @result byte length of the represented integer value 00398 */ 00399 size_t bytes() const { return (bits() + 7) / 8; } 00400 00401 /** 00402 * Get the bit length of the integer 00403 * @result bit length of the represented integer value 00404 */ 00405 size_t bits() const; 00406 00407 /** 00408 * Return a mutable pointer to the register 00409 * @result a pointer to the start of the internal register 00410 */ 00411 word* mutable_data() { return &m_reg[0]; } 00412 00413 /** 00414 * Return a const pointer to the register 00415 * @result a pointer to the start of the internal register 00416 */ 00417 const word* data() const { return &m_reg[0]; } 00418 00419 secure_vector<word>& get_word_vector() { return m_reg; } 00420 const secure_vector<word>& get_word_vector() const { return m_reg; } 00421 00422 /** 00423 * Increase internal register buffer to at least n words 00424 * @param n new size of register 00425 */ 00426 void grow_to(size_t n) 00427 { 00428 if(n > size()) 00429 m_reg.resize(n + (8 - n % 8)); 00430 } 00431 00432 /** 00433 * Fill BigInt with a random number with size of bitsize 00434 * @param rng the random number generator to use 00435 * @param bitsize number of bits the created random value should have 00436 */ 00437 void randomize(RandomNumberGenerator& rng, size_t bitsize = 0); 00438 00439 /** 00440 * Store BigInt-value in a given byte array 00441 * @param buf destination byte array for the integer value 00442 */ 00443 void binary_encode(byte buf[]) const; 00444 00445 /** 00446 * Read integer value from a byte array with given size 00447 * @param buf byte array buffer containing the integer 00448 * @param length size of buf 00449 */ 00450 void binary_decode(const byte buf[], size_t length); 00451 00452 /** 00453 * Read integer value from a byte array (secure_vector<byte>) 00454 * @param buf the array to load from 00455 */ 00456 void binary_decode(const secure_vector<byte>& buf) 00457 { 00458 binary_decode(&buf[0], buf.size()); 00459 } 00460 00461 /** 00462 * @param base the base to measure the size for 00463 * @return size of this integer in base base 00464 */ 00465 size_t encoded_size(Base base = Binary) const; 00466 00467 /** 00468 * @param rng a random number generator 00469 * @param min the minimum value 00470 * @param max the maximum value 00471 * @return random integer in [min,max) 00472 */ 00473 static BigInt random_integer(RandomNumberGenerator& rng, 00474 const BigInt& min, 00475 const BigInt& max); 00476 00477 /** 00478 * Create a power of two 00479 * @param n the power of two to create 00480 * @return bigint representing 2^n 00481 */ 00482 static BigInt power_of_2(size_t n) 00483 { 00484 BigInt b; 00485 b.set_bit(n); 00486 return b; 00487 } 00488 00489 /** 00490 * Encode the integer value from a BigInt to a std::vector of bytes 00491 * @param n the BigInt to use as integer source 00492 * @param base number-base of resulting byte array representation 00493 * @result secure_vector of bytes containing the integer with given base 00494 */ 00495 static std::vector<byte> encode(const BigInt& n, Base base = Binary); 00496 00497 /** 00498 * Encode the integer value from a BigInt to a secure_vector of bytes 00499 * @param n the BigInt to use as integer source 00500 * @param base number-base of resulting byte array representation 00501 * @result secure_vector of bytes containing the integer with given base 00502 */ 00503 static secure_vector<byte> encode_locked(const BigInt& n, 00504 Base base = Binary); 00505 00506 /** 00507 * Encode the integer value from a BigInt to a byte array 00508 * @param buf destination byte array for the encoded integer 00509 * value with given base 00510 * @param n the BigInt to use as integer source 00511 * @param base number-base of resulting byte array representation 00512 */ 00513 static void encode(byte buf[], const BigInt& n, Base base = Binary); 00514 00515 /** 00516 * Create a BigInt from an integer in a byte array 00517 * @param buf the binary value to load 00518 * @param length size of buf 00519 * @param base number-base of the integer in buf 00520 * @result BigInt representing the integer in the byte array 00521 */ 00522 static BigInt decode(const byte buf[], size_t length, 00523 Base base = Binary); 00524 00525 /** 00526 * Create a BigInt from an integer in a byte array 00527 * @param buf the binary value to load 00528 * @param base number-base of the integer in buf 00529 * @result BigInt representing the integer in the byte array 00530 */ 00531 static BigInt decode(const secure_vector<byte>& buf, 00532 Base base = Binary) 00533 { 00534 return BigInt::decode(&buf[0], buf.size(), base); 00535 } 00536 00537 /** 00538 * Create a BigInt from an integer in a byte array 00539 * @param buf the binary value to load 00540 * @param base number-base of the integer in buf 00541 * @result BigInt representing the integer in the byte array 00542 */ 00543 static BigInt decode(const std::vector<byte>& buf, 00544 Base base = Binary) 00545 { 00546 return BigInt::decode(&buf[0], buf.size(), base); 00547 } 00548 00549 /** 00550 * Encode a BigInt to a byte array according to IEEE 1363 00551 * @param n the BigInt to encode 00552 * @param bytes the length of the resulting secure_vector<byte> 00553 * @result a secure_vector<byte> containing the encoded BigInt 00554 */ 00555 static secure_vector<byte> encode_1363(const BigInt& n, size_t bytes); 00556 00557 private: 00558 secure_vector<word> m_reg; 00559 Sign m_signedness = Positive; 00560 }; 00561 00562 /* 00563 * Arithmetic Operators 00564 */ 00565 BigInt BOTAN_DLL operator+(const BigInt& x, const BigInt& y); 00566 BigInt BOTAN_DLL operator-(const BigInt& x, const BigInt& y); 00567 BigInt BOTAN_DLL operator*(const BigInt& x, const BigInt& y); 00568 BigInt BOTAN_DLL operator/(const BigInt& x, const BigInt& d); 00569 BigInt BOTAN_DLL operator%(const BigInt& x, const BigInt& m); 00570 word BOTAN_DLL operator%(const BigInt& x, word m); 00571 BigInt BOTAN_DLL operator<<(const BigInt& x, size_t n); 00572 BigInt BOTAN_DLL operator>>(const BigInt& x, size_t n); 00573 00574 /* 00575 * Comparison Operators 00576 */ 00577 inline bool operator==(const BigInt& a, const BigInt& b) 00578 { return (a.cmp(b) == 0); } 00579 inline bool operator!=(const BigInt& a, const BigInt& b) 00580 { return (a.cmp(b) != 0); } 00581 inline bool operator<=(const BigInt& a, const BigInt& b) 00582 { return (a.cmp(b) <= 0); } 00583 inline bool operator>=(const BigInt& a, const BigInt& b) 00584 { return (a.cmp(b) >= 0); } 00585 inline bool operator<(const BigInt& a, const BigInt& b) 00586 { return (a.cmp(b) < 0); } 00587 inline bool operator>(const BigInt& a, const BigInt& b) 00588 { return (a.cmp(b) > 0); } 00589 00590 /* 00591 * I/O Operators 00592 */ 00593 BOTAN_DLL std::ostream& operator<<(std::ostream&, const BigInt&); 00594 BOTAN_DLL std::istream& operator>>(std::istream&, BigInt&); 00595 00596 } 00597 00598 namespace std { 00599 00600 template<> 00601 inline void swap<Botan::BigInt>(Botan::BigInt& x, Botan::BigInt& y) 00602 { 00603 x.swap(y); 00604 } 00605 00606 } 00607 00608 #endif