aboutsummaryrefslogtreecommitdiffstats
path: root/src/lib/math/bigint
diff options
context:
space:
mode:
authorJack Lloyd <[email protected]>2019-01-24 10:14:13 -0500
committerJack Lloyd <[email protected]>2019-01-24 10:14:13 -0500
commit8eef2fa2799a95f9f076d2dcd379a0dcd45e42d0 (patch)
treec3c0839f32bf083e48ee17e83e6f1e790ca01f39 /src/lib/math/bigint
parent80fd675d196b4d589f965f6f4575f802a8f7168d (diff)
Revamp BigInt encoding and decoding.
Deprecate some crufty functions. Optimize binary encoding/decoding.
Diffstat (limited to 'src/lib/math/bigint')
-rw-r--r--src/lib/math/bigint/big_code.cpp95
-rw-r--r--src/lib/math/bigint/big_io.cpp20
-rw-r--r--src/lib/math/bigint/bigint.cpp49
-rw-r--r--src/lib/math/bigint/bigint.h69
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);