randombit / botan / 5123321399

coverage: 92.213% (+0.004%) from 92.209%
5123321399

Pull #3558

github

web-flow 
Merge dd72f7389 into 057bcbc35
Pull Request #3558: Add braces around all if/else statements

75602 of 81986 relevant lines covered (92.21%)

11859779.3 hits per line

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

96.23
/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,447✔





19



   // Assumes Montgomery rep of zero is zero










20



}




24,447✔





21












22



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




20,542✔





23



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




20,542✔





24



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




41,084✔





25



      throw Invalid_Argument("Invalid EC_Point affine x");




558✔





26



   }










27



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




39,833✔





28



      throw Invalid_Argument("Invalid EC_Point affine y");




203✔





29



   }










30












31



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




19,781✔





32



   m_curve.to_rep(m_coord_x, monty_ws);




19,781✔





33



   m_curve.to_rep(m_coord_y, monty_ws);




19,781✔





34



}




22,819✔





35












36



void EC_Point::randomize_repr(RandomNumberGenerator& rng) {




752✔





37



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




752✔





38



   randomize_repr(rng, ws);




752✔





39



}




752✔





40












41



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




6,406✔





42



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




6,406✔





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




6,406✔





52



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




6,406✔





53












54



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




6,406✔





55



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




6,406✔





56



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




12,812✔





57



}




19,218✔





58












59



namespace {










60












61



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




9,776,460✔





62



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




9,776,460✔





63












64



   for(auto& ws : ws_bn) {




87,988,140✔





65



      if(ws.size() < cap_size) {




78,211,680✔





66



         ws.get_word_vector().resize(cap_size);




1,491,404✔





67



      }










68



   }










69



}




9,776,460✔





70












71



}  // namespace










72












73



void EC_Point::add_affine(




2,290,187✔





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)).is_set()) {




17,131,927✔





76



      return;










77



   }










78












79



   if(is_zero()) {




4,470,073✔





80



      m_coord_x.set_words(x_words, x_size);




15,660✔





81



      m_coord_y.set_words(y_words, y_size);




15,660✔





82



      m_coord_z = m_curve.get_1_rep();




15,660✔





83



      return;




15,660✔





84



   }










85












86



   resize_ws(ws_bn, m_curve.get_ws_size());




2,219,402✔





87












88



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




2,219,402✔





89



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




2,219,402✔





90












91



   BigInt& T0 = ws_bn[2];




2,219,402✔





92



   BigInt& T1 = ws_bn[3];




2,219,402✔





93



   BigInt& T2 = ws_bn[4];




2,219,402✔





94



   BigInt& T3 = ws_bn[5];




2,219,402✔





95



   BigInt& T4 = ws_bn[6];




2,219,402✔





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,219,402✔





103












104



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




2,219,402✔





105



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




2,219,402✔





106












107



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




2,219,402✔





108



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




2,219,402✔





109












110



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




2,219,402✔





111












112



   T0.mod_sub(m_coord_y, p, sub_ws);




2,219,402✔





113












114



   if(T4.is_zero()) {




4,438,804✔





115



      if(T0.is_zero()) {




338✔





116



         mult2(ws_bn);




26✔





117



         return;




26✔





118



      }










119












120



      // setting to zero:










121



      m_coord_x.clear();




143✔





122



      m_coord_y = m_curve.get_1_rep();




143✔





123



      m_coord_z.clear();




143✔





124



      return;




143✔





125



   }










126












127



   m_curve.sqr(T2, T4, ws);




2,219,233✔





128












129



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




2,219,233✔





130












131



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




2,219,233✔





132












133



   m_curve.sqr(m_coord_x, T0, ws);




2,219,233✔





134



   m_coord_x.mod_sub(T1, p, sub_ws);




2,219,233✔





135












136



   m_coord_x.mod_sub(T3, p, sub_ws);




2,219,233✔





137



   m_coord_x.mod_sub(T3, p, sub_ws);




2,219,233✔





138












139



   T3.mod_sub(m_coord_x, p, sub_ws);




2,219,233✔





140












141



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




2,219,233✔





142



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




2,219,233✔





143



   T2.mod_sub(T0, p, sub_ws);




2,219,233✔





144



   m_coord_y.swap(T2);




2,219,233✔





145












146



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




2,219,233✔





147



   m_coord_z.swap(T0);




2,219,233✔





148



}










149












150



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




1,474,794✔





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)).is_set()) {




10,991,458✔





158



      return;










159



   }










160












