25650639339

Committed 10 May 2026 07:03PM UTC coverage: 89.326% (-0.002%) from 89.328%

Build # 25650639339

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #5592 from randombit/jack/bn-hardening

Various BigInt/mp related hardenings and bug fixes

Coverage Stats

107853 of 120741 relevant lines covered (89.33%)

11294230.95 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

95.02

/src/tests/test_bigint.cpp

/*
* (C) 2009,2015,2016 Jack Lloyd
* (C) 2024           Fabian Albert, René Meusel -  Rohde & Schwarz Cybersecurity
*
* Botan is released under the Simplified BSD License (see license.txt)
*/

#include "tests.h"

#if defined(BOTAN_HAS_NUMBERTHEORY)
   #include "test_rng.h"
   #include <botan/bigint.h>
   #include <botan/exceptn.h>
   #include <botan/numthry.h>
   #include <botan/internal/barrett.h>
   #include <botan/internal/concat_util.h>
   #include <botan/internal/ct_utils.h>
   #include <botan/internal/divide.h>
   #include <botan/internal/fmt.h>
   #include <botan/internal/mod_inv.h>
   #include <botan/internal/parsing.h>
   #include <botan/internal/primality.h>
   #include <set>
#endif

namespace Botan_Tests {

namespace {

#if defined(BOTAN_HAS_NUMBERTHEORY)

using Botan::BigInt;

class BigInt_Unit_Tests final : public Test {
   public:
      std::vector<Test::Result> run() override {
         std::vector<Test::Result> results;

         results.push_back(test_bigint_sizes());
         results.push_back(test_random_prime());
         results.push_back(test_encode());
         results.push_back(test_bigint_io());
         results.push_back(test_get_substring());

         return results;
      }

   private:
      static Test::Result test_bigint_sizes() {
         Test::Result result("BigInt size functions");

         for(const size_t bit : {1, 8, 16, 31, 32, 64, 97, 128, 179, 192, 512, 521}) {
            BigInt a;

            a.set_bit(bit);

            // Test 2^n and 2^n-1
            for(size_t i = 0; i != 2; ++i) {
               const size_t exp_bits = bit + 1 - i;
               result.test_sz_eq("BigInt::bits", a.bits(), exp_bits);
               result.test_sz_eq(
                  "BigInt::bytes", a.bytes(), (exp_bits % 8 == 0) ? (exp_bits / 8) : (exp_bits + 8 - exp_bits % 8) / 8);

               if(bit == 1 && i == 1) {
                  result.test_u32_eq("BigInt::to_u32bit zero", a.to_u32bit(), static_cast<uint32_t>(1));
               } else if(bit <= 31 || (bit == 32 && i == 1)) {
                  result.test_u32_eq(
                     "BigInt::to_u32bit", a.to_u32bit(), static_cast<uint32_t>((uint64_t(1) << bit) - i));
               } else {
                  try {
                     a.to_u32bit();
                     result.test_failure("BigInt::to_u32bit roundtripped out of range value");
                  } catch(std::exception&) {
                     result.test_success("BigInt::to_u32bit rejected out of range");
                  }
               }

               a--;
            }
         }

         return result;
      }

      static Test::Result test_random_prime() {
         Test::Result result("BigInt prime generation");

         auto rng = Test::new_rng("random_prime");

         result.test_throws(
            "Invalid bit size", "random_prime: Can't make a prime of 0 bits", [&]() { Botan::random_prime(*rng, 0); });
         result.test_throws(
            "Invalid bit size", "random_prime: Can't make a prime of 1 bits", [&]() { Botan::random_prime(*rng, 1); });
         result.test_throws("Invalid arg", "random_prime Invalid value for equiv/modulo", [&]() {
            Botan::random_prime(*rng, 2, 1, 0, 2);
         });

         BigInt p = Botan::random_prime(*rng, 2);
         result.test_is_true("Only two 2-bit primes", p == 2 || p == 3);

         p = Botan::random_prime(*rng, 3);
         result.test_is_true("Only two 3-bit primes", p == 5 || p == 7);

         p = Botan::random_prime(*rng, 4);
         result.test_is_true("Only two 4-bit primes", p == 11 || p == 13);

         for(size_t bits = 5; bits <= 32; ++bits) {
            p = Botan::random_prime(*rng, bits);
            result.test_sz_eq("Expected bit size", p.bits(), bits);
            result.test_is_true("P is prime", Botan::is_prime(p, *rng));
         }

         const size_t safe_prime_bits = 65;
         const BigInt safe_prime = Botan::random_safe_prime(*rng, safe_prime_bits);
         result.test_sz_eq("Safe prime size", safe_prime.bits(), safe_prime_bits);
         result.test_is_true("P is prime", Botan::is_prime(safe_prime, *rng));
         result.test_is_true("(P-1)/2 is prime", Botan::is_prime((safe_prime - 1) / 2, *rng));

         for(const size_t modulo : {3, 5, 7, 11}) {
            const size_t equiv = (modulo - 1) / 2;
            const BigInt q = Botan::random_prime(*rng, 64, BigInt::zero(), equiv, modulo);
            result.test_is_true(
               "random_prime returned a prime for equiv=" + std::to_string(equiv) + " modulo=" + std::to_string(modulo),
               Botan::is_prime(q, *rng));
            result.test_bn_eq("congruence holds", q % BigInt::from_word(modulo), BigInt::from_word(equiv));
         }

         return result;
      }

