randombit / botan / 4800894698

coverage: 92.152% (+0.006%) from 92.146%
4800894698

Pull #3522

github

Pull Request #3522: Add CT::all_zeros

77584 of 84191 relevant lines covered (92.15%)

12025531.87 hits per line

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

96.32
/src/lib/pubkey/ec_group/ec_point.cpp
1 
/*
2 
* Point arithmetic on elliptic curves over GF(p)
3 
*
4 
* (C) 2007 Martin Doering, Christoph Ludwig, Falko Strenzke
5 
*     2008-2011,2012,2014,2015,2018 Jack Lloyd
6 
*
7 
* Botan is released under the Simplified BSD License (see license.txt)
8 
*/
9 









10



#include <botan/ec_point.h>










11












12



#include <botan/numthry.h>










13



#include <botan/rng.h>










14



#include <botan/internal/ct_utils.h>










15












16



namespace Botan {










17












18



EC_Point::EC_Point(const CurveGFp& curve) :




24,398✔





19



   m_curve(curve),




24,398✔





20



   m_coord_x(0),




24,398✔





21



   m_coord_y(curve.get_1_rep()),




24,398✔





22



   m_coord_z(0)




24,398✔





23



   {










24



   // Assumes Montgomery rep of zero is zero










25



   }




24,398✔





26












27



EC_Point::EC_Point(const CurveGFp& curve, const BigInt& x, const BigInt& y) :




20,420✔





28



   m_curve(curve),




20,420✔





29



   m_coord_x(x),




20,420✔





30



   m_coord_y(y),




20,420✔





31



   m_coord_z(m_curve.get_1_rep())




20,420✔





32



   {










33



   if(x < 0 || x >= curve.get_p())




40,840✔





34



      throw Invalid_Argument("Invalid EC_Point affine x");




559✔





35



   if(y < 0 || y >= curve.get_p())




39,582✔





36



      throw Invalid_Argument("Invalid EC_Point affine y");




208✔





37












38



   secure_vector<word> monty_ws(m_curve.get_ws_size());




19,653✔





39



   m_curve.to_rep(m_coord_x, monty_ws);




19,653✔





40



   m_curve.to_rep(m_coord_y, monty_ws);




39,306✔





41



   }




22,715✔





42












43



void EC_Point::randomize_repr(RandomNumberGenerator& rng)




758✔





44



   {










45



   secure_vector<word> ws(m_curve.get_ws_size());




758✔





46



   randomize_repr(rng, ws);




758✔





47



   }




758✔





48












49



void EC_Point::randomize_repr(RandomNumberGenerator& rng, secure_vector<word>& ws)




6,420✔





50



   {










51



   const BigInt mask = BigInt::random_integer(rng, 2, m_curve.get_p());




6,420✔





52












53



   /*










54



   * No reason to convert this to Montgomery representation first,










55



   * just pretend the random mask was chosen as Redc(mask) and the










56



   * random mask we generated above is in the Montgomery










57



   * representation.










58



   * //m_curve.to_rep(mask, ws);










59



   */










60



   const BigInt mask2 = m_curve.sqr_to_tmp(mask, ws);




6,420✔





61



   const BigInt mask3 = m_curve.mul_to_tmp(mask2, mask, ws);




6,420✔





62












63



   m_coord_x = m_curve.mul_to_tmp(m_coord_x, mask2, ws);




6,420✔





64



   m_coord_y = m_curve.mul_to_tmp(m_coord_y, mask3, ws);




6,420✔





65



   m_coord_z = m_curve.mul_to_tmp(m_coord_z, mask, ws);




12,840✔





66



   }




19,260✔





67












68



namespace {










69












70



inline void resize_ws(std::vector<BigInt>& ws_bn, size_t cap_size)




9,743,529✔





71



   {










72



   BOTAN_ASSERT(ws_bn.size() >= EC_Point::WORKSPACE_SIZE,




9,743,529✔





73



                "Expected size for EC_Point workspace");










74












75



   for(auto& ws : ws_bn)




87,691,761✔





76



      if(ws.size() < cap_size)




77,948,232✔





77



         ws.get_word_vector().resize(cap_size);




1,491,089✔





78



   }




9,743,529✔





79












80



}










81












82



void EC_Point::add_affine(const word x_words[], size_t x_size,




2,279,887✔





83



                          const word y_words[], size_t y_size,










84



                          std::vector<BigInt>& ws_bn)










85



