Botan  1.11.15
src/lib/math/ec_gfp/point_gfp.cpp
Go to the documentation of this file.
00001 /*
00002 * Point arithmetic on elliptic curves over GF(p)
00003 *
00004 * (C) 2007 Martin Doering, Christoph Ludwig, Falko Strenzke
00005 *     2008-2011,2012,2014 Jack Lloyd
00006 *
00007 * Botan is released under the Simplified BSD License (see license.txt)
00008 */
00009 
00010 #include <botan/point_gfp.h>
00011 #include <botan/numthry.h>
00012 
00013 namespace Botan {
00014 
00015 PointGFp::PointGFp(const CurveGFp& curve) :
00016    curve(curve),
00017    coord_x(0),
00018    coord_y(1),
00019    coord_z(0)
00020    {
00021    curve.to_rep(coord_x, ws);
00022    curve.to_rep(coord_y, ws);
00023    curve.to_rep(coord_z, ws);
00024    }
00025 
00026 PointGFp::PointGFp(const CurveGFp& curve, const BigInt& x, const BigInt& y) :
00027    curve(curve),
00028    coord_x(x),
00029    coord_y(y),
00030    coord_z(1)
00031    {
00032    curve.to_rep(coord_x, ws);
00033    curve.to_rep(coord_y, ws);
00034    curve.to_rep(coord_z, ws);
00035    }
00036 
00037 // Point addition
00038 void PointGFp::add(const PointGFp& rhs, std::vector<BigInt>& ws_bn)
00039    {
00040    if(is_zero())
00041       {
00042       coord_x = rhs.coord_x;
00043       coord_y = rhs.coord_y;
00044       coord_z = rhs.coord_z;
00045       return;
00046       }
00047    else if(rhs.is_zero())
00048       return;
00049 
00050    const BigInt& p = curve.get_p();
00051 
00052    BigInt& rhs_z2 = ws_bn[0];
00053    BigInt& U1 = ws_bn[1];
00054    BigInt& S1 = ws_bn[2];
00055 
00056    BigInt& lhs_z2 = ws_bn[3];
00057    BigInt& U2 = ws_bn[4];
00058    BigInt& S2 = ws_bn[5];
00059 
00060    BigInt& H = ws_bn[6];
00061    BigInt& r = ws_bn[7];
00062 
00063    /*
00064    http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#addition-add-1998-cmo-2
00065    */
00066 
00067    curve_sqr(rhs_z2, rhs.coord_z);
00068    curve_mult(U1, coord_x, rhs_z2);
00069    curve_mult(S1, coord_y, curve_mult(rhs.coord_z, rhs_z2));
00070 
00071    curve_sqr(lhs_z2, coord_z);
00072    curve_mult(U2, rhs.coord_x, lhs_z2);
00073    curve_mult(S2, rhs.coord_y, curve_mult(coord_z, lhs_z2));
00074 
00075    H = U2;
00076    H -= U1;
00077    if(H.is_negative())
00078       H += p;
00079 
00080    r = S2;
00081    r -= S1;
00082    if(r.is_negative())
00083       r += p;
00084 
00085    if(H.is_zero())
00086       {
00087       if(r.is_zero())
00088          {
00089          mult2(ws_bn);
00090          return;
00091          }
00092 
00093       *this = PointGFp(curve); // setting myself to zero
00094       return;
00095       }
00096 
00097    curve_sqr(U2, H);
00098 
00099    curve_mult(S2, U2, H);
00100 
00101    U2 = curve_mult(U1, U2);
00102 
00103    curve_sqr(coord_x, r);
00104    coord_x -= S2;
00105    coord_x -= (U2 << 1);
00106    while(coord_x.is_negative())
00107       coord_x += p;
00108 
00109    U2 -= coord_x;
00110    if(U2.is_negative())
00111       U2 += p;
00112 
00113    curve_mult(coord_y, r, U2);
00114    coord_y -= curve_mult(S1, S2);
00115    if(coord_y.is_negative())
00116       coord_y += p;
00117 
00118    curve_mult(coord_z, curve_mult(coord_z, rhs.coord_z), H);
00119    }
00120 
00121 // *this *= 2
00122 void PointGFp::mult2(std::vector<BigInt>& ws_bn)
00123    {
00124    if(is_zero())
00125       return;
00126    else if(coord_y.is_zero())
00127       {
00128       *this = PointGFp(curve); // setting myself to zero
00129       return;
00130       }
00131 
00132    /*
00133    http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#doubling-dbl-1986-cc
00134    */
00135 
00136    const BigInt& p = curve.get_p();
00137 
00138    BigInt& y_2 = ws_bn[0];
00139    BigInt& S = ws_bn[1];
00140    BigInt& z4 = ws_bn[2];
00141    BigInt& a_z4 = ws_bn[3];
00142    BigInt& M = ws_bn[4];
00143    BigInt& U = ws_bn[5];
00144    BigInt& x = ws_bn[6];
00145    BigInt& y = ws_bn[7];
00146    BigInt& z = ws_bn[8];
00147 
00148    curve_sqr(y_2, coord_y);
00149 
00150    curve_mult(S, coord_x, y_2);
00151    S <<= 2; // * 4
00152    while(S >= p)
00153       S -= p;
00154 
00155    curve_sqr(z4, curve_sqr(coord_z));
00156    curve_mult(a_z4, curve.get_a_rep(), z4);
00157 
00158    M = curve_sqr(coord_x);
00159    M *= 3;
00160    M += a_z4;
00161    while(M >= p)
00162       M -= p;
00163 
00164    curve_sqr(x, M);
00165    x -= (S << 1);
00166    while(x.is_negative())
00167       x += p;
00168 
00169    curve_sqr(U, y_2);
00170    U <<= 3;
00171    while(U >= p)
00172       U -= p;
00173 
00174    S -= x;
00175    while(S.is_negative())
00176       S += p;
00177 
00178    curve_mult(y, M, S);
00179    y -= U;
00180    if(y.is_negative())
00181       y += p;
00182 
00183    curve_mult(z, coord_y, coord_z);
00184    z <<= 1;
00185    if(z >= p)
00186       z -= p;
00187 
00188    coord_x = x;
00189    coord_y = y;
00190    coord_z = z;
00191    }
00192 
00193 // arithmetic operators
00194 PointGFp& PointGFp::operator+=(const PointGFp& rhs)
00195    {
00196    std::vector<BigInt> ws(9);
00197    add(rhs, ws);
00198    return *this;
00199    }
00200 
00201 PointGFp& PointGFp::operator-=(const PointGFp& rhs)
00202    {
00203    PointGFp minus_rhs = PointGFp(rhs).negate();
00204 
00205    if(is_zero())
00206       *this = minus_rhs;
00207    else
00208       *this += minus_rhs;
00209 
00210    return *this;
00211    }
00212 
00213 PointGFp& PointGFp::operator*=(const BigInt& scalar)
00214    {
00215    *this = scalar * *this;
00216    return *this;
00217    }
00218 
00219 PointGFp multi_exponentiate(const PointGFp& p1, const BigInt& z1,
00220                             const PointGFp& p2, const BigInt& z2)
00221    {
00222    const PointGFp p3 = p1 + p2;
00223 
00224    PointGFp H(p1.curve); // create as zero
00225    size_t bits_left = std::max(z1.bits(), z2.bits());
00226 
00227    std::vector<BigInt> ws(9);
00228 
00229    while(bits_left)
00230       {
00231       H.mult2(ws);
00232 
00233       const bool z1_b = z1.get_bit(bits_left - 1);
00234       const bool z2_b = z2.get_bit(bits_left - 1);
00235 
00236       if(z1_b == true && z2_b == true)
00237          H.add(p3, ws);
00238       else if(z1_b)
00239          H.add(p1, ws);
00240       else if(z2_b)
00241          H.add(p2, ws);
00242 
00243       --bits_left;
00244       }
00245 
00246    if(z1.is_negative() != z2.is_negative())
00247       H.negate();
00248 
00249    return H;
00250    }
00251 
00252 PointGFp operator*(const BigInt& scalar, const PointGFp& point)
00253    {
00254    //BOTAN_ASSERT(point.on_the_curve(), "Input is valid");
00255 
00256    const CurveGFp& curve = point.get_curve();
00257 
00258    if(scalar.is_zero())
00259       return PointGFp(curve); // zero point
00260 
00261    std::vector<BigInt> ws(9);
00262 
00263    if(scalar.abs() <= 2) // special cases for small values
00264       {
00265       byte value = scalar.abs().byte_at(0);
00266 
00267       PointGFp result = point;
00268 
00269       if(value == 2)
00270          result.mult2(ws);
00271 
00272       if(scalar.is_negative())
00273          result.negate();
00274 
00275       return result;
00276       }
00277 
00278    const size_t scalar_bits = scalar.bits();
00279 
00280    PointGFp x1(curve); // zero
00281 
00282    size_t bits_left = scalar_bits;
00283 
00284 #if BOTAN_CURVE_GFP_USE_MONTGOMERY_LADDER
00285 
00286    PointGFp x2 = point;
00287    while(bits_left)
00288       {
00289       if(scalar.get_bit(bits_left - 1))
00290          {
00291          x1.add(x2, ws);
00292          x2.mult2(ws);
00293          }
00294       else
00295          {
00296          x2.add(x1, ws);
00297          x1.mult2(ws);
00298          }
00299 
00300       --bits_left;
00301       }
00302 
00303 #else
00304    const size_t window_bits = 4;
00305 
00306    std::vector<PointGFp> Ps(1 << window_bits);
00307    Ps[0] = x1;
00308    Ps[1] = point;
00309 
00310    for(size_t i = 2; i < Ps.size(); ++i)
00311       {
00312       Ps[i] = Ps[i-1];
00313       Ps[i].add(point, ws);
00314       }
00315 
00316    while(bits_left >= window_bits)
00317       {
00318       for(size_t i = 0; i != window_bits; ++i)
00319          x1.mult2(ws);
00320 
00321       const u32bit nibble = scalar.get_substring(bits_left - window_bits, window_bits);
00322       x1.add(Ps[nibble], ws);
00323       bits_left -= window_bits;
00324       }
00325 
00326    while(bits_left)
00327       {
00328       x1.mult2(ws);
00329       if(scalar.get_bit(bits_left-1))
00330          x1.add(point, ws);
00331       --bits_left;
00332       }
00333 
00334 #endif
00335 
00336    if(scalar.is_negative())
00337       x1.negate();
00338 
00339    //BOTAN_ASSERT(x1.on_the_curve(), "Output is on the curve");
00340 
00341    return x1;
00342    }
00343 
00344 BigInt PointGFp::get_affine_x() const
00345    {
00346    if(is_zero())
00347       throw Illegal_Transformation("Cannot convert zero point to affine");
00348 
00349    BigInt z2 = curve_sqr(coord_z);
00350    curve.from_rep(z2, ws);
00351    z2 = inverse_mod(z2, curve.get_p());
00352 
00353    return curve_mult(z2, coord_x);
00354    }
00355 
00356 BigInt PointGFp::get_affine_y() const
00357    {
00358    if(is_zero())
00359       throw Illegal_Transformation("Cannot convert zero point to affine");
00360 
00361    BigInt z3 = curve_mult(coord_z, curve_sqr(coord_z));
00362    z3 = inverse_mod(z3, curve.get_p());
00363    curve.to_rep(z3, ws);
00364 
00365    return curve_mult(z3, coord_y);
00366    }
00367 
00368 bool PointGFp::on_the_curve() const
00369    {
00370    /*
00371    Is the point still on the curve?? (If everything is correct, the
00372    point is always on its curve; then the function will return true.
00373    If somehow the state is corrupted, which suggests a fault attack
00374    (or internal computational error), then return false.
00375    */
00376    if(is_zero())
00377       return true;
00378 
00379    const BigInt y2 = curve.from_rep(curve_sqr(coord_y), ws);
00380    const BigInt x3 = curve_mult(coord_x, curve_sqr(coord_x));
00381    const BigInt ax = curve_mult(coord_x, curve.get_a_rep());
00382    const BigInt z2 = curve_sqr(coord_z);
00383 
00384    if(coord_z == z2) // Is z equal to 1 (in Montgomery form)?
00385       {
00386       if(y2 != curve.from_rep(x3 + ax + curve.get_b_rep(), ws))
00387          return false;
00388       }
00389 
00390    const BigInt z3 = curve_mult(coord_z, z2);
00391    const BigInt ax_z4 = curve_mult(ax, curve_sqr(z2));
00392    const BigInt b_z6 = curve_mult(curve.get_b_rep(), curve_sqr(z3));
00393 
00394    if(y2 != curve.from_rep(x3 + ax_z4 + b_z6, ws))
00395       return false;
00396 
00397    return true;
00398    }
00399 
00400 // swaps the states of *this and other, does not throw!
00401 void PointGFp::swap(PointGFp& other)
00402    {
00403    curve.swap(other.curve);
00404    coord_x.swap(other.coord_x);
00405    coord_y.swap(other.coord_y);
00406    coord_z.swap(other.coord_z);
00407    ws.swap(other.ws);
00408    }
00409 
00410 bool PointGFp::operator==(const PointGFp& other) const
00411    {
00412    if(get_curve() != other.get_curve())
00413       return false;
00414 
00415    // If this is zero, only equal if other is also zero
00416    if(is_zero())
00417       return other.is_zero();
00418 
00419    return (get_affine_x() == other.get_affine_x() &&
00420            get_affine_y() == other.get_affine_y());
00421    }
00422 
00423 // encoding and decoding
00424 secure_vector<byte> EC2OSP(const PointGFp& point, byte format)
00425    {
00426    if(point.is_zero())
00427       return secure_vector<byte>(1); // single 0 byte
00428 
00429    const size_t p_bytes = point.get_curve().get_p().bytes();
00430 
00431    BigInt x = point.get_affine_x();
00432    BigInt y = point.get_affine_y();
00433 
00434    secure_vector<byte> bX = BigInt::encode_1363(x, p_bytes);
00435    secure_vector<byte> bY = BigInt::encode_1363(y, p_bytes);
00436 
00437    if(format == PointGFp::UNCOMPRESSED)
00438       {
00439       secure_vector<byte> result;
00440       result.push_back(0x04);
00441 
00442       result += bX;
00443       result += bY;
00444 
00445       return result;
00446       }
00447    else if(format == PointGFp::COMPRESSED)
00448       {
00449       secure_vector<byte> result;
00450       result.push_back(0x02 | static_cast<byte>(y.get_bit(0)));
00451 
00452       result += bX;
00453 
00454       return result;
00455       }
00456    else if(format == PointGFp::HYBRID)
00457       {
00458       secure_vector<byte> result;
00459       result.push_back(0x06 | static_cast<byte>(y.get_bit(0)));
00460 
00461       result += bX;
00462       result += bY;
00463 
00464       return result;
00465       }
00466    else
00467       throw Invalid_Argument("EC2OSP illegal point encoding");
00468    }
00469 
00470 namespace {
00471 
00472 BigInt decompress_point(bool yMod2,
00473                         const BigInt& x,
00474                         const CurveGFp& curve)
00475    {
00476    BigInt xpow3 = x * x * x;
00477 
00478    const BigInt& p = curve.get_p();
00479 
00480    BigInt g = curve.get_a() * x;
00481    g += xpow3;
00482    g += curve.get_b();
00483    g = g % p;
00484 
00485    BigInt z = ressol(g, p);
00486 
00487    if(z < 0)
00488       throw Illegal_Point("error during EC point decompression");
00489 
00490    if(z.get_bit(0) != yMod2)
00491       z = p - z;
00492 
00493    return z;
00494    }
00495 
00496 }
00497 
00498 PointGFp OS2ECP(const byte data[], size_t data_len,
00499                 const CurveGFp& curve)
00500    {
00501    if(data_len <= 1)
00502       return PointGFp(curve); // return zero
00503 
00504    const byte pc = data[0];
00505 
00506    BigInt x, y;
00507 
00508    if(pc == 2 || pc == 3)
00509       {
00510       //compressed form
00511       x = BigInt::decode(&data[1], data_len - 1);
00512 
00513       const bool y_mod_2 = ((pc & 0x01) == 1);
00514       y = decompress_point(y_mod_2, x, curve);
00515       }
00516    else if(pc == 4)
00517       {
00518       const size_t l = (data_len - 1) / 2;
00519 
00520       // uncompressed form
00521       x = BigInt::decode(&data[1], l);
00522       y = BigInt::decode(&data[l+1], l);
00523       }
00524    else if(pc == 6 || pc == 7)
00525       {
00526       const size_t l = (data_len - 1) / 2;
00527 
00528       // hybrid form
00529       x = BigInt::decode(&data[1], l);
00530       y = BigInt::decode(&data[l+1], l);
00531 
00532       const bool y_mod_2 = ((pc & 0x01) == 1);
00533 
00534       if(decompress_point(y_mod_2, x, curve) != y)
00535          throw Illegal_Point("OS2ECP: Decoding error in hybrid format");
00536       }
00537    else
00538       throw Invalid_Argument("OS2ECP: Unknown format type " + std::to_string(pc));
00539 
00540    PointGFp result(curve, x, y);
00541 
00542    if(!result.on_the_curve())
00543       throw Illegal_Point("OS2ECP: Decoded point was not on the curve");
00544 
00545    return result;
00546    }
00547 
00548 }