Move lib into src

10 files changed, 1779 insertions, 0 deletions

diff --git a/src/lib/math/bigint/big_code.cpp b/src/lib/math/bigint/big_code.cpp
new file mode 100644
index 000000000..972312cdb
--- /dev/null
+++ b/src/lib/math/bigint/big_code.cpp
@@ -0,0 +1,150 @@
+/*
+* BigInt Encoding/Decoding
+* (C) 1999-2010,2012 Jack Lloyd
+*
+* Distributed under the terms of the Botan license
+*/
+
+#include <botan/bigint.h>
+#include <botan/divide.h>
+#include <botan/charset.h>
+#include <botan/hex.h>
+
+namespace Botan {
+
+/*
+* Encode a BigInt
+*/
+void BigInt::encode(byte output[], const BigInt& n, Base base)
+   {
+   if(base == Binary)
+      {
+      n.binary_encode(output);
+      }
+   else if(base == Hexadecimal)
+      {
+      secure_vector<byte> binary(n.encoded_size(Binary));
+      n.binary_encode(&binary[0]);
+
+      hex_encode(reinterpret_cast<char*>(output),
+                 &binary[0], binary.size());
+      }
+   else if(base == Decimal)
+      {
+      BigInt copy = n;
+      BigInt remainder;
+      copy.set_sign(Positive);
+      const size_t output_size = n.encoded_size(Decimal);
+      for(size_t j = 0; j != output_size; ++j)
+         {
+         divide(copy, 10, copy, remainder);
+         output[output_size - 1 - j] =
+            Charset::digit2char(static_cast<byte>(remainder.word_at(0)));
+         if(copy.is_zero())
+            break;
+         }
+      }
+   else
+      throw Invalid_Argument("Unknown BigInt encoding method");
+   }
+
+/*
+* Encode a BigInt
+*/
+std::vector<byte> BigInt::encode(const BigInt& n, Base base)
+   {
+   std::vector<byte> output(n.encoded_size(base));
+   encode(&output[0], n, base);
+   if(base != Binary)
+      for(size_t j = 0; j != output.size(); ++j)
+         if(output[j] == 0)
+            output[j] = '0';
+   return output;
+   }
+
+/*
+* Encode a BigInt
+*/
+secure_vector<byte> BigInt::encode_locked(const BigInt& n, Base base)
+   {
+   secure_vector<byte> output(n.encoded_size(base));
+   encode(&output[0], n, base);
+   if(base != Binary)
+      for(size_t j = 0; j != output.size(); ++j)
+         if(output[j] == 0)
+            output[j] = '0';
+   return output;
+   }
+
+/*
+* Encode a BigInt, with leading 0s if needed
+*/
+secure_vector<byte> BigInt::encode_1363(const BigInt& n, size_t bytes)
+   {
+   const size_t n_bytes = n.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;
+
+   secure_vector<byte> output(bytes);
+   encode(&output[leading_0s], n, Binary);
+   return output;
+   }
+
+/*
+* Decode a BigInt
+*/
+BigInt BigInt::decode(const byte buf[], size_t length, Base base)
+   {
+   BigInt r;
+   if(base == Binary)
+      r.binary_decode(buf, length);
+   else if(base == Hexadecimal)
+      {
+      secure_vector<byte> binary;
+
+      if(length % 2)
+         {
+         // Handle lack of leading 0
+         const char buf0_with_leading_0[2] =
+            { '0', static_cast<char>(buf[0]) };
+
+         binary = hex_decode_locked(buf0_with_leading_0, 2);
+
+         binary += hex_decode_locked(reinterpret_cast<const char*>(&buf[1]),
+                                     length - 1,
+                                     false);
+         }
+      else
+         binary = hex_decode_locked(reinterpret_cast<const char*>(buf),
+                                    length, false);
+
+      r.binary_decode(&binary[0], binary.size());
+      }
+   else if(base == Decimal)
+      {
+      for(size_t i = 0; i != length; ++i)
+         {
+         if(Charset::is_space(buf[i]))
+            continue;
+
+         if(!Charset::is_digit(buf[i]))
+            throw Invalid_Argument("BigInt::decode: "
+                                   "Invalid character in decimal input");
+
+         const byte x = Charset::char2digit(buf[i]);
+
+         if(x >= 10)
+            throw Invalid_Argument("BigInt: Invalid decimal string");
+
+         r *= 10;
+         r += x;
+         }
+      }
+   else
+      throw Invalid_Argument("Unknown BigInt decoding method");
+   return r;
+   }
+
+}
diff --git a/src/lib/math/bigint/big_io.cpp b/src/lib/math/bigint/big_io.cpp
new file mode 100644
index 000000000..b561c218f
--- /dev/null
+++ b/src/lib/math/bigint/big_io.cpp
@@ -0,0 +1,55 @@
+/*
+* BigInt Input/Output
+* (C) 1999-2007 Jack Lloyd
+*
+* Distributed under the terms of the Botan license
+*/
+
+#include <botan/bigint.h>
+#include <iostream>
+
+namespace Botan {
+
+/*
+* Write the BigInt into a stream
+*/
+std::ostream& operator<<(std::ostream& stream, const BigInt& n)
+   {
+   BigInt::Base base = BigInt::Decimal;
+   if(stream.flags() & std::ios::hex)
+      base = BigInt::Hexadecimal;
+   else if(stream.flags() & std::ios::oct)
+      throw std::runtime_error("Octal output of BigInt not supported");
+
+   if(n == 0)
+      stream.write("0", 1);
+   else
+      {
+      if(n < 0)
+         stream.write("-", 1);
+      const std::vector<byte> buffer = BigInt::encode(n, base);
+      size_t skip = 0;
+      while(skip < buffer.size() && buffer[skip] == '0')
+         ++skip;
+      stream.write(reinterpret_cast<const char*>(&buffer[0]) + skip,
+                   buffer.size() - skip);
+      }
+   if(!stream.good())
+      throw Stream_IO_Error("BigInt output operator has failed");
+   return stream;
+   }
+
+/*
+* Read the BigInt from a stream
+*/
+std::istream& operator>>(std::istream& stream, BigInt& n)
+   {
+   std::string str;
+   std::getline(stream, str);
+   if(stream.bad() || (stream.fail() && !stream.eof()))
+      throw Stream_IO_Error("BigInt input operator has failed");
+   n = BigInt(str);
+   return stream;
+   }
+
+}
diff --git a/src/lib/math/bigint/big_ops2.cpp b/src/lib/math/bigint/big_ops2.cpp
new file mode 100644
index 000000000..37b6a5df1
--- /dev/null
+++ b/src/lib/math/bigint/big_ops2.cpp
@@ -0,0 +1,221 @@
+/*
+* BigInt Assignment Operators
+* (C) 1999-2007 Jack Lloyd
+*
+* Distributed under the terms of the Botan license
+*/
+
+#include <botan/bigint.h>
+#include <botan/internal/mp_core.h>
+#include <botan/internal/bit_ops.h>
+#include <algorithm>
+
+namespace Botan {
+
+/*
+* Addition Operator
+*/
+BigInt& BigInt::operator+=(const BigInt& y)
+   {
+   const size_t x_sw = sig_words(), y_sw = y.sig_words();
+
+   const size_t reg_size = std::max(x_sw, y_sw) + 1;
+   grow_to(reg_size);
+
+   if(sign() == y.sign())
+      bigint_add2(mutable_data(), reg_size - 1, y.data(), y_sw);
+   else
+      {
+      s32bit relative_size = bigint_cmp(data(), x_sw, y.data(), y_sw);
+
+      if(relative_size < 0)
+         {
+         secure_vector<word> z(reg_size - 1);
+         bigint_sub3(&z[0], y.data(), reg_size - 1, data(), x_sw);
+         std::swap(m_reg, z);
+         set_sign(y.sign());
+         }
+      else if(relative_size == 0)
+         {
+         zeroise(m_reg);
+         set_sign(Positive);
+         }
+      else if(relative_size > 0)
+         bigint_sub2(mutable_data(), x_sw, y.data(), y_sw);
+      }
+
+   return (*this);
+   }
+
+/*
+* Subtraction Operator
+*/
+BigInt& BigInt::operator-=(const BigInt& y)
+   {
+   const size_t x_sw = sig_words(), y_sw = y.sig_words();
+
+   s32bit relative_size = bigint_cmp(data(), x_sw, y.data(), y_sw);
+
+   const size_t reg_size = std::max(x_sw, y_sw) + 1;
+   grow_to(reg_size);
+
+   if(relative_size < 0)
+      {
+      if(sign() == y.sign())
+         bigint_sub2_rev(mutable_data(), y.data(), y_sw);
+      else
+         bigint_add2(mutable_data(), reg_size - 1, y.data(), y_sw);
+
+      set_sign(y.reverse_sign());
+      }
+   else if(relative_size == 0)
+      {
+      if(sign() == y.sign())
+         {
+         clear();
+         set_sign(Positive);
+         }
+      else
+         bigint_shl1(mutable_data(), x_sw, 0, 1);
+      }
+   else if(relative_size > 0)
+      {
+      if(sign() == y.sign())
+         bigint_sub2(mutable_data(), x_sw, y.data(), y_sw);
+      else
+         bigint_add2(mutable_data(), reg_size - 1, y.data(), y_sw);
+      }
+
+   return (*this);
+   }
+
+/*
+* Multiplication Operator
+*/
+BigInt& BigInt::operator*=(const BigInt& y)
+   {
+   const size_t x_sw = sig_words(), y_sw = y.sig_words();
+   set_sign((sign() == y.sign()) ? Positive : Negative);
+
+   if(x_sw == 0 || y_sw == 0)
+      {
+      clear();
+      set_sign(Positive);
+      }
+   else if(x_sw == 1 && y_sw)
+      {
+      grow_to(y_sw + 2);
+      bigint_linmul3(mutable_data(), y.data(), y_sw, word_at(0));
+      }
+   else if(y_sw == 1 && x_sw)
+      {
+      grow_to(x_sw + 2);
+      bigint_linmul2(mutable_data(), x_sw, y.word_at(0));
+      }
+   else
+      {
+      grow_to(size() + y.size());
+
+      secure_vector<word> z(data(), data() + x_sw);
+      secure_vector<word> workspace(size());
+
+      bigint_mul(mutable_data(), size(), &workspace[0],
+                 &z[0], z.size(), x_sw,
+                 y.data(), y.size(), y_sw);
+      }
+
+   return (*this);
+   }
+
+/*
+* Division Operator
+*/
+BigInt& BigInt::operator/=(const BigInt& y)
+   {
+   if(y.sig_words() == 1 && is_power_of_2(y.word_at(0)))
+      (*this) >>= (y.bits() - 1);
+   else
+      (*this) = (*this) / y;
+   return (*this);
+   }
+
+/*
+* Modulo Operator
+*/
+BigInt& BigInt::operator%=(const BigInt& mod)
+   {
+   return (*this = (*this) % mod);
+   }
+
+/*
+* Modulo Operator
+*/
+word BigInt::operator%=(word mod)
+   {
+   if(mod == 0)
+      throw BigInt::DivideByZero();
+
+   if(is_power_of_2(mod))
+       {
+       word result = (word_at(0) & (mod - 1));
+       clear();
+       grow_to(2);
+       m_reg[0] = result;
+       return result;
+       }
+
+   word remainder = 0;
+
+   for(size_t j = sig_words(); j > 0; --j)
+      remainder = bigint_modop(remainder, word_at(j-1), mod);
+   clear();
+   grow_to(2);
+
+   if(remainder && sign() == BigInt::Negative)
+      m_reg[0] = mod - remainder;
+   else
+      m_reg[0] = remainder;
+
+   set_sign(BigInt::Positive);
+
+   return word_at(0);
+   }
+
+/*
+* Left Shift Operator
+*/
+BigInt& BigInt::operator<<=(size_t shift)
+   {
+   if(shift)
+      {
+      const size_t shift_words = shift / MP_WORD_BITS,
+                   shift_bits  = shift % MP_WORD_BITS,
+                   words = sig_words();
+
+      grow_to(words + shift_words + (shift_bits ? 1 : 0));
+      bigint_shl1(mutable_data(), words, shift_words, shift_bits);
+      }
+
+   return (*this);
+   }
+
+/*
+* Right Shift Operator
+*/
+BigInt& BigInt::operator>>=(size_t shift)
+   {
+   if(shift)
+      {
+      const size_t shift_words = shift / MP_WORD_BITS,
+                   shift_bits  = shift % MP_WORD_BITS;
+
+      bigint_shr1(mutable_data(), sig_words(), shift_words, shift_bits);
+
+      if(is_zero())
+         set_sign(Positive);
+      }
+
+   return (*this);
+   }
+
+}
diff --git a/src/lib/math/bigint/big_ops3.cpp b/src/lib/math/bigint/big_ops3.cpp
new file mode 100644
index 000000000..cad730197
--- /dev/null
+++ b/src/lib/math/bigint/big_ops3.cpp
@@ -0,0 +1,191 @@
+/*
+* BigInt Binary Operators
+* (C) 1999-2007 Jack Lloyd
+*
+* Distributed under the terms of the Botan license
+*/
+
+#include <botan/bigint.h>
+#include <botan/divide.h>
+#include <botan/internal/mp_core.h>
+#include <botan/internal/bit_ops.h>
+#include <algorithm>
+
+namespace Botan {
+
+/*
+* Addition Operator
+*/
+BigInt operator+(const BigInt& x, const BigInt& y)
+   {
+   const size_t x_sw = x.sig_words(), y_sw = y.sig_words();
+
+   BigInt z(x.sign(), std::max(x_sw, y_sw) + 1);
+
+   if((x.sign() == y.sign()))
+      bigint_add3(z.mutable_data(), x.data(), x_sw, y.data(), y_sw);
+   else
+      {
+      s32bit relative_size = bigint_cmp(x.data(), x_sw, y.data(), y_sw);
+
+      if(relative_size < 0)
+         {
+         bigint_sub3(z.mutable_data(), y.data(), y_sw, x.data(), x_sw);
+         z.set_sign(y.sign());
+         }
+      else if(relative_size == 0)
+         z.set_sign(BigInt::Positive);
+      else if(relative_size > 0)
+         bigint_sub3(z.mutable_data(), x.data(), x_sw, y.data(), y_sw);
+      }
+
+   return z;
+   }
+
+/*
+* Subtraction Operator
+*/
+BigInt operator-(const BigInt& x, const BigInt& y)
+   {
+   const size_t x_sw = x.sig_words(), y_sw = y.sig_words();
+
+   s32bit relative_size = bigint_cmp(x.data(), x_sw, y.data(), y_sw);
+
+   BigInt z(BigInt::Positive, std::max(x_sw, y_sw) + 1);
+
+   if(relative_size < 0)
+      {
+      if(x.sign() == y.sign())
+         bigint_sub3(z.mutable_data(), y.data(), y_sw, x.data(), x_sw);
+      else
+         bigint_add3(z.mutable_data(), x.data(), x_sw, y.data(), y_sw);
+      z.set_sign(y.reverse_sign());
+      }
+   else if(relative_size == 0)
+      {
+      if(x.sign() != y.sign())
+         bigint_shl2(z.mutable_data(), x.data(), x_sw, 0, 1);
+      }
+   else if(relative_size > 0)
+      {
+      if(x.sign() == y.sign())
+         bigint_sub3(z.mutable_data(), x.data(), x_sw, y.data(), y_sw);
+      else
+         bigint_add3(z.mutable_data(), x.data(), x_sw, y.data(), y_sw);
+      z.set_sign(x.sign());
+      }
+   return z;
+   }
+
+/*
+* Multiplication Operator
+*/
+BigInt operator*(const BigInt& x, const BigInt& y)
+   {
+   const size_t x_sw = x.sig_words(), y_sw = y.sig_words();
+
+   BigInt z(BigInt::Positive, x.size() + y.size());
+
+   if(x_sw == 1 && y_sw)
+      bigint_linmul3(z.mutable_data(), y.data(), y_sw, x.word_at(0));
+   else if(y_sw == 1 && x_sw)
+      bigint_linmul3(z.mutable_data(), x.data(), x_sw, y.word_at(0));
+   else if(x_sw && y_sw)
+      {
+      secure_vector<word> workspace(z.size());
+      bigint_mul(z.mutable_data(), z.size(), &workspace[0],
+                 x.data(), x.size(), x_sw,
+                 y.data(), y.size(), y_sw);
+      }
+
+   if(x_sw && y_sw && x.sign() != y.sign())
+      z.flip_sign();
+   return z;
+   }
+
+/*
+* Division Operator
+*/
+BigInt operator/(const BigInt& x, const BigInt& y)
+   {
+   BigInt q, r;
+   divide(x, y, q, r);
+   return q;
+   }
+
+/*
+* Modulo Operator
+*/
+BigInt operator%(const BigInt& n, const BigInt& mod)
+   {
+   if(mod.is_zero())
+      throw BigInt::DivideByZero();
+   if(mod.is_negative())
+      throw Invalid_Argument("BigInt::operator%: modulus must be > 0");
+   if(n.is_positive() && mod.is_positive() && n < mod)
+      return n;
+
+   BigInt q, r;
+   divide(n, mod, q, r);
+   return r;
+   }
+
+/*
+* Modulo Operator
+*/
+word operator%(const BigInt& n, word mod)
+   {
+   if(mod == 0)
+      throw BigInt::DivideByZero();
+
+   if(is_power_of_2(mod))
+      return (n.word_at(0) & (mod - 1));
+
+   word remainder = 0;
+
+   for(size_t j = n.sig_words(); j > 0; --j)
+      remainder = bigint_modop(remainder, n.word_at(j-1), mod);
+
+   if(remainder && n.sign() == BigInt::Negative)
+      return mod - remainder;
+   return remainder;
+   }
+
+/*
+* Left Shift Operator
+*/
+BigInt operator<<(const BigInt& x, size_t shift)
+   {
+   if(shift == 0)
+      return x;
+
+   const size_t shift_words = shift / MP_WORD_BITS,
+                shift_bits  = shift % MP_WORD_BITS;
+
+   const size_t x_sw = x.sig_words();
+
+   BigInt y(x.sign(), x_sw + shift_words + (shift_bits ? 1 : 0));
+   bigint_shl2(y.mutable_data(), x.data(), x_sw, shift_words, shift_bits);
+   return y;
+   }
+
+/*
+* Right Shift Operator
+*/
+BigInt operator>>(const BigInt& x, size_t shift)
+   {
+   if(shift == 0)
+      return x;
+   if(x.bits() <= shift)
+      return 0;
+
+   const size_t shift_words = shift / MP_WORD_BITS,
+                shift_bits  = shift % MP_WORD_BITS,
+                x_sw = x.sig_words();
+
+   BigInt y(x.sign(), x_sw - shift_words);
+   bigint_shr2(y.mutable_data(), x.data(), x_sw, shift_words, shift_bits);
+   return y;
+   }
+
+}
diff --git a/src/lib/math/bigint/big_rand.cpp b/src/lib/math/bigint/big_rand.cpp
new file mode 100644
index 000000000..78b9ee244
--- /dev/null
+++ b/src/lib/math/bigint/big_rand.cpp
@@ -0,0 +1,48 @@
+/*
+* BigInt Random Generation
+* (C) 1999-2007 Jack Lloyd
+*
+* Distributed under the terms of the Botan license
+*/
+
+#include <botan/bigint.h>
+#include <botan/parsing.h>
+
+namespace Botan {
+
+/*
+* Randomize this number
+*/
+void BigInt::randomize(RandomNumberGenerator& rng,
+                       size_t bitsize)
+   {
+   set_sign(Positive);
+
+   if(bitsize == 0)
+      clear();
+   else
+      {
+      secure_vector<byte> array = rng.random_vec((bitsize + 7) / 8);
+
+      if(bitsize % 8)
+         array[0] &= 0xFF >> (8 - (bitsize % 8));
+      array[0] |= 0x80 >> ((bitsize % 8) ? (8 - bitsize % 8) : 0);
+      binary_decode(&array[0], array.size());
+      }
+   }
+
+/*
+* Generate a random integer within given range
+*/
+BigInt BigInt::random_integer(RandomNumberGenerator& rng,
+                              const BigInt& min, const BigInt& max)
+   {
+   BigInt range = max - min;
+
+   if(range <= 0)
+      throw Invalid_Argument("random_integer: invalid min/max values");
+
+   return (min + (BigInt(rng, range.bits() + 2) % range));
+   }
+
+}
diff --git a/src/lib/math/bigint/bigint.cpp b/src/lib/math/bigint/bigint.cpp
new file mode 100644
index 000000000..45c351256
--- /dev/null
+++ b/src/lib/math/bigint/bigint.cpp
@@ -0,0 +1,350 @@
+/*
+* BigInt Base
+* (C) 1999-2011,2012 Jack Lloyd
+*
+* Distributed under the terms of the Botan license
+*/
+
+#include <botan/bigint.h>
+#include <botan/internal/mp_core.h>
+#include <botan/get_byte.h>
+#include <botan/parsing.h>
+#include <botan/internal/rounding.h>
+
+namespace Botan {
+
+/*
+* Construct a BigInt from a regular number
+*/
+BigInt::BigInt(u64bit n)
+   {
+   set_sign(Positive);
+
+   if(n == 0)
+      return;
+
+   const size_t limbs_needed = sizeof(u64bit) / sizeof(word);
+
+   m_reg.resize(4*limbs_needed);
+   for(size_t i = 0; i != limbs_needed; ++i)
+      m_reg[i] = ((n >> (i*MP_WORD_BITS)) & MP_WORD_MASK);
+   }
+
+/*
+* Construct a BigInt of the specified size
+*/
+BigInt::BigInt(Sign s, size_t size)
+   {
+   m_reg.resize(round_up<size_t>(size, 8));
+   m_signedness = s;
+   }
+
+/*
+* Copy constructor
+*/
+BigInt::BigInt(const BigInt& other)
+   {
+   m_reg = other.m_reg;
+   m_signedness = other.m_signedness;
+   }
+
+/*
+* Construct a BigInt from a string
+*/
+BigInt::BigInt(const std::string& str)
+   {
+   Base base = Decimal;
+   size_t markers = 0;
+   bool negative = false;
+
+   if(str.length() > 0 && str[0] == '-')
+      {
+      markers += 1;
+      negative = true;
+      }
+
+   if(str.length() > markers + 2 && str[markers    ] == '0' &&
+                                    str[markers + 1] == 'x')
+      {
+      markers += 2;
+      base = Hexadecimal;
+      }
+
+   *this = decode(reinterpret_cast<const byte*>(str.data()) + markers,
+                  str.length() - markers, base);
+
+   if(negative) set_sign(Negative);
+   else         set_sign(Positive);
+   }
+
+/*
+* Construct a BigInt from an encoded BigInt
+*/
+BigInt::BigInt(const byte input[], size_t length, Base base)
+   {
+   set_sign(Positive);
+   *this = decode(input, length, base);
+   }
+
+/*
+* Construct a BigInt from an encoded BigInt
+*/
+BigInt::BigInt(RandomNumberGenerator& rng, size_t bits)
+   {
+   set_sign(Positive);
+   randomize(rng, bits);
+   }
+
+/*
+* Grow the internal storage
+*/
+void BigInt::grow_to(size_t n)
+   {
+   if(n > size())
+      m_reg.resize(round_up<size_t>(n, 8));
+   }
+
+/*
+* Comparison Function
+*/
+s32bit BigInt::cmp(const BigInt& other, bool check_signs) const
+   {
+   if(check_signs)
+      {
+      if(other.is_positive() && this->is_negative())
+         return -1;
+
+      if(other.is_negative() && this->is_positive())
+         return 1;
+
+      if(other.is_negative() && this->is_negative())
+         return (-bigint_cmp(this->data(), this->sig_words(),
+                             other.data(), other.sig_words()));
+      }
+
+   return bigint_cmp(this->data(), this->sig_words(),
+                     other.data(), other.sig_words());
+   }
+
+/*
+* Return byte n of this number
+*/
+byte BigInt::byte_at(size_t n) const
+   {
+   const size_t WORD_BYTES = sizeof(word);
+   size_t word_num = n / WORD_BYTES, byte_num = n % WORD_BYTES;
+   if(word_num >= size())
+      return 0;
+   else
+      return get_byte(WORD_BYTES - byte_num - 1, m_reg[word_num]);
+   }
+
+/*
+* Return bit n of this number
+*/
+bool BigInt::get_bit(size_t n) const
+   {
+   return ((word_at(n / MP_WORD_BITS) >> (n % MP_WORD_BITS)) & 1);
+   }
+
+/*
+* Return bits {offset...offset+length}
+*/
+u32bit BigInt::get_substring(size_t offset, size_t length) const
+   {
+   if(length > 32)
+      throw Invalid_Argument("BigInt::get_substring: Substring size too big");
+
+   u64bit piece = 0;
+   for(size_t i = 0; i != 8; ++i)
+      {
+      const byte part = byte_at((offset / 8) + (7-i));
+      piece = (piece << 8) | part;
+      }
+
+   const u64bit mask = (static_cast<u64bit>(1) << length) - 1;
+   const size_t shift = (offset % 8);
+
+   return static_cast<u32bit>((piece >> shift) & mask);
+   }
+
+/*
+* Convert this number to a u32bit, if possible
+*/
+u32bit BigInt::to_u32bit() const
+   {
+   if(is_negative())
+      throw Encoding_Error("BigInt::to_u32bit: Number is negative");
+   if(bits() >= 32)
+      throw Encoding_Error("BigInt::to_u32bit: Number is too big to convert");
+
+   u32bit out = 0;
+   for(u32bit j = 0; j != 4; ++j)
+      out = (out << 8) | byte_at(3-j);
+   return out;
+   }
+
+/*
+* Set bit number n
+*/
+void BigInt::set_bit(size_t n)
+   {
+   const size_t which = n / MP_WORD_BITS;
+   const word mask = static_cast<word>(1) << (n % MP_WORD_BITS);
+   if(which >= size()) grow_to(which + 1);
+   m_reg[which] |= mask;
+   }
+
+/*
+* Clear bit number n
+*/
+void BigInt::clear_bit(size_t n)
+   {
+   const size_t which = n / MP_WORD_BITS;
+   const word mask = static_cast<word>(1) << (n % MP_WORD_BITS);
+   if(which < size())
+      m_reg[which] &= ~mask;
+   }
+
+/*
+* Clear all but the lowest n bits
+*/
+void BigInt::mask_bits(size_t n)
+   {
+   if(n == 0) { clear(); return; }
+   if(n >= bits()) return;
+
+   const size_t top_word = n / MP_WORD_BITS;
+   const word mask = (static_cast<word>(1) << (n % MP_WORD_BITS)) - 1;
+
+   if(top_word < size())
+      clear_mem(&m_reg[top_word+1], size() - (top_word + 1));
+
+   m_reg[top_word] &= mask;
+   }
+
+/*
+* Count how many bytes are being used
+*/
+size_t BigInt::bytes() const
+   {
+   return (bits() + 7) / 8;
+   }
+
+/*
+* Count how many bits are being used
+*/
+size_t BigInt::bits() const
+   {
+   const size_t words = sig_words();
+
+   if(words == 0)
+      return 0;
+
+   size_t full_words = words - 1, top_bits = MP_WORD_BITS;
+   word top_word = word_at(full_words), mask = MP_WORD_TOP_BIT;
+
+   while(top_bits && ((top_word & mask) == 0))
+      { mask >>= 1; top_bits--; }
+
+   return (full_words * MP_WORD_BITS + top_bits);
+   }
+
+/*
+* Calcluate the size in a certain base
+*/
+size_t BigInt::encoded_size(Base base) const
+   {
+   static const double LOG_2_BASE_10 = 0.30102999566;
+
+   if(base == Binary)
+      return bytes();
+   else if(base == Hexadecimal)
+      return 2*bytes();
+   else if(base == Decimal)
+      return static_cast<size_t>((bits() * LOG_2_BASE_10) + 1);
+   else
+      throw Invalid_Argument("Unknown base for BigInt encoding");
+   }
+
+/*
+* Set the sign
+*/
+void BigInt::set_sign(Sign s)
+   {
+   if(is_zero())
+      m_signedness = Positive;
+   else
+      m_signedness = s;
+   }
+
+/*
+* Reverse the value of the sign flag
+*/
+void BigInt::flip_sign()
+   {
+   set_sign(reverse_sign());
+   }
+
+/*
+* Return the opposite value of the current sign
+*/
+BigInt::Sign BigInt::reverse_sign() const
+   {
+   if(sign() == Positive)
+      return Negative;
+   return Positive;
+   }
+
+/*
+* Return the negation of this number
+*/
+BigInt BigInt::operator-() const
+   {
+   BigInt x = (*this);
+   x.flip_sign();
+   return x;
+   }
+
+/*
+* Return the absolute value of this number
+*/
+BigInt BigInt::abs() const
+   {
+   BigInt x = (*this);
+   x.set_sign(Positive);
+   return x;
+   }
+
+/*
+* Encode this number into bytes
+*/
+void BigInt::binary_encode(byte output[]) const
+   {
+   const size_t sig_bytes = bytes();
+   for(size_t i = 0; i != sig_bytes; ++i)
+      output[sig_bytes-i-1] = byte_at(i);
+   }
+
+/*
+* Set this number to the value in buf
+*/
+void BigInt::binary_decode(const byte buf[], size_t length)
+   {
+   const size_t WORD_BYTES = sizeof(word);
+
+   clear();
+   m_reg.resize(round_up<size_t>((length / WORD_BYTES) + 1, 8));
+
+   for(size_t i = 0; i != length / WORD_BYTES; ++i)
+      {
+      const size_t top = length - WORD_BYTES*i;
+      for(size_t j = WORD_BYTES; j > 0; --j)
+         m_reg[i] = (m_reg[i] << 8) | buf[top - j];
+      }
+
+   for(size_t i = 0; i != length % WORD_BYTES; ++i)
+      m_reg[length / WORD_BYTES] = (m_reg[length / WORD_BYTES] << 8) | buf[i];
+   }
+
+}
diff --git a/src/lib/math/bigint/bigint.h b/src/lib/math/bigint/bigint.h
new file mode 100644
index 000000000..08b7d53fc
--- /dev/null
+++ b/src/lib/math/bigint/bigint.h
@@ -0,0 +1,570 @@
+/*
+* BigInt
+* (C) 1999-2008,2012 Jack Lloyd
+*     2007 FlexSecure
+*
+* Distributed under the terms of the Botan license
+*/
+
+#ifndef BOTAN_BIGINT_H__
+#define BOTAN_BIGINT_H__
+
+#include <botan/rng.h>
+#include <botan/secmem.h>
+#include <botan/mp_types.h>
+#include <iosfwd>
+
+namespace Botan {
+
+/**
+* Arbitrary precision integer
+*/
+class BOTAN_DLL BigInt
+   {
+   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
+     */
+     struct BOTAN_DLL DivideByZero : public Exception
+        { DivideByZero() : Exception("BigInt divide by zero") {} };
+
+     /**
+     * Create empty BigInt
+     */
+     BigInt() { m_signedness = Positive; }
+
+     /**
+     * Create BigInt from 64 bit integer
+     * @param n initial value of this BigInt
+     */
+     BigInt(u64bit 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
+     */
+     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
+     * @param base is the number base of the integer in buf
+     */
+     BigInt(const byte buf[], size_t length, Base base = Binary);
+
+     /**
+     * Create a random BigInt of the specified size
+     * @param rng random number generator
+     * @param bits size in bits
+     */
+     BigInt(RandomNumberGenerator& rng, size_t bits);
+
+     /**
+     * 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);
+        }
+
+     /**
+     * += 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 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()); }
+
+     /**
+     * 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]
+     */
+     s32bit 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);
+
+     /**
+     * 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 (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
+     */
+     u32bit get_substring(size_t offset, size_t length) const;
+
+     /**
+     * Convert this value into a u32bit, if it is in the range
+     * [0 ... 2**32-1], or otherwise throw an exception.
+     * @result the value as a u32bit if conversion is possible
+     */
+     u32bit to_u32bit() const;
+
+     /**
+     * @param n the offset to get a byte from
+     * @result byte at offset n
+     */
+     byte byte_at(size_t n) const;
+
+     /**
+     * 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); }
+
+     /**
+     * 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;
+
+     /**
+     * Flip the sign of this BigInt
+     */
+     void flip_sign();
+
+     /**
+     * Set sign of the integer
+     * @param sign new Sign to set
+     */
+     void set_sign(Sign 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[0];
+        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[0]; }
+
+     /**
+     * Return a const pointer to the register
+     * @result a pointer to the start of the internal register
+     */
+     const word* data() const { return &m_reg[0]; }
+
+     /**
+     * Increase internal register buffer to at least n words
+     * @param n new size of register
+     */
+     void grow_to(size_t n);
+
+     /**
+     * Fill BigInt with a random number with size of bitsize
+     * @param rng the random number generator to use
+     * @param bitsize number of bits the created random value should have
+     */
+     void randomize(RandomNumberGenerator& rng, size_t bitsize = 0);
+
+     /**
+     * Store BigInt-value in a given byte array
+     * @param buf destination byte array for the integer value
+     */
+     void binary_encode(byte 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 byte buf[], size_t length);
+
+     /**
+     * Read integer value from a byte array (secure_vector<byte>)
+     * @param buf the array to load from
+     */
+     void binary_decode(const secure_vector<byte>& buf)
+        {
+        binary_decode(&buf[0], 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;
+
+     /**
+     * @param rng a random number generator
+     * @param min the minimum value
+     * @param max the maximum value
+     * @return random integer between min and 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<byte> 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<byte> 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(byte 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 byte 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<byte>& buf,
+                          Base base = Binary)
+        {
+        return BigInt::decode(&buf[0], 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<byte>& buf,
+                          Base base = Binary)
+        {
+        return BigInt::decode(&buf[0], 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<byte>
+     * @result a secure_vector<byte> containing the encoded BigInt
+     */
+     static secure_vector<byte> encode_1363(const BigInt& n, size_t bytes);
+
+   private:
+      secure_vector<word> m_reg;
+      Sign m_signedness;
+   };
+
+/*
+* Arithmetic Operators
+*/
+BigInt BOTAN_DLL operator+(const BigInt& x, const BigInt& y);
+BigInt BOTAN_DLL operator-(const BigInt& x, const BigInt& y);
+BigInt BOTAN_DLL operator*(const BigInt& x, const BigInt& y);
+BigInt BOTAN_DLL operator/(const BigInt& x, const BigInt& d);
+BigInt BOTAN_DLL operator%(const BigInt& x, const BigInt& m);
+word   BOTAN_DLL operator%(const BigInt& x, word m);
+BigInt BOTAN_DLL operator<<(const BigInt& x, size_t n);
+BigInt BOTAN_DLL 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_DLL std::ostream& operator<<(std::ostream&, const BigInt&);
+BOTAN_DLL std::istream& operator>>(std::istream&, BigInt&);
+
+}
+
+namespace std {
+
+template<>
+inline void swap<Botan::BigInt>(Botan::BigInt& x, Botan::BigInt& y)
+   {
+   x.swap(y);
+   }
+
+}
+
+#endif
diff --git a/src/lib/math/bigint/divide.cpp b/src/lib/math/bigint/divide.cpp
new file mode 100644
index 000000000..8b21bce13
--- /dev/null
+++ b/src/lib/math/bigint/divide.cpp
@@ -0,0 +1,140 @@
+/*
+* Division Algorithm
+* (C) 1999-2007,2012 Jack Lloyd
+*
+* Distributed under the terms of the Botan license
+*/
+
+#include <botan/divide.h>
+#include <botan/internal/mp_core.h>
+#include <botan/internal/mp_madd.h>
+
+namespace Botan {
+
+namespace {
+
+/*
+* Handle signed operands, if necessary
+*/
+void sign_fixup(const BigInt& x, const BigInt& y, BigInt& q, BigInt& r)
+   {
+   if(x.sign() == BigInt::Negative)
+      {
+      q.flip_sign();
+      if(r.is_nonzero()) { --q; r = y.abs() - r; }
+      }
+   if(y.sign() == BigInt::Negative)
+      q.flip_sign();
+   }
+
+bool division_check(word q, word y2, word y1,
+                    word x3, word x2, word x1)
+   {
+   // Compute (y3,y2,y1) = (y2,y1) * q
+
+   word y3 = 0;
+   y1 = word_madd2(q, y1, &y3);
+   y2 = word_madd2(q, y2, &y3);
+
+   // Return (y3,y2,y1) >? (x3,x2,x1)
+
+   if(y3 > x3) return true;
+   if(y3 < x3) return false;
+
+   if(y2 > x2) return true;
+   if(y2 < x2) return false;
+
+   if(y1 > x1) return true;
+   if(y1 < x1) return false;
+
+   return false;
+   }
+
+}
+
+/*
+* Solve x = q * y + r
+*/
+void divide(const BigInt& x, const BigInt& y_arg, BigInt& q, BigInt& r)
+   {
+   if(y_arg.is_zero())
+      throw BigInt::DivideByZero();
+
+   BigInt y = y_arg;
+   const size_t y_words = y.sig_words();
+
+   r = x;
+   q = 0;
+
+   r.set_sign(BigInt::Positive);
+   y.set_sign(BigInt::Positive);
+
+   s32bit compare = r.cmp(y);
+
+   if(compare == 0)
+      {
+      q = 1;
+      r = 0;
+      }
+   else if(compare > 0)
+      {
+      size_t shifts = 0;
+      word y_top = y.word_at(y.sig_words()-1);
+      while(y_top < MP_WORD_TOP_BIT) { y_top <<= 1; ++shifts; }
+      y <<= shifts;
+      r <<= shifts;
+
+      const size_t n = r.sig_words() - 1, t = y_words - 1;
+
+      if(n < t)
+         throw Internal_Error("BigInt division word sizes");
+
+      q.grow_to(n - t + 1);
+
+      word* q_words = q.mutable_data();
+
+      if(n <= t)
+         {
+         while(r > y) { r -= y; ++q; }
+         r >>= shifts;
+         sign_fixup(x, y_arg, q, r);
+         return;
+         }
+
+      BigInt temp = y << (MP_WORD_BITS * (n-t));
+
+      while(r >= temp) { r -= temp; q_words[n-t] += 1; }
+
+      for(size_t j = n; j != t; --j)
+         {
+         const word x_j0  = r.word_at(j);
+         const word x_j1 = r.word_at(j-1);
+         const word y_t  = y.word_at(t);
+
+         if(x_j0 == y_t)
+            q_words[j-t-1] = MP_WORD_MAX;
+         else
+            q_words[j-t-1] = bigint_divop(x_j0, x_j1, y_t);
+
+         while(division_check(q_words[j-t-1],
+                              y_t, y.word_at(t-1),
+                              x_j0, x_j1, r.word_at(j-2)))
+            {
+            q_words[j-t-1] -= 1;
+            }
+
+         r -= (q_words[j-t-1] * y) << (MP_WORD_BITS * (j-t-1));
+
+         if(r.is_negative())
+            {
+            r += y << (MP_WORD_BITS * (j-t-1));
+            q_words[j-t-1] -= 1;
+            }
+         }
+      r >>= shifts;
+      }
+
+   sign_fixup(x, y_arg, q, r);
+   }
+
+}
diff --git a/src/lib/math/bigint/divide.h b/src/lib/math/bigint/divide.h
new file mode 100644
index 000000000..36aed7854
--- /dev/null
+++ b/src/lib/math/bigint/divide.h
@@ -0,0 +1,29 @@
+/*
+* Division
+* (C) 1999-2007 Jack Lloyd
+*
+* Distributed under the terms of the Botan license
+*/
+
+#ifndef BOTAN_DIVISON_ALGORITHM_H__
+#define BOTAN_DIVISON_ALGORITHM_H__
+
+#include <botan/bigint.h>
+
+namespace Botan {
+
+/**
+* BigInt Division
+* @param x an integer
+* @param y a non-zero integer
+* @param q will be set to x / y
+* @param r will be set to x % y
+*/
+void BOTAN_DLL divide(const BigInt& x,
+                      const BigInt& y,
+                      BigInt& q,
+                      BigInt& r);
+
+}
+
+#endif
diff --git a/src/lib/math/bigint/info.txt b/src/lib/math/bigint/info.txt
new file mode 100644
index 000000000..b5dabb7bc
--- /dev/null
+++ b/src/lib/math/bigint/info.txt
@@ -0,0 +1,25 @@
+load_on auto
+
+define BIGINT 20131128
+
+<header:public>
+bigint.h
+divide.h
+</header:public>
+
+<source>
+big_code.cpp
+big_io.cpp
+big_ops2.cpp
+big_ops3.cpp
+big_rand.cpp
+bigint.cpp
+divide.cpp
+</source>
+
+<requires>
+alloc
+mp
+hex
+rng
+</requires>