randombit / botan / 24054627669

coverage: 89.447% (-0.008%) from 89.455%
24054627669

push

github

web-flow 
Merge pull request #5521 from randombit/jack/fix-rollup

Rollup of small fixes

105877 of 118368 relevant lines covered (89.45%)

11509334.19 hits per line

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

99.5
/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)) {




8,582✔





47



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




8,573✔





48












49



               sqr_timer->start();




8,573✔





50



               x.square(ws);




8,573✔





51



               sqr_timer->stop();




8,573✔





52












53



               x.mask_bits(bits);




8,573✔





54












55



               mul_timer->start();




8,573✔





56



               x.mul(y, ws);




8,573✔





57



               mul_timer->stop();




8,573✔





58



            }




8,573✔





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



            auto ct_div_timer = config.make_timer("BigInt ct_div " + bit_descr);




18✔





79












80



            Botan::BigInt y;




9✔





81



            Botan::BigInt x;




9✔





82



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




9✔





83












84



            Botan::BigInt q1;




9✔





85



            Botan::BigInt r1;




9✔





86



            Botan::BigInt q2;




9✔





87



            Botan::BigInt r2;




9✔





88












89



            while(ct_div_timer->under(runtime_per_size)) {




9✔





90



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




57✔





91



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




57✔





92












93



               div_timer->start();




57✔





94



               Botan::vartime_divide(x, y, q1, r1);




57✔





95



               div_timer->stop();




57✔





96












97



               ct_div_timer->start();




57✔





98



               Botan::ct_divide(x, y, q2, r2);




57✔





99



               ct_div_timer->stop();




57✔





100












101



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




57✔





102



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




123✔





103



            }










104












105



            config.record_result(*div_timer);




9✔





106



            config.record_result(*ct_div_timer);




9✔





107



         }




18✔





108



      }




1✔





109



};










110












111



BOTAN_REGISTER_PERF_TEST("mp_div", PerfTest_MpDiv);




1✔





112












113



class PerfTest_MpDiv10 final : public PerfTest {




1✔





114



   public:










115



      void go(const PerfConfig& config) override {




1✔





116



         const auto runtime_per_size = config.runtime();




1✔





117












118



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




10✔





119



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




18✔





120












121



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




18✔





122



            auto ct_div_timer = config.make_timer("BigInt ct_div " + bit_descr);




18✔





123












124



            Botan::BigInt x;




9✔





125



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




9✔





126












127



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




9✔





128



            Botan::BigInt q1;




9✔





129



            Botan::BigInt r1;




9✔





130



            Botan::BigInt q2;




9✔





131



            Botan::word r2 = 0;




9✔





132












133



            while(ct_div_timer->under(runtime_per_size)) {




9✔





134



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




688✔





135












136



               div_timer->start();




688✔





137



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




688✔





138



               div_timer->stop();




688✔





139












140



               ct_div_timer->start();




688✔





141



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




688✔





142



               ct_div_timer->stop();




688✔





143












144



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




688✔





145



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




1,385✔





146



            }










147












148



            config.record_result(*div_timer);




9✔





149



            config.record_result(*ct_div_timer);




9✔





150



         }




18✔





151



      }




1✔





152



};










153












154



BOTAN_REGISTER_PERF_TEST("mp_div10", PerfTest_MpDiv10);




1✔





155












156



#endif










157












158



#if defined(BOTAN_HAS_NUMBERTHEORY)










159












160



class PerfTest_BnRedc final : public PerfTest {




1✔





161



   public:










162



      void go(const PerfConfig& config) override {




1✔





163



         const auto runtime = config.runtime();




1✔





164












165



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




6✔





166



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




5✔





167












168



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




10✔





169



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




10✔





170



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




10✔





171












172



            while(barrett_setup_sec_timer->under(runtime)) {




57✔





173



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




104✔





174



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




104✔





175



            }










176












177



            config.record_result(*barrett_setup_pub_timer);




5✔





178



            config.record_result(*barrett_setup_sec_timer);




5✔





179












180



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




5✔





181












182



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




10✔





183



            auto knuth_timer = config.make_timer(bit_str + "Knuth redc");




10✔





184



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




10✔





185












186



            while(ct_modulo_timer->under(runtime)) {




25✔





187



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




20✔





188












189



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




40✔





190



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




40✔





191



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




40✔





192












193



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




20✔





194



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




20✔





195



            }




20✔





196












197



            config.record_result(*barrett_timer);




5✔





198



            config.record_result(*knuth_timer);




5✔





199



            config.record_result(*ct_modulo_timer);




10✔





200



         }




25✔





201



      }