      static Test::Result test_encode() {
         Test::Result result("BigInt encoding functions");

         const auto n1 = Botan::BigInt::from_u64(0xffff);
         const auto n2 = Botan::BigInt::from_u64(1023);

         const auto encoded_n1 = n1.serialize(256);
         const auto encoded_n2 = n2.serialize(256);
         const auto expected = Botan::concat(encoded_n1, encoded_n2);

         const auto encoded_n1_n2 = BigInt::encode_fixed_length_int_pair(n1, n2, 256);
         result.test_bin_eq("encode_fixed_length_int_pair", encoded_n1_n2, expected);

         for(size_t i = 0; i < 256 - n1.bytes(); ++i) {
            if(encoded_n1[i] != 0) {
               result.test_failure("BigInt::serialize", "no zero byte");
            }
         }

         return result;
      }

      static Test::Result test_get_substring() {
         Test::Result result("BigInt get_substring");

         const size_t rbits = 1024;

         auto rng = Test::new_rng("get_substring");

         const Botan::BigInt r(*rng, rbits);

         for(size_t wlen = 1; wlen <= 32; ++wlen) {
            for(size_t offset = 0; offset != rbits + 64; ++offset) {
               const uint32_t val = r.get_substring(offset, wlen);

               Botan::BigInt t = r >> offset;
               t.mask_bits(wlen);

               const uint32_t cmp = t.to_u32bit();

               result.test_sz_eq("Same value", size_t(val), size_t(cmp));
            }
         }

         return result;
      }

      static Test::Result test_bigint_io() {
         Test::Result result("BigInt IO operators");

         const std::map<std::string, Botan::BigInt> str_to_val = {{"-13", -Botan::BigInt(13)},
                                                                  {"0", Botan::BigInt(0)},
                                                                  {"0x13", Botan::BigInt(0x13)},
                                                                  {"1", Botan::BigInt(1)},
                                                                  {"4294967297", Botan::BigInt(2147483648) * 2 + 1}};

         for(const auto& vec : str_to_val) {
            Botan::BigInt n;
            std::istringstream iss;

            iss.str(vec.first);
            iss >> n;
            result.test_bn_eq("input '" + vec.first + "'", n, vec.second);
         }

         auto check_bigint_formatting = [&](const Botan::BigInt& n,
                                            const std::string& dec,
                                            const std::string& hex,
                                            const std::string& neg_dec,
                                            const std::string& neg_hex) {
            std::ostringstream oss;
            oss << n;
            result.test_str_eq("output decimal", oss.str(), dec);

            oss.str("");
            oss << (-n);
            result.test_str_eq("output negative decimal", oss.str(), neg_dec);

            oss.str("");
            oss << std::hex << n;
            result.test_str_eq("output hex", oss.str(), hex);

            oss.str("");
            oss << std::hex << (-n);
            result.test_str_eq("output negative hex", oss.str(), neg_hex);
         };

         check_bigint_formatting(Botan::BigInt(33), "33", "0x21", "-33", "-0x21");
         check_bigint_formatting(Botan::BigInt::from_s32(-33), "-33", "-0x21", "33", "0x21");
         check_bigint_formatting(Botan::BigInt(255), "255", "0xFF", "-255", "-0xFF");
         check_bigint_formatting(Botan::BigInt(0), "0", "0x00", "0", "0x00");
         check_bigint_formatting(Botan::BigInt(5), "5", "0x05", "-5", "-0x05");

         result.test_throws("octal output not supported", [&]() {
            const Botan::BigInt n(5);
            std::ostringstream oss;
            oss << std::oct << n;
         });

         return result;
      }
};

BOTAN_REGISTER_TEST("math", "bigint_unit", BigInt_Unit_Tests);

class BigInt_Cmp_Test final : public Text_Based_Test {
   public:
      BigInt_Cmp_Test() : Text_Based_Test("bn/cmp.vec", "X,Y,R") {}

