randombit / botan / 11087146043

coverage: 92.003% (+0.7%) from 91.274%
11087146043

push

github

web-flow 
Create terraform.yml

82959 of 90170 relevant lines covered (92.0%)

9376319.11 hits per line

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

96.24
/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) : m_curve(curve), m_coord_x(0), m_coord_y(curve.get_1_rep()), m_coord_z(0) {




24,855✔





19



   // Assumes Montgomery rep of zero is zero










20



}




24,855✔





21












22



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




21,786✔





23



      m_curve(curve), m_coord_x(x), m_coord_y(y), m_coord_z(m_curve.get_1_rep()) {




21,786✔





24



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




43,572✔





25



      throw Invalid_Argument("Invalid EC_Point affine x");




568✔





26



   }










27



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




42,295✔





28



      throw Invalid_Argument("Invalid EC_Point affine y");




210✔





29



   }










30












31



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




21,008✔





32



   m_curve.to_rep(m_coord_x, monty_ws);




21,008✔





33



   m_curve.to_rep(m_coord_y, monty_ws);




21,008✔





34



}




24,114✔





35












36



void EC_Point::randomize_repr(RandomNumberGenerator& rng) {




583✔





37



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




583✔





38



   randomize_repr(rng, ws);




583✔





39



}




583✔





40












41



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




5,934✔





42



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




5,934✔





43












44



   /*










45



   * No reason to convert this to Montgomery representation first,










46



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










47



   * random mask we generated above is in the Montgomery










48



   * representation.










49



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










50



   */










51



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




5,934✔





52



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




5,934✔





53












54



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




5,934✔





55



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




5,934✔





56



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




11,868✔





57



}




17,802✔





58












59



namespace {










60












61



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




10,539,826✔





62



   BOTAN_ASSERT(ws_bn.size() >= EC_Point::WORKSPACE_SIZE, "Expected size for EC_Point workspace");




10,539,826✔





63












64



   for(auto& ws : ws_bn) {




94,858,434✔





65



      if(ws.size() < cap_size) {




84,318,608✔





66



         ws.get_word_vector().resize(cap_size);




1,515,927✔





67



      }










68



   }










69



}




10,539,826✔





70












71



}  // namespace










72












73



void EC_Point::add_affine(




2,411,006✔





74



   const word x_words[], size_t x_size, const word y_words[], size_t y_size, std::vector<BigInt>& ws_bn) {










75



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




18,132,886✔





76



      return;










77



   }










78












79



   if(is_zero()) {




4,714,139✔





80



      m_coord_x.set_words(x_words, x_size);




16,275✔





81



      m_coord_y.set_words(y_words, y_size);




16,275✔





82



      m_coord_z = m_curve.get_1_rep();




16,275✔





83



      return;




16,275✔





84



   }










85












86



   resize_ws(ws_bn, m_curve.get_ws_size());




2,340,818✔





87












88



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




2,340,818✔





89



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




2,340,818✔





90












91



   BigInt& T0 = ws_bn[2];




2,340,818✔





92



   BigInt& T1 = ws_bn[3];




2,340,818✔





93



   BigInt& T2 = ws_bn[4];




2,340,818✔





94



   BigInt& T3 = ws_bn[5];




2,340,818✔





95



   BigInt& T4 = ws_bn[6];




2,340,818✔





96












97



   /*










98



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










99



   simplified with Z2 = 1










100



   */










101












102



   const BigInt& p = m_curve.get_p();




2,340,818✔





103












104



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




2,340,818✔





105



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




2,340,818✔





106












107



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




2,340,818✔





108



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




2,340,818✔





109












110



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




2,340,818✔





111












112



   T0.mod_sub(m_coord_y, p, sub_ws);




2,340,818✔





113












114



   if(T4.is_zero()) {




4,681,636✔





115



      if(T0.is_zero()) {




308✔





116



         mult2(ws_bn);




14✔





117



         return;




14✔





118



      }










119












120



      // setting to zero:










121



      m_coord_x.clear();




140✔





122



      m_coord_y = m_curve.get_1_rep();




140✔





123



      m_coord_z.clear();




140✔





124



      return;




140✔





125



   }










126












127



   m_curve.sqr(T2, T4, ws);




2,340,664✔





128












129



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




2,340,664✔





130












131



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




2,340,664✔





132