1✔





202



};










203












204



BOTAN_REGISTER_PERF_TEST("bn_redc", PerfTest_BnRedc);




1✔





205












206



class PerfTest_InvMod final : public PerfTest {




1✔





207



   public:










208



      void go(const PerfConfig& config) override {




1✔





209



         const auto runtime = config.runtime();




1✔





210












211



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




6✔





212



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




5✔





213












214



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




10✔





215



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




10✔





216












217



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




15✔





218



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




10✔





219



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




10✔





220












221



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




20✔





222












223



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




20✔





224












225



               if(x_inv == 0) {




10✔





226



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




4✔





227



               } else {










228



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




6✔





229



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




6✔





230



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




6✔





231



               }




6✔





232



            }




10✔





233












234



            config.record_result(*timer);




5✔





235



            config.record_result(*gcd_timer);




10✔





236



         }




5✔





237



      }




1✔





238



};










239












240



BOTAN_REGISTER_PERF_TEST("inverse_mod", PerfTest_InvMod);




1✔





241












242



class PerfTest_IsPrime final : public PerfTest {




1✔





243



   public:










244



      void go(const PerfConfig& config) override {




1✔





245



         const auto runtime = config.runtime();




1✔





246












247



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




4✔





248



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




6✔





249



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




6✔





250



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




6✔





251












252



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




3✔





253












254



            while(lucas_timer->under(runtime)) {




6✔





255



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




3✔





256



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




3✔





257












258



               mr_timer->run(




3✔





259



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




3✔





260












261



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




6✔





262












263



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




6✔





264












265



               n += 2;




3✔





266



            }




6✔





267












268



            config.record_result(*mr_timer);




3✔





269



            config.record_result(*bpsw_timer);




3✔





270



            config.record_result(*lucas_timer);




3✔





271



         }




9✔





272



      }




1✔





273



};










274












275



BOTAN_REGISTER_PERF_TEST("primality_test", PerfTest_IsPrime);




1✔





276












277



class PerfTest_RandomPrime final : public PerfTest {




1✔





278



   public:










279



      void go(const PerfConfig& config) override {




1✔





280



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




1✔





281



         const auto runtime = config.runtime();




1✔





282












283



         auto& rng = config.rng();




1✔





284












285



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




7✔





286



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




12✔





287



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




12✔





288












289



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




12✔





290



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




12✔





291












292



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




12✔





293



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




×







294



               }










295












296



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










297



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




198✔





298



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




384✔





299



               }










300



            }




6✔





301












302



            config.record_result(*genprime_timer);




6✔





303



            config.record_result(*is_prime_timer);




12✔





304



         }




6✔





305



      }




1✔





306



};










307












308



BOTAN_REGISTER_PERF_TEST("random_prime", PerfTest_RandomPrime);




1✔





309












310



#endif










311












312



#if defined(BOTAN_HAS_DL_GROUP)










313












314



class PerfTest_ModExp final : public PerfTest {




1✔





315



   public:










316



      void go(const PerfConfig& config) override {




1✔





317



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




8✔





318



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




14✔





319



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




7✔





320












321



            const size_t e_bits = group.exponent_bits();




7✔





322



            const size_t f_bits = group_bits - 1;




7✔





323












324



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




7✔





325



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




7✔





326












327



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




14✔





328



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




14✔





329












330



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




15✔





331



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




16✔





332



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




16✔





333



            }










334












335



            config.record_result(*e_timer);




7✔





336



            config.record_result(*f_timer);




14✔





337



         }




21✔





338



      }




1✔





339



};










340












341



BOTAN_REGISTER_PERF_TEST("modexp", PerfTest_ModExp);




1✔





342












343



#endif










344












345



}  // namespace










346












347



}  // namespace Botan_CLI
























    

  • 

    •