   {










86



   if((CT::all_zeros(x_words, x_size) & CT::all_zeros(y_words, y_size)).is_set())




17,055,403✔





87



      {










88



      return;










89



      }










90












91



   if(is_zero())




4,448,808✔





92



      {










93



      m_coord_x.set_words(x_words, x_size);




15,589✔





94



      m_coord_y.set_words(y_words, y_size);




15,589✔





95



      m_coord_z = m_curve.get_1_rep();




15,589✔





96



      return;




15,589✔





97



      }










98












99



   resize_ws(ws_bn, m_curve.get_ws_size());




2,208,839✔





100












101



   secure_vector<word>& ws = ws_bn[0].get_word_vector();




2,208,839✔





102



   secure_vector<word>& sub_ws = ws_bn[1].get_word_vector();




2,208,839✔





103












104



   BigInt& T0 = ws_bn[2];




2,208,839✔





105



   BigInt& T1 = ws_bn[3];




2,208,839✔





106



   BigInt& T2 = ws_bn[4];




2,208,839✔





107



   BigInt& T3 = ws_bn[5];




2,208,839✔





108



   BigInt& T4 = ws_bn[6];




2,208,839✔





109












110



   /*










111



   https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#addition-add-1998-cmo-2










112



   simplified with Z2 = 1










113



   */










114












115



   const BigInt& p = m_curve.get_p();




2,208,839✔





116












117



   m_curve.sqr(T3, m_coord_z, ws); // z1^2




2,208,839✔





118



   m_curve.mul(T4, x_words, x_size, T3, ws); // x2*z1^2




2,208,839✔





119












120



   m_curve.mul(T2, m_coord_z, T3, ws); // z1^3




2,208,839✔





121



   m_curve.mul(T0, y_words, y_size, T2, ws); // y2*z1^3




2,208,839✔





122












123



   T4.mod_sub(m_coord_x, p, sub_ws); // x2*z1^2 - x1*z2^2




2,208,839✔





124












125



   T0.mod_sub(m_coord_y, p, sub_ws);




2,208,839✔





126












127



   if(T4.is_zero())




4,417,678✔





128



      {










129



      if(T0.is_zero())




318✔





130



         {










131



         mult2(ws_bn);




15✔





132



         return;




15✔





133



         }










134












135



      // setting to zero:










136



      m_coord_x.clear();




144✔





137



      m_coord_y = m_curve.get_1_rep();




144✔





138



      m_coord_z.clear();




144✔





139



      return;




144✔





140



      }










141












142



   m_curve.sqr(T2, T4, ws);




2,208,680✔





143












144



   m_curve.mul(T3, m_coord_x, T2, ws);




2,208,680✔





145












146



   m_curve.mul(T1, T2, T4, ws);




2,208,680✔





147












148



   m_curve.sqr(m_coord_x, T0, ws);




2,208,680✔





149



   m_coord_x.mod_sub(T1, p, sub_ws);




2,208,680✔





150












151



   m_coord_x.mod_sub(T3, p, sub_ws);




2,208,680✔





152



   m_coord_x.mod_sub(T3, p, sub_ws);




2,208,680✔





153












154



   T3.mod_sub(m_coord_x, p, sub_ws);




2,208,680✔





155












156



   m_curve.mul(T2, T0, T3, ws);




2,208,680✔





157



   m_curve.mul(T0, m_coord_y, T1, ws);




2,208,680✔





158



   T2.mod_sub(T0, p, sub_ws);




2,208,680✔





159



   m_coord_y.swap(T2);




2,208,680✔





160












161



   m_curve.mul(T0, m_coord_z, T4, ws);




2,208,680✔





162



   m_coord_z.swap(T0);




2,208,680✔





163



   }










164












165



void EC_Point::add(const word x_words[], size_t x_size,




1,472,405✔





166



                   const word y_words[], size_t y_size,










167



                   const word z_words[], size_t z_size,










168



                   std::vector<BigInt>& ws_bn)










169