      Test::Result run_one_test(const std::string& op, const VarMap& vars) override {
         Test::Result result("BigInt Comparison " + op);

         const BigInt x = vars.get_req_bn("X");
         const BigInt y = vars.get_req_bn("Y");
         const bool expected = vars.get_req_bool("R");

         if(op == "EQ") {
            result.test_bool_eq("Values equal", x == y, expected);
         } else if(op == "LT") {
            result.test_bool_eq("Values LT", x < y, expected);

            if(expected) {
               result.test_is_true("If LT then reverse is GT", y >= x);
            } else {
               result.test_is_true("If not LT then GTE", x >= y);
            }
         } else if(op == "LTE") {
            result.test_bool_eq("Values LTE", x <= y, expected);

            if(expected) {
               result.test_is_true("If LTE then either LT or EQ", x < y || x == y);
            } else {
               result.test_is_true("If not LTE then GT", x > y);
            }
         } else {
            throw Test_Error("Unknown BigInt comparison type " + op);
         }

         return result;
      }
};

BOTAN_REGISTER_TEST("math", "bn_cmp", BigInt_Cmp_Test);

class BigInt_Add_Test final : public Text_Based_Test {
   public:
      BigInt_Add_Test() : Text_Based_Test("bn/add.vec", "In1,In2,Output") {}

      Test::Result run_one_test(const std::string& /*header*/, const VarMap& vars) override {
         Test::Result result("BigInt Addition");

         using Botan::BigInt;

         const BigInt a = vars.get_req_bn("In1");
         const BigInt b = vars.get_req_bn("In2");
         const BigInt c = vars.get_req_bn("Output");

         result.test_bn_eq("a + b", a + b, c);
         result.test_bn_eq("b + a", b + a, c);

         BigInt e = a;
         e += b;
         result.test_bn_eq("a += b", e, c);

         e = b;
         e += a;
         result.test_bn_eq("b += a", e, c);

         return result;
      }
};

BOTAN_REGISTER_TEST("math", "bn_add", BigInt_Add_Test);

class BigInt_Sub_Test final : public Text_Based_Test {
   public:
      BigInt_Sub_Test() : Text_Based_Test("bn/sub.vec", "In1,In2,Output") {}

      Test::Result run_one_test(const std::string& /*header*/, const VarMap& vars) override {
         Test::Result result("BigInt Subtraction");

         const BigInt a = vars.get_req_bn("In1");
         const BigInt b = vars.get_req_bn("In2");
         const BigInt c = vars.get_req_bn("Output");

         result.test_bn_eq("a - b", a - b, c);

         BigInt e = a;
         e -= b;
         result.test_bn_eq("a -= b", e, c);

         return result;
      }
};

BOTAN_REGISTER_TEST("math", "bn_sub", BigInt_Sub_Test);

class BigInt_Mul_Test final : public Text_Based_Test {
   public:
      BigInt_Mul_Test() : Text_Based_Test("bn/mul.vec", "In1,In2,Output") {}

      Test::Result run_one_test(const std::string& /*header*/, const VarMap& vars) override {
         Test::Result result("BigInt Multiply");

         const BigInt a = vars.get_req_bn("In1");
         const BigInt b = vars.get_req_bn("In2");
         const BigInt c = vars.get_req_bn("Output");

         result.test_bn_eq("a * b", a * b, c);
         result.test_bn_eq("b * a", b * a, c);

         BigInt e = a;
         e *= b;
         result.test_bn_eq("a *= b", e, c);

         e = b;
         e *= a;
         result.test_bn_eq("b *= a", e, c);

         return result;
      }
};

BOTAN_REGISTER_TEST("math", "bn_mul", BigInt_Mul_Test);

class BigInt_Sqr_Test final : public Text_Based_Test {
   public:
      BigInt_Sqr_Test() : Text_Based_Test("bn/sqr.vec", "Input,Output") {}

      Test::Result run_one_test(const std::string& /*header*/, const VarMap& vars) override {
         Test::Result result("BigInt Square");

         const BigInt input = vars.get_req_bn("Input");
         const BigInt output = vars.get_req_bn("Output");

         result.test_bn_eq("a * a", input * input, output);
         result.test_bn_eq("sqr(a)", square(input), output);

         return result;
      }
};

BOTAN_REGISTER_TEST("math", "bn_sqr", BigInt_Sqr_Test);

class BigInt_Div_Test final : public Text_Based_Test {
   public:
      BigInt_Div_Test() : Text_Based_Test("bn/divide.vec", "In1,In2,Output") {}

