The Tor Browser / annotate

security/nss/lib/freebl/ecl/ecp_256.c@b8a032363ba2 (annotated)

security/nss/lib/freebl/ecl/ecp_256.c

Thu, 22 Jan 2015 13:21:57 +0100

author
Michael Schloh von Bennewitz <michael@schloh.com>
date
Thu, 22 Jan 2015 13:21:57 +0100
branch
TOR_BUG_9701
changeset 15
b8a032363ba2
permissions
-rw-r--r--

Incorporate requested changes from Mozilla in review:
https://bugzilla.mozilla.org/show_bug.cgi?id=1123480#c6

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

Mercurial Repository: The Tor Browser

Europalab SCM Repository Server

mercurial