Botan
1.11.15
|
00001 /* 00002 * NIST curve reduction 00003 * (C) 2014,2015 Jack Lloyd 00004 * 00005 * Botan is released under the Simplified BSD License (see license.txt) 00006 */ 00007 00008 #include <botan/internal/curve_nistp.h> 00009 #include <botan/internal/mp_core.h> 00010 00011 namespace Botan { 00012 00013 void CurveGFp_NIST::curve_mul(BigInt& z, const BigInt& x, const BigInt& y, 00014 secure_vector<word>& ws) const 00015 { 00016 if(x.is_zero() || y.is_zero()) 00017 { 00018 z = 0; 00019 return; 00020 } 00021 00022 const size_t p_words = get_p_words(); 00023 const size_t output_size = 2*p_words + 1; 00024 ws.resize(2*(p_words+2)); 00025 00026 z.grow_to(output_size); 00027 z.clear(); 00028 00029 bigint_mul(z.mutable_data(), output_size, &ws[0], 00030 x.data(), x.size(), x.sig_words(), 00031 y.data(), y.size(), y.sig_words()); 00032 00033 this->redc(z, ws); 00034 } 00035 00036 void CurveGFp_NIST::curve_sqr(BigInt& z, const BigInt& x, 00037 secure_vector<word>& ws) const 00038 { 00039 if(x.is_zero()) 00040 { 00041 z = 0; 00042 return; 00043 } 00044 00045 const size_t p_words = get_p_words(); 00046 const size_t output_size = 2*p_words + 1; 00047 00048 ws.resize(2*(p_words+2)); 00049 00050 z.grow_to(output_size); 00051 z.clear(); 00052 00053 bigint_sqr(z.mutable_data(), output_size, &ws[0], 00054 x.data(), x.size(), x.sig_words()); 00055 00056 this->redc(z, ws); 00057 } 00058 00059 //static 00060 const BigInt& CurveGFp_P521::prime() 00061 { 00062 static const BigInt p521("0x1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" 00063 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"); 00064 00065 return p521; 00066 } 00067 00068 void CurveGFp_P521::redc(BigInt& x, secure_vector<word>& ws) const 00069 { 00070 const size_t p_words = get_p_words(); 00071 00072 const size_t shift_words = 521 / MP_WORD_BITS, 00073 shift_bits = 521 % MP_WORD_BITS; 00074 00075 const size_t x_sw = x.sig_words(); 00076 00077 if(x_sw < p_words) 00078 return; // already smaller 00079 00080 if(ws.size() < p_words + 1) 00081 ws.resize(p_words + 1); 00082 00083 clear_mem(&ws[0], ws.size()); 00084 bigint_shr2(&ws[0], x.data(), x_sw, shift_words, shift_bits); 00085 00086 x.mask_bits(521); 00087 00088 bigint_add3(x.mutable_data(), x.data(), p_words, &ws[0], p_words); 00089 00090 normalize(x, ws, max_redc_subtractions()); 00091 } 00092 00093 #if defined(BOTAN_HAS_CURVEGFP_NISTP_M32) 00094 00095 namespace { 00096 00097 /** 00098 * Treating this MPI as a sequence of 32-bit words in big-endian 00099 * order, return word i (or 0 if out of range) 00100 */ 00101 inline u32bit get_u32bit(const BigInt& x, size_t i) 00102 { 00103 #if (BOTAN_MP_WORD_BITS == 32) 00104 return x.word_at(i); 00105 #elif (BOTAN_MP_WORD_BITS == 64) 00106 return (x.word_at(i/2) >> ((i % 2)*32)); 00107 #else 00108 #error "Not implemented" 00109 #endif 00110 } 00111 00112 /** 00113 * Treating this MPI as a sequence of 32-bit words in big-endian 00114 * order, set word i to the value x 00115 */ 00116 inline void set_u32bit(BigInt& x, size_t i, u32bit v) 00117 { 00118 #if (BOTAN_MP_WORD_BITS == 32) 00119 x.set_word_at(i, v); 00120 #elif (BOTAN_MP_WORD_BITS == 64) 00121 const word shift_32 = (i % 2) * 32; 00122 const word w = (x.word_at(i/2) & (static_cast<word>(0xFFFFFFFF) << (32-shift_32))) | (static_cast<word>(v) << shift_32); 00123 x.set_word_at(i/2, w); 00124 #else 00125 #error "Not implemented" 00126 #endif 00127 } 00128 00129 } 00130 00131 //static 00132 const BigInt& CurveGFp_P192::prime() 00133 { 00134 static const BigInt p192("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFF"); 00135 return p192; 00136 } 00137 00138 void CurveGFp_P192::redc(BigInt& x, secure_vector<word>& ws) const 00139 { 00140 const u32bit X6 = get_u32bit(x, 6); 00141 const u32bit X7 = get_u32bit(x, 7); 00142 const u32bit X8 = get_u32bit(x, 8); 00143 const u32bit X9 = get_u32bit(x, 9); 00144 const u32bit X10 = get_u32bit(x, 10); 00145 const u32bit X11 = get_u32bit(x, 11); 00146 00147 x.mask_bits(192); 00148 00149 u64bit S = 0; 00150 00151 S += get_u32bit(x, 0); 00152 S += X6; 00153 S += X10; 00154 set_u32bit(x, 0, S); 00155 S >>= 32; 00156 00157 S += get_u32bit(x, 1); 00158 S += X7; 00159 S += X11; 00160 set_u32bit(x, 1, S); 00161 S >>= 32; 00162 00163 S += get_u32bit(x, 2); 00164 S += X6; 00165 S += X8; 00166 S += X10; 00167 set_u32bit(x, 2, S); 00168 S >>= 32; 00169 00170 S += get_u32bit(x, 3); 00171 S += X7; 00172 S += X9; 00173 S += X11; 00174 set_u32bit(x, 3, S); 00175 S >>= 32; 00176 00177 S += get_u32bit(x, 4); 00178 S += X8; 00179 S += X10; 00180 set_u32bit(x, 4, S); 00181 S >>= 32; 00182 00183 S += get_u32bit(x, 5); 00184 S += X9; 00185 S += X11; 00186 set_u32bit(x, 5, S); 00187 S >>= 32; 00188 00189 set_u32bit(x, 6, S); 00190 00191 // No underflow possible 00192 00193 normalize(x, ws, max_redc_subtractions()); 00194 } 00195 00196 //static 00197 const BigInt& CurveGFp_P224::prime() 00198 { 00199 static const BigInt p224("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF000000000000000000000001"); 00200 return p224; 00201 } 00202 00203 void CurveGFp_P224::redc(BigInt& x, secure_vector<word>& ws) const 00204 { 00205 const u32bit X7 = get_u32bit(x, 7); 00206 const u32bit X8 = get_u32bit(x, 8); 00207 const u32bit X9 = get_u32bit(x, 9); 00208 const u32bit X10 = get_u32bit(x, 10); 00209 const u32bit X11 = get_u32bit(x, 11); 00210 const u32bit X12 = get_u32bit(x, 12); 00211 const u32bit X13 = get_u32bit(x, 13); 00212 00213 x.mask_bits(224); 00214 00215 // One full copy of P224 is added, so the result is always positive 00216 00217 int64_t S = 0; 00218 00219 S += get_u32bit(x, 0); 00220 S += 1; 00221 S -= X7; 00222 S -= X11; 00223 set_u32bit(x, 0, S); 00224 S >>= 32; 00225 00226 S += get_u32bit(x, 1); 00227 S -= X8; 00228 S -= X12; 00229 set_u32bit(x, 1, S); 00230 S >>= 32; 00231 00232 S += get_u32bit(x, 2); 00233 S -= X9; 00234 S -= X13; 00235 set_u32bit(x, 2, S); 00236 S >>= 32; 00237 00238 S += get_u32bit(x, 3); 00239 S += 0xFFFFFFFF; 00240 S += X7; 00241 S += X11; 00242 S -= X10; 00243 set_u32bit(x, 3, S); 00244 S >>= 32; 00245 00246 S += get_u32bit(x, 4); 00247 S += 0xFFFFFFFF; 00248 S += X8; 00249 S += X12; 00250 S -= X11; 00251 set_u32bit(x, 4, S); 00252 S >>= 32; 00253 00254 S += get_u32bit(x, 5); 00255 S += 0xFFFFFFFF; 00256 S += X9; 00257 S += X13; 00258 S -= X12; 00259 set_u32bit(x, 5, S); 00260 S >>= 32; 00261 00262 S += get_u32bit(x, 6); 00263 S += 0xFFFFFFFF; 00264 S += X10; 00265 S -= X13; 00266 set_u32bit(x, 6, S); 00267 S >>= 32; 00268 set_u32bit(x, 7, S); 00269 00270 BOTAN_ASSERT_EQUAL(S >> 32, 0, "No underflow"); 00271 00272 normalize(x, ws, max_redc_subtractions()); 00273 } 00274 00275 //static 00276 const BigInt& CurveGFp_P256::prime() 00277 { 00278 static const BigInt p256("0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF"); 00279 return p256; 00280 } 00281 00282 void CurveGFp_P256::redc(BigInt& x, secure_vector<word>& ws) const 00283 { 00284 const u32bit X8 = get_u32bit(x, 8); 00285 const u32bit X9 = get_u32bit(x, 9); 00286 const u32bit X10 = get_u32bit(x, 10); 00287 const u32bit X11 = get_u32bit(x, 11); 00288 const u32bit X12 = get_u32bit(x, 12); 00289 const u32bit X13 = get_u32bit(x, 13); 00290 const u32bit X14 = get_u32bit(x, 14); 00291 const u32bit X15 = get_u32bit(x, 15); 00292 00293 x.mask_bits(256); 00294 00295 int64_t S = 0; 00296 00297 // Adds 6 * P-256 to prevent underflow 00298 00299 S = get_u32bit(x, 0); 00300 S += 0xFFFFFFFA; 00301 S += X8; 00302 S += X9; 00303 S -= X11; 00304 S -= X12; 00305 S -= X13; 00306 S -= X14; 00307 set_u32bit(x, 0, S); 00308 S >>= 32; 00309 00310 S += get_u32bit(x, 1); 00311 S += 0xFFFFFFFF; 00312 S += X9; 00313 S += X10; 00314 S -= X12; 00315 S -= X13; 00316 S -= X14; 00317 S -= X15; 00318 set_u32bit(x, 1, S); 00319 S >>= 32; 00320 00321 S += get_u32bit(x, 2); 00322 S += 0xFFFFFFFF; 00323 S += X10; 00324 S += X11; 00325 S -= X13; 00326 S -= X14; 00327 S -= X15; 00328 set_u32bit(x, 2, S); 00329 S >>= 32; 00330 00331 S += get_u32bit(x, 3); 00332 S += 5; 00333 S += X11; 00334 S += X11; 00335 S += X12; 00336 S += X12; 00337 S += X13; 00338 S -= X15; 00339 S -= X8; 00340 S -= X9; 00341 set_u32bit(x, 3, S); 00342 S >>= 32; 00343 00344 S += get_u32bit(x, 4); 00345 S += X12; 00346 S += X12; 00347 S += X13; 00348 S += X13; 00349 S += X14; 00350 S -= X9; 00351 S -= X10; 00352 set_u32bit(x, 4, S); 00353 S >>= 32; 00354 00355 S += get_u32bit(x, 5); 00356 S += X13; 00357 S += X13; 00358 S += X14; 00359 S += X14; 00360 S += X15; 00361 S -= X10; 00362 S -= X11; 00363 set_u32bit(x, 5, S); 00364 S >>= 32; 00365 00366 S += get_u32bit(x, 6); 00367 S += 6; 00368 S += X14; 00369 S += X14; 00370 S += X15; 00371 S += X15; 00372 S += X14; 00373 S += X13; 00374 S -= X8; 00375 S -= X9; 00376 set_u32bit(x, 6, S); 00377 S >>= 32; 00378 00379 S += get_u32bit(x, 7); 00380 S += 0xFFFFFFFA; 00381 S += X15; 00382 S += X15; 00383 S += X15; 00384 S += X8; 00385 S -= X10; 00386 S -= X11; 00387 S -= X12; 00388 S -= X13; 00389 set_u32bit(x, 7, S); 00390 S >>= 32; 00391 00392 S += 5; 00393 set_u32bit(x, 8, S); 00394 00395 BOTAN_ASSERT_EQUAL(S >> 32, 0, "No underflow"); 00396 00397 if(S >= 2) 00398 { 00399 BOTAN_ASSERT(S <= 10, "Expected overflow"); 00400 static const BigInt P256_mults[9] = { 00401 2*get_p(), 00402 3*get_p(), 00403 4*get_p(), 00404 5*get_p(), 00405 6*get_p(), 00406 7*get_p(), 00407 8*get_p(), 00408 9*get_p(), 00409 10*get_p() 00410 }; 00411 x -= P256_mults[S - 2]; 00412 } 00413 00414 normalize(x, ws, max_redc_subtractions()); 00415 } 00416 00417 //static 00418 const BigInt& CurveGFp_P384::prime() 00419 { 00420 static const BigInt p384("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFF0000000000000000FFFFFFFF"); 00421 return p384; 00422 } 00423 00424 void CurveGFp_P384::redc(BigInt& x, secure_vector<word>& ws) const 00425 { 00426 const u32bit X12 = get_u32bit(x, 12); 00427 const u32bit X13 = get_u32bit(x, 13); 00428 const u32bit X14 = get_u32bit(x, 14); 00429 const u32bit X15 = get_u32bit(x, 15); 00430 const u32bit X16 = get_u32bit(x, 16); 00431 const u32bit X17 = get_u32bit(x, 17); 00432 const u32bit X18 = get_u32bit(x, 18); 00433 const u32bit X19 = get_u32bit(x, 19); 00434 const u32bit X20 = get_u32bit(x, 20); 00435 const u32bit X21 = get_u32bit(x, 21); 00436 const u32bit X22 = get_u32bit(x, 22); 00437 const u32bit X23 = get_u32bit(x, 23); 00438 00439 x.mask_bits(384); 00440 00441 int64_t S = 0; 00442 00443 // One copy of P-384 is added to prevent underflow 00444 S = get_u32bit(x, 0); 00445 S += 0xFFFFFFFF; 00446 S += X12; 00447 S += X21; 00448 S += X20; 00449 S -= X23; 00450 set_u32bit(x, 0, S); 00451 S >>= 32; 00452 00453 S += get_u32bit(x, 1); 00454 S += X13; 00455 S += X22; 00456 S += X23; 00457 S -= X12; 00458 S -= X20; 00459 set_u32bit(x, 1, S); 00460 S >>= 32; 00461 00462 S += get_u32bit(x, 2); 00463 S += X14; 00464 S += X23; 00465 S -= X13; 00466 S -= X21; 00467 set_u32bit(x, 2, S); 00468 S >>= 32; 00469 00470 S += get_u32bit(x, 3); 00471 S += 0xFFFFFFFF; 00472 S += X15; 00473 S += X12; 00474 S += X20; 00475 S += X21; 00476 S -= X14; 00477 S -= X22; 00478 S -= X23; 00479 set_u32bit(x, 3, S); 00480 S >>= 32; 00481 00482 S += get_u32bit(x, 4); 00483 S += 0xFFFFFFFE; 00484 S += X21; 00485 S += X21; 00486 S += X16; 00487 S += X13; 00488 S += X12; 00489 S += X20; 00490 S += X22; 00491 S -= X15; 00492 S -= X23; 00493 S -= X23; 00494 set_u32bit(x, 4, S); 00495 S >>= 32; 00496 00497 S += get_u32bit(x, 5); 00498 S += 0xFFFFFFFF; 00499 S += X22; 00500 S += X22; 00501 S += X17; 00502 S += X14; 00503 S += X13; 00504 S += X21; 00505 S += X23; 00506 S -= X16; 00507 set_u32bit(x, 5, S); 00508 S >>= 32; 00509 00510 S += get_u32bit(x, 6); 00511 S += 0xFFFFFFFF; 00512 S += X23; 00513 S += X23; 00514 S += X18; 00515 S += X15; 00516 S += X14; 00517 S += X22; 00518 S -= X17; 00519 set_u32bit(x, 6, S); 00520 S >>= 32; 00521 00522 S += get_u32bit(x, 7); 00523 S += 0xFFFFFFFF; 00524 S += X19; 00525 S += X16; 00526 S += X15; 00527 S += X23; 00528 S -= X18; 00529 set_u32bit(x, 7, S); 00530 S >>= 32; 00531 00532 S += get_u32bit(x, 8); 00533 S += 0xFFFFFFFF; 00534 S += X20; 00535 S += X17; 00536 S += X16; 00537 S -= X19; 00538 set_u32bit(x, 8, S); 00539 S >>= 32; 00540 00541 S += get_u32bit(x, 9); 00542 S += 0xFFFFFFFF; 00543 S += X21; 00544 S += X18; 00545 S += X17; 00546 S -= X20; 00547 set_u32bit(x, 9, S); 00548 S >>= 32; 00549 00550 S += get_u32bit(x, 10); 00551 S += 0xFFFFFFFF; 00552 S += X22; 00553 S += X19; 00554 S += X18; 00555 S -= X21; 00556 set_u32bit(x, 10, S); 00557 S >>= 32; 00558 00559 S += get_u32bit(x, 11); 00560 S += 0xFFFFFFFF; 00561 S += X23; 00562 S += X20; 00563 S += X19; 00564 S -= X22; 00565 set_u32bit(x, 11, S); 00566 S >>= 32; 00567 BOTAN_ASSERT_EQUAL(S >> 32, 0, "No underflow"); 00568 set_u32bit(x, 12, S); 00569 00570 if(S >= 2) 00571 { 00572 BOTAN_ASSERT(S <= 4, "Expected overflow"); 00573 00574 static const BigInt P384_mults[3] = { 00575 2*get_p(), 00576 3*get_p(), 00577 4*get_p() 00578 }; 00579 00580 x -= P384_mults[S - 2]; 00581 } 00582 00583 normalize(x, ws, max_redc_subtractions()); 00584 } 00585 00586 #endif 00587 00588 00589 }