133



   m_curve.sqr(m_coord_x, T0, ws);




2,340,664✔





134



   m_coord_x.mod_sub(T1, p, sub_ws);




2,340,664✔





135












136



   m_coord_x.mod_sub(T3, p, sub_ws);




2,340,664✔





137



   m_coord_x.mod_sub(T3, p, sub_ws);




2,340,664✔





138












139



   T3.mod_sub(m_coord_x, p, sub_ws);




2,340,664✔





140












141



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




2,340,664✔





142



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




2,340,664✔





143



   T2.mod_sub(T0, p, sub_ws);




2,340,664✔





144



   m_coord_y.swap(T2);




2,340,664✔





145












146



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




2,340,664✔





147



   m_coord_z.swap(T0);




2,340,664✔





148



}










149












150



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




1,705,849✔





151



                   size_t x_size,










152



                   const word y_words[],










153



                   size_t y_size,










154



                   const word z_words[],










155



                   size_t z_size,










156



                   std::vector<BigInt>& ws_bn) {










157



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




13,344,523✔





158



      return;










159



   }










160












161



   if(is_zero()) {




3,335,005✔





162



      m_coord_x.set_words(x_words, x_size);




5,761✔





163



      m_coord_y.set_words(y_words, y_size);




5,761✔





164



      m_coord_z.set_words(z_words, z_size);




5,761✔





165



      return;




5,761✔





166



   }










167












168



   resize_ws(ws_bn, m_curve.get_ws_size());




1,678,018✔





169












170



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




1,678,018✔





171



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




1,678,018✔





172












173



   BigInt& T0 = ws_bn[2];




1,678,018✔





174



   BigInt& T1 = ws_bn[3];




1,678,018✔





175



   BigInt& T2 = ws_bn[4];




1,678,018✔





176



   BigInt& T3 = ws_bn[5];




1,678,018✔





177



   BigInt& T4 = ws_bn[6];




1,678,018✔





178



   BigInt& T5 = ws_bn[7];




1,678,018✔





179












180



   /*










181



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










182



   */










183












184



   const BigInt& p = m_curve.get_p();




1,678,018✔





185












186



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




1,678,018✔





187



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




1,678,018✔





188



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




1,678,018✔





189



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




1,678,018✔





190












191



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




1,678,018✔





192



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




1,678,018✔





193












194



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




1,678,018✔





195



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




1,678,018✔





196












197



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




1,678,018✔





198












199



   T0.mod_sub(T2, p, sub_ws);




1,678,018✔





200












201



   if(T4.is_zero()) {




3,356,036✔





202



      if(T0.is_zero()) {




1,026✔





203



         mult2(ws_bn);




156✔





204



         return;




156✔





205



      }










206












207



      // setting to zero:










208



      m_coord_x.clear();




357✔





209



      m_coord_y = m_curve.get_1_rep();




357✔





210



      m_coord_z.clear();




357✔





211



      return;




357✔





212



   }










213












214



   m_curve.sqr(T5, T4, ws);




1,677,505✔





215












216



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




1,677,505✔





217












218



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




1,677,505✔





219












220



   m_curve.sqr(m_coord_x, T0, ws);




1,677,505✔





221



   m_coord_x.mod_sub(T1, p, sub_ws);




1,677,505✔





222



   m_coord_x.mod_sub(T3, p, sub_ws);




1,677,505✔





223



   m_coord_x.mod_sub(T3, p, sub_ws);




1,677,505✔





224












225



   T3.mod_sub(m_coord_x, p, sub_ws);




1,677,505✔





226












227



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




1,677,505✔





228



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




1,677,505✔





229












230



   m_coord_y.mod_sub(T3, p, sub_ws);




1,677,505✔





231












232



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




1,677,505✔





233



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




1,677,505✔





234



}










235












236



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




2,411,640✔





237



   if(iterations == 0) {




2,411,640✔





238



      return;










239



   }










240












241



   if(m_coord_y.is_zero()) {




4,820,451✔





242



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




×







243



      return;




×







244



   }










245












246



   /*










247



   TODO we can save 2 squarings per iteration by computing










248



   a*Z^4 using values cached from previous iteration










249



   */










250



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




7,824,994✔





251



      mult2(ws_bn);




5,413,354✔





252



   }










253



}










254












255



// *this *= 2










256



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




6,527,167✔