161



   if(is_zero()) {




2,872,343✔





162



      m_coord_x.set_words(x_words, x_size);




5,813✔





163



      m_coord_y.set_words(y_words, y_size);




5,813✔





164



      m_coord_z.set_words(z_words, z_size);




5,813✔





165



      return;




5,813✔





166



   }










167












168



   resize_ws(ws_bn, m_curve.get_ws_size());




1,445,471✔





169












170



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




1,445,471✔





171



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




1,445,471✔





172












173



   BigInt& T0 = ws_bn[2];




1,445,471✔





174



   BigInt& T1 = ws_bn[3];




1,445,471✔





175



   BigInt& T2 = ws_bn[4];




1,445,471✔





176



   BigInt& T3 = ws_bn[5];




1,445,471✔





177



   BigInt& T4 = ws_bn[6];




1,445,471✔





178



   BigInt& T5 = ws_bn[7];




1,445,471✔





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,445,471✔





185












186



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




1,445,471✔





187



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




1,445,471✔





188



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




1,445,471✔





189



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




1,445,471✔





190












191



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




1,445,471✔





192



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




1,445,471✔





193












194



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




1,445,471✔





195



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




1,445,471✔





196












197



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




1,445,471✔





198












199



   T0.mod_sub(T2, p, sub_ws);




1,445,471✔





200












201



   if(T4.is_zero()) {




2,890,942✔





202



      if(T0.is_zero()) {




988✔





203



         mult2(ws_bn);




154✔





204



         return;




154✔





205



      }










206












207



      // setting to zero:










208



      m_coord_x.clear();




340✔





209



      m_coord_y = m_curve.get_1_rep();




340✔





210



      m_coord_z.clear();




340✔





211



      return;




340✔





212



   }










213












214



   m_curve.sqr(T5, T4, ws);




1,444,977✔





215












216



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




1,444,977✔





217












218



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




1,444,977✔





219












220



   m_curve.sqr(m_coord_x, T0, ws);




1,444,977✔





221



   m_coord_x.mod_sub(T1, p, sub_ws);




1,444,977✔





222



   m_coord_x.mod_sub(T3, p, sub_ws);




1,444,977✔





223



   m_coord_x.mod_sub(T3, p, sub_ws);




1,444,977✔





224












225



   T3.mod_sub(m_coord_x, p, sub_ws);




1,444,977✔





226












227



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




1,444,977✔





228



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




1,444,977✔





229












230



   m_coord_y.mod_sub(T3, p, sub_ws);




1,444,977✔





231












232



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




1,444,977✔





233



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




1,444,977✔





234



}










235












236



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




2,283,284✔





237



   if(iterations == 0) {




2,283,284✔





238



      return;










239



   }










240












241



   if(m_coord_y.is_zero()) {




4,563,742✔





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,469,872✔





251



      mult2(ws_bn);




5,186,588✔





252



   }










253



}










254












255



// *this *= 2










256



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




6,117,756✔





257



   if(is_zero()) {




12,202,207✔





258



      return;










259



   }










260












261



   if(m_coord_y.is_zero()) {




9,942,748✔





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,111,587✔





267












268



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




6,111,587✔





269



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




6,111,587✔





270












271



   BigInt& T0 = ws_bn[2];




6,111,587✔





272



   BigInt& T1 = ws_bn[3];




6,111,587✔





273



   BigInt& T2 = ws_bn[4];




6,111,587✔





274



   BigInt& T3 = ws_bn[5];




6,111,587✔





275



   BigInt& T4 = ws_bn[6];




6,111,587✔





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,111,587✔





281












282



   m_curve.sqr(T0, m_coord_y, ws);




6,111,587✔





283












284



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




6,111,587✔





285



   T1.mod_mul(4, p, sub_ws);




6,111,587✔





286












287



   if(m_curve.a_is_zero()) {




6,111,587✔





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




268,455✔





290



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




268,455✔





291



   } else if(m_curve.a_is_minus_3()) {




5,843,132✔





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,632,315✔





297












298



      // (x-z^2)










299



      T2 = m_coord_x;




4,632,315✔





300



      T2.mod_sub(T3, p, sub_ws);




4,632,315✔





301












302



      // (x+z^2)










303



      T3.mod_add(m_coord_x, p, sub_ws);




4,632,315✔





304












305



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




4,632,315✔





306












307



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




4,632,315✔





308



   } else {










309



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




1,210,817✔





310



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




1,210,817✔





311



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




1,210,817✔





312












313



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




1,210,817✔





314



      T4.mod_mul(3, p, sub_ws);




1,210,817✔





315



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




1,210,817✔





316



   }










317












318



   m_curve.sqr(T2, T4, ws);




6,111,587✔





319



   T2.mod_sub(T1, p, sub_ws);




6,111,587✔





320



   T2.mod_sub(T1, p, sub_ws);




6,111,587✔





321












322



   m_curve.sqr(T3, T0, ws);




6,111,587✔





323



   T3.mod_mul(8, p, sub_ws);




6,111,587✔





324












325



   T1.mod_sub(T2, p, sub_ws);




6,111,587✔





326












327



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




6,111,587✔





328



   T0.mod_sub(T3, p, sub_ws);




6,111,587✔





329












330



   m_coord_x.swap(T2);




6,111,587✔





331












332



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




6,111,587✔





333



   T2.mod_mul(2, p, sub_ws);




6,111,587✔





334












335



   m_coord_y.swap(T0);




6,111,587✔





336



   m_coord_z.swap(T2);




6,117,756✔





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




2,958✔





364



   BOTAN_DEBUG_ASSERT(point.on_the_curve());




2,958✔





365












366



   const size_t scalar_bits = scalar.bits();




2,958✔





367












368



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




2,958✔





369












370



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




8,874✔





371












372



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




502,817✔





373



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




499,859✔





374



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




499,859✔





375



      R[b].mult2(ws);




499,859✔





376



   }










