randombit / botan / 33231351942

coverage: 89.685% (-0.001%) from 89.686%
33231351942

push

github

web-flow 
Merge pull request #5880 from randombit/jack/bn-divide-is-ct

Convert all BigInt integer divisions to constant time

123278 of 137456 relevant lines covered (89.69%)

10257995.98 hits per line

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

99.48
/src/cli/perf_math.cpp
1 
/*
2 
* (C) 2024 Jack Lloyd
3 
*
4 
* Botan is released under the Simplified BSD License (see license.txt)
5 
*/
6 









7



#include "perf.h"










8












9



#include <ostream>










10












11



#if defined(BOTAN_HAS_BIGINT)










12



   #include <botan/assert.h>










13



   #include <botan/bigint.h>










14



   #include <botan/internal/divide.h>










15



#endif










16












17



#if defined(BOTAN_HAS_NUMBERTHEORY)










18



   #include <botan/numthry.h>










19



   #include <botan/internal/barrett.h>










20



   #include <botan/internal/monty.h>










21



   #include <botan/internal/primality.h>










22



#endif










23












24



#if defined(BOTAN_HAS_DL_GROUP)










25



   #include <botan/dl_group.h>










26



#endif










27












28



namespace Botan_CLI {










29












30



namespace {










31












32



#if defined(BOTAN_HAS_BIGINT)










33












34



class PerfTest_MpMul final : public PerfTest {




1✔





35



   public:










36



      void go(const PerfConfig& config) override {




1✔





37



         const auto runtime_per_size = config.runtime();




1✔





38












39



         for(const size_t bits : {256, 384, 512, 768, 1024, 1536, 2048, 3072, 4096}) {




10✔





40



            auto mul_timer = config.make_timer("BigInt mul " + std::to_string(bits));




18✔





41



            auto sqr_timer = config.make_timer("BigInt sqr " + std::to_string(bits));




18✔





42












43



            const Botan::BigInt y(config.rng(), bits);




9✔





44



            Botan::secure_vector<Botan::word> ws;




9✔





45












46



            while(mul_timer->under(runtime_per_size)) {




7,820✔





47



               Botan::BigInt x(config.rng(), bits);




7,811✔





48












49



               sqr_timer->start();




7,811✔





50



               x.square(ws);




7,811✔





51



               sqr_timer->stop();




7,811✔





52












53



               x.mask_bits(bits);




7,811✔





54












55



               mul_timer->start();




7,811✔





56



               x.mul(y, ws);




7,811✔





57



               mul_timer->stop();




7,811✔





58



            }




7,811✔





59












60



            config.record_result(*mul_timer);




9✔





61



            config.record_result(*sqr_timer);




18✔





62



         }




18✔





63



      }




1✔





64



};










65












66



BOTAN_REGISTER_PERF_TEST("mp_mul", PerfTest_MpMul);




1✔





67












68



class PerfTest_MpDiv final : public PerfTest {




1✔





69



   public:










70



      void go(const PerfConfig& config) override {




1✔





71



         const auto runtime_per_size = config.runtime();




1✔





72












73



         for(const size_t n_bits : {256, 384, 512, 768, 1024, 1536, 2048, 3072, 4096}) {




10✔





74



            const size_t q_bits = n_bits / 2;




9✔





75



            const std::string bit_descr = std::to_string(n_bits) + "/" + std::to_string(q_bits);




27✔





76












77



            auto div_timer = config.make_timer("BigInt div " + bit_descr);




18✔





78












79



            Botan::BigInt y;




9✔





80



            Botan::BigInt x;




9✔





81












82



            Botan::BigInt q;




9✔





83



            Botan::BigInt r;




9✔





84












85



            while(div_timer->under(runtime_per_size)) {




9✔





86



               x.randomize(config.rng(), n_bits);




3,527✔





87



               y.randomize(config.rng(), q_bits);




3,527✔





88












89



               div_timer->start();




3,527✔





90



               Botan::ct_divide(x, y, q, r);




3,527✔





91



               div_timer->stop();




3,527✔





92












93



               BOTAN_ASSERT_NOMSG(r < y);




3,527✔





94



               BOTAN_ASSERT_NOMSG(q * y + r == x);




10,590✔





95



            }










96












97



            config.record_result(*div_timer);




9✔





98



         }




9✔





99



      }




1✔





100



};










101












102



BOTAN_REGISTER_PERF_TEST("mp_div", PerfTest_MpDiv);




1✔





103












104



class PerfTest_MpDiv10 final : public PerfTest {




1✔





105