   {










170



   if((CT::all_zeros(x_words, x_size) & CT::all_zeros(z_words, z_size)).is_set())




10,974,875✔





171



      return;










172












173



   if(is_zero())




2,867,312✔





174



      {










175



      m_coord_x.set_words(x_words, x_size);




5,832✔





176



      m_coord_y.set_words(y_words, y_size);




5,832✔





177



      m_coord_z.set_words(z_words, z_size);




5,832✔





178



      return;




5,832✔





179



      }










180












181



   resize_ws(ws_bn, m_curve.get_ws_size());




1,442,843✔





182












183



   secure_vector<word>& ws = ws_bn[0].get_word_vector();




1,442,843✔





184



   secure_vector<word>& sub_ws = ws_bn[1].get_word_vector();




1,442,843✔





185












186



   BigInt& T0 = ws_bn[2];




1,442,843✔





187



   BigInt& T1 = ws_bn[3];




1,442,843✔





188



   BigInt& T2 = ws_bn[4];




1,442,843✔





189



   BigInt& T3 = ws_bn[5];




1,442,843✔





190



   BigInt& T4 = ws_bn[6];




1,442,843✔





191



   BigInt& T5 = ws_bn[7];




1,442,843✔





192












193



   /*










194



   https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#addition-add-1998-cmo-2










195



   */










196












197



   const BigInt& p = m_curve.get_p();




1,442,843✔





198












199



   m_curve.sqr(T0, z_words, z_size, ws); // z2^2




1,442,843✔





200



   m_curve.mul(T1, m_coord_x, T0, ws); // x1*z2^2




1,442,843✔





201



   m_curve.mul(T3, z_words, z_size, T0, ws); // z2^3




1,442,843✔





202



   m_curve.mul(T2, m_coord_y, T3, ws); // y1*z2^3




1,442,843✔





203












204



   m_curve.sqr(T3, m_coord_z, ws); // z1^2




1,442,843✔





205



   m_curve.mul(T4, x_words, x_size, T3, ws); // x2*z1^2




1,442,843✔





206












207



   m_curve.mul(T5, m_coord_z, T3, ws); // z1^3




1,442,843✔





208



   m_curve.mul(T0, y_words, y_size, T5, ws); // y2*z1^3




1,442,843✔





209












210



   T4.mod_sub(T1, p, sub_ws); // x2*z1^2 - x1*z2^2




1,442,843✔





211












212



   T0.mod_sub(T2, p, sub_ws);




1,442,843✔





213












214



   if(T4.is_zero())




2,885,686✔





215



      {










216



      if(T0.is_zero())




992✔





217



         {










218



         mult2(ws_bn);




150✔





219



         return;




150✔





220



         }










221












222



      // setting to zero:










223



      m_coord_x.clear();




346✔





224



      m_coord_y = m_curve.get_1_rep();




346✔





225



      m_coord_z.clear();




346✔





226



      return;




346✔





227



      }










228












229



   m_curve.sqr(T5, T4, ws);




1,442,347✔





230












231



   m_curve.mul(T3, T1, T5, ws);




1,442,347✔





232












233



   m_curve.mul(T1, T5, T4, ws);




1,442,347✔





234












235



   m_curve.sqr(m_coord_x, T0, ws);




1,442,347✔





236



   m_coord_x.mod_sub(T1, p, sub_ws);




1,442,347✔





237



   m_coord_x.mod_sub(T3, p, sub_ws);




1,442,347✔





238



   m_coord_x.mod_sub(T3, p, sub_ws);




1,442,347✔





239












240



   T3.mod_sub(m_coord_x, p, sub_ws);




1,442,347✔





241












242



   m_curve.mul(m_coord_y, T0, T3, ws);




1,442,347✔





243



   m_curve.mul(T3, T2, T1, ws);




1,442,347✔





244












245



   m_coord_y.mod_sub(T3, p, sub_ws);




1,442,347✔





246












247



   m_curve.mul(T3, z_words, z_size, m_coord_z, ws);




1,442,347✔





248



   m_curve.mul(m_coord_z, T3, T4, ws);




1,442,347✔





249



   }










250












251



void EC_Point::mult2i(size_t iterations, std::vector<BigInt>& ws_bn)




2,273,396✔





252