377












378



   if(scalar.is_negative()) {




2,958✔





379



      R[0].negate();




×







380



   }










381












382



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




2,958✔





383












384



   return R[0];




5,916✔





385



}




11,832✔





386












387



//static










388



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




10,836✔





389



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




10,836✔





390



      for(auto& point : points) {




×







391



         point.force_affine();




×







392



      }










393



      return;




×







394



   }










395












396



   for(auto& point : points) {




1,072,737✔





397



      if(point.is_zero()) {




1,974,018✔





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;




10,836✔





412



   const BigInt& rep_1 = curve.get_1_rep();




10,836✔





413












414



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




10,836✔





415



      ws.resize(curve.get_ws_size());




×







416



   }










417












418



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




10,836✔





419



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




10,836✔





420












421



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




1,061,901✔





422



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




2,102,130✔





423



   }










424












425



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




10,836✔





426












427



   BigInt z_inv, z2_inv, z3_inv;




10,836✔





428












429



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




1,061,901✔





430



      EC_Point& point = points[i];




1,051,065✔





431












432



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




1,051,065✔





433












434



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




1,051,065✔





435












436



      curve.sqr(z2_inv, z_inv, ws);




1,051,065✔





437



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




1,051,065✔





438



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




2,102,130✔





439



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




2,102,130✔





440



      point.m_coord_z = rep_1;




1,051,065✔





441



   }










442












443



   curve.sqr(z2_inv, s_inv, ws);




10,836✔





444



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




10,836✔





445



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




21,672✔





446



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




21,672✔





447



   points[0].m_coord_z = rep_1;




10,836✔





448



}




43,344✔





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 { return m_curve.is_one(m_coord_z); }




40,970✔





466












467



BigInt EC_Point::get_affine_x() const {




27,470✔





468



   if(is_zero()) {




30,688✔





469



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




27✔





470



   }










471












472



   secure_vector<word> monty_ws;




27,443✔





473












474



   if(is_affine()) {




27,443✔





475



      return m_curve.from_rep_to_tmp(m_coord_x, monty_ws);




2,370✔





476



   }










477












478



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




25,073✔





479



   z2 = m_curve.invert_element(z2, monty_ws);




25,073✔





480












481



   BigInt r;




25,073✔





482



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




25,073✔





483



   m_curve.from_rep(r, monty_ws);




25,073✔





484



   return r;




25,073✔





485



}




79,119✔





486












487



BigInt EC_Point::get_affine_y() const {




13,554✔





488



   if(is_zero()) {




13,554✔





489



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




27✔





490



   }










491












492



   secure_vector<word> monty_ws;




13,527✔





493












494



   if(is_affine()) {




13,527✔





495



      return m_curve.from_rep_to_tmp(m_coord_y, monty_ws);




2,363✔





496



   }










497












498



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




11,164✔





499



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




11,164✔





500



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




11,164✔





501












502



   BigInt r;




11,164✔





503



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




11,164✔





504



   m_curve.from_rep(r, monty_ws);




11,164✔





505



   return r;




11,164✔





506



}




59,708✔





507












508