257



   if(is_zero()) {




13,019,388✔





258



      return;










259



   }










260












261



   if(m_coord_y.is_zero()) {




10,633,200✔





262



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




×







263



      return;




×







264



   }










265












266



   resize_ws(ws_bn, m_curve.get_ws_size());




6,520,990✔





267












268



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




6,520,990✔





269



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




6,520,990✔





270












271



   BigInt& T0 = ws_bn[2];




6,520,990✔





272



   BigInt& T1 = ws_bn[3];




6,520,990✔





273



   BigInt& T2 = ws_bn[4];




6,520,990✔





274



   BigInt& T3 = ws_bn[5];




6,520,990✔





275



   BigInt& T4 = ws_bn[6];




6,520,990✔





276












277



   /*










278



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










279



   */










280



   const BigInt& p = m_curve.get_p();




6,520,990✔





281












282



   m_curve.sqr(T0, m_coord_y, ws);




6,520,990✔





283












284



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




6,520,990✔





285



   T1.mod_mul(4, p, sub_ws);




6,520,990✔





286












287



   if(m_curve.a_is_zero()) {




6,520,990✔





288



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










289



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




310,112✔





290



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




310,112✔





291



   } else if(m_curve.a_is_minus_3()) {




6,210,878✔





292



      /*










293



      if a == -3 then










294



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










295



      */










296



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




4,992,315✔





297












298



      // (x-z^2)










299



      T2 = m_coord_x;




4,992,315✔





300



      T2.mod_sub(T3, p, sub_ws);




4,992,315✔





301












302



      // (x+z^2)










303



      T3.mod_add(m_coord_x, p, sub_ws);




4,992,315✔





304












305



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




4,992,315✔





306












307



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




4,992,315✔





308



   } else {










309



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




1,218,563✔





310



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




1,218,563✔





311



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




1,218,563✔





312












313



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




1,218,563✔





314



      T4.mod_mul(3, p, sub_ws);




1,218,563✔





315



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




1,218,563✔





316



   }










317












318



   m_curve.sqr(T2, T4, ws);




6,520,990✔





319



   T2.mod_sub(T1, p, sub_ws);




6,520,990✔





320



   T2.mod_sub(T1, p, sub_ws);




6,520,990✔





321












322



   m_curve.sqr(T3, T0, ws);




6,520,990✔





323



   T3.mod_mul(8, p, sub_ws);




6,520,990✔





324












325



   T1.mod_sub(T2, p, sub_ws);




6,520,990✔





326












327



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




6,520,990✔





328



   T0.mod_sub(T3, p, sub_ws);




6,520,990✔





329












330



   m_coord_x.swap(T2);




6,520,990✔





331












332



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




6,520,990✔





333



   T2.mod_mul(2, p, sub_ws);




6,520,990✔





334












335



   m_coord_y.swap(T0);




6,520,990✔





336



   m_coord_z.swap(T2);




6,527,167✔





337



}










338












339



// arithmetic operators










340



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




2,376✔





341



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




2,376✔





342



   add(rhs, ws);




2,376✔





343



   return *this;




2,375✔





344



}




2,376✔





345












346



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




82✔





347



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




82✔





348












349



   if(is_zero()) {




82✔





350



      *this = minus_rhs;




×







351



   } else {










352



      *this += minus_rhs;




82✔





353



   }










354












355



   return *this;




82✔





356



}




82✔





357












358



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




67✔





359



   *this = scalar * *this;




67✔





360



   return *this;




67✔





361



}










362












363



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




3,057✔





364



   BOTAN_DEBUG_ASSERT(point.on_the_curve());




3,057✔





365












366



   const size_t scalar_bits = scalar.bits();




3,057✔





367












368



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




3,057✔





369












370



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




9,171✔





371












372



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




514,340✔





373



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




511,283✔





374



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




511,283✔





375



      R[b].mult2(ws);




511,283✔





376



   }










377












378



   if(scalar.is_negative()) {




3,057✔





379



      R[0].negate();




×







380



   }










381












382



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




3,057✔





383












384



   return R[0];




6,114✔





385



}




12,228✔





386












387



//static










388