      Test::Result run_one_test(const std::string& /*header*/, const VarMap& vars) override {
         Test::Result result("BigInt Divide");

         const BigInt a = vars.get_req_bn("In1");
         const BigInt b = vars.get_req_bn("In2");
         const BigInt c = vars.get_req_bn("Output");

         result.test_bn_eq("a / b", a / b, c);

         BigInt e = a;
         e /= b;
         result.test_bn_eq("a /= b", e, c);

         if(b.sig_words() == 1 && b.signum() >= 0) {
            const Botan::word bw = b.word_at(0);
            result.test_bn_eq("Low word correct", Botan::BigInt::from_word(bw), b);

            Botan::BigInt ct_q;
            Botan::word ct_r = 0;
            Botan::ct_divide_word(a, bw, ct_q, ct_r);
            result.test_bn_eq("ct_divide_word q", ct_q, c);
            result.test_bn_eq("ct_divide_word r", ct_q * b + ct_r, a);
         }

         Botan::BigInt ct_q;
         Botan::BigInt ct_r;
         Botan::ct_divide(a, b, ct_q, ct_r);
         result.test_bn_eq("ct_divide q", ct_q, c);
         result.test_bn_eq("ct_divide r", ct_q * b + ct_r, a);

         return result;
      }
};

BOTAN_REGISTER_TEST("math", "bn_div", BigInt_Div_Test);

class BigInt_DivPow2k_Test final : public Test {
   public:
      std::vector<Test::Result> run() override {
         Test::Result result("BigInt divide pow2k");

         for(size_t k = 2; k != 128; ++k) {
            testcase(k, 1, result);
            testcase(k, 2, result);
            testcase(k, 4, result);
         }

         for(size_t k = 4; k != 512; ++k) {
            const BigInt pow2k = BigInt::power_of_2(k);

            for(size_t y_bits = k / 2; y_bits <= (k + 2); ++y_bits) {
               const BigInt y(rng(), y_bits, false);
               if(y.is_zero()) {
                  continue;
               }

               testcase(k, y, result);
            }
         }

         return {result};
      }

   private:
      static void testcase(size_t k, const BigInt& y, Test::Result& result) {
         const BigInt ct_pow2k = ct_divide_pow2k(k, y);
         const BigInt vt_pow2k = vartime_divide_pow2k(k, y);
         const BigInt ref = BigInt::power_of_2(k) / y;

         result.test_bn_eq("ct_divide_pow2k matches Knuth division", ct_pow2k, ref);
         result.test_bn_eq("vartime_divide_pow2k matches Knuth division", vt_pow2k, ref);
      }
};

BOTAN_REGISTER_TEST("math", "bn_div_pow2k", BigInt_DivPow2k_Test);

class BigInt_Mod_Test final : public Text_Based_Test {
   public:
      BigInt_Mod_Test() : Text_Based_Test("bn/mod.vec", "In1,In2,Output") {}

      Test::Result run_one_test(const std::string& /*header*/, const VarMap& vars) override {
         Test::Result result("BigInt Mod");

         const BigInt a = vars.get_req_bn("In1");
         const BigInt b = vars.get_req_bn("In2");
         const BigInt expected = vars.get_req_bn("Output");

         result.test_bn_eq("a % b", a % b, expected);

         BigInt e = a;
         e %= b;
         result.test_bn_eq("a %= b", e, expected);

         if(a.signum() >= 0 && a < (b * b)) {
            auto mod_b_pub = Botan::Barrett_Reduction::for_public_modulus(b);
            result.test_bn_eq("Barrett public", mod_b_pub.reduce(a), expected);

            auto mod_b_sec = Botan::Barrett_Reduction::for_secret_modulus(b);
            result.test_bn_eq("Barrett secret", mod_b_sec.reduce(a), expected);
         }

         // if b fits into a Botan::word test %= operator for words
         if(b.sig_words() == 1) {
            const Botan::word b_word = b.word_at(0);

            e = a;
            e %= b_word;
            result.test_bn_eq("a %= b (as word)", e, expected);

            result.test_bn_eq("a % b (as word)", a % b_word, expected);

            Botan::BigInt ct_q;
            Botan::word ct_r = 0;
            Botan::ct_divide_word(a, b.word_at(0), ct_q, ct_r);
            result.test_bn_eq("ct_divide_u8 r", ct_r, expected);
         }

         Botan::BigInt ct_q;
         Botan::BigInt ct_r;
         Botan::ct_divide(a, b, ct_q, ct_r);
         result.test_bn_eq("ct_divide r", ct_r, expected);

         return result;
      }
};

BOTAN_REGISTER_TEST("math", "bn_mod", BigInt_Mod_Test);

class Barrett_Redc_Test final : public Test {
   public:
      std::vector<Test::Result> run() override {
         Test::Result result("Barrett reduction");

         for(size_t t = 0; t != 10000; ++t) {
            const auto mod = [&]() {
               if(t <= 16) {
                  return BigInt::from_u64(t) + 1;
               } else {
                  const size_t bits = (t / 4) + 2;

                  if(t % 4 == 0) {
                     return BigInt::power_of_2(bits);
                  } else if(t % 4 == 1) {
                     return BigInt::power_of_2(bits) - 1;
                  } else if(t % 4 == 2) {
                     return BigInt::power_of_2(bits) + 1;
                  } else {
                     Botan::BigInt b;
                     b.randomize(rng(), bits, true);
                     return b;
                  }
               }
            }();

            const size_t mod_bits = mod.bits();
            auto barrett = Botan::Barrett_Reduction::for_public_modulus(mod);

            for(size_t i = 0; i != 10; ++i) {
               const auto input = [&]() {
                  Botan::BigInt b;
                  b.randomize(rng(), 2 * mod_bits, false);
                  return b;
               }();

               const auto reduced_ref = input % mod;
               const auto reduced_barrett = barrett.reduce(input);

               result.test_bn_eq("Barrett reduction matches variable time division", reduced_barrett, reduced_ref);
            }
         }

         return {result};
      }
};

BOTAN_REGISTER_TEST("math", "barrett_redc", Barrett_Redc_Test);

class BigInt_GCD_Test final : public Text_Based_Test {
   public:
      BigInt_GCD_Test() : Text_Based_Test("bn/gcd.vec", "X,Y,GCD") {}