   {










253



   if(iterations == 0)




2,273,396✔





254



      return;










255












256



   if(m_coord_y.is_zero())




4,543,966✔





257



      {










258



      *this = EC_Point(m_curve); // setting myself to zero




×







259



      return;




×







260



      }










261












262



   /*










263



   TODO we can save 2 squarings per iteration by computing










264



   a*Z^4 using values cached from previous iteration










265



   */










266



   for(size_t i = 0; i != iterations; ++i)




7,442,488✔





267



      mult2(ws_bn);




5,169,092✔





268



   }










269












270



// *this *= 2










271



void EC_Point::mult2(std::vector<BigInt>& ws_bn)




6,098,028✔





272



   {










273



   if(is_zero())




12,162,882✔





274



      return;










275












276



   if(m_coord_y.is_zero())




9,913,159✔





277



      {










278



      *this = EC_Point(m_curve); // setting myself to zero




×







279



      return;




×







280



      }










281












282



   resize_ws(ws_bn, m_curve.get_ws_size());




6,091,847✔





283












284



   secure_vector<word>& ws = ws_bn[0].get_word_vector();




6,091,847✔





285



   secure_vector<word>& sub_ws = ws_bn[1].get_word_vector();




6,091,847✔





286












287



   BigInt& T0 = ws_bn[2];




6,091,847✔





288



   BigInt& T1 = ws_bn[3];




6,091,847✔





289



   BigInt& T2 = ws_bn[4];




6,091,847✔





290



   BigInt& T3 = ws_bn[5];




6,091,847✔





291



   BigInt& T4 = ws_bn[6];




6,091,847✔





292












293



   /*










294



   https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#doubling-dbl-1986-cc










295



   */










296



   const BigInt& p = m_curve.get_p();




6,091,847✔





297












298



   m_curve.sqr(T0, m_coord_y, ws);




6,091,847✔





299












300



   m_curve.mul(T1, m_coord_x, T0, ws);




6,091,847✔





301



   T1.mod_mul(4, p, sub_ws);




6,091,847✔





302












303



   if(m_curve.a_is_zero())




6,091,847✔





304



      {










305



      // if a == 0 then 3*x^2 + a*z^4 is just 3*x^2










306



      m_curve.sqr(T4, m_coord_x, ws); // x^2




268,506✔





307



      T4.mod_mul(3, p, sub_ws); // 3*x^2




268,506✔





308



      }










309



   else if(m_curve.a_is_minus_3())




5,823,341✔





310



      {










311



      /*










312



      if a == -3 then










313



        3*x^2 + a*z^4 == 3*x^2 - 3*z^4 == 3*(x^2-z^4) == 3*(x-z^2)*(x+z^2)










314



      */










315



      m_curve.sqr(T3, m_coord_z, ws); // z^2




4,611,390✔





316












317



      // (x-z^2)










318



      T2 = m_coord_x;




4,611,390✔





319



      T2.mod_sub(T3, p, sub_ws);




4,611,390✔





320












321



      // (x+z^2)










322



      T3.mod_add(m_coord_x, p, sub_ws);




4,611,390✔





323












324



      m_curve.mul(T4, T2, T3, ws); // (x-z^2)*(x+z^2)




4,611,390✔





325












326



      T4.mod_mul(3, p, sub_ws); // 3*(x-z^2)*(x+z^2)




4,611,390✔





327



      }










328



   else










329



      {










330



      m_curve.sqr(T3, m_coord_z, ws); // z^2




1,211,951✔





331



      m_curve.sqr(T4, T3, ws); // z^4




1,211,951✔





332



      m_curve.mul(T3, m_curve.get_a_rep(), T4, ws); // a*z^4




1,211,951✔





333












334



      m_curve.sqr(T4, m_coord_x, ws); // x^2




1,211,951✔





335



      T4.mod_mul(3, p, sub_ws);




1,211,951✔





336



      T4.mod_add(T3, p, sub_ws); // 3*x^2 + a*z^4




1,211,951✔





337



      }










338












339



   m_curve.sqr(T2, T4, ws);




6,091,847✔





340



   T2.mod_sub(T1, p, sub_ws);




6,091,847✔





341



   T2.mod_sub(T1, p, sub_ws);




6,091,847✔





342












343



   m_curve.sqr(T3, T0, ws);




6,091,847✔





344



   T3.mod_mul(8, p, sub_ws);




6,091,847✔





345












346



   T1.mod_sub(T2, p, sub_ws);




6,091,847✔





347












348



   m_curve.mul(T0, T4, T1, ws);




6,091,847✔





349



   T0.mod_sub(T3, p, sub_ws);




6,091,847✔





350












351



   m_coord_x.swap(T2);




6,091,847✔





352












353



   m_curve.mul(T2, m_coord_y, m_coord_z, ws);




6,091,847✔





354



   T2.mod_mul(2, p, sub_ws);




6,091,847✔





355












356



   m_coord_y.swap(T0);




6,091,847✔





357



   m_coord_z.swap(T2);




6,098,028✔





358



   }










359












360



// arithmetic operators










361



EC_Point& EC_Point::operator+=(const EC_Point& rhs)




2,376✔





362