bool EC_Point::on_the_curve() const {




29,594✔





509



   /*










510



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










511



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










512



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










513



   (or internal computational error), then return false.










514



   */










515



   if(is_zero()) {




41,542✔





516



      return true;










517



   }










518












519



   secure_vector<word> monty_ws;




29,532✔





520












521



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




29,532✔





522



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




29,532✔





523



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




29,532✔





524



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




29,532✔





525












526



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




29,532✔





527



   {










528



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




132,580✔





529



         return false;










530



      }










531



   }










532












533



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




29,265✔





534



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




29,265✔





535



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





536












537



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




146,325✔





538



      return false;




53✔





539



   }










540












541



   return true;










542



}




235,784✔





543












544



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










545



void EC_Point::swap(EC_Point& other) {




934,716✔





546



   m_curve.swap(other.m_curve);




934,716✔





547



   m_coord_x.swap(other.m_coord_x);




934,716✔





548



   m_coord_y.swap(other.m_coord_y);




934,716✔





549



   m_coord_z.swap(other.m_coord_z);




934,716✔





550



}




934,716✔





551












552



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




5,333✔





553



   if(m_curve != other.m_curve) {




5,333✔





554



      return false;










555



   }










556












557



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










558



   if(is_zero()) {




8,121✔





559



      return other.is_zero();




202✔





560



   }










561












562



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




25,687✔





563



}










564












565



// encoding and decoding










566



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




1,860✔





567



   if(is_zero()) {




1,940✔





568



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




162✔





569



   }










570












571



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




1,698✔





572












573



   const BigInt x = get_affine_x();




1,698✔





574



   const BigInt y = get_affine_y();




1,698✔





575












576



   std::vector<uint8_t> result;




1,698✔





577












578



   if(format == EC_Point_Format::Uncompressed) {




1,698✔





579



      result.resize(1 + 2 * p_bytes);




1,480✔





580



      result[0] = 0x04;




1,480✔





581



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




1,480✔





582



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




1,480✔





583



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




218✔





584



      result.resize(1 + p_bytes);




126✔





585



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




252✔





586



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




126✔





587



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




92✔





588



      result.resize(1 + 2 * p_bytes);




92✔





589



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




184✔





590



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




92✔





591



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




92✔





592



   } else {










593



      throw Invalid_Argument("EC2OSP illegal point encoding");




×







594



   }










595












596



   return result;




1,698✔





597



}




5,256✔





598












599



namespace {










600












601



BigInt decompress_point(




6,231✔





602



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










603



   BigInt xpow3 = x * x * x;




6,231✔





604












605



   BigInt g = curve_a * x;




6,231✔





606



   g += xpow3;




6,231✔





607



   g += curve_b;




6,231✔





608



   g = g % curve_p;




6,231✔





609












610



   BigInt z = sqrt_modulo_prime(g, curve_p);




6,231✔





611












612



   if(z < 0) {




6,231✔





613



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




2,376✔





614



   }










615












616



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




7,710✔





617



      z = curve_p - z;




3,956✔





618



   }










619












620



   return z;




3,855✔





621



}




12,452✔





622












623



}  // namespace










624












625



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




9,829✔





626



   // Should we really be doing this?










627



   if(data_len <= 1) {




9,829✔





628



      return EC_Point(curve);  // return zero




173✔





629



   }










630












631



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




9,656✔





632












633



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




7,082✔





634












635



   if(!point.on_the_curve()) {




6,496✔





636



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




200✔





637



   }










638












639



   return point;




6,296✔





640



}




7,282✔





641












642



std::pair<BigInt, BigInt> OS2ECP(




9,688✔





643



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










644



   if(data_len <= 1) {




9,688✔





645



      throw Decoding_Error("OS2ECP invalid point");




×







646



   }










647












648



   const uint8_t pc = data[0];




9,688✔





649












650



   BigInt x, y;




9,688✔





651












652



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




9,688✔





653



      //compressed form










654



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




5,748✔





655












656



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




5,748✔





657



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




5,748✔





658



   } else if(pc == 4) {




3,940✔





659



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




3,436✔





660












661



      // uncompressed form










662



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




3,436✔





663



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




3,436✔





664



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




504✔





665



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




483✔





666












667



      // hybrid form










668



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




483✔





669



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




483✔





670












671



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




483✔





672












673



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




3,702✔





674



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




177✔





675



      }










676



   } else {










677



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




42✔





678



   }










679












680



   return std::make_pair(x, y);




7,114✔





681



}




16,794✔





682












683



}  // namespace Botan
























    

  • 

    •