      Test::Result run_one_test(const std::string& /*header*/, const VarMap& vars) override {
         Test::Result result("BigInt GCD");

         const BigInt x = vars.get_req_bn("X");
         const BigInt y = vars.get_req_bn("Y");
         const BigInt expected = vars.get_req_bn("GCD");

         const BigInt g1 = Botan::gcd(x, y);
         result.test_bn_eq("gcd", g1, expected);

         const BigInt g2 = Botan::gcd(y, x);
         result.test_bn_eq("gcd", g2, expected);

         return result;
      }
};

BOTAN_REGISTER_TEST("math", "bn_gcd", BigInt_GCD_Test);

class BigInt_Jacobi_Test final : public Text_Based_Test {
   public:
      BigInt_Jacobi_Test() : Text_Based_Test("bn/jacobi.vec", "A,N,J") {}

      Test::Result run_one_test(const std::string& /*header*/, const VarMap& vars) override {
         Test::Result result("BigInt Jacobi");

         const BigInt a = vars.get_req_bn("A");
         const BigInt n = vars.get_req_bn("N");
         const std::string expected = vars.get_req_str("J");

         const int32_t j = Botan::jacobi(a, n);

         if(j == 0) {
            result.test_str_eq("jacobi", expected, "0");
         } else if(j == -1) {
            result.test_str_eq("jacobi", expected, "-1");
         } else {
            result.test_str_eq("jacobi", expected, "1");
         }

         return result;
      }
};

BOTAN_REGISTER_TEST("math", "bn_jacobi", BigInt_Jacobi_Test);

class BigInt_Lshift_Test final : public Text_Based_Test {
   public:
      BigInt_Lshift_Test() : Text_Based_Test("bn/lshift.vec", "Value,Shift,Output") {}

      Test::Result run_one_test(const std::string& /*header*/, const VarMap& vars) override {
         Test::Result result("BigInt Lshift");

         const BigInt value = vars.get_req_bn("Value");
         const size_t shift = vars.get_req_bn("Shift").to_u32bit();
         const BigInt output = vars.get_req_bn("Output");

         result.test_bn_eq("a << s", value << shift, output);

         BigInt e = value;
         e <<= shift;
         result.test_bn_eq("a <<= s", e, output);

         return result;
      }
};

BOTAN_REGISTER_TEST("math", "bn_lshift", BigInt_Lshift_Test);

class BigInt_Rshift_Test final : public Text_Based_Test {
   public:
      BigInt_Rshift_Test() : Text_Based_Test("bn/rshift.vec", "Value,Shift,Output") {}

      Test::Result run_one_test(const std::string& /*header*/, const VarMap& vars) override {
         Test::Result result("BigInt Rshift");

         const BigInt value = vars.get_req_bn("Value");
         const size_t shift = vars.get_req_bn("Shift").to_u32bit();
         const BigInt output = vars.get_req_bn("Output");

         result.test_bn_eq("a >> s", value >> shift, output);

         BigInt e = value;
         e >>= shift;
         result.test_bn_eq("a >>= s", e, output);

         return result;
      }
};

BOTAN_REGISTER_TEST("math", "bn_rshift", BigInt_Rshift_Test);

Test::Result test_const_time_left_shift() {
   Test::Result result("BigInt const time shift");
   const size_t bits = Test::run_long_tests() ? 4096 : 2048;

   auto rng = Test::new_rng("const_time_left_shift");

   result.start_timer();

   Botan::BigInt a = Botan::BigInt::with_capacity(bits / sizeof(Botan::word));
   for(size_t i = 0; i < bits; ++i) {
      if(rng->next_byte() % 2 == 1) {
         a.set_bit(i);
      }
   }

   for(size_t i = 0; i < bits; ++i) {
      auto ct = a;
      auto chk = a;
      Botan::CT::poison(ct);
      ct.ct_shift_left(i);
      Botan::CT::unpoison(ct);
      chk <<= i;
      result.test_bn_eq(Botan::fmt("ct << {}", i), ct, chk);
   }

   result.end_timer();

   return result;
}

class BigInt_Powmod_Test final : public Text_Based_Test {
   public:
      BigInt_Powmod_Test() : Text_Based_Test("bn/powmod.vec", "Base,Exponent,Modulus,Output") {}