void EC_Point::force_all_affine(std::vector<EC_Point>& points, secure_vector<word>& ws) {




11,901✔





389



   if(points.size() <= 1) {




11,901✔





390



      for(auto& point : points) {




×







391



         point.force_affine();




×







392



      }










393



      return;




×







394



   }










395












396



   for(auto& point : points) {




1,480,914✔





397



      if(point.is_zero()) {




2,776,460✔





398



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




×







399



      }










400



   }










401












402



   /*










403



   For >= 2 points use Montgomery's trick










404












405



   See Algorithm 2.26 in "Guide to Elliptic Curve Cryptography"










406



   (Hankerson, Menezes, Vanstone)










407












408



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










409



   */










410












411



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




11,901✔





412



   const BigInt& rep_1 = curve.get_1_rep();




11,901✔





413












414



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




11,901✔





415



      ws.resize(curve.get_ws_size());




×







416



   }










417












418



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




11,901✔





419



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




11,901✔





420












421



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




1,469,013✔





422



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




2,914,224✔





423



   }










424












425



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




11,901✔





426












427



   BigInt z_inv, z2_inv, z3_inv;




11,901✔





428












429



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




1,469,013✔





430



      EC_Point& point = points[i];




1,457,112✔





431












432



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




1,457,112✔





433












434



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




1,457,112✔





435












436



      curve.sqr(z2_inv, z_inv, ws);




1,457,112✔





437



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




1,457,112✔





438



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




2,914,224✔





439



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




2,914,224✔





440



      point.m_coord_z = rep_1;




1,457,112✔





441



   }










442












443



   curve.sqr(z2_inv, s_inv, ws);




11,901✔





444



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




11,901✔





445



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




23,802✔





446



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




23,802✔





447



   points[0].m_coord_z = rep_1;




11,901✔





448



}




47,604✔





449












450



void EC_Point::force_affine() {




1,377✔





451



   if(is_zero()) {




1,377✔





452



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




×







453



   }










454












455



   secure_vector<word> ws;




1,377✔





456












457



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




1,377✔





458



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




1,377✔





459



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




1,377✔





460



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




1,377✔





461



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




1,377✔





462



   m_coord_z = m_curve.get_1_rep();




1,377✔





463



}




5,508✔





464












465



bool EC_Point::is_affine() const {




43,349✔





466



   return m_curve.is_one(m_coord_z);




43,349✔





467



}










468












469



BigInt EC_Point::get_affine_x() const {




28,974✔





470



   if(is_zero()) {




31,112✔





471



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




27✔





472



   }










473












474



   secure_vector<word> monty_ws;




28,947✔





475












476



   if(is_affine()) {




28,947✔





477



      return m_curve.from_rep_to_tmp(m_coord_x, monty_ws);




3,369✔





478



   }










479












480



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




25,578✔





481



   z2 = m_curve.invert_element(z2, monty_ws);




25,578✔





482












483



   BigInt r;




25,578✔





484



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




25,578✔





485



   m_curve.from_rep(r, monty_ws);




25,578✔





486



   return r;




25,578✔





487



}




82,132✔





488












489



BigInt EC_Point::get_affine_y() const {




14,429✔





490



   if(is_zero()) {




14,429✔





491



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




27✔





492



   }










493












494



   secure_vector<word> monty_ws;




14,402✔





495












496



   if(is_affine()) {




14,402✔





497



      return m_curve.from_rep_to_tmp(m_coord_y, monty_ws);




3,362✔





498



   }










499












500



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




11,040✔





501



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




11,040✔





502



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




11,040✔





503












504



   BigInt r;




11,040✔





505



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




11,040✔





506



   m_curve.from_rep(r, monty_ws);




11,040✔





507



   return r;




11,040✔





508



}




60,586✔





509












510



bool EC_Point::on_the_curve() const {




31,959✔





511



   /*










512



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










513



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










514



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










515



   (or internal computational error), then return false.










516



   */










517



   if(is_zero()) {




44,611✔





518



      return true;










519



   }










520












521



   secure_vector<word> monty_ws;




31,902✔





522












523



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




31,902✔





524



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




31,902✔





525



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




31,902✔





526



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




31,902✔





527












528



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




31,902✔





529



   {










530



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




145,025✔





531



         return false;










532



      }










533



   }










534












535



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




31,626✔





536



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




31,626✔





537



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




31,626✔





538












539



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




158,130✔





540



      return false;




52✔





541



   }










542












543



   return true;










544



}




254,721✔





545












546



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










547