   public:










106



      void go(const PerfConfig& config) override {




1✔





107



         const auto runtime_per_size = config.runtime();




1✔





108












109



         for(const size_t n_bits : {256, 384, 512, 768, 1024, 1536, 2048, 3072, 4096}) {




10✔





110



            const std::string bit_descr = std::to_string(n_bits) + "/10";




18✔





111












112



            auto div_timer = config.make_timer("BigInt div " + bit_descr);




18✔





113



            auto div_word_timer = config.make_timer("BigInt div_word " + bit_descr);




18✔





114












115



            Botan::BigInt x;




9✔





116












117



            const auto ten = Botan::BigInt::from_word(10);




9✔





118



            Botan::BigInt q1;




9✔





119



            Botan::BigInt r1;




9✔





120



            Botan::BigInt q2;




9✔





121



            Botan::word r2 = 0;




9✔





122












123



            while(div_timer->under(runtime_per_size)) {




9✔





124



               x.randomize(config.rng(), n_bits);




5,723✔





125












126



               div_timer->start();




5,723✔





127



               Botan::ct_divide(x, ten, q1, r1);




5,723✔





128



               div_timer->stop();




5,723✔





129












130



               div_word_timer->start();




5,723✔





131



               Botan::ct_divide_word(x, 10, q2, r2);




5,723✔





132



               div_word_timer->stop();




5,723✔





133












134



               BOTAN_ASSERT_EQUAL(q1, q2, "Quotient ok");




5,723✔





135



               BOTAN_ASSERT_EQUAL(r1, r2, "Remainder ok");




11,455✔





136



            }










137












138



            config.record_result(*div_timer);




9✔





139



            config.record_result(*div_word_timer);




9✔





140



         }




18✔





141



      }




1✔





142



};










143












144



BOTAN_REGISTER_PERF_TEST("mp_div10", PerfTest_MpDiv10);




1✔





145












146



#endif










147












148



#if defined(BOTAN_HAS_NUMBERTHEORY)










149












150



class PerfTest_BnRedc final : public PerfTest {




1✔





151



   public:










152



      void go(const PerfConfig& config) override {




1✔





153



         const auto runtime = config.runtime();




1✔





154












155



         for(const size_t bitsize : {256, 512, 1024, 2048, 4096}) {




6✔





156



            Botan::BigInt p(config.rng(), bitsize);




5✔





157












158



            const std::string bit_str = std::to_string(bitsize) + " bit ";




10✔





159



            auto barrett_setup_pub_timer = config.make_timer(bit_str + "Barrett setup public");




10✔





160



            auto barrett_setup_sec_timer = config.make_timer(bit_str + "Barrett setup secret");




10✔





161












162



            while(barrett_setup_sec_timer->under(runtime)) {




847✔





163



               barrett_setup_sec_timer->run([&]() { Botan::Barrett_Reduction::for_secret_modulus(p); });




1,684✔





164



               barrett_setup_pub_timer->run([&]() { Botan::Barrett_Reduction::for_public_modulus(p); });




1,684✔





165



            }










166












167



            config.record_result(*barrett_setup_pub_timer);




5✔





168



            config.record_result(*barrett_setup_sec_timer);




5✔





169












170



            auto mod_p = Botan::Barrett_Reduction::for_public_modulus(p);




5✔





171












172



            auto barrett_timer = config.make_timer(bit_str + "Barrett redc");




10✔





173



            auto mod_op_timer = config.make_timer(bit_str + "operator% redc");




10✔





174



            auto ct_modulo_timer = config.make_timer(bit_str + "ct_modulo");




10✔





175












176



            while(ct_modulo_timer->under(runtime)) {




1,579✔





177



               const Botan::BigInt x(config.rng(), p.bits() * 2 - 1);




1,574✔





178












179



               const Botan::BigInt r1 = barrett_timer->run([&] { return mod_p.reduce(x); });




3,148✔





180



               const Botan::BigInt r2 = mod_op_timer->run([&] { return x % p; });




3,148✔





181



               const Botan::BigInt r3 = ct_modulo_timer->run([&] { return Botan::ct_modulo(x, p); });




3,148✔





182












183



               BOTAN_ASSERT(r1 == r2, "Computed different results");




1,574✔





184



               BOTAN_ASSERT(r1 == r3, "Computed different results");




1,574✔





185



            }




1,574✔





186












187



            config.record_result(*barrett_timer);




5✔





188



            config.record_result(*mod_op_timer);




5✔





189



            config.record_result(*ct_modulo_timer);




10✔





190



         }




25✔





191



      }




1✔





192



};










193












194



BOTAN_REGISTER_PERF_TEST("bn_redc", PerfTest_BnRedc);




1✔





195












196



class PerfTest_InvMod final : public PerfTest {




1✔





197