      Test::Result run_one_test(const std::string& /*header*/, const VarMap& vars) override {
         Test::Result result("BigInt Powmod");

         const BigInt base = vars.get_req_bn("Base");
         const BigInt exponent = vars.get_req_bn("Exponent");
         const BigInt modulus = vars.get_req_bn("Modulus");
         const BigInt expected = vars.get_req_bn("Output");

         result.test_bn_eq("power_mod", Botan::power_mod(base, exponent, modulus), expected);
         return result;
      }
};

BOTAN_REGISTER_TEST("math", "bn_powmod", BigInt_Powmod_Test);

class BigInt_IsPrime_Test final : public Text_Based_Test {
   public:
      BigInt_IsPrime_Test() : Text_Based_Test("bn/isprime.vec", "X") {}

      Test::Result run_one_test(const std::string& header, const VarMap& vars) override {
         if(header != "Prime" && header != "NonPrime") {
            throw Test_Error("Bad header for prime test " + header);
         }

         const BigInt value = vars.get_req_bn("X");
         const bool is_prime = (header == "Prime");

         Test::Result result("BigInt Test " + header);
         result.test_bool_eq("is_prime", Botan::is_prime(value, this->rng()), is_prime);

         return result;
      }
};

BOTAN_REGISTER_TEST("math", "bn_isprime", BigInt_IsPrime_Test);

class BigInt_IsSquare_Test final : public Text_Based_Test {
   public:
      BigInt_IsSquare_Test() : Text_Based_Test("bn/perfect_square.vec", "X,R") {}

      Test::Result run_one_test(const std::string& /*header*/, const VarMap& vars) override {
         const BigInt value = vars.get_req_bn("X");
         const BigInt expected = vars.get_req_bn("R");
         const BigInt computed = Botan::is_perfect_square(value);

         Test::Result result("BigInt IsSquare");
         result.test_bn_eq("is_perfect_square", computed, expected);
         return result;
      }
};

BOTAN_REGISTER_TEST("math", "bn_issquare", BigInt_IsSquare_Test);

class BigInt_Sqrt_Modulo_Prime_Test final : public Text_Based_Test {
   public:
      BigInt_Sqrt_Modulo_Prime_Test() : Text_Based_Test("bn/sqrt_modulo_prime.vec", "Input,Modulus,Output") {}

      Test::Result run_one_test(const std::string& /*header*/, const VarMap& vars) override {
         Test::Result result("BigInt Sqrt Modulo Prime");

         const Botan::BigInt a = vars.get_req_bn("Input");
         const Botan::BigInt p = vars.get_req_bn("Modulus");
         const Botan::BigInt exp = vars.get_req_bn("Output");

         const Botan::BigInt a_sqrt = Botan::sqrt_modulo_prime(a, p);

         result.test_bn_eq("sqrt_modulo_prime", a_sqrt, exp);

         if(a_sqrt > 1) {
            const Botan::BigInt a_sqrt2 = (a_sqrt * a_sqrt) % p;
            result.test_bn_eq("square correct", a_sqrt2, a);
         }

         return result;
      }
};

BOTAN_REGISTER_TEST("math", "bn_sqrt_modulo_prime", BigInt_Sqrt_Modulo_Prime_Test);

class BigInt_InvMod_Test final : public Text_Based_Test {
   public:
      BigInt_InvMod_Test() : Text_Based_Test("bn/invmod.vec", "Input,Modulus,Output") {}

      Test::Result run_one_test(const std::string& /*header*/, const VarMap& vars) override {
         Test::Result result("BigInt InvMod");

         const Botan::BigInt a = vars.get_req_bn("Input");
         const Botan::BigInt mod = vars.get_req_bn("Modulus");
         const Botan::BigInt expected = vars.get_req_bn("Output");

         result.test_bn_eq("inverse_mod", Botan::inverse_mod(a, mod), expected);

         if(a < mod && a > 0 && a < mod) {
            auto g = Botan::inverse_mod_general(a, mod);
            if(g.has_value()) {
               result.test_bn_eq("inverse_mod_general", g.value(), expected);
               result.test_bn_eq("inverse works", ((g.value() * a) % mod), BigInt::one());
            } else {
               result.test_is_true("inverse_mod_general", expected.is_zero());
            }

            if(Botan::is_prime(mod, rng()) && mod != 2) {
               BOTAN_ASSERT_NOMSG(expected > 0);
               result.test_bn_eq("inverse_mod_secret_prime", Botan::inverse_mod_secret_prime(a, mod), expected);
               result.test_bn_eq("inverse_mod_public_prime", Botan::inverse_mod_public_prime(a, mod), expected);
            }
         }

         return result;
      }
};

BOTAN_REGISTER_TEST("math", "bn_invmod", BigInt_InvMod_Test);

class BigInt_Rand_Test final : public Text_Based_Test {
   public:
      BigInt_Rand_Test() : Text_Based_Test("bn/random.vec", "Seed,Min,Max,Output") {}