   {










363



   std::vector<BigInt> ws(EC_Point::WORKSPACE_SIZE);




2,376✔





364



   add(rhs, ws);




2,376✔





365



   return *this;




2,375✔





366



   }




2,376✔





367












368



EC_Point& EC_Point::operator-=(const EC_Point& rhs)




82✔





369



   {










370



   EC_Point minus_rhs = EC_Point(rhs).negate();




82✔





371












372



   if(is_zero())




82✔





373



      *this = minus_rhs;




×







374



   else










375



      *this += minus_rhs;




82✔





376












377



   return *this;




82✔





378



   }




82✔





379












380



EC_Point& EC_Point::operator*=(const BigInt& scalar)




67✔





381



   {










382



   *this = scalar * *this;




67✔





383



   return *this;




67✔





384



   }










385












386



EC_Point operator*(const BigInt& scalar, const EC_Point& point)




2,958✔





387



   {










388



   BOTAN_DEBUG_ASSERT(point.on_the_curve());




2,958✔





389












390



   const size_t scalar_bits = scalar.bits();




2,958✔





391












392



   std::vector<BigInt> ws(EC_Point::WORKSPACE_SIZE);




2,958✔





393












394



   EC_Point R[2] = { point.zero(), point };




8,874✔





395












396



   for(size_t i = scalar_bits; i > 0; i--)




502,712✔





397



      {










398



      const size_t b = scalar.get_bit(i - 1);




499,754✔





399



      R[b ^ 1].add(R[b], ws);




499,754✔





400



      R[b].mult2(ws);




499,754✔





401



      }










402












403



   if(scalar.is_negative())




2,958✔





404



      R[0].negate();




×







405












406



   BOTAN_DEBUG_ASSERT(R[0].on_the_curve());




2,958✔





407












408



   return R[0];




5,916✔





409



   }




11,832✔





410












411



//static










412



void EC_Point::force_all_affine(std::vector<EC_Point>& points,




10,766✔





413



                                secure_vector<word>& ws)










414



   {










415



   if(points.size() <= 1)




10,766✔





416



      {










417



      for(auto& point : points)




×







418



         point.force_affine();




×







419



      return;




×







420



      }










421












422



   for(auto& point : points)




1,066,393✔





423



      {










424



      if(point.is_zero())




1,962,446✔





425



         throw Invalid_State("Cannot convert zero ECC point to affine");




×







426



      }










427












428



   /*










429



   For >= 2 points use Montgomery's trick










430












431



   See Algorithm 2.26 in "Guide to Elliptic Curve Cryptography"










432



   (Hankerson, Menezes, Vanstone)










433












434



   TODO is it really necessary to save all k points in c?










435



   */










436












437



   const CurveGFp& curve = points[0].m_curve;




10,766✔





438



   const BigInt& rep_1 = curve.get_1_rep();




10,766✔





439












440



   if(ws.size() < curve.get_ws_size())




10,766✔





441



      ws.resize(curve.get_ws_size());




×







442












443



   std::vector<BigInt> c(points.size());




10,766✔





444



   c[0] = points[0].m_coord_z;




10,766✔





445












446



   for(size_t i = 1; i != points.size(); ++i)




1,055,627✔





447



      {










448



      curve.mul(c[i], c[i-1], points[i].m_coord_z, ws);




2,089,722✔





449



      }










450












451



   BigInt s_inv = curve.invert_element(c[c.size()-1], ws);




10,766✔





452












453



   BigInt z_inv, z2_inv, z3_inv;




10,766✔





454












455



   for(size_t i = points.size() - 1; i != 0; i--)




1,055,627✔





456



      {










457



      EC_Point& point = points[i];




1,044,861✔





458












459



      curve.mul(z_inv, s_inv, c[i-1], ws);




1,044,861✔





460












461



      s_inv = curve.mul_to_tmp(s_inv, point.m_coord_z, ws);




1,044,861✔





462












463



      curve.sqr(z2_inv, z_inv, ws);




1,044,861✔





464



      curve.mul(z3_inv, z2_inv, z_inv, ws);




1,044,861✔





465



      point.m_coord_x = curve.mul_to_tmp(point.m_coord_x, z2_inv, ws);




2,089,722✔





466



      point.m_coord_y = curve.mul_to_tmp(point.m_coord_y, z3_inv, ws);




2,089,722✔





467



      point.m_coord_z = rep_1;




1,044,861✔





468



      }










469












470



   curve.sqr(z2_inv, s_inv, ws);




10,766✔





471



   curve.mul(z3_inv, z2_inv, s_inv, ws);




10,766✔





472



   points[0].m_coord_x = curve.mul_to_tmp(points[0].m_coord_x, z2_inv, ws);




21,532✔





473



   points[0].m_coord_y = curve.mul_to_tmp(points[0].m_coord_y, z3_inv, ws);




21,532✔





474



   points[0].m_coord_z = rep_1;




10,766✔





475



   }




43,064✔





476












477



void EC_Point::force_affine()




1,377✔





478