   public:










198



      void go(const PerfConfig& config) override {




1✔





199



         const auto runtime = config.runtime();




1✔





200












201



         for(const size_t bits : {256, 384, 512, 1024, 2048}) {




6✔





202



            const std::string bit_str = std::to_string(bits);




5✔





203












204



            auto timer = config.make_timer("inverse_mod-" + bit_str);




10✔





205



            auto gcd_timer = config.make_timer("gcd-" + bit_str);




10✔





206












207



            while(timer->under(runtime) && gcd_timer->under(runtime)) {




15✔





208



               const Botan::BigInt x(config.rng(), bits - 1);




10✔





209



               Botan::BigInt mod(config.rng(), bits);




10✔





210












211



               const Botan::BigInt x_inv = timer->run([&] { return Botan::inverse_mod(x, mod); });




20✔





212












213



               const Botan::BigInt g = gcd_timer->run([&] { return gcd(x, mod); });




20✔





214












215



               if(x_inv == 0) {




10✔





216



                  BOTAN_ASSERT(g != 1, "Inversion only fails if gcd(x, mod) > 1");




4✔





217



               } else {










218



                  BOTAN_ASSERT(g == 1, "Inversion succeeds only if gcd != 1");




6✔





219



                  const Botan::BigInt check = (x_inv * x) % mod;




6✔





220



                  BOTAN_ASSERT_EQUAL(check, 1, "Const time inversion correct");




6✔





221



               }




6✔





222



            }




10✔





223












224



            config.record_result(*timer);




5✔





225



            config.record_result(*gcd_timer);




10✔





226



         }




5✔





227



      }




1✔





228



};










229












230



BOTAN_REGISTER_PERF_TEST("inverse_mod", PerfTest_InvMod);




1✔





231












232



class PerfTest_IsPrime final : public PerfTest {




1✔





233



   public:










234



      void go(const PerfConfig& config) override {




1✔





235



         const auto runtime = config.runtime();




1✔





236












237



         for(const size_t bits : {256, 512, 1024}) {




4✔





238



            auto mr_timer = config.make_timer("Miller-Rabin-" + std::to_string(bits));




6✔





239



            auto bpsw_timer = config.make_timer("Bailie-PSW-" + std::to_string(bits));




6✔





240



            auto lucas_timer = config.make_timer("Lucas-" + std::to_string(bits));




6✔





241












242



            Botan::BigInt n = Botan::random_prime(config.rng(), bits);




3✔





243












244



            while(lucas_timer->under(runtime)) {




6✔





245



               auto mod_n = Botan::Barrett_Reduction::for_public_modulus(n);




3✔





246



               const Botan::Montgomery_Params monty_n(n, mod_n);




3✔





247












248



               mr_timer->run(




3✔





249



                  [&]() { return Botan::is_miller_rabin_probable_prime(n, mod_n, monty_n, config.rng(), 2); });




3✔





250












251



               bpsw_timer->run([&]() { return Botan::is_bailie_psw_probable_prime(n, mod_n); });




6✔





252












253



               lucas_timer->run([&]() { return Botan::is_lucas_probable_prime(n, mod_n); });




6✔





254












255



               n += 2;




3✔





256



            }




6✔





257












258



            config.record_result(*mr_timer);




3✔





259



            config.record_result(*bpsw_timer);




3✔





260



            config.record_result(*lucas_timer);




3✔





261



         }




9✔





262



      }




1✔





263



};










264












265



BOTAN_REGISTER_PERF_TEST("primality_test", PerfTest_IsPrime);




1✔





266












267



class PerfTest_RandomPrime final : public PerfTest {




1✔





268