      Test::Result run_one_test(const std::string& /*header*/, const VarMap& vars) override {
         Test::Result result("BigInt Random");

         const std::vector<uint8_t> seed = vars.get_req_bin("Seed");
         const Botan::BigInt min = vars.get_req_bn("Min");
         const Botan::BigInt max = vars.get_req_bn("Max");
         const Botan::BigInt expected = vars.get_req_bn("Output");

         Fixed_Output_RNG rng(seed);
         const Botan::BigInt generated = BigInt::random_integer(rng, min, max);

         result.test_bn_eq("random_integer KAT", generated, expected);

         return result;
      }
};

BOTAN_REGISTER_TEST("math", "bn_rand", BigInt_Rand_Test);

class Lucas_Primality_Test final : public Test {
   public:
      std::vector<Test::Result> run() override {
         const uint32_t lucas_max = (Test::run_long_tests() ? 100000 : 10000) + 1;

         // OEIS A217120
         const std::set<uint32_t> lucas_pp{
            323,   377,   1159,  1829,  3827,  5459,  5777,  9071,  9179,  10877, 11419, 11663, 13919, 14839, 16109,
            16211, 18407, 18971, 19043, 22499, 23407, 24569, 25199, 25877, 26069, 27323, 32759, 34943, 35207, 39059,
            39203, 39689, 40309, 44099, 46979, 47879, 50183, 51983, 53663, 56279, 58519, 60377, 63881, 69509, 72389,
            73919, 75077, 77219, 79547, 79799, 82983, 84419, 86063, 90287, 94667, 97019, 97439,
         };

         Test::Result result("Lucas primality test");

         for(uint32_t i = 3; i <= lucas_max; i += 2) {
            auto mod_i = Botan::Barrett_Reduction::for_public_modulus(i);
            const bool passes_lucas = Botan::is_lucas_probable_prime(i, mod_i);
            const bool is_prime = Botan::is_prime(i, this->rng());

            const bool is_lucas_pp = (is_prime == false && passes_lucas == true);

            if(is_lucas_pp) {
               result.test_is_true("Lucas pseudoprime is in list", lucas_pp.contains(i));
            } else {
               result.test_is_true("Lucas non-pseudoprime is not in list", !lucas_pp.contains(i));
            }
         }

         return {result};
      }
};

BOTAN_REGISTER_TEST("math", "bn_lucas", Lucas_Primality_Test);

class RSA_Compute_Exp_Test : public Test {
   public:
      std::vector<Test::Result> run() override {
         const size_t iter = 4000;

         Test::Result result("RSA compute exponent");

         const auto e = Botan::BigInt::from_u64(65537);

         /*
         * Rather than create a fresh p/q for each iteration this test creates
         * a pool of primes then selects 2 at random as p/q
         */

         const auto random_primes = [&]() {
            std::vector<Botan::BigInt> rp;
            for(size_t i = 0; i != iter / 10; ++i) {
               const size_t bits = (128 + (i % 1024)) % 4096;
               auto p = Botan::random_prime(rng(), bits);
               if(gcd(p - 1, e) == 1) {
                  rp.push_back(p);
               }
            }
            return rp;
         }();

         for(size_t i = 0; i != iter; ++i) {
            const size_t p_idx = random_index(rng(), random_primes.size());
            const size_t q_idx = random_index(rng(), random_primes.size());

            if(p_idx == q_idx) {
               continue;
            }

            const auto& p = random_primes[p_idx];
            const auto& q = random_primes[q_idx];

            auto phi_n = lcm(p - 1, q - 1);

            auto d = Botan::compute_rsa_secret_exponent(e, phi_n, p, q);

            auto ed_mod_phi_n = (e * d) % phi_n;

            result.test_bn_eq("compute_rsa_secret_exponent returned inverse", ed_mod_phi_n, Botan::BigInt::one());
         }

         return {result};
      }
};

BOTAN_REGISTER_TEST("math", "rsa_compute_d", RSA_Compute_Exp_Test);

class DSA_ParamGen_Test final : public Text_Based_Test {
   public:
      DSA_ParamGen_Test() : Text_Based_Test("bn/dsa_gen.vec", "P,Q,Counter,Seed") {}

