randombit / botan / 39538855493

coverage: 89.792% (-2.5%) from 92.339%
39538855493

push

github

web-flow 
Merge pull request #6048 from Rohde-Schwarz/ffi/shared_rng

134391 of 149670 relevant lines covered (89.79%)

8874616.75 hits per line

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

99.51
/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,983
✔





47



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




8,974
✔





48












49



               sqr_timer->start();




8,974
✔





50



               x.square(ws);




8,974
✔





51



               sqr_timer->stop();




8,974
✔





52












53



               x.mask_bits(bits);




8,974
✔





54












55



               mul_timer->start();




8,974
✔





56



               x.mul(y, ws);




8,974
✔





57



               mul_timer->stop();




8,974
✔





58



            }




8,974
✔





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,753
✔





87



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




3,753
✔





88












89



               div_timer->start();




3,753
✔





90



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




3,753
✔





91



               div_timer->stop();




3,753
✔





92












93



               BOTAN_ASSERT_NOMSG(r < y);




3,753
✔





94



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




11,268
✔





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,927
✔





125












126



               div_timer->start();




5,927
✔





127



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




5,927
✔





128



               div_timer->stop();




5,927
✔





129












130



               div_word_timer->start();




5,927
✔





131



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




5,927
✔





132



               div_word_timer->stop();




5,927
✔





133












134



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




5,927
✔





135



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




11,863
✔





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




836
✔





163



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




1,662
✔





164



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




1,662
✔





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,568
✔





177



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




1,563
✔





178












179



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




3,126
✔





180



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




3,126
✔





181



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




3,126
✔





182












183



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




1,563
✔





184



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




1,563
✔





185



            }




1,563
✔





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




14
✔





208



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




9
✔





209



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




9
✔





210












211



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




18
✔





212












213



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




18
✔





214












215



               if(x_inv == 0) {




9
✔





216



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




3
✔





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



            }




9
✔





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, 2048}) {




5
✔





238



            const std::string suffix = "-" + std::to_string(bits);




8
✔





239












240



            auto mr_timer = config.make_timer("Miller-Rabin" + suffix);




8
✔





241



            auto mr_vt_timer = config.make_timer("Miller-Rabin-vartime" + suffix);




8
✔





242



            auto lucas_timer = config.make_timer("Lucas" + suffix);




8
✔





243



            auto lucas_vt_timer = config.make_timer("Lucas-vartime" + suffix);




8
✔





244



            auto bpsw_timer = config.make_timer("Bailie-PSW" + suffix);




8
✔





245



            auto bpsw_vt_timer = config.make_timer("Bailie-PSW-vartime" + suffix);




8
✔





246



            auto strong_timer = config.make_timer("is_prime-strong" + suffix);




8
✔





247



            auto strong_vt_timer = config.make_timer("is_prime-strong-vartime" + suffix);




8
✔





248












249



            // Testing a prime is the worst case, since no test can fail early










250



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




4
✔





251



            const Botan::Montgomery_Params monty_n(n);




4
✔





252












253



            while(lucas_timer->under(runtime)) {




10
✔





254



               mr_timer->run([&]() { return Botan::is_miller_rabin_probable_prime(n, monty_n, config.rng(), 1); });




12
✔





255



               mr_vt_timer->run(




6
✔





256



                  [&]() { return Botan::is_miller_rabin_probable_prime_vartime(n, monty_n, config.rng(), 1); });




6
✔





257












258



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




12
✔





259



               lucas_vt_timer->run([&]() { return Botan::is_lucas_probable_prime_vartime(n, monty_n); });




12
✔





260












261



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




12
✔





262



               bpsw_vt_timer->run([&]() { return Botan::is_bailie_psw_probable_prime_vartime(n, monty_n); });




12
✔





263












264



               strong_timer->run([&]() { return Botan::is_prime(n, config.rng(), 128, false); });




12
✔





265



               strong_vt_timer->run([&]() { return Botan::is_prime_vartime(n, config.rng(), 128, false); });




12
✔





266



            }










267












268



            config.record_result(*mr_timer);




4
✔





269



            config.record_result(*mr_vt_timer);




4
✔





270



            config.record_result(*lucas_timer);




4
✔





271



            config.record_result(*lucas_vt_timer);




4
✔





272



            config.record_result(*bpsw_timer);




4
✔





273



            config.record_result(*bpsw_vt_timer);




4
✔





274



            config.record_result(*strong_timer);




4
✔





275



            config.record_result(*strong_vt_timer);




8
✔





276



         }




32
✔





277



      }




1
✔





278



};










279












280



BOTAN_REGISTER_PERF_TEST("primality_test", PerfTest_IsPrime);




1
✔





281












282



class PerfTest_RandomPrime final : public PerfTest {




1
✔





283



   public:










284



      void go(const PerfConfig& config) override {




1
✔





285



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




1
✔





286



         const auto runtime = config.runtime();




1
✔





287












288



         auto& rng = config.rng();




1
✔





289












290



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




7
✔





291



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




12
✔





292



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




12
✔





293












294



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




12
✔





295



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




12
✔





296












297



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




12
✔





298



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




×







299



               }










300












301



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










302



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




198
✔





303



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




384
✔





304



               }










305



            }




6
✔





306












307



            config.record_result(*genprime_timer);




6
✔





308



            config.record_result(*is_prime_timer);




12
✔





309



         }




6
✔





310



      }




1
✔





311



};










312












313



BOTAN_REGISTER_PERF_TEST("random_prime", PerfTest_RandomPrime);




1
✔





314












315



#endif










316












317



#if defined(BOTAN_HAS_DL_GROUP)










318












319



class PerfTest_ModExp final : public PerfTest {




1
✔





320



   public:










321



      void go(const PerfConfig& config) override {




1
✔





322



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




8
✔





323



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




14
✔





324



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




7
✔





325












326



            const size_t e_bits = group.exponent_bits();




7
✔





327



            const size_t f_bits = group_bits - 1;




7
✔





328












329



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




7
✔





330



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




7
✔





331












332



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




14
✔





333



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




14
✔





334












335



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




15
✔





336



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




16
✔





337



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




16
✔





338



            }










339












340



            config.record_result(*e_timer);




7
✔





341



            config.record_result(*f_timer);




14
✔





342



         }




21
✔





343



      }




1
✔





344



};










345












346



BOTAN_REGISTER_PERF_TEST("modexp", PerfTest_ModExp);




1
✔





347












348



#endif










349












350



}  // namespace










351












352



}  // namespace Botan_CLI
























    

  • 

    •