   public:










269



      void go(const PerfConfig& config) override {




1✔





270



         const auto coprime = Botan::BigInt::from_word(0x10001);




1✔





271



         const auto runtime = config.runtime();




1✔





272












273



         auto& rng = config.rng();




1✔





274












275



         for(size_t bits : {256, 384, 512, 768, 1024, 1536}) {




7✔





276



            auto genprime_timer = config.make_timer("random_prime " + std::to_string(bits));




12✔





277



            auto is_prime_timer = config.make_timer("is_prime " + std::to_string(bits));




12✔





278












279



            while(genprime_timer->under(runtime) && is_prime_timer->under(runtime)) {




12✔





280



               const Botan::BigInt p = genprime_timer->run([&] { return Botan::random_prime(rng, bits, coprime); });




12✔





281












282



               if(!is_prime_timer->run([&] { return Botan::is_prime(p, rng, 64, true); })) {




12✔





283



                  config.error_output() << "Generated prime " << p << " which failed a primality test";




×







284



               }










285












286



               // Now test p+2, p+4, ... which may or may not be prime










287



               for(size_t i = 2; i <= 64; i += 2) {




198✔





288



                  is_prime_timer->run([&]() { Botan::is_prime(p + i, rng, 64, true); });




384✔





289



               }










290



            }




6✔





291












292



            config.record_result(*genprime_timer);




6✔





293



            config.record_result(*is_prime_timer);




12✔





294



         }




6✔





295



      }




1✔





296



};










297












298



BOTAN_REGISTER_PERF_TEST("random_prime", PerfTest_RandomPrime);




1✔





299












300



#endif










301












302



#if defined(BOTAN_HAS_DL_GROUP)










303












304



class PerfTest_ModExp final : public PerfTest {




1✔





305



   public:










306



      void go(const PerfConfig& config) override {




1✔





307



         for(const size_t group_bits : {1024, 1536, 2048, 3072, 4096, 6144, 8192}) {




8✔





308



            const std::string group_name = "modp/ietf/" + std::to_string(group_bits);




14✔





309



            auto group = Botan::DL_Group::from_name(group_name);




7✔





310












311



            const size_t e_bits = group.exponent_bits();




7✔





312



            const size_t f_bits = group_bits - 1;




7✔





313












314



            const Botan::BigInt random_e(config.rng(), e_bits);




7✔





315



            const Botan::BigInt random_f(config.rng(), f_bits);




7✔





316












317



            auto e_timer = config.make_timer(group_name + " short exp");




14✔





318



            auto f_timer = config.make_timer(group_name + "  full exp");




14✔





319












320



            while(f_timer->under(config.runtime())) {




15✔





321



               e_timer->run([&]() { group.power_g_p(random_e, e_bits); });




16✔





322



               f_timer->run([&]() { group.power_g_p(random_f, f_bits); });




16✔





323



            }










324












325



            config.record_result(*e_timer);




7✔





326



            config.record_result(*f_timer);




14✔





327



         }




21✔





328



      }




1✔





329



};










330












331



BOTAN_REGISTER_PERF_TEST("modexp", PerfTest_ModExp);




1✔





332












333



#endif










334












335



}  // namespace










336












337



}  // namespace Botan_CLI
























    

  • 

    •