   {










479



   if(is_zero())




1,377✔





480



      throw Invalid_State("Cannot convert zero ECC point to affine");




×







481












482



   secure_vector<word> ws;




1,377✔





483












484



   const BigInt z_inv = m_curve.invert_element(m_coord_z, ws);




1,377✔





485



   const BigInt z2_inv = m_curve.sqr_to_tmp(z_inv, ws);




1,377✔





486



   const BigInt z3_inv = m_curve.mul_to_tmp(z_inv, z2_inv, ws);




1,377✔





487



   m_coord_x = m_curve.mul_to_tmp(m_coord_x, z2_inv, ws);




1,377✔





488



   m_coord_y = m_curve.mul_to_tmp(m_coord_y, z3_inv, ws);




1,377✔





489



   m_coord_z = m_curve.get_1_rep();




1,377✔





490



   }




5,508✔





491












492



bool EC_Point::is_affine() const




40,775✔





493



   {










494



   return m_curve.is_one(m_coord_z);




40,775✔





495



   }










496












497



BigInt EC_Point::get_affine_x() const




27,338✔





498



   {










499



   if(is_zero())




30,561✔





500



      throw Invalid_State("Cannot convert zero point to affine");




27✔





501












502



   secure_vector<word> monty_ws;




27,311✔





503












504



   if(is_affine())




27,311✔





505



      return m_curve.from_rep_to_tmp(m_coord_x, monty_ws);




2,301✔





506












507



   BigInt z2 = m_curve.sqr_to_tmp(m_coord_z, monty_ws);




25,010✔





508



   z2 = m_curve.invert_element(z2, monty_ws);




25,010✔





509












510



   BigInt r;




25,010✔





511



   m_curve.mul(r, m_coord_x, z2, monty_ws);




25,010✔





512



   m_curve.from_rep(r, monty_ws);




25,010✔





513



   return r;




25,010✔





514



   }




78,847✔





515












516



BigInt EC_Point::get_affine_y() const




13,491✔





517



   {










518



   if(is_zero())




13,491✔





519



      throw Invalid_State("Cannot convert zero point to affine");




27✔





520












521



   secure_vector<word> monty_ws;




13,464✔





522












523



   if(is_affine())




13,464✔





524



      return m_curve.from_rep_to_tmp(m_coord_y, monty_ws);




2,294✔





525












526



   const BigInt z2 = m_curve.sqr_to_tmp(m_coord_z, monty_ws);




11,170✔





527



   const BigInt z3 = m_curve.mul_to_tmp(m_coord_z, z2, monty_ws);




11,170✔





528



   const BigInt z3_inv = m_curve.invert_element(z3, monty_ws);




11,170✔





529












530



   BigInt r;




11,170✔





531



   m_curve.mul(r, m_coord_y, z3_inv, monty_ws);




11,170✔





532



   m_curve.from_rep(r, monty_ws);




11,170✔





533



   return r;




11,170✔





534



   }




59,655✔





535












536



bool EC_Point::on_the_curve() const




29,336✔





537



   {










538



   /*










539



   Is the point still on the curve?? (If everything is correct, the










540



   point is always on its curve; then the function will return true.










541



   If somehow the state is corrupted, which suggests a fault attack










542



   (or internal computational error), then return false.










543



   */










544



   if(is_zero())




41,160✔





545



      return true;










546












547



   secure_vector<word> monty_ws;




29,274✔





548












549



   const BigInt y2 = m_curve.from_rep_to_tmp(m_curve.sqr_to_tmp(m_coord_y, monty_ws), monty_ws);




29,274✔





550



   const BigInt x3 = m_curve.mul_to_tmp(m_coord_x, m_curve.sqr_to_tmp(m_coord_x, monty_ws), monty_ws);




29,274✔





551



   const BigInt ax = m_curve.mul_to_tmp(m_coord_x, m_curve.get_a_rep(), monty_ws);




29,274✔





552



   const BigInt z2 = m_curve.sqr_to_tmp(m_coord_z, monty_ws);




29,274✔





553












554



   if(m_coord_z == z2) // Is z equal to 1 (in Montgomery form)?




29,274✔





555



      {










556



      if(y2 != m_curve.from_rep_to_tmp(x3 + ax + m_curve.get_b_rep(), monty_ws))




131,265✔





557



         return false;










558



      }










559












560



   const BigInt z3 = m_curve.mul_to_tmp(m_coord_z, z2, monty_ws);




29,007✔





561



   const BigInt ax_z4 = m_curve.mul_to_tmp(ax, m_curve.sqr_to_tmp(z2, monty_ws), monty_ws);




29,007✔





562



   const BigInt b_z6 = m_curve.mul_to_tmp(m_curve.get_b_rep(), m_curve.sqr_to_tmp(z3, monty_ws), monty_ws);




29,007✔





563












564



   if(y2 != m_curve.from_rep_to_tmp(x3 + ax_z4 + b_z6, monty_ws))




145,035✔





565



      return false;




54✔





566












567



   return true;










568



   }




233,720✔





569












570



// swaps the states of *this and other, does not throw!










571



void EC_Point::swap(EC_Point& other)




929,538✔





572



   {










573



   m_curve.swap(other.m_curve);




929,538✔





574



   m_coord_x.swap(other.m_coord_x);




929,538✔





575



   m_coord_y.swap(other.m_coord_y);




929,538✔





576



   m_coord_z.swap(other.m_coord_z);




929,538✔





577



   }




929,538✔





578












579



bool EC_Point::operator==(const EC_Point& other) const




5,333✔





580



   {










581



   if(m_curve != other.m_curve)




5,333✔





582



      return false;










583












584



   // If this is zero, only equal if other is also zero










585



   if(is_zero())




8,121✔





586



      return other.is_zero();




202✔





587












588



   return (get_affine_x() == other.get_affine_x() &&




20,552✔





589



           get_affine_y() == other.get_affine_y());




20,544✔





590



   }










591












592



// encoding and decoding










593



std::vector<uint8_t> EC_Point::encode(EC_Point_Format format) const




1,792✔





594



   {










595



   if(is_zero())




1,872✔





596



      return std::vector<uint8_t>(1); // single 0 byte




162✔





597












598



   const size_t p_bytes = m_curve.get_p().bytes();




1,630✔





599












600



   const BigInt x = get_affine_x();




1,630✔





601



   const BigInt y = get_affine_y();




1,630✔





602












603



   std::vector<uint8_t> result;




1,630✔





604












605



   if(format == EC_Point_Format::Uncompressed)




1,630✔





606



      {










607



      result.resize(1 + 2*p_bytes);




1,412✔





608



      result[0] = 0x04;




1,412✔





609



      BigInt::encode_1363(&result[1], p_bytes, x);




1,412✔





610



      BigInt::encode_1363(&result[1+p_bytes], p_bytes, y);




1,412✔





611



      }










612



   else if(format == EC_Point_Format::Compressed)




218✔





613



      {










614



      result.resize(1 + p_bytes);




126✔





615



      result[0] = 0x02 | static_cast<uint8_t>(y.get_bit(0));




252✔





616



      BigInt::encode_1363(&result[1], p_bytes, x);




126✔





617



      }










618



   else if(format == EC_Point_Format::Hybrid)




92✔





619



      {










620



      result.resize(1 + 2*p_bytes);




92✔





621



      result[0] = 0x06 | static_cast<uint8_t>(y.get_bit(0));




184✔





622



      BigInt::encode_1363(&result[1], p_bytes, x);




92✔





623



      BigInt::encode_1363(&result[1+p_bytes], p_bytes, y);




92✔





624



      }










625



   else










626



      throw Invalid_Argument("EC2OSP illegal point encoding");




×







627












628



   return result;




1,630✔





629



   }




5,052✔





630












631



namespace {










632












633



BigInt decompress_point(bool yMod2,




6,231✔





634



                        const BigInt& x,










635



                        const BigInt& curve_p,










636



                        const BigInt& curve_a,










637



                        const BigInt& curve_b)










638