      Test::Result run_one_test(const std::string& header, const VarMap& vars) override {
         const std::vector<uint8_t> seed = vars.get_req_bin("Seed");
         const size_t offset = vars.get_req_sz("Counter");

         const Botan::BigInt exp_P = vars.get_req_bn("P");
         const Botan::BigInt exp_Q = vars.get_req_bn("Q");

         const std::vector<std::string> header_parts = Botan::split_on(header, ',');

         if(header_parts.size() != 2) {
            throw Test_Error("Unexpected header '" + header + "' in DSA param gen test");
         }

         const size_t p_bits = Botan::to_u32bit(header_parts[1]);
         const size_t q_bits = Botan::to_u32bit(header_parts[0]);

         Test::Result result("DSA Parameter Generation");

         try {
            Botan::BigInt gen_P;
            Botan::BigInt gen_Q;
            if(Botan::generate_dsa_primes(this->rng(), gen_P, gen_Q, p_bits, q_bits, seed, offset)) {
               result.test_bn_eq("P", gen_P, exp_P);
               result.test_bn_eq("Q", gen_Q, exp_Q);
            } else {
               result.test_failure("Seed did not generate a DSA parameter");
            }
         } catch(Botan::Lookup_Error&) {}

         return result;
      }
};

BOTAN_REGISTER_TEST("math", "dsa_param", DSA_ParamGen_Test);

std::vector<Test::Result> test_bigint_serialization() {
   auto rng = Test::new_rng("test_bigint_serialization");

   return {
      CHECK("BigInt binary serialization",
            [](Test::Result& res) {
               Botan::BigInt a(0x1234567890ABCDEF);
               auto enc = a.serialize();
               res.test_bin_eq("BigInt::serialize", enc, "1234567890ABCDEF");

               auto enc10 = a.serialize(10);
               res.test_bin_eq("BigInt::serialize", enc10, "00001234567890ABCDEF");

               res.test_throws("BigInt::serialize rejects short output", [&]() { a.serialize(7); });
            }),

      CHECK("BigInt truncated/padded binary serialization",
            [&](Test::Result& res) {
               const Botan::BigInt a(0xFEDCBA9876543210);

               std::vector<uint8_t> enc1(a.bytes() - 1);
               a.binary_encode(enc1.data(), enc1.size());
               res.test_bin_eq("BigInt::binary_encode", enc1, "DCBA9876543210");

               std::vector<uint8_t> enc2(a.bytes() - 3);
               a.binary_encode(enc2.data(), enc2.size());
               res.test_bin_eq("BigInt::binary_encode", enc2, "9876543210");

               std::vector<uint8_t> enc3(a.bytes() + 1);
               a.binary_encode(enc3.data(), enc3.size());
               res.test_bin_eq("BigInt::binary_encode", enc3, "00FEDCBA9876543210");

               // make sure that the padding is actually written
               std::vector<uint8_t> enc4(a.bytes() + 3);
               rng->randomize(enc4);
               a.binary_encode(enc4.data(), enc4.size());
               res.test_bin_eq("BigInt::binary_encode", enc4, "000000FEDCBA9876543210");

               const Botan::BigInt b("0xFEDCBA9876543210BAADC0FFEE");

               std::vector<uint8_t> enc5(b.bytes() + 12);
               rng->randomize(enc5);
               b.binary_encode(enc5.data(), enc5.size());
               res.test_bin_eq("BigInt::binary_encode", enc5, "000000000000000000000000FEDCBA9876543210BAADC0FFEE");
            }),
   };
}

BOTAN_REGISTER_TEST_FN("math", "bignum_auxiliary", test_const_time_left_shift, test_bigint_serialization);

class BigInt_FromRadix_Tests final : public Text_Based_Test {
   public:
      BigInt_FromRadix_Tests() : Text_Based_Test("bn/from_radix.vec", "Input,Radix,Output") {}

      bool clear_between_callbacks() const override { return false; }

      Test::Result run_one_test(const std::string& header, const VarMap& vars) override {
         Test::Result result("BigInt from_radix_digits");

         const std::string input = vars.get_req_str("Input");
         const size_t radix = vars.get_req_sz("Radix");
         const std::string expected_output = vars.get_req_str("Output");

         if(header == "Valid") {
            const Botan::BigInt n = Botan::BigInt::from_radix_digits(input, radix);
            const auto serialized = n.serialize();
            result.test_bin_eq("from_radix_digits", serialized, expected_output);
         } else if(header == "Invalid") {
            try {
               Botan::BigInt::from_radix_digits(input, radix);
               result.test_failure("from_radix_digits should have thrown");
            } catch(const std::exception& e) {
               const std::string msg = e.what();
               result.test_is_true("exception message contains '" + expected_output + "'",
                                   msg.find(expected_output) != std::string::npos);
            }
         } else {
            result.test_failure("Unknown header " + header);
         }

         return result;
      }
};

BOTAN_REGISTER_TEST("math", "bn_from_radix", BigInt_FromRadix_Tests);

#endif

}  // namespace

}  // namespace Botan_Tests

randombit / botan / 25650639339

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous