randombit / botan / 11342303498

coverage: 91.131% (+0.006%) from 91.125%
11342303498

push

github

web-flow 
Merge pull request #3893 from Rohde-Schwarz/feature/mlkem_ipd

PQC: ML-KEM

90490 of 99297 relevant lines covered (91.13%)

9030375.1 hits per line

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

98.3
/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



#if defined(BOTAN_HAS_BIGINT)










10



   #include <botan/bigint.h>










11



   #include <botan/internal/divide.h>










12



#endif










13












14



#if defined(BOTAN_HAS_NUMBERTHEORY)










15



   #include <botan/numthry.h>










16



   #include <botan/reducer.h>










17



   #include <botan/internal/curve_nistp.h>










18



   #include <botan/internal/primality.h>










19



#endif










20












21



#if defined(BOTAN_HAS_DL_GROUP)










22



   #include <botan/dl_group.h>










23



   #include <botan/internal/workfactor.h>










24



#endif










25












26



namespace Botan_CLI {










27












28



#if defined(BOTAN_HAS_BIGINT)










29












30



class PerfTest_MpMul final : public PerfTest {




1✔





31



   public:










32



      void go(const PerfConfig& config) override {




1✔





33



         std::chrono::milliseconds runtime_per_size = config.runtime();




1✔





34












35



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




10✔





36



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




27✔





37



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




27✔





38












39



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




9✔





40



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




9✔





41












42



            while(mul_timer->under(runtime_per_size)) {




9,468✔





43



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




9,459✔





44












45



               sqr_timer->start();




9,459✔





46



               x.square(ws);




9,459✔





47



               sqr_timer->stop();




9,459✔





48












49



               x.mask_bits(bits);




9,459✔





50












51



               mul_timer->start();




9,459✔





52



               x.mul(y, ws);




9,459✔





53



               mul_timer->stop();




9,459✔





54



            }




9,459✔





55












56



            config.record_result(*mul_timer);




9✔





57



            config.record_result(*sqr_timer);




9✔





58



         }




18✔





59



      }




1✔





60



};










61












62



BOTAN_REGISTER_PERF_TEST("mp_mul", PerfTest_MpMul);




1✔





63












64



class PerfTest_MpDiv final : public PerfTest {




1✔





65



   public:










66



      void go(const PerfConfig& config) override {




1✔





67



         std::chrono::milliseconds runtime_per_size = config.runtime();




1✔





68












69



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




10✔





70



            const size_t q_bits = n_bits / 2;




9✔





71



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




27✔





72












73



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




18✔





74



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




18✔





75












76



            Botan::BigInt y;




9✔





77



            Botan::BigInt x;




9✔





78



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




9✔





79












80



            Botan::BigInt q1, r1, q2, r2;




9✔





81












82



            while(ct_div_timer->under(runtime_per_size)) {




9✔





83



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




99✔





84



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




99✔





85












86



               div_timer->start();




99✔





87



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




99✔





88



               div_timer->stop();




99✔





89












90



               ct_div_timer->start();




99✔





91



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




99✔





92



               ct_div_timer->stop();




99✔





93












94



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




99✔





95



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




207✔





96



            }










97












98



            config.record_result(*div_timer);




9✔





99



            config.record_result(*ct_div_timer);




9✔





100



         }




54✔





101



      }




1✔





102



};










103












104



BOTAN_REGISTER_PERF_TEST("mp_div", PerfTest_MpDiv);




1✔





105












106



class PerfTest_MpDiv10 final : public PerfTest {




1✔





107



   public:










108



      void go(const PerfConfig& config) override {




1✔





109



         std::chrono::milliseconds runtime_per_size = config.runtime();




1✔





110












111



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




10✔





112



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




18✔





113












114



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




18✔





115



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




18✔





116












117



            Botan::BigInt x;




9✔





118



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




9✔





119












120



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




9✔





121



            Botan::BigInt q1, r1, q2;




9✔





122



            Botan::word r2;




9✔





123












124



            while(ct_div_timer->under(runtime_per_size)) {




9✔





125



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




720✔





126












127



               div_timer->start();




720✔





128



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




720✔





129



               div_timer->stop();




720✔





130












131



               ct_div_timer->start();




720✔





132



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




720✔





133



               ct_div_timer->stop();




720✔





134












135



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




720✔





136



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




1,449✔





137



            }










138












139



            config.record_result(*div_timer);




9✔





140



            config.record_result(*ct_div_timer);




9✔





141



         }




45✔





142



      }