   {










639



   BigInt xpow3 = x * x * x;




6,231✔





640












641



   BigInt g = curve_a * x;




6,231✔





642



   g += xpow3;




6,231✔





643



   g += curve_b;




6,231✔





644



   g = g % curve_p;




6,231✔





645












646



   BigInt z = sqrt_modulo_prime(g, curve_p);




6,231✔





647












648



   if(z < 0)




6,231✔





649



      throw Decoding_Error("Error during EC point decompression");




2,376✔





650












651



   if(z.get_bit(0) != yMod2)




7,710✔





652



      z = curve_p - z;




3,956✔





653












654



   return z;




3,855✔





655



   }




12,452✔





656












657



}










658












659



EC_Point OS2ECP(const uint8_t data[], size_t data_len,




9,695✔





660



                const CurveGFp& curve)










661



   {










662



   // Should we really be doing this?










663



   if(data_len <= 1)




9,695✔





664



      return EC_Point(curve); // return zero




173✔





665












666



   std::pair<BigInt, BigInt> xy = OS2ECP(data, data_len, curve.get_p(), curve.get_a(), curve.get_b());




9,522✔





667












668



   EC_Point point(curve, xy.first, xy.second);




6,948✔





669












670



   if(!point.on_the_curve())




6,362✔





671



      throw Decoding_Error("OS2ECP: Decoded point was not on the curve");




200✔





672












673



   return point;




6,162✔





674



   }




7,148✔





675












676



std::pair<BigInt, BigInt> OS2ECP(const uint8_t data[], size_t data_len,




9,554✔





677



                                 const BigInt& curve_p,










678



                                 const BigInt& curve_a,










679



                                 const BigInt& curve_b)










680



   {










681



   if(data_len <= 1)




9,554✔





682



      throw Decoding_Error("OS2ECP invalid point");




×







683












684



   const uint8_t pc = data[0];




9,554✔





685












686



   BigInt x, y;




9,554✔





687












688



   if(pc == 2 || pc == 3)




9,554✔





689



      {










690



      //compressed form










691



      x = BigInt::decode(&data[1], data_len - 1);




5,748✔





692












693



      const bool y_mod_2 = ((pc & 0x01) == 1);




5,748✔





694



      y = decompress_point(y_mod_2, x, curve_p, curve_a, curve_b);




5,748✔





695



      }










696



   else if(pc == 4)




3,806✔





697



      {










698



      const size_t l = (data_len - 1) / 2;




3,302✔





699












700



      // uncompressed form










701



      x = BigInt::decode(&data[1], l);




3,302✔





702



      y = BigInt::decode(&data[l+1], l);




3,302✔





703



      }










704



   else if(pc == 6 || pc == 7)




504✔





705



      {










706



      const size_t l = (data_len - 1) / 2;




483✔





707












708



      // hybrid form










709



      x = BigInt::decode(&data[1], l);




483✔





710



      y = BigInt::decode(&data[l+1], l);




483✔





711












712



      const bool y_mod_2 = ((pc & 0x01) == 1);




483✔





713












714



      if(decompress_point(y_mod_2, x, curve_p, curve_a, curve_b) != y)




3,702✔





715



         throw Decoding_Error("OS2ECP: Decoding error in hybrid format");




177✔





716



      }










717



   else










718



      throw Invalid_Argument("OS2ECP: Unknown format type " + std::to_string(pc));




42✔





719












720



   return std::make_pair(x, y);




6,980✔





721



   }




16,526✔





722












723



}
























    

  • 

    •