| OLD | NEW |
|---|
| (Empty) |
| 1 /* This Source Code Form is subject to the terms of the Mozilla Public | |
| 2 * License, v. 2.0. If a copy of the MPL was not distributed with this | |
| 3 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ | |
| 4 | |
| 5 #include "ecp.h" | |
| 6 #include "mpi.h" | |
| 7 #include "mplogic.h" | |
| 8 #include "mpi-priv.h" | |
| 9 | |
| 10 /* Fast modular reduction for p256 = 2^256 - 2^224 + 2^192+ 2^96 - 1. a can be
r. | |
| 11 * Uses algorithm 2.29 from Hankerson, Menezes, Vanstone. Guide to | |
| 12 * Elliptic Curve Cryptography. */ | |
| 13 static mp_err | |
| 14 ec_GFp_nistp256_mod(const mp_int *a, mp_int *r, const GFMethod *meth) | |
| 15 { | |
| 16 mp_err res = MP_OKAY; | |
| 17 mp_size a_used = MP_USED(a); | |
| 18 int a_bits = mpl_significant_bits(a); | |
| 19 mp_digit carry; | |
| 20 | |
| 21 #ifdef ECL_THIRTY_TWO_BIT | |
| 22 mp_digit a8=0, a9=0, a10=0, a11=0, a12=0, a13=0, a14=0, a15=0; | |
| 23 mp_digit r0, r1, r2, r3, r4, r5, r6, r7; | |
| 24 int r8; /* must be a signed value ! */ | |
| 25 #else | |
| 26 mp_digit a4=0, a5=0, a6=0, a7=0; | |
| 27 mp_digit a4h, a4l, a5h, a5l, a6h, a6l, a7h, a7l; | |
| 28 mp_digit r0, r1, r2, r3; | |
| 29 int r4; /* must be a signed value ! */ | |
| 30 #endif | |
| 31 /* for polynomials larger than twice the field size | |
| 32 * use regular reduction */ | |
| 33 if (a_bits < 256) { | |
| 34 if (a == r) return MP_OKAY; | |
| 35 return mp_copy(a,r); | |
| 36 } | |
| 37 if (a_bits > 512) { | |
| 38 MP_CHECKOK(mp_mod(a, &meth->irr, r)); | |
| 39 } else { | |
| 40 | |
| 41 #ifdef ECL_THIRTY_TWO_BIT | |
| 42 switch (a_used) { | |
| 43 case 16: | |
| 44 a15 = MP_DIGIT(a,15); | |
| 45 case 15: | |
| 46 a14 = MP_DIGIT(a,14); | |
| 47 case 14: | |
| 48 a13 = MP_DIGIT(a,13); | |
| 49 case 13: | |
| 50 a12 = MP_DIGIT(a,12); | |
| 51 case 12: | |
| 52 a11 = MP_DIGIT(a,11); | |
| 53 case 11: | |
| 54 a10 = MP_DIGIT(a,10); | |
| 55 case 10: | |
| 56 a9 = MP_DIGIT(a,9); | |
| 57 case 9: | |
| 58 a8 = MP_DIGIT(a,8); | |
| 59 } | |
| 60 | |
| 61 r0 = MP_DIGIT(a,0); | |
| 62 r1 = MP_DIGIT(a,1); | |
| 63 r2 = MP_DIGIT(a,2); | |
| 64 r3 = MP_DIGIT(a,3); | |
| 65 r4 = MP_DIGIT(a,4); | |
| 66 r5 = MP_DIGIT(a,5); | |
| 67 r6 = MP_DIGIT(a,6); | |
| 68 r7 = MP_DIGIT(a,7); | |
| 69 | |
| 70 /* sum 1 */ | |
| 71 carry = 0; | |
| 72 MP_ADD_CARRY(r3, a11, r3, carry); | |
| 73 MP_ADD_CARRY(r4, a12, r4, carry); | |
| 74 MP_ADD_CARRY(r5, a13, r5, carry); | |
| 75 MP_ADD_CARRY(r6, a14, r6, carry); | |
| 76 MP_ADD_CARRY(r7, a15, r7, carry); | |
| 77 r8 = carry; carry = 0; | |
| 78 MP_ADD_CARRY(r3, a11, r3, carry); | |
| 79 MP_ADD_CARRY(r4, a12, r4, carry); | |
| 80 MP_ADD_CARRY(r5, a13, r5, carry); | |
| 81 MP_ADD_CARRY(r6, a14, r6, carry); | |
| 82 MP_ADD_CARRY(r7, a15, r7, carry); | |
| 83 r8 += carry; carry = 0; | |
| 84 /* sum 2 */ | |
| 85 MP_ADD_CARRY(r3, a12, r3, carry); | |
| 86 MP_ADD_CARRY(r4, a13, r4, carry); | |
| 87 MP_ADD_CARRY(r5, a14, r5, carry); | |
| 88 MP_ADD_CARRY(r6, a15, r6, carry); | |
| 89 MP_ADD_CARRY(r7, 0, r7, carry); | |
| 90 r8 += carry; carry = 0; | |
| 91 /* combine last bottom of sum 3 with second sum 2 */ | |
| 92 MP_ADD_CARRY(r0, a8, r0, carry); | |
| 93 MP_ADD_CARRY(r1, a9, r1, carry); | |
| 94 MP_ADD_CARRY(r2, a10, r2, carry); | |
| 95 MP_ADD_CARRY(r3, a12, r3, carry); | |
| 96 MP_ADD_CARRY(r4, a13, r4, carry); | |
| 97 MP_ADD_CARRY(r5, a14, r5, carry); | |
| 98 MP_ADD_CARRY(r6, a15, r6, carry); | |
| 99 MP_ADD_CARRY(r7, a15, r7, carry); /* from sum 3 */ | |
| 100 r8 += carry; carry = 0; | |
| 101 /* sum 3 (rest of it)*/ | |
| 102 MP_ADD_CARRY(r6, a14, r6, carry); | |
| 103 MP_ADD_CARRY(r7, 0, r7, carry); | |
| 104 r8 += carry; carry = 0; | |
| 105 /* sum 4 (rest of it)*/ | |
| 106 MP_ADD_CARRY(r0, a9, r0, carry); | |
| 107 MP_ADD_CARRY(r1, a10, r1, carry); | |
| 108 MP_ADD_CARRY(r2, a11, r2, carry); | |
| 109 MP_ADD_CARRY(r3, a13, r3, carry); | |
| 110 MP_ADD_CARRY(r4, a14, r4, carry); | |
| 111 MP_ADD_CARRY(r5, a15, r5, carry); | |
| 112 MP_ADD_CARRY(r6, a13, r6, carry); | |
| 113 MP_ADD_CARRY(r7, a8, r7, carry); | |
| 114 r8 += carry; carry = 0; | |
| 115 /* diff 5 */ | |
| 116 MP_SUB_BORROW(r0, a11, r0, carry); | |
| 117 MP_SUB_BORROW(r1, a12, r1, carry); | |
| 118 MP_SUB_BORROW(r2, a13, r2, carry); | |
| 119 MP_SUB_BORROW(r3, 0, r3, carry); | |
| 120 MP_SUB_BORROW(r4, 0, r4, carry); | |
| 121 MP_SUB_BORROW(r5, 0, r5, carry); | |
| 122 MP_SUB_BORROW(r6, a8, r6, carry); | |
| 123 MP_SUB_BORROW(r7, a10, r7, carry); | |
| 124 r8 -= carry; carry = 0; | |
| 125 /* diff 6 */ | |
| 126 MP_SUB_BORROW(r0, a12, r0, carry); | |
| 127 MP_SUB_BORROW(r1, a13, r1, carry); | |
| 128 MP_SUB_BORROW(r2, a14, r2, carry); | |
| 129 MP_SUB_BORROW(r3, a15, r3, carry); | |
| 130 MP_SUB_BORROW(r4, 0, r4, carry); | |
| 131 MP_SUB_BORROW(r5, 0, r5, carry); | |
| 132 MP_SUB_BORROW(r6, a9, r6, carry); | |
| 133 MP_SUB_BORROW(r7, a11, r7, carry); | |
| 134 r8 -= carry; carry = 0; | |
| 135 /* diff 7 */ | |
| 136 MP_SUB_BORROW(r0, a13, r0, carry); | |
| 137 MP_SUB_BORROW(r1, a14, r1, carry); | |
| 138 MP_SUB_BORROW(r2, a15, r2, carry); | |
| 139 MP_SUB_BORROW(r3, a8, r3, carry); | |
| 140 MP_SUB_BORROW(r4, a9, r4, carry); | |
| 141 MP_SUB_BORROW(r5, a10, r5, carry); | |
| 142 MP_SUB_BORROW(r6, 0, r6, carry); | |
| 143 MP_SUB_BORROW(r7, a12, r7, carry); | |
| 144 r8 -= carry; carry = 0; | |
| 145 /* diff 8 */ | |
| 146 MP_SUB_BORROW(r0, a14, r0, carry); | |
| 147 MP_SUB_BORROW(r1, a15, r1, carry); | |
| 148 MP_SUB_BORROW(r2, 0, r2, carry); | |
| 149 MP_SUB_BORROW(r3, a9, r3, carry); | |
| 150 MP_SUB_BORROW(r4, a10, r4, carry); | |
| 151 MP_SUB_BORROW(r5, a11, r5, carry); | |
| 152 MP_SUB_BORROW(r6, 0, r6, carry); | |
| 153 MP_SUB_BORROW(r7, a13, r7, carry); | |
| 154 r8 -= carry; | |
| 155 | |
| 156 /* reduce the overflows */ | |
| 157 while (r8 > 0) { | |
| 158 mp_digit r8_d = r8; carry = 0; | |
| 159 carry = 0; | |
| 160 MP_ADD_CARRY(r0, r8_d, r0, carry); | |
| 161 MP_ADD_CARRY(r1, 0, r1, carry); | |
| 162 MP_ADD_CARRY(r2, 0, r2, carry); | |
| 163 MP_ADD_CARRY(r3, 0-r8_d, r3, carry); | |
| 164 MP_ADD_CARRY(r4, MP_DIGIT_MAX, r4, carry); | |
| 165 MP_ADD_CARRY(r5, MP_DIGIT_MAX, r5, carry); | |
| 166 MP_ADD_CARRY(r6, 0-(r8_d+1), r6, carry); | |
| 167 MP_ADD_CARRY(r7, (r8_d-1), r7, carry); | |
| 168 r8 = carry; | |
| 169 } | |
| 170 | |
| 171 /* reduce the underflows */ | |
| 172 while (r8 < 0) { | |
| 173 mp_digit r8_d = -r8; | |
| 174 carry = 0; | |
| 175 MP_SUB_BORROW(r0, r8_d, r0, carry); | |
| 176 MP_SUB_BORROW(r1, 0, r1, carry); | |
| 177 MP_SUB_BORROW(r2, 0, r2, carry); | |
| 178 MP_SUB_BORROW(r3, 0-r8_d, r3, carry); | |
| 179 MP_SUB_BORROW(r4, MP_DIGIT_MAX, r4, carry); | |
| 180 MP_SUB_BORROW(r5, MP_DIGIT_MAX, r5, carry); | |
| 181 MP_SUB_BORROW(r6, 0-(r8_d+1), r6, carry); | |
| 182 MP_SUB_BORROW(r7, (r8_d-1), r7, carry); | |
| 183 r8 = 0-carry; | |
| 184 } | |
| 185 if (a != r) { | |
| 186 MP_CHECKOK(s_mp_pad(r,8)); | |
| 187 } | |
| 188 MP_SIGN(r) = MP_ZPOS; | |
| 189 MP_USED(r) = 8; | |
| 190 | |
| 191 MP_DIGIT(r,7) = r7; | |
| 192 MP_DIGIT(r,6) = r6; | |
| 193 MP_DIGIT(r,5) = r5; | |
| 194 MP_DIGIT(r,4) = r4; | |
| 195 MP_DIGIT(r,3) = r3; | |
| 196 MP_DIGIT(r,2) = r2; | |
| 197 MP_DIGIT(r,1) = r1; | |
| 198 MP_DIGIT(r,0) = r0; | |
| 199 | |
| 200 /* final reduction if necessary */ | |
| 201 if ((r7 == MP_DIGIT_MAX) && | |
| 202 ((r6 > 1) || ((r6 == 1) && | |
| 203 (r5 || r4 || r3 || | |
| 204 ((r2 == MP_DIGIT_MAX) && (r1 == MP_DIGIT_MAX) | |
| 205 && (r0 == MP_DIGIT_MAX)))))) { | |
| 206 MP_CHECKOK(mp_sub(r, &meth->irr, r)); | |
| 207 } | |
| 208 | |
| 209 s_mp_clamp(r); | |
| 210 #else | |
| 211 switch (a_used) { | |
| 212 case 8: | |
| 213 a7 = MP_DIGIT(a,7); | |
| 214 case 7: | |
| 215 a6 = MP_DIGIT(a,6); | |
| 216 case 6: | |
| 217 a5 = MP_DIGIT(a,5); | |
| 218 case 5: | |
| 219 a4 = MP_DIGIT(a,4); | |
| 220 } | |
| 221 a7l = a7 << 32; | |
| 222 a7h = a7 >> 32; | |
| 223 a6l = a6 << 32; | |
| 224 a6h = a6 >> 32; | |
| 225 a5l = a5 << 32; | |
| 226 a5h = a5 >> 32; | |
| 227 a4l = a4 << 32; | |
| 228 a4h = a4 >> 32; | |
| 229 r3 = MP_DIGIT(a,3); | |
| 230 r2 = MP_DIGIT(a,2); | |
| 231 r1 = MP_DIGIT(a,1); | |
| 232 r0 = MP_DIGIT(a,0); | |
| 233 | |
| 234 /* sum 1 */ | |
| 235 carry = 0; | |
| 236 carry = 0; | |
| 237 MP_ADD_CARRY(r1, a5h << 32, r1, carry); | |
| 238 MP_ADD_CARRY(r2, a6, r2, carry); | |
| 239 MP_ADD_CARRY(r3, a7, r3, carry); | |
| 240 r4 = carry; carry = 0; | |
| 241 carry = 0; | |
| 242 MP_ADD_CARRY(r1, a5h << 32, r1, carry); | |
| 243 MP_ADD_CARRY(r2, a6, r2, carry); | |
| 244 MP_ADD_CARRY(r3, a7, r3, carry); | |
| 245 r4 += carry; carry = 0; | |
| 246 /* sum 2 */ | |
| 247 carry = 0; | |
| 248 MP_ADD_CARRY(r1, a6l, r1, carry); | |
| 249 MP_ADD_CARRY(r2, a6h | a7l, r2, carry); | |
| 250 MP_ADD_CARRY(r3, a7h, r3, carry); | |
| 251 r4 += carry; carry = 0; | |
| 252 carry = 0; | |
| 253 MP_ADD_CARRY(r1, a6l, r1, carry); | |
| 254 MP_ADD_CARRY(r2, a6h | a7l, r2, carry); | |
| 255 MP_ADD_CARRY(r3, a7h, r3, carry); | |
| 256 r4 += carry; carry = 0; | |
| 257 | |
| 258 /* sum 3 */ | |
| 259 carry = 0; | |
| 260 MP_ADD_CARRY(r0, a4, r0, carry); | |
| 261 MP_ADD_CARRY(r1, a5l >> 32, r1, carry); | |
| 262 MP_ADD_CARRY(r2, 0, r2, carry); | |
| 263 MP_ADD_CARRY(r3, a7, r3, carry); | |
| 264 r4 += carry; carry = 0; | |
| 265 /* sum 4 */ | |
| 266 carry = 0; | |
| 267 MP_ADD_CARRY(r0, a4h | a5l, r0, carry); | |
| 268 MP_ADD_CARRY(r1, a5h|(a6h<<32), r1, carry); | |
| 269 MP_ADD_CARRY(r2, a7, r2, carry); | |
| 270 MP_ADD_CARRY(r3, a6h | a4l, r3, carry); | |
| 271 r4 += carry; | |
| 272 /* diff 5 */ | |
| 273 carry = 0; | |
| 274 MP_SUB_BORROW(r0, a5h | a6l, r0, carry); | |
| 275 MP_SUB_BORROW(r1, a6h, r1, carry); | |
| 276 MP_SUB_BORROW(r2, 0, r2, carry); | |
| 277 MP_SUB_BORROW(r3, (a4l>>32)|a5l,r3, carry); | |
| 278 r4 -= carry; | |
| 279 /* diff 6 */ | |
| 280 carry = 0; | |
| 281 MP_SUB_BORROW(r0, a6, r0, carry); | |
| 282 MP_SUB_BORROW(r1, a7, r1, carry); | |
| 283 MP_SUB_BORROW(r2, 0, r2, carry); | |
| 284 MP_SUB_BORROW(r3, a4h|(a5h<<32),r3, carry); | |
| 285 r4 -= carry; | |
| 286 /* diff 7 */ | |
| 287 carry = 0; | |
| 288 MP_SUB_BORROW(r0, a6h|a7l, r0, carry); | |
| 289 MP_SUB_BORROW(r1, a7h|a4l, r1, carry); | |
| 290 MP_SUB_BORROW(r2, a4h|a5l, r2, carry); | |
| 291 MP_SUB_BORROW(r3, a6l, r3, carry); | |
| 292 r4 -= carry; | |
| 293 /* diff 8 */ | |
| 294 carry = 0; | |
| 295 MP_SUB_BORROW(r0, a7, r0, carry); | |
| 296 MP_SUB_BORROW(r1, a4h<<32, r1, carry); | |
| 297 MP_SUB_BORROW(r2, a5, r2, carry); | |
| 298 MP_SUB_BORROW(r3, a6h<<32, r3, carry); | |
| 299 r4 -= carry; | |
| 300 | |
| 301 /* reduce the overflows */ | |
| 302 while (r4 > 0) { | |
| 303 mp_digit r4_long = r4; | |
| 304 mp_digit r4l = (r4_long << 32); | |
| 305 carry = 0; | |
| 306 carry = 0; | |
| 307 MP_ADD_CARRY(r0, r4_long, r0, carry); | |
| 308 MP_ADD_CARRY(r1, 0-r4l, r1, carry); | |
| 309 MP_ADD_CARRY(r2, MP_DIGIT_MAX, r2, carry); | |
| 310 MP_ADD_CARRY(r3, r4l-r4_long-1,r3, carry); | |
| 311 r4 = carry; | |
| 312 } | |
| 313 | |
| 314 /* reduce the underflows */ | |
| 315 while (r4 < 0) { | |
| 316 mp_digit r4_long = -r4; | |
| 317 mp_digit r4l = (r4_long << 32); | |
| 318 carry = 0; | |
| 319 MP_SUB_BORROW(r0, r4_long, r0, carry); | |
| 320 MP_SUB_BORROW(r1, 0-r4l, r1, carry); | |
| 321 MP_SUB_BORROW(r2, MP_DIGIT_MAX, r2, carry); | |
| 322 MP_SUB_BORROW(r3, r4l-r4_long-1,r3, carry); | |
| 323 r4 = 0-carry; | |
| 324 } | |
| 325 | |
| 326 if (a != r) { | |
| 327 MP_CHECKOK(s_mp_pad(r,4)); | |
| 328 } | |
| 329 MP_SIGN(r) = MP_ZPOS; | |
| 330 MP_USED(r) = 4; | |
| 331 | |
| 332 MP_DIGIT(r,3) = r3; | |
| 333 MP_DIGIT(r,2) = r2; | |
| 334 MP_DIGIT(r,1) = r1; | |
| 335 MP_DIGIT(r,0) = r0; | |
| 336 | |
| 337 /* final reduction if necessary */ | |
| 338 if ((r3 > 0xFFFFFFFF00000001ULL) || | |
| 339 ((r3 == 0xFFFFFFFF00000001ULL) && | |
| 340 (r2 || (r1 >> 32)|| | |
| 341 (r1 == 0xFFFFFFFFULL && r0 == MP_DIGIT_MAX)))) { | |
| 342 /* very rare, just use mp_sub */ | |
| 343 MP_CHECKOK(mp_sub(r, &meth->irr, r)); | |
| 344 } | |
| 345 | |
| 346 s_mp_clamp(r); | |
| 347 #endif | |
| 348 } | |
| 349 | |
| 350 CLEANUP: | |
| 351 return res; | |
| 352 } | |
| 353 | |
| 354 /* Compute the square of polynomial a, reduce modulo p256. Store the | |
| 355 * result in r. r could be a. Uses optimized modular reduction for p256. | |
| 356 */ | |
| 357 static mp_err | |
| 358 ec_GFp_nistp256_sqr(const mp_int *a, mp_int *r, const GFMethod *meth) | |
| 359 { | |
| 360 mp_err res = MP_OKAY; | |
| 361 | |
| 362 MP_CHECKOK(mp_sqr(a, r)); | |
| 363 MP_CHECKOK(ec_GFp_nistp256_mod(r, r, meth)); | |
| 364 CLEANUP: | |
| 365 return res; | |
| 366 } | |
| 367 | |
| 368 /* Compute the product of two polynomials a and b, reduce modulo p256. | |
| 369 * Store the result in r. r could be a or b; a could be b. Uses | |
| 370 * optimized modular reduction for p256. */ | |
| 371 static mp_err | |
| 372 ec_GFp_nistp256_mul(const mp_int *a, const mp_int *b, mp_int *r, | |
| 373 const GFMethod *meth) | |
| 374 { | |
| 375 mp_err res = MP_OKAY; | |
| 376 | |
| 377 MP_CHECKOK(mp_mul(a, b, r)); | |
| 378 MP_CHECKOK(ec_GFp_nistp256_mod(r, r, meth)); | |
| 379 CLEANUP: | |
| 380 return res; | |
| 381 } | |
| 382 | |
| 383 /* Wire in fast field arithmetic and precomputation of base point for | |
| 384 * named curves. */ | |
| 385 mp_err | |
| 386 ec_group_set_gfp256(ECGroup *group, ECCurveName name) | |
| 387 { | |
| 388 if (name == ECCurve_NIST_P256) { | |
| 389 group->meth->field_mod = &ec_GFp_nistp256_mod; | |
| 390 group->meth->field_mul = &ec_GFp_nistp256_mul; | |
| 391 group->meth->field_sqr = &ec_GFp_nistp256_sqr; | |
| 392 } | |
| 393 return MP_OKAY; | |
| 394 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 2078763002:
Delete bundled copy of NSS and replace with README. (Closed)
Base URL: https://chromium.googlesource.com/chromium/deps/nss@master