1✔





143



};










144












145



BOTAN_REGISTER_PERF_TEST("mp_div10", PerfTest_MpDiv10);




1✔





146












147



#endif










148












149



#if defined(BOTAN_HAS_NUMBERTHEORY)










150












151



class PerfTest_NistpRedc final : public PerfTest {




1✔





152



   public:










153



      void go(const PerfConfig& config) override {




1✔





154



         std::chrono::milliseconds runtime_per_group = config.runtime();




1✔





155












156



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




1✔





157












158



         auto p192_timer = config.make_timer("P-192 redc");




2✔





159



         Botan::BigInt r192(config.rng(), 192 * 2 - 1);




1✔





160



         while(p192_timer->under(runtime_per_group)) {




7,452✔





161



            Botan::BigInt r = r192;




7,451✔





162



            p192_timer->run([&]() { Botan::redc_p192(r, ws); });




14,902✔





163



            r192 += 1;




7,451✔





164



         }




7,451✔





165



         config.record_result(*p192_timer);




1✔





166












167



         auto p224_timer = config.make_timer("P-224 redc");




2✔





168



         Botan::BigInt r224(config.rng(), 224 * 2 - 1);




1✔





169



         while(p224_timer->under(runtime_per_group)) {




7,083✔





170



            Botan::BigInt r = r224;




7,082✔





171



            p224_timer->run([&]() { Botan::redc_p224(r, ws); });




14,164✔





172



            r224 += 1;




7,082✔





173



         }




7,082✔





174



         config.record_result(*p224_timer);




1✔





175












176



         auto p256_timer = config.make_timer("P-256 redc");




2✔





177



         Botan::BigInt r256(config.rng(), 256 * 2 - 1);




1✔





178



         while(p256_timer->under(runtime_per_group)) {




6,891✔





179



            Botan::BigInt r = r256;




6,890✔





180



            p256_timer->run([&]() { Botan::redc_p256(r, ws); });




13,780✔





181



            r256 += 1;




6,890✔





182



         }




6,890✔





183



         config.record_result(*p256_timer);




1✔





184












185



         auto p384_timer = config.make_timer("P-384 redc");




2✔





186



         Botan::BigInt r384(config.rng(), 384 * 2 - 1);




1✔





187



         while(p384_timer->under(runtime_per_group)) {




6,116✔





188



            Botan::BigInt r = r384;




6,115✔





189



            p384_timer->run([&]() { Botan::redc_p384(r384, ws); });




12,230✔





190



            r384 += 1;




6,115✔





191



         }




6,115✔





192



         config.record_result(*p384_timer);




1✔





193












194



         auto p521_timer = config.make_timer("P-521 redc");




2✔





195



         Botan::BigInt r521(config.rng(), 521 * 2 - 1);




1✔





196



         while(p521_timer->under(runtime_per_group)) {




4,201✔





197



            Botan::BigInt r = r521;




4,200✔





198



            p521_timer->run([&]() { Botan::redc_p521(r521, ws); });




8,400✔





199



            r521 += 1;




4,200✔





200



         }




4,200✔





201



         config.record_result(*p521_timer);




1✔





202



      }




6✔





203



};










204












205



BOTAN_REGISTER_PERF_TEST("nistp_redc", PerfTest_NistpRedc);




1✔





206












207



class PerfTest_BnRedc final : public PerfTest {




1✔





208



   public:










209



      void go(const PerfConfig& config) override {




1✔





210



         const auto runtime = config.runtime();




1✔





211












212



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




5✔





213



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




4✔





214












215



            std::string bit_str = std::to_string(bitsize);




4✔





216



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




8✔





217



            auto schoolbook_timer = config.make_timer("Schoolbook-" + bit_str);




8✔





218












219



            Botan::Modular_Reducer mod_p(p);




4✔





220












221



            while(schoolbook_timer->under(runtime)) {




130✔





222



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




126✔





223












224



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




252✔





225



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




252✔





226












227



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




126✔





228



            }




378✔





229












230



            config.record_result(*barrett_timer);




4✔





231



            config.record_result(*schoolbook_timer);




4✔





232



         }




8✔





233



      }




1✔





234



};










235












236



BOTAN_REGISTER_PERF_TEST("bn_redc", PerfTest_BnRedc);




1✔





237












238



class PerfTest_InvMod final : public PerfTest {




1✔





239



   public:










240



      void go(const PerfConfig& config) override {




1✔





241



         const auto runtime = config.runtime();




1✔





242












243



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




6✔





244



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




5✔





245












246



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




10✔





247



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




10✔





248












249



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




13✔





250



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




8✔





251



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




8✔





252












253



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




16✔





254












255



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




16✔





256












257



               if(x_inv == 0) {




8✔





258



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




×







259



               } else {










260



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




8✔





261



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




8✔





262



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




8✔





263



               }




8✔





264



            }




32✔





265












266



            config.record_result(*timer);




5✔





267



            config.record_result(*gcd_timer);




5✔





268



         }




5✔





269



      }




1✔





270



};










271












272



BOTAN_REGISTER_PERF_TEST("inverse_mod", PerfTest_InvMod);




1✔





273












274



class PerfTest_IsPrime final : public PerfTest {




1✔





275



   public:










276



      void go(const PerfConfig& config) override {




1✔





277



         const auto runtime = config.runtime();




1✔





278












279



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




4✔





280



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




9✔





281



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




9✔





282



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




9✔





283












284



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




3✔





285












286



            while(lucas_timer->under(runtime)) {




6✔





287



               Botan::Modular_Reducer mod_n(n);




3✔





288












289



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




6✔





290












291



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




6✔





292












293



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




6✔





294












295



               n += 2;




3✔





296



            }




3✔





297












298



            config.record_result(*mr_timer);




3✔





299



            config.record_result(*bpsw_timer);




3✔





300



            config.record_result(*lucas_timer);




3✔





301



         }




3✔





302



      }




1✔





303



};










304












305



BOTAN_REGISTER_PERF_TEST("primality_test", PerfTest_IsPrime);




1✔





306












307



class PerfTest_RandomPrime final : public PerfTest {




1✔





308



   public:










309



      void go(const PerfConfig& config) override {




1✔





310



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




1✔





311



         const auto runtime = config.runtime();




1✔





312












313



         auto& rng = config.rng();




1✔





314












315



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




7✔





316



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




18✔





317



            auto gensafe_timer = config.make_timer("random_safe_prime " + std::to_string(bits));




18✔





318



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




18✔





319












320



            while(gensafe_timer->under(runtime)) {




12✔





321



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




12✔





322












323



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




12✔





324



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




×







325



               }










326












327



               const Botan::BigInt sg = gensafe_timer->run([&] { return Botan::random_safe_prime(rng, bits); });




12✔





328












329



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




12✔





330



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




×







331



               }










332












333



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




18✔





334



                  config.error_output() << "Generated prime " << sg / 2 << " which failed a primality test";




×







335



               }










336












337



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










338



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




198✔





339



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




576✔





340



               }










341



            }




12✔





342












343



            config.record_result(*genprime_timer);




6✔





344



            config.record_result(*gensafe_timer);




6✔





345



            config.record_result(*is_prime_timer);




6✔





346



         }




6✔





347



      }




1✔





348



};










349












350



BOTAN_REGISTER_PERF_TEST("random_prime", PerfTest_RandomPrime);




1✔





351












352



#endif










353












354



#if defined(BOTAN_HAS_DL_GROUP)










355












356



class PerfTest_ModExp final : public PerfTest {




1✔





357



   public:










358



      void go(const PerfConfig& config) override {




1✔





359



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




6✔





360



            const std::string group_bits_str = std::to_string(group_bits);




5✔





361



            const Botan::DL_Group group("modp/srp/" + group_bits_str);




5✔





362












363



            const size_t e_bits = Botan::dl_exponent_size(group_bits);




5✔





364



            const size_t f_bits = group_bits - 1;




5✔





365












366



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




5✔





367



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




5✔





368












369



            auto e_timer = config.make_timer(group_bits_str + " short exponent");




10✔





370



            auto f_timer = config.make_timer(group_bits_str + "  full exponent");




10✔





371












372



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




11✔





373



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




12✔





374



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




12✔





375



            }










376












377



            config.record_result(*e_timer);




5✔





378



            config.record_result(*f_timer);




5✔





379



         }




20✔





380



      }




6✔





381



};










382












383



BOTAN_REGISTER_PERF_TEST("modexp", PerfTest_ModExp);




1✔





384












385



#endif










386












387



}  // namespace Botan_CLI
























    

  • 

    •