diff options
Diffstat (limited to 'src/lib/math/bigint')
| -rw-r--r-- | src/lib/math/bigint/big_code.cpp | 95 | ||||
| -rw-r--r-- | src/lib/math/bigint/big_io.cpp | 20 | ||||
| -rw-r--r-- | src/lib/math/bigint/bigint.cpp | 49 | ||||
| -rw-r--r-- | src/lib/math/bigint/bigint.h | 69 |
4 files changed, 130 insertions, 103 deletions
diff --git a/src/lib/math/bigint/big_code.cpp b/src/lib/math/bigint/big_code.cpp index 6d8c61fd5..6eb27549e 100644 --- a/src/lib/math/bigint/big_code.cpp +++ b/src/lib/math/bigint/big_code.cpp @@ -1,6 +1,6 @@ /* * BigInt Encoding/Decoding -* (C) 1999-2010,2012 Jack Lloyd +* (C) 1999-2010,2012,2019 Jack Lloyd * * Botan is released under the Simplified BSD License (see license.txt) */ @@ -53,36 +53,28 @@ std::string BigInt::to_hex_string() const */ void BigInt::encode(uint8_t output[], const BigInt& n, Base base) { - if(base == Binary) - { - n.binary_encode(output); - } - else if(base == Hexadecimal) - { - secure_vector<uint8_t> binary(n.encoded_size(Binary)); - n.binary_encode(binary.data()); + secure_vector<uint8_t> enc = n.encode_locked(base); + copy_mem(output, enc.data(), enc.size()); + } - hex_encode(cast_uint8_ptr_to_char(output), - binary.data(), binary.size()); - } - else if(base == Decimal) - { - BigInt copy = n; - uint8_t remainder; - copy.set_sign(Positive); - const size_t output_size = n.encoded_size(Decimal); - for(size_t j = 0; j != output_size; ++j) - { - ct_divide_u8(copy, 10, copy, remainder); - output[output_size - 1 - j] = Charset::digit2char(remainder); - if(copy.is_zero()) - break; - } - } - else - throw Invalid_Argument("Unknown BigInt encoding method"); +namespace { + +std::vector<uint8_t> str_to_vector(const std::string& s) + { + std::vector<uint8_t> v(s.size()); + std::memcpy(v.data(), s.data(), s.size()); + return v; + } + +secure_vector<uint8_t> str_to_lvector(const std::string& s) + { + secure_vector<uint8_t> v(s.size()); + std::memcpy(v.data(), s.data(), s.size()); + return v; } +} + /* * Encode a BigInt */ @@ -90,14 +82,12 @@ std::vector<uint8_t> BigInt::encode(const BigInt& n, Base base) { if(base == Binary) return BigInt::encode(n); - - std::vector<uint8_t> output(n.encoded_size(base)); - encode(output.data(), n, base); - for(size_t j = 0; j != output.size(); ++j) - if(output[j] == 0) - output[j] = '0'; - - return output; + else if(base == Hexadecimal) + return str_to_vector(n.to_hex_string()); + else if(base == Decimal) + return str_to_vector(n.to_dec_string()); + else + throw Invalid_Argument("Unknown BigInt encoding base"); } /* @@ -107,14 +97,12 @@ secure_vector<uint8_t> BigInt::encode_locked(const BigInt& n, Base base) { if(base == Binary) return BigInt::encode_locked(n); - - secure_vector<uint8_t> output(n.encoded_size(base)); - encode(output.data(), n, base); - for(size_t j = 0; j != output.size(); ++j) - if(output[j] == 0) - output[j] = '0'; - - return output; + else if(base == Hexadecimal) + return str_to_lvector(n.to_hex_string()); + else if(base == Decimal) + return str_to_lvector(n.to_dec_string()); + else + throw Invalid_Argument("Unknown BigInt encoding base"); } /* @@ -122,20 +110,21 @@ secure_vector<uint8_t> BigInt::encode_locked(const BigInt& n, Base base) */ secure_vector<uint8_t> BigInt::encode_1363(const BigInt& n, size_t bytes) { + if(n.bytes() > bytes) + throw Encoding_Error("encode_1363: n is too large to encode properly"); + secure_vector<uint8_t> output(bytes); - BigInt::encode_1363(output.data(), output.size(), n); + n.binary_encode(output.data(), output.size()); return output; } //static void BigInt::encode_1363(uint8_t output[], size_t bytes, const BigInt& n) { - const size_t n_bytes = n.bytes(); - if(n_bytes > bytes) + if(n.bytes() > bytes) throw Encoding_Error("encode_1363: n is too large to encode properly"); - const size_t leading_0s = bytes - n_bytes; - encode(&output[leading_0s], n, Binary); + n.binary_encode(output, bytes); } /* @@ -143,9 +132,11 @@ void BigInt::encode_1363(uint8_t output[], size_t bytes, const BigInt& n) */ secure_vector<uint8_t> BigInt::encode_fixed_length_int_pair(const BigInt& n1, const BigInt& n2, size_t bytes) { + if(n1.bytes() > bytes || n2.bytes() > bytes) + throw Encoding_Error("encode_fixed_length_int_pair: values too large to encode properly"); secure_vector<uint8_t> output(2 * bytes); - BigInt::encode_1363(output.data(), bytes, n1); - BigInt::encode_1363(output.data() + bytes, bytes, n2); + n1.binary_encode(output.data() , bytes); + n2.binary_encode(output.data() + bytes, bytes); return output; } @@ -156,7 +147,9 @@ BigInt BigInt::decode(const uint8_t buf[], size_t length, Base base) { BigInt r; if(base == Binary) + { r.binary_decode(buf, length); + } else if(base == Hexadecimal) { secure_vector<uint8_t> binary; diff --git a/src/lib/math/bigint/big_io.cpp b/src/lib/math/bigint/big_io.cpp index 90c2253e9..b31315eac 100644 --- a/src/lib/math/bigint/big_io.cpp +++ b/src/lib/math/bigint/big_io.cpp @@ -16,10 +16,10 @@ namespace Botan { */ std::ostream& operator<<(std::ostream& stream, const BigInt& n) { - BigInt::Base base = BigInt::Decimal; + size_t base = 10; if(stream.flags() & std::ios::hex) - base = BigInt::Hexadecimal; - else if(stream.flags() & std::ios::oct) + base = 16; + if(stream.flags() & std::ios::oct) throw Invalid_Argument("Octal output of BigInt not supported"); if(n == 0) @@ -28,12 +28,18 @@ std::ostream& operator<<(std::ostream& stream, const BigInt& n) { if(n < 0) stream.write("-", 1); - const std::vector<uint8_t> buffer = BigInt::encode(n, base); + + std::string enc; + + if(base == 10) + enc = n.to_dec_string(); + else + enc = n.to_hex_string(); + size_t skip = 0; - while(skip < buffer.size() && buffer[skip] == '0') + while(skip < enc.size() && enc[skip] == '0') ++skip; - stream.write(cast_uint8_ptr_to_char(buffer.data()) + skip, - buffer.size() - skip); + stream.write(&enc[skip], enc.size() - skip); } if(!stream.good()) throw Stream_IO_Error("BigInt output operator has failed"); diff --git a/src/lib/math/bigint/bigint.cpp b/src/lib/math/bigint/bigint.cpp index d2551a991..d2a2f8ee9 100644 --- a/src/lib/math/bigint/bigint.cpp +++ b/src/lib/math/bigint/bigint.cpp @@ -1,6 +1,6 @@ /* * BigInt Base -* (C) 1999-2011,2012,2014 Jack Lloyd +* (C) 1999-2011,2012,2014,2019 Jack Lloyd * * Botan is released under the Simplified BSD License (see license.txt) */ @@ -381,14 +381,34 @@ BigInt BigInt::abs() const return x; } +void BigInt::binary_encode(uint8_t buf[]) const + { + this->binary_encode(buf, bytes()); + } + /* * Encode this number into bytes */ -void BigInt::binary_encode(uint8_t output[]) const +void BigInt::binary_encode(uint8_t output[], size_t len) const { - const size_t sig_bytes = bytes(); - for(size_t i = 0; i != sig_bytes; ++i) - output[sig_bytes-i-1] = byte_at(i); + const size_t full_words = len / sizeof(word); + const size_t extra_bytes = len % sizeof(word); + + for(size_t i = 0; i != full_words; ++i) + { + const word w = word_at(i); + store_be(w, output + (len - (i+1)*sizeof(word))); + } + + if(extra_bytes > 0) + { + const word w = word_at(full_words); + + for(size_t i = 0; i != extra_bytes; ++i) + { + output[extra_bytes - i - 1] = get_byte(sizeof(word) - i - 1, w); + } + } } /* @@ -396,21 +416,20 @@ void BigInt::binary_encode(uint8_t output[]) const */ void BigInt::binary_decode(const uint8_t buf[], size_t length) { - const size_t WORD_BYTES = sizeof(word); - clear(); - secure_vector<word> reg((round_up((length / WORD_BYTES) + 1, 8))); - // TODO can load a word at a time here - for(size_t i = 0; i != length / WORD_BYTES; ++i) + const size_t full_words = length / sizeof(word); + const size_t extra_bytes = length % sizeof(word); + + secure_vector<word> reg((round_up(full_words + 1, 8))); + + for(size_t i = 0; i != full_words; ++i) { - const size_t top = length - WORD_BYTES*i; - for(size_t j = WORD_BYTES; j > 0; --j) - reg[i] = (reg[i] << 8) | buf[top - j]; + reg[i] = load_be<word>(buf + length - sizeof(word)*(i+1), 0); } - for(size_t i = 0; i != length % WORD_BYTES; ++i) - reg[length / WORD_BYTES] = (reg[length / WORD_BYTES] << 8) | buf[i]; + for(size_t i = 0; i != length % sizeof(word); ++i) + reg[full_words] = (reg[full_words] << 8) | buf[i]; m_data.swap(reg); } diff --git a/src/lib/math/bigint/bigint.h b/src/lib/math/bigint/bigint.h index 387bbe8f9..227edfb6b 100644 --- a/src/lib/math/bigint/bigint.h +++ b/src/lib/math/bigint/bigint.h @@ -669,6 +669,18 @@ class BOTAN_PUBLIC_API(2,0) BigInt final void binary_encode(uint8_t buf[]) const; /** + * Store BigInt-value in a given byte array. If len is less than + * the size of the value, then it will be truncated. If len is + * greater than the size of the value, it will be zero-padded. + * If len exactly equals this->bytes(), this function behaves identically + * to binary_encode. + * + * @param buf destination byte array for the integer value + * @param len how many bytes to write + */ + void binary_encode(uint8_t buf[], size_t len) const; + + /** * Read integer value from a byte array with given size * @param buf byte array buffer containing the integer * @param length size of buf @@ -676,10 +688,11 @@ class BOTAN_PUBLIC_API(2,0) BigInt final 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 + * Read integer value from a byte vector + * @param buf the vector to load from */ - void binary_decode(const secure_vector<uint8_t>& buf) + template<typename Alloc> + void binary_decode(const std::vector<uint8_t, Alloc>& buf) { binary_decode(buf.data(), buf.size()); } @@ -687,7 +700,11 @@ class BOTAN_PUBLIC_API(2,0) BigInt final /** * @param base the base to measure the size for * @return size of this integer in base base + * + * Deprecated. This is only needed when using the `encode` and + * `encode_locked` functions, which are also deprecated. */ + BOTAN_DEPRECATED("See comments on declaration") size_t encoded_size(Base base = Binary) const; /** @@ -772,7 +789,7 @@ class BOTAN_PUBLIC_API(2,0) BigInt final * @param buf destination byte array for the encoded integer * @param n the BigInt to use as integer source */ - static void encode(uint8_t buf[], const BigInt& n) + static BOTAN_DEPRECATED("Use n.binary_encode") void encode(uint8_t buf[], const BigInt& n) { n.binary_encode(buf); } @@ -793,17 +810,8 @@ class BOTAN_PUBLIC_API(2,0) BigInt final * @param buf the binary value to load * @result BigInt representing the integer in the byte array */ - static BigInt decode(const secure_vector<uint8_t>& buf) - { - return BigInt(buf); - } - - /** - * Create a BigInt from an integer in a byte array - * @param buf the binary value to load - * @result BigInt representing the integer in the byte array - */ - static BigInt decode(const std::vector<uint8_t>& buf) + template<typename Alloc> + static BigInt decode(const std::vector<uint8_t, Alloc>& buf) { return BigInt(buf); } @@ -813,7 +821,12 @@ class BOTAN_PUBLIC_API(2,0) BigInt final * @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 + * + * Deprecated. If you need Binary, call the version of encode that doesn't + * take a Base. If you need Hex or Decimal output, use to_hex_string or + * to_dec_string resp. */ + BOTAN_DEPRECATED("See comments on declaration") static std::vector<uint8_t> encode(const BigInt& n, Base base); /** @@ -821,7 +834,12 @@ class BOTAN_PUBLIC_API(2,0) BigInt final * @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 + * + * Deprecated. If you need Binary, call the version of encode_locked that + * doesn't take a Base. If you need Hex or Decimal output, use to_hex_string + * or to_dec_string resp. */ + BOTAN_DEPRECATED("See comments on declaration") static secure_vector<uint8_t> encode_locked(const BigInt& n, Base base); @@ -831,7 +849,11 @@ class BOTAN_PUBLIC_API(2,0) BigInt final * value with given base * @param n the BigInt to use as integer source * @param base number-base of resulting byte array representation + * + * Deprecated. If you need Binary, call binary_encode. If you need + * Hex or Decimal output, use to_hex_string or to_dec_string resp. */ + BOTAN_DEPRECATED("See comments on declaration") static void encode(uint8_t buf[], const BigInt& n, Base base); /** @@ -850,21 +872,8 @@ class BOTAN_PUBLIC_API(2,0) BigInt final * @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) - { - if(base == Binary) - return BigInt(buf); - 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) + template<typename Alloc> + static BigInt decode(const std::vector<uint8_t, Alloc>& buf, Base base) { if(base == Binary) return BigInt(buf); |