void EC_Point::swap(EC_Point& other) {




1,280,214✔





548



   m_curve.swap(other.m_curve);




1,280,214✔





549



   m_coord_x.swap(other.m_coord_x);




1,280,214✔





550



   m_coord_y.swap(other.m_coord_y);




1,280,214✔





551



   m_coord_z.swap(other.m_coord_z);




1,280,214✔





552



}




1,280,214✔





553












554



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




6,443✔





555



   if(m_curve != other.m_curve) {




6,443✔





556



      return false;










557



   }










558












559



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










560



   if(is_zero()) {




10,339✔





561



      return other.is_zero();




202✔





562



   }










563












564



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




31,237✔





565



}










566












567



// encoding and decoding










568



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




1,592✔





569



   if(is_zero()) {




1,674✔





570



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




162✔





571



   }










572












573



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




1,430✔





574












575



   const BigInt x = get_affine_x();




1,430✔





576



   const BigInt y = get_affine_y();




1,430✔





577












578



   std::vector<uint8_t> result;




1,430✔





579












580



   if(format == EC_Point_Format::Uncompressed) {




1,430✔





581



      result.resize(1 + 2 * p_bytes);




1,210✔





582



      result[0] = 0x04;




1,210✔





583



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




1,210✔





584



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




1,210✔





585



   } else if(format == EC_Point_Format::Compressed) {




220✔





586



      result.resize(1 + p_bytes);




128✔





587



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




256✔





588



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




128✔





589



   } else if(format == EC_Point_Format::Hybrid) {




92✔





590



      result.resize(1 + 2 * p_bytes);




92✔





591



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




184✔





592



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




92✔





593



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




92✔





594



   } else {










595



      throw Invalid_Argument("EC2OSP illegal point encoding");




×







596



   }










597












598



   return result;




1,430✔





599



}




4,452✔





600












601



namespace {










602












603



BigInt decompress_point(




6,380✔





604



   bool yMod2, const BigInt& x, const BigInt& curve_p, const BigInt& curve_a, const BigInt& curve_b) {










605



   BigInt xpow3 = x * x * x;




6,380✔





606












607



   BigInt g = curve_a * x;




6,380✔





608



   g += xpow3;




6,380✔





609



   g += curve_b;




6,380✔





610



   g = g % curve_p;




6,380✔





611












612



   BigInt z = sqrt_modulo_prime(g, curve_p);




6,380✔





613












614



   if(z < 0) {




6,380✔





615



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




2,409✔





616



   }










617












618



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




7,942✔





619



      z = curve_p - z;




4,096✔





620



   }










621












622



   return z;




3,971✔





623



}




12,750✔





624












625



}  // namespace










626












627



EC_Point OS2ECP(const uint8_t data[], size_t data_len, const CurveGFp& curve) {




10,808✔





628



   // Should we really be doing this?










629



   if(data_len <= 1) {




10,808✔





630



      return EC_Point(curve);  // return zero




174✔





631



   }










632












633



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




10,634✔





634












635



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




8,021✔





636












637



   if(!point.on_the_curve()) {




7,425✔





638



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




209✔





639



   }










640












641



   return point;




7,216✔





642



}




8,230✔





643












644



std::pair<BigInt, BigInt> OS2ECP(




10,693✔





645



   const uint8_t data[], size_t data_len, const BigInt& curve_p, const BigInt& curve_a, const BigInt& curve_b) {










646



   if(data_len <= 1) {




10,693✔





647



      throw Decoding_Error("OS2ECP invalid point");




×







648



   }










649












650



   const uint8_t pc = data[0];




10,693✔





651












652



   BigInt x, y;




10,693✔





653












654



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




10,693✔





655



      //compressed form










656



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




5,892✔





657












658



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




5,892✔





659



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




5,892✔





660



   } else if(pc == 4) {




4,801✔





661



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




4,290✔





662












663



      // uncompressed form










664



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




4,290✔





665



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




4,290✔





666



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




511✔





667



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




488✔





668












669



      // hybrid form










670



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




488✔





671



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




488✔





672












673



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




488✔





674












675



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




3,753✔





676



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




181✔





677



      }










678



   } else {










679



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




46✔





680



   }










681












682



   return std::make_pair(x, y);




8,080✔





683



}




18,764✔





684












685



}  // namespace Botan
























    

  • 

    •