randombit / botan / 17294509643

coverage: 90.665%. Remained the same
17294509643

Pull #5068

github

web-flow 
Merge 81f17011b into 1b82e522d
Pull Request #5068: Add explicit algorithm for variable-time division of 2^k / x

100251 of 110573 relevant lines covered (90.66%)

12175614.13 hits per line

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

97.75
/src/lib/math/bigint/divide.cpp
1 
/*
2 
* Division Algorithms
3 
* (C) 1999-2007,2012,2018,2021 Jack Lloyd
4 
*
5 
* Botan is released under the Simplified BSD License (see license.txt)
6 
*/
7 









8



#include <botan/internal/divide.h>










9












10



#include <botan/internal/bit_ops.h>










11



#include <botan/internal/ct_utils.h>










12



#include <botan/internal/mp_core.h>










13












14



namespace Botan {










15












16



namespace {










17












18



/*










19



* Handle signed operands, if necessary










20



*/










21



void sign_fixup(const BigInt& x, const BigInt& y, BigInt& q, BigInt& r) {




296,370✔





22



   q.cond_flip_sign(x.sign() != y.sign());




296,370✔





23












24



   if(x.is_negative() && r.is_nonzero()) {




297,646✔





25



      q -= 1;




1,272✔





26



      r = y.abs() - r;




1,272✔





27



   }










28



}




296,370✔





29












30



inline bool division_check_vartime(word q, word y2, word y1, word x3, word x2, word x1) {




4,553,721✔





31



   /*










32



   Compute (y3,y2,y1) = (y2,y1) * q










33



   and return true if (y3,y2,y1) > (x3,x2,x1)










34



   */










35












36



   word y3 = 0;




4,553,721✔





37



   y1 = word_madd2(q, y1, &y3);




4,553,721✔





38



   y2 = word_madd2(q, y2, &y3);




4,553,721✔





39












40



   if(x3 != y3) {




4,553,721✔





41



      return (y3 > x3);




1,576,979✔





42



   }










43



   if(x2 != y2) {




2,976,742✔





44



      return (y2 > x2);




2,856,370✔





45



   }










46



   return (y1 > x1);




120,372✔





47



}










48












49



}  // namespace










50












51



void ct_divide(const BigInt& x, const BigInt& y, BigInt& q_out, BigInt& r_out) {




6,649✔





52



   if(y.is_zero()) {




11,279✔





53



      throw Invalid_Argument("ct_divide: cannot divide by zero");




×







54



   }










55












56



   const size_t x_words = x.sig_words();




6,649✔





57



   const size_t y_words = y.sig_words();




6,649✔





58












59



   const size_t x_bits = x.bits();




6,649✔





60












61



   BigInt q = BigInt::with_capacity(x_words);




6,649✔





62



   BigInt r = BigInt::with_capacity(y_words);




6,649✔





63



   BigInt t = BigInt::with_capacity(y_words);  // a temporary




6,649✔





64












65



   for(size_t i = 0; i != x_bits; ++i) {




6,061,420✔





66



      const size_t b = x_bits - 1 - i;




6,054,771✔





67



      const bool x_b = x.get_bit(b);




6,054,771✔





68












69



      r <<= 1;




6,054,771✔





70



      r.conditionally_set_bit(0, x_b);




6,054,771✔





71












72



      const bool r_gte_y = bigint_sub3(t.mutable_data(), r._data(), r.size(), y._data(), y_words) == 0;




6,054,771✔





73












74



      q.conditionally_set_bit(b, r_gte_y);




6,054,771✔





75



      r.ct_cond_swap(r_gte_y, t);




6,054,771✔





76



   }










77












78



   sign_fixup(x, y, q, r);




6,649✔





79



   r_out = r;




6,649✔





80



   q_out = q;




6,649✔





81



}




6,649✔





82












83



BigInt ct_divide_pow2k(size_t k, const BigInt& y) {




117,278✔





84



   BOTAN_ARG_CHECK(!y.is_zero(), "Cannot divide by zero");




117,656✔





85



   BOTAN_ARG_CHECK(!y.is_negative(), "Negative divisor not supported");




117,278✔





86



   BOTAN_ARG_CHECK(k > 1, "Invalid k");




117,278✔





87












88



   const size_t x_bits = k + 1;




117,278✔





89



   const size_t y_bits = y.bits();




117,278✔





90












91



   if(x_bits < y_bits) {




117,278✔





92



      return BigInt::zero();




253✔





93



   }










94












95



   BOTAN_ASSERT_NOMSG(y_bits >= 1);




117,025✔





96



   const size_t x_words = (x_bits + WordInfo<word>::bits - 1) / WordInfo<word>::bits;




117,025✔





97



   const size_t y_words = y.sig_words();




117,025✔





98












99



   BigInt q = BigInt::with_capacity(x_words);




117,025✔





100



   BigInt r = BigInt::with_capacity(y_words + 1);




117,025✔





101



   BigInt t = BigInt::with_capacity(y_words + 1);  // a temporary




117,025✔





102












103



   r.set_bit(y_bits - 1);




117,025✔





104



   for(size_t i = y_bits - 1; i != x_bits; ++i) {




36,951,406✔





105



      const size_t b = x_bits - 1 - i;




36,834,381✔





106












107



      if(i >= y_bits) {




36,834,381✔





108



         bigint_shl1(r.mutable_data(), r.size(), r.size(), 1);




36,717,356✔





109



      }










110












111



      const bool r_gte_y = bigint_sub3(t.mutable_data(), r._data(), r.size(), y._data(), y_words) == 0;




36,834,381✔





112












113



      q.conditionally_set_bit(b, r_gte_y);




36,834,381✔





114












115



      bigint_cnd_swap(static_cast<word>(r_gte_y), r.mutable_data(), t.mutable_data(), y_words + 1);




36,834,381✔





116



   }










117












118



   // No need for sign fixup










119












120



   return q;




117,025✔





121



}




117,025✔





122












123



void ct_divide_word(const BigInt& x, word y, BigInt& q_out, word& r_out) {




12,457✔





124



   if(y == 0) {




12,457✔





125



      throw Invalid_Argument("ct_divide_word: cannot divide by zero");




×







126



   }










127












128



   const size_t x_words = x.sig_words();




12,457✔





129



   const size_t x_bits = x.bits();




12,457✔





130












131



   BigInt q = BigInt::with_capacity(x_words);




12,457✔





132



   word r = 0;










133












134



   for(size_t i = 0; i != x_bits; ++i) {




6,531,745✔





135



      const size_t b = x_bits - 1 - i;




6,519,288✔





136



      const bool x_b = x.get_bit(b);




6,519,288✔





137












138



      const auto r_carry = CT::Mask<word>::expand_top_bit(r);




6,519,288✔





139












140



      r <<= 1;




6,519,288✔





141



      r += static_cast<word>(x_b);




6,519,288✔





142












143



      const auto r_gte_y = CT::Mask<word>::is_gte(r, y) | r_carry;




6,519,288✔





144



      q.conditionally_set_bit(b, r_gte_y.as_bool());




6,519,288✔





145



      r = r_gte_y.select(r - y, r);




6,519,288✔





146



   }










147












148



   if(x.is_negative()) {




12,457✔





149



      q.flip_sign();




23✔





150



      if(r != 0) {




23✔





151



         --q;




19✔





152



         r = y - r;




19✔





153



      }










154



   }










155












156



   r_out = r;




12,457✔





157



   q_out = q;




12,457✔





158



}




12,457✔





159












160



BigInt ct_divide_word(const BigInt& x, word y) {




4,338✔





161



   BigInt q;




4,338✔





162



   word r = 0;




4,338✔





163



   ct_divide_word(x, y, q, r);




4,338✔





164



   BOTAN_UNUSED(r);




4,338✔





165



   return q;




4,338✔





166



}




×







167












168



word ct_mod_word(const BigInt& x, word y) {




4,338✔





169



   BOTAN_ARG_CHECK(x.is_positive(), "The argument x must be positive");




4,338✔





170



   BOTAN_ARG_CHECK(y != 0, "Cannot divide by zero");




4,338✔





171












172



   const size_t x_bits = x.bits();




4,338✔





173












174



   word r = 0;




4,338✔





175












176



   for(size_t i = 0; i != x_bits; ++i) {




3,012,153✔





177



      const size_t b = x_bits - 1 - i;




3,007,815✔





178



      const bool x_b = x.get_bit(b);




3,007,815✔





179












180



      const auto r_carry = CT::Mask<word>::expand_top_bit(r);




3,007,815✔





181












182



      r <<= 1;




3,007,815✔





183



      r += static_cast<word>(x_b);




3,007,815✔





184












185



      const auto r_gte_y = CT::Mask<word>::is_gte(r, y) | r_carry;




3,007,815✔





186



      r = r_gte_y.select(r - y, r);




3,007,815✔





187



   }










188












189



   return r;




4,338✔





190



}










191












192



BigInt ct_modulo(const BigInt& x, const BigInt& y) {




3,577✔





193



   if(y.is_negative() || y.is_zero()) {




7,154✔





194



      throw Invalid_Argument("ct_modulo requires y > 0");




×







195



   }










196












197



   const size_t y_words = y.sig_words();




3,577✔





198












199



   const size_t x_bits = x.bits();




3,577✔





200












201



   BigInt r = BigInt::with_capacity(y_words);




3,577✔





202



   BigInt t = BigInt::with_capacity(y_words);




3,577✔





203












204



   for(size_t i = 0; i != x_bits; ++i) {




5,379,841✔





205



      const size_t b = x_bits - 1 - i;




5,376,264✔





206



      const bool x_b = x.get_bit(b);




5,376,264✔





207












208



      r <<= 1;




5,376,264✔





209



      r.conditionally_set_bit(0, x_b);




5,376,264✔





210












211



      const bool r_gte_y = bigint_sub3(t.mutable_data(), r._data(), r.size(), y._data(), y_words) == 0;




5,376,264✔





212












213



      r.ct_cond_swap(r_gte_y, t);




5,376,264✔





214



   }










215












216



   if(x.is_negative()) {




3,577✔





217



      if(r.is_nonzero()) {




94✔





218



         r = y - r;




45✔





219



      }










220



   }










221












222



   return r;




3,577✔





223



}




3,577✔





224












225



BigInt vartime_divide_pow2k(size_t k, const BigInt& y_arg) {




153,109✔





226



   constexpr size_t WB = WordInfo<word>::bits;




153,109✔





227












228



   BOTAN_ARG_CHECK(!y_arg.is_zero(), "Cannot divide by zero");




153,109✔





229



   BOTAN_ARG_CHECK(!y_arg.is_negative(), "Negative divisor not supported");




153,109✔





230



   BOTAN_ARG_CHECK(k > 1, "Invalid k");




153,109✔





231












232



   BigInt y = y_arg;




153,109✔





233












234



   const size_t y_words = y.sig_words();




153,109✔





235












236



   BOTAN_ASSERT_NOMSG(y_words > 0);




153,109✔





237












238



   // Calculate shifts needed to normalize y with high bit set










239



   const size_t shifts = y.top_bits_free();




153,109✔





240












241



   if(shifts > 0) {




153,109✔





242



      y <<= shifts;




131,836✔





243



   }










244












245



   BigInt r;




153,109✔





246



   r.set_bit(k + shifts);  // (2^k) << shifts




153,109✔





247












248



   // we know y has not changed size, since we only shifted up to set high bit










249



   const size_t t = y_words - 1;




153,109✔





250



   const size_t n = std::max(y_words, r.sig_words()) - 1;




306,218✔





251












252



   BOTAN_ASSERT_NOMSG(n >= t);




153,109✔





253












254



   BigInt q = BigInt::zero();




153,109✔





255



   q.grow_to(n - t + 1);




153,109✔





256












257



   word* q_words = q.mutable_data();




153,109✔





258












259



   BigInt shifted_y = y << (WB * (n - t));




153,109✔





260












261



   // Set q_{n-t} to number of times r > shifted_y










262



   secure_vector<word> ws;




153,109✔





263



   q_words[n - t] = r.reduce_below(shifted_y, ws);




153,109✔





264












265



   const word y_t0 = y.word_at(t);




153,109✔





266



   const word y_t1 = y.word_at(t - 1);




153,109✔





267



   BOTAN_DEBUG_ASSERT((y_t0 >> (WB - 1)) == 1);




153,109✔





268












269



   divide_precomp div_y_t0(y_t0);




153,109✔





270












271



   for(size_t i = n; i != t; --i) {




1,338,824✔





272



      const word x_i0 = r.word_at(i);




1,185,715✔





273



      const word x_i1 = r.word_at(i - 1);




1,185,715✔





274



      const word x_i2 = r.word_at(i - 2);




1,185,715✔





275












276



      word qit = (x_i0 == y_t0) ? WordInfo<word>::max : div_y_t0.vartime_div_2to1(x_i0, x_i1);




2,371,188✔





277












278



      // Per HAC 14.23, this operation is required at most twice










279



      for(size_t j = 0; j != 2; ++j) {




1,476,689✔





280



         if(division_check_vartime(qit, y_t0, y_t1, x_i0, x_i1, x_i2)) {




2,934,728✔





281



            BOTAN_ASSERT_NOMSG(qit > 0);




290,974✔





282



            qit--;




290,974✔





283



         } else {










284



            break;










285



         }










286



      }










287












288



      shifted_y >>= WB;




1,185,715✔





289



      // Now shifted_y == y << (WB * (i-t-1))










290












291



      /*










292



      * Special case qit == 0 and qit == 1 which occurs relatively often here due to a










293



      * combination of the fixed 2^k and in many cases the typical structure of










294



      * public moduli (as this function is called by Barrett_Reduction::for_public_modulus).










295



      *










296



      * Over the test suite, about 5% of loop iterations have qit == 1 and 10% have qit == 0










297



      */










298












299



      if(qit != 0) {




1,185,715✔





300



         if(qit == 1) {




1,076,937✔





301



            r -= shifted_y;




21,848✔





302



         } else {










303



            r -= qit * shifted_y;




1,055,089✔





304



         }










305












306



         if(r.is_negative()) {




1,076,937✔





307



            BOTAN_ASSERT_NOMSG(qit > 0);




2,407✔





308



            qit--;




2,407✔





309



            r += shifted_y;




2,407✔





310



            BOTAN_ASSERT_NOMSG(r.is_positive());




2,407✔





311



         }










312



      }










313












314



      q_words[i - t - 1] = qit;




1,185,715✔





315



   }










316












317



   return q;




306,218✔





318



}




153,109✔





319












320



/*










321



* Solve x = q * y + r










322



*










323



* See Handbook of Applied Cryptography algorithm 14.20










324



*/










325



void vartime_divide(const BigInt& x, const BigInt& y_arg, BigInt& q_out, BigInt& r_out) {




289,721✔





326



   constexpr size_t WB = WordInfo<word>::bits;




289,721✔





327












328



   if(y_arg.is_zero()) {




289,798✔





329



      throw Invalid_Argument("vartime_divide: cannot divide by zero");




×







330



   }










331












332



   const size_t y_words = y_arg.sig_words();




289,721✔





333












334



   BOTAN_ASSERT_NOMSG(y_words > 0);




289,721✔





335












336



   BigInt y = y_arg;




289,721✔





337












338



   BigInt r = x;




289,721✔





339



   BigInt q = BigInt::zero();




289,721✔





340



   secure_vector<word> ws;




289,721✔





341












342



   r.set_sign(BigInt::Positive);




289,721✔





343



   y.set_sign(BigInt::Positive);




289,721✔





344












345



   // Calculate shifts needed to normalize y with high bit set










346



   const size_t shifts = y.top_bits_free();




289,721✔





347












348



   if(shifts > 0) {




289,721✔





349



      y <<= shifts;




277,201✔





350



      r <<= shifts;




277,201✔





351



   }










352












353



   // we know y has not changed size, since we only shifted up to set high bit










354



   const size_t t = y_words - 1;




289,721✔





355



   const size_t n = std::max(y_words, r.sig_words()) - 1;  // r may have changed size however




568,030✔





356












357



   BOTAN_ASSERT_NOMSG(n >= t);




289,721✔





358












359



   q.grow_to(n - t + 1);




289,721✔





360












361



   word* q_words = q.mutable_data();




289,721✔





362












363



   BigInt shifted_y = y << (WB * (n - t));




289,721✔





364












365



   // Set q_{n-t} to number of times r > shifted_y










366



   q_words[n - t] = r.reduce_below(shifted_y, ws);




289,721✔





367












368



   const word y_t0 = y.word_at(t);




289,721✔





369



   const word y_t1 = y.word_at(t - 1);




289,721✔





370



   BOTAN_DEBUG_ASSERT((y_t0 >> (WB - 1)) == 1);




289,721✔





371












372



   divide_precomp div_y_t0(y_t0);




289,721✔





373












374



   for(size_t i = n; i != t; --i) {




2,851,238✔





375



      const word x_i0 = r.word_at(i);




2,561,517✔





376



      const word x_i1 = r.word_at(i - 1);




2,561,517✔





377



      const word x_i2 = r.word_at(i - 2);




2,561,517✔





378












379



      word qit = (x_i0 == y_t0) ? WordInfo<word>::max : div_y_t0.vartime_div_2to1(x_i0, x_i1);




5,122,868✔





380












381



      // Per HAC 14.23, this operation is required at most twice










382



      for(size_t j = 0; j != 2; ++j) {




3,096,586✔





383



         if(division_check_vartime(qit, y_t0, y_t1, x_i0, x_i1, x_i2)) {




6,172,714✔





384



            BOTAN_ASSERT_NOMSG(qit > 0);




535,069✔





385



            qit--;




535,069✔





386



         } else {










387



            break;










388



         }










389



      }










390












391



      shifted_y >>= WB;




2,561,517✔





392



      // Now shifted_y == y << (WB * (i-t-1))










393












394



      if(qit != 0) {




2,561,517✔





395



         r -= qit * shifted_y;




2,560,946✔





396



         if(r.is_negative()) {




2,560,946✔





397



            BOTAN_ASSERT_NOMSG(qit > 0);




531✔





398



            qit--;




531✔





399



            r += shifted_y;




531✔





400



            BOTAN_ASSERT_NOMSG(r.is_positive());




531✔





401



         }










402



      }










403












404



      q_words[i - t - 1] = qit;




2,561,517✔





405



   }










406












407



   if(shifts > 0) {




289,721✔





408



      r >>= shifts;




277,201✔





409



   }










410












411



   sign_fixup(x, y_arg, q, r);




289,721✔





412












413



   r_out = r;




289,721✔





414



   q_out = q;




289,721✔





415



}




579,442✔





416












417



}  // namespace Botan
























    

  • 

    •