## Coverage Report

#### Created: 2022-06-23 06:44

/src/botan/src/lib/pubkey/ec_group/curve_gfp.cpp
 Line Count Source (jump to first uncovered line) 1 /* 2 * Elliptic curves over GF(p) Montgomery Representation 3 * (C) 2014,2015,2018 Jack Lloyd 4 * 2016 Matthias Gierlings 5 * 6 * Botan is released under the Simplified BSD License (see license.txt) 7 */ 8 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 16 namespace Botan { 17 18 namespace { 19 20 class CurveGFp_Montgomery final : public CurveGFp_Repr 21 { 22 public: 23 CurveGFp_Montgomery(const BigInt& p, const BigInt& a, const BigInt& b) : 24 m_p(p), m_a(a), m_b(b), 25 m_p_words(m_p.sig_words()), 26 m_p_dash(monty_inverse(m_p.word_at(0))) 27 1.20k { 28 1.20k Modular_Reducer mod_p(m_p); 29 30 1.20k m_r.set_bit(m_p_words * BOTAN_MP_WORD_BITS); 31 1.20k m_r = mod_p.reduce(m_r); 32 33 1.20k m_r2 = mod_p.square(m_r); 34 1.20k m_r3 = mod_p.multiply(m_r, m_r2); 35 1.20k m_a_r = mod_p.multiply(m_r, m_a); 36 1.20k m_b_r = mod_p.multiply(m_r, m_b); 37 38 1.20k m_a_is_zero = m_a.is_zero(); 39 1.20k m_a_is_minus_3 = (m_a + 3 == m_p); 40 1.20k } 41 42 4.59M bool a_is_zero() const override { return m_a_is_zero; } 43 4.35M bool a_is_minus_3() const override { return m_a_is_minus_3; } 44 45 11.1k const BigInt& get_a() const override { return m_a; } 46 47 11.1k const BigInt& get_b() const override { return m_b; } 48 49 8.69M const BigInt& get_p() const override { return m_p; } 50 51 4.28M const BigInt& get_a_rep() const override { return m_a_r; } 52 53 24.0k const BigInt& get_b_rep() const override { return m_b_r; } 54 55 66.2k const BigInt& get_1_rep() const override { return m_r; } 56 57 70.3k bool is_one(const BigInt& x) const override { return x == m_r; } 58 59 796k size_t get_p_words() const override { return m_p_words; } 60 61 113M size_t get_ws_size() const override { return 2*m_p_words + 4; } 62 63 BigInt invert_element(const BigInt& x, secure_vector& ws) const override; 64 65 void to_curve_rep(BigInt& x, secure_vector& ws) const override; 66 67 void from_curve_rep(BigInt& x, secure_vector& ws) const override; 68 69 void curve_mul_words(BigInt& z, 70 const word x_words[], 71 size_t x_size, 72 const BigInt& y, 73 secure_vector& ws) const override; 74 75 void curve_sqr_words(BigInt& z, 76 const word x_words[], 77 size_t x_size, 78 secure_vector& ws) const override; 79 80 private: 81 BigInt m_p; 82 BigInt m_a, m_b; 83 BigInt m_a_r, m_b_r; 84 size_t m_p_words; // cache of m_p.sig_words() 85 86 // Montgomery parameters 87 BigInt m_r, m_r2, m_r3; 88 word m_p_dash; 89 90 bool m_a_is_zero; 91 bool m_a_is_minus_3; 92 }; 93 94 BigInt CurveGFp_Montgomery::invert_element(const BigInt& x, secure_vector& ws) const 95 71.5k { 96 // Should we use Montgomery inverse instead? 97 71.5k const BigInt inv = inverse_mod(x, m_p); 98 71.5k BigInt res; 99 71.5k curve_mul(res, inv, m_r3, ws); 100 71.5k return res; 101 71.5k } 102 103 void CurveGFp_Montgomery::to_curve_rep(BigInt& x, secure_vector& ws) const 104 13.9k { 105 13.9k const BigInt tx = x; 106 13.9k curve_mul(x, tx, m_r2, ws); 107 13.9k } 108 109 void CurveGFp_Montgomery::from_curve_rep(BigInt& z, secure_vector& ws) const 110 113k { 111 113k if(ws.size() < get_ws_size()) 112 90 ws.resize(get_ws_size()); 113 114 113k const size_t output_size = 2*m_p_words + 2; 115 113k if(z.size() < output_size) 116 23.0k z.grow_to(output_size); 117 118 113k bigint_monty_redc(z.mutable_data(), 119 113k m_p.data(), m_p_words, m_p_dash, 120 113k ws.data(), ws.size()); 121 113k } 122 123 void CurveGFp_Montgomery::curve_mul_words(BigInt& z, 124 const word x_w[], 125 size_t x_size, 126 const BigInt& y, 127 secure_vector& ws) const 128 63.1M { 129 63.1M BOTAN_DEBUG_ASSERT(y.sig_words() <= m_p_words); 130 131 63.1M if(ws.size() < get_ws_size()) 132 0 ws.resize(get_ws_size()); 133 134 63.1M const size_t output_size = 2*m_p_words + 2; 135 63.1M if(z.size() < output_size) 136 3.93M z.grow_to(output_size); 137 138 63.1M bigint_mul(z.mutable_data(), z.size(), 139 63.1M x_w, x_size, std::min(m_p_words, x_size), 140 63.1M y.data(), y.size(), std::min(m_p_words, y.size()), 141 63.1M ws.data(), ws.size()); 142 143 63.1M bigint_monty_redc(z.mutable_data(), 144 63.1M m_p.data(), m_p_words, m_p_dash, 145 63.1M ws.data(), ws.size()); 146 63.1M } 147 148 void CurveGFp_Montgomery::curve_sqr_words(BigInt& z, 149 const word x[], 150 size_t x_size, 151 secure_vector& ws) const 152 41.8M { 153 41.8M if(ws.size() < get_ws_size()) 154 107k ws.resize(get_ws_size()); 155 156 41.8M const size_t output_size = 2*m_p_words + 2; 157 41.8M if(z.size() < output_size) 158 279k z.grow_to(output_size); 159 160 41.8M bigint_sqr(z.mutable_data(), z.size(), 161 41.8M x, x_size, std::min(m_p_words, x_size), 162 41.8M ws.data(), ws.size()); 163 164 41.8M bigint_monty_redc(z.mutable_data(), 165 41.8M m_p.data(), m_p_words, m_p_dash, 166 41.8M ws.data(), ws.size()); 167 41.8M } 168 169 class CurveGFp_NIST : public CurveGFp_Repr 170 { 171 public: 172 CurveGFp_NIST(size_t p_bits, const BigInt& a, const BigInt& b) : 173 m_1(1), m_a(a), m_b(b), m_p_words((p_bits + BOTAN_MP_WORD_BITS - 1) / BOTAN_MP_WORD_BITS) 174 983 { 175 // All Solinas prime curves are assumed a == -3 176 983 } 177 178 11.7M bool a_is_zero() const override { return false; } 179 11.7M bool a_is_minus_3() const override { return true; } 180 181 19.4k const BigInt& get_a() const override { return m_a; } 182 183 19.4k const BigInt& get_b() const override { return m_b; } 184 185 107k const BigInt& get_1_rep() const override { return m_1; } 186 187 1.92M size_t get_p_words() const override { return m_p_words; } 188 189 290M size_t get_ws_size() const override { return 2*m_p_words + 4; } 190 191 20.4k const BigInt& get_a_rep() const override { return m_a; } 192 193 28.0k const BigInt& get_b_rep() const override { return m_b; } 194 195 142k bool is_one(const BigInt& x) const override { return x == 1; } 196 197 void to_curve_rep(BigInt& x, secure_vector& ws) const override 198 22.1k { redc_mod_p(x, ws); } 199 200 void from_curve_rep(BigInt& x, secure_vector& ws) const override 201 190k { redc_mod_p(x, ws); } 202 203 virtual void redc_mod_p(BigInt& z, secure_vector& ws) const = 0; 204 205 BigInt invert_element(const BigInt& x, secure_vector& ws) const override; 206 207 void curve_mul_words(BigInt& z, 208 const word x_words[], 209 size_t x_size, 210 const BigInt& y, 211 secure_vector& ws) const override; 212 213 void curve_mul_tmp(BigInt& x, const BigInt& y, BigInt& tmp, secure_vector& ws) const 214 1.70M { 215 1.70M curve_mul(tmp, x, y, ws); 216 1.70M x.swap(tmp); 217 1.70M } 218 219 void curve_sqr_tmp(BigInt& x, BigInt& tmp, secure_vector& ws) const 220 57.2M { 221 57.2M curve_sqr(tmp, x, ws); 222 57.2M x.swap(tmp); 223 57.2M } 224 225 void curve_sqr_words(BigInt& z, 226 const word x_words[], 227 size_t x_size, 228 secure_vector& ws) const override; 229 private: 230 // Curve parameters 231 BigInt m_1; 232 BigInt m_a, m_b; 233 size_t m_p_words; // cache of m_p.sig_words() 234 }; 235 236 BigInt CurveGFp_NIST::invert_element(const BigInt& x, secure_vector& ws) const 237 480 { 238 480 BOTAN_UNUSED(ws); 239 480 return inverse_mod(x, get_p()); 240 480 } 241 242 void CurveGFp_NIST::curve_mul_words(BigInt& z, 243 const word x_w[], 244 size_t x_size, 245 const BigInt& y, 246 secure_vector& ws) const 247 136M { 248 136M BOTAN_DEBUG_ASSERT(y.sig_words() <= m_p_words); 249 250 136M if(ws.size() < get_ws_size()) 251 0 ws.resize(get_ws_size()); 252 253 136M const size_t output_size = 2*m_p_words + 2; 254 136M if(z.size() < output_size) 255 5.88M z.grow_to(output_size); 256 257 136M bigint_mul(z.mutable_data(), z.size(), 258 136M x_w, x_size, std::min(m_p_words, x_size), 259 136M y.data(), y.size(), std::min(m_p_words, y.size()), 260 136M ws.data(), ws.size()); 261 262 136M this->redc_mod_p(z, ws); 263 136M } 264 265 void CurveGFp_NIST::curve_sqr_words(BigInt& z, const word x[], size_t x_size, 266 secure_vector& ws) const 267 133M { 268 133M if(ws.size() < get_ws_size()) 269 189k ws.resize(get_ws_size()); 270 271 133M const size_t output_size = 2*m_p_words + 2; 272 133M if(z.size() < output_size) 273 12.2M z.grow_to(output_size); 274 275 133M bigint_sqr(z.mutable_data(), output_size, 276 133M x, x_size, std::min(m_p_words, x_size), 277 133M ws.data(), ws.size()); 278 279 133M this->redc_mod_p(z, ws); 280 133M } 281 282 /** 283 * The NIST P-192 curve 284 */ 285 class CurveGFp_P192 final : public CurveGFp_NIST 286 { 287 public: 288 50 CurveGFp_P192(const BigInt& a, const BigInt& b) : CurveGFp_NIST(192, a, b) {} 289 42.0k const BigInt& get_p() const override { return prime_p192(); } 290 private: 291 725k void redc_mod_p(BigInt& x, secure_vector& ws) const override { redc_p192(x, ws); } 292 }; 293 294 /** 295 * The NIST P-224 curve 296 */ 297 class CurveGFp_P224 final : public CurveGFp_NIST 298 { 299 public: 300 339 CurveGFp_P224(const BigInt& a, const BigInt& b) : CurveGFp_NIST(224, a, b) {} 301 356k const BigInt& get_p() const override { return prime_p224(); } 302 private: 303 6.22M void redc_mod_p(BigInt& x, secure_vector& ws) const override { redc_p224(x, ws); } 304 }; 305 306 /** 307 * The NIST P-256 curve 308 */ 309 class CurveGFp_P256 final : public CurveGFp_NIST 310 { 311 public: 312 22 CurveGFp_P256(const BigInt& a, const BigInt& b) : CurveGFp_NIST(256, a, b) {} 313 3.05M const BigInt& get_p() const override { return prime_p256(); } 314 private: 315 41.7M void redc_mod_p(BigInt& x, secure_vector& ws) const override { redc_p256(x, ws); } 316 BigInt invert_element(const BigInt& x, secure_vector& ws) const override; 317 }; 318 319 BigInt CurveGFp_P256::invert_element(const BigInt& x, secure_vector& ws) const 320 39.0k { 321 39.0k BigInt r, p2, p4, p8, p16, p32, tmp; 322 323 39.0k curve_sqr(r, x, ws); 324 325 39.0k curve_mul(p2, r, x, ws); 326 39.0k curve_sqr(r, p2, ws); 327 39.0k curve_sqr_tmp(r, tmp, ws); 328 329 39.0k curve_mul(p4, r, p2, ws); 330 331 39.0k curve_sqr(r, p4, ws); 332 156k for(size_t i = 0; i != 3; ++i) 333 117k curve_sqr_tmp(r, tmp, ws); 334 39.0k curve_mul(p8, r, p4, ws); 335 336 39.0k curve_sqr(r, p8, ws); 337 312k for(size_t i = 0; i != 7; ++i) 338 273k curve_sqr_tmp(r, tmp, ws); 339 39.0k curve_mul(p16, r, p8, ws); 340 341 39.0k curve_sqr(r, p16, ws); 342 625k for(size_t i = 0; i != 15; ++i) 343 586k curve_sqr_tmp(r, tmp, ws); 344 39.0k curve_mul(p32, r, p16, ws); 345 346 39.0k curve_sqr(r, p32, ws); 347 1.25M for(size_t i = 0; i != 31; ++i) 348 1.21M curve_sqr_tmp(r, tmp, ws); 349 39.0k curve_mul_tmp(r, x, tmp, ws); 350 351 5.04M for(size_t i = 0; i != 32*4; ++i) 352 5.00M curve_sqr_tmp(r, tmp, ws); 353 39.0k curve_mul_tmp(r, p32, tmp, ws); 354 355 1.28M for(size_t i = 0; i != 32; ++i) 356 1.25M curve_sqr_tmp(r, tmp, ws); 357 39.0k curve_mul_tmp(r, p32, tmp, ws); 358 359 664k for(size_t i = 0; i != 16; ++i) 360 625k curve_sqr_tmp(r, tmp, ws); 361 39.0k curve_mul_tmp(r, p16, tmp, ws); 362 351k for(size_t i = 0; i != 8; ++i) 363 312k curve_sqr_tmp(r, tmp, ws); 364 39.0k curve_mul_tmp(r, p8, tmp, ws); 365 366 195k for(size_t i = 0; i != 4; ++i) 367 156k curve_sqr_tmp(r, tmp, ws); 368 39.0k curve_mul_tmp(r, p4, tmp, ws); 369 370 117k for(size_t i = 0; i != 2; ++i) 371 78.1k curve_sqr_tmp(r, tmp, ws); 372 39.0k curve_mul_tmp(r, p2, tmp, ws); 373 374 117k for(size_t i = 0; i != 2; ++i) 375 78.1k curve_sqr_tmp(r, tmp, ws); 376 39.0k curve_mul_tmp(r, x, tmp, ws); 377 378 39.0k return r; 379 39.0k } 380 381 /** 382 * The NIST P-384 curve 383 */ 384 class CurveGFp_P384 final : public CurveGFp_NIST 385 { 386 public: 387 204 CurveGFp_P384(const BigInt& a, const BigInt& b) : CurveGFp_NIST(384, a, b) {} 388 6.07M const BigInt& get_p() const override { return prime_p384(); } 389 private: 390 83.5M void redc_mod_p(BigInt& x, secure_vector& ws) const override { redc_p384(x, ws); } 391 BigInt invert_element(const BigInt& x, secure_vector& ws) const override; 392 }; 393 394 BigInt CurveGFp_P384::invert_element(const BigInt& x, secure_vector& ws) const 395 46.9k { 396 // From https://briansmith.org/ecc-inversion-addition-chains-01 397 398 46.9k BigInt r, x2, x3, x15, x30, tmp, rl; 399 400 46.9k r = x; 401 46.9k curve_sqr_tmp(r, tmp, ws); 402 46.9k curve_mul_tmp(r, x, tmp, ws); 403 46.9k x2 = r; 404 405 46.9k curve_sqr_tmp(r, tmp, ws); 406 46.9k curve_mul_tmp(r, x, tmp, ws); 407 408 46.9k x3 = r; 409 410 187k for(size_t i = 0; i != 3; ++i) 411 140k curve_sqr_tmp(r, tmp, ws); 412 46.9k curve_mul_tmp(r, x3, tmp, ws); 413 414 46.9k rl = r; 415 328k for(size_t i = 0; i != 6; ++i) 416 281k curve_sqr_tmp(r, tmp, ws); 417 46.9k curve_mul_tmp(r, rl, tmp, ws); 418 419 187k for(size_t i = 0; i != 3; ++i) 420 140k curve_sqr_tmp(r, tmp, ws); 421 46.9k curve_mul_tmp(r, x3, tmp, ws); 422 423 46.9k x15 = r; 424 750k for(size_t i = 0; i != 15; ++i) 425 703k curve_sqr_tmp(r, tmp, ws); 426 46.9k curve_mul_tmp(r, x15, tmp, ws); 427 428 46.9k x30 = r; 429 1.45M for(size_t i = 0; i != 30; ++i) 430 1.40M curve_sqr_tmp(r, tmp, ws); 431 46.9k curve_mul_tmp(r, x30, tmp, ws); 432 433 46.9k rl = r; 434 2.86M for(size_t i = 0; i != 60; ++i) 435 2.81M curve_sqr_tmp(r, tmp, ws); 436 46.9k curve_mul_tmp(r, rl, tmp, ws); 437 438 46.9k rl = r; 439 5.67M for(size_t i = 0; i != 120; ++i) 440 5.62M curve_sqr_tmp(r, tmp, ws); 441 46.9k curve_mul_tmp(r, rl, tmp, ws); 442 443 750k for(size_t i = 0; i != 15; ++i) 444 703k curve_sqr_tmp(r, tmp, ws); 445 46.9k curve_mul_tmp(r, x15, tmp, ws); 446 447 1.50M for(size_t i = 0; i != 31; ++i) 448 1.45M curve_sqr_tmp(r, tmp, ws); 449 46.9k curve_mul_tmp(r, x30, tmp, ws); 450 451 140k for(size_t i = 0; i != 2; ++i) 452 93.8k curve_sqr_tmp(r, tmp, ws); 453 46.9k curve_mul_tmp(r, x2, tmp, ws); 454 455 4.45M for(size_t i = 0; i != 94; ++i) 456 4.40M curve_sqr_tmp(r, tmp, ws); 457 46.9k curve_mul_tmp(r, x30, tmp, ws); 458 459 140k for(size_t i = 0; i != 2; ++i) 460 93.8k curve_sqr_tmp(r, tmp, ws); 461 462 46.9k curve_mul_tmp(r, x, tmp, ws); 463 464 46.9k return r; 465 46.9k } 466 467 /** 468 * The NIST P-521 curve 469 */ 470 class CurveGFp_P521 final : public CurveGFp_NIST 471 { 472 public: 473 368 CurveGFp_P521(const BigInt& a, const BigInt& b) : CurveGFp_NIST(521, a, b) {} 474 10.0M const BigInt& get_p() const override { return prime_p521(); } 475 private: 476 138M void redc_mod_p(BigInt& x, secure_vector& ws) const override { redc_p521(x, ws); } 477 BigInt invert_element(const BigInt& x, secure_vector& ws) const override; 478 }; 479 480 BigInt CurveGFp_P521::invert_element(const BigInt& x, secure_vector& ws) const 481 56.9k { 482 // Addition chain from https://eprint.iacr.org/2014/852.pdf section 483 484 56.9k BigInt r; 485 56.9k BigInt rl; 486 56.9k BigInt a7; 487 56.9k BigInt tmp; 488 489 56.9k curve_sqr(r, x, ws); 490 56.9k curve_mul_tmp(r, x, tmp, ws); 491 492 56.9k curve_sqr_tmp(r, tmp, ws); 493 56.9k curve_mul_tmp(r, x, tmp, ws); 494 495 56.9k rl = r; 496 497 227k for(size_t i = 0; i != 3; ++i) 498 170k curve_sqr_tmp(r, tmp, ws); 499 56.9k curve_mul_tmp(r, rl, tmp, ws); 500 501 56.9k curve_sqr_tmp(r, tmp, ws); 502 56.9k curve_mul_tmp(r, x, tmp, ws); 503 56.9k a7 = r; // need this value later 504 505 56.9k curve_sqr_tmp(r, tmp, ws); 506 56.9k curve_mul_tmp(r, x, tmp, ws); 507 508 56.9k rl = r; 509 512k for(size_t i = 0; i != 8; ++i) 510 455k curve_sqr_tmp(r, tmp, ws); 511 56.9k curve_mul_tmp(r, rl, tmp, ws); 512 513 56.9k rl = r; 514 967k for(size_t i = 0; i != 16; ++i) 515 910k curve_sqr_tmp(r, tmp, ws); 516 56.9k curve_mul_tmp(r, rl, tmp, ws); 517 518 56.9k rl = r; 519 1.87M for(size_t i = 0; i != 32; ++i) 520 1.82M curve_sqr_tmp(r, tmp, ws); 521 56.9k curve_mul_tmp(r, rl, tmp, ws); 522 523 56.9k rl = r; 524 3.69M for(size_t i = 0; i != 64; ++i) 525 3.64M curve_sqr_tmp(r, tmp, ws); 526 56.9k curve_mul_tmp(r, rl, tmp, ws); 527 528 56.9k rl = r; 529 7.34M for(size_t i = 0; i != 128; ++i) 530 7.28M curve_sqr_tmp(r, tmp, ws); 531 56.9k curve_mul_tmp(r, rl, tmp, ws); 532 533 56.9k rl = r; 534 14.6M for(size_t i = 0; i != 256; ++i) 535 14.5M curve_sqr_tmp(r, tmp, ws); 536 56.9k curve_mul_tmp(r, rl, tmp, ws); 537 538 455k for(size_t i = 0; i != 7; ++i) 539 398k curve_sqr_tmp(r, tmp, ws); 540 56.9k curve_mul_tmp(r, a7, tmp, ws); 541 542 170k for(size_t i = 0; i != 2; ++i) 543 113k curve_sqr_tmp(r, tmp, ws); 544 56.9k curve_mul_tmp(r, x, tmp, ws); 545 546 56.9k return r; 547 56.9k } 548 549 } 550 551 std::shared_ptr 552 CurveGFp::choose_repr(const BigInt& p, const BigInt& a, const BigInt& b) 553 2.18k { 554 2.18k if(p == prime_p192()) 555 50 return std::make_shared(a, b); 556 2.13k if(p == prime_p224()) 557 339 return std::make_shared(a, b); 558 1.80k if(p == prime_p256()) 559 22 return std::make_shared(a, b); 560 1.77k if(p == prime_p384()) 561 204 return std::make_shared(a, b); 562 1.57k if(p == prime_p521()) 563 368 return std::make_shared(a, b); 564 565 1.20k return std::make_shared(p, a, b); 566 1.57k } 567 568 }