Botan
1.11.15
|
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 }