| 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 "mp_gf2m.h" | |
| 6 #include "mp_gf2m-priv.h" | |
| 7 #include "mplogic.h" | |
| 8 #include "mpi-priv.h" | |
| 9 | |
| 10 const mp_digit mp_gf2m_sqr_tb[16] = | |
| 11 { | |
| 12 0, 1, 4, 5, 16, 17, 20, 21, | |
| 13 64, 65, 68, 69, 80, 81, 84, 85 | |
| 14 }; | |
| 15 | |
| 16 /* Multiply two binary polynomials mp_digits a, b. | |
| 17 * Result is a polynomial with degree < 2 * MP_DIGIT_BITS - 1. | |
| 18 * Output in two mp_digits rh, rl. | |
| 19 */ | |
| 20 #if MP_DIGIT_BITS == 32 | |
| 21 void | |
| 22 s_bmul_1x1(mp_digit *rh, mp_digit *rl, const mp_digit a, const mp_digit b) | |
| 23 { | |
| 24 register mp_digit h, l, s; | |
| 25 mp_digit tab[8], top2b = a >> 30; | |
| 26 register mp_digit a1, a2, a4; | |
| 27 | |
| 28 a1 = a & (0x3FFFFFFF); a2 = a1 << 1; a4 = a2 << 1; | |
| 29 | |
| 30 tab[0] = 0; tab[1] = a1; tab[2] = a2; tab[3] = a1^a2; | |
| 31 tab[4] = a4; tab[5] = a1^a4; tab[6] = a2^a4; tab[7] = a1^a2^a4; | |
| 32 | |
| 33 s = tab[b & 0x7]; l = s; | |
| 34 s = tab[b >> 3 & 0x7]; l ^= s << 3; h = s >> 29; | |
| 35 s = tab[b >> 6 & 0x7]; l ^= s << 6; h ^= s >> 26; | |
| 36 s = tab[b >> 9 & 0x7]; l ^= s << 9; h ^= s >> 23; | |
| 37 s = tab[b >> 12 & 0x7]; l ^= s << 12; h ^= s >> 20; | |
| 38 s = tab[b >> 15 & 0x7]; l ^= s << 15; h ^= s >> 17; | |
| 39 s = tab[b >> 18 & 0x7]; l ^= s << 18; h ^= s >> 14; | |
| 40 s = tab[b >> 21 & 0x7]; l ^= s << 21; h ^= s >> 11; | |
| 41 s = tab[b >> 24 & 0x7]; l ^= s << 24; h ^= s >> 8; | |
| 42 s = tab[b >> 27 & 0x7]; l ^= s << 27; h ^= s >> 5; | |
| 43 s = tab[b >> 30 ]; l ^= s << 30; h ^= s >> 2; | |
| 44 | |
| 45 /* compensate for the top two bits of a */ | |
| 46 | |
| 47 if (top2b & 01) { l ^= b << 30; h ^= b >> 2; } | |
| 48 if (top2b & 02) { l ^= b << 31; h ^= b >> 1; } | |
| 49 | |
| 50 *rh = h; *rl = l; | |
| 51 } | |
| 52 #else | |
| 53 void | |
| 54 s_bmul_1x1(mp_digit *rh, mp_digit *rl, const mp_digit a, const mp_digit b) | |
| 55 { | |
| 56 register mp_digit h, l, s; | |
| 57 mp_digit tab[16], top3b = a >> 61; | |
| 58 register mp_digit a1, a2, a4, a8; | |
| 59 | |
| 60 a1 = a & (0x1FFFFFFFFFFFFFFFULL); a2 = a1 << 1; | |
| 61 a4 = a2 << 1; a8 = a4 << 1; | |
| 62 tab[ 0] = 0; tab[ 1] = a1; tab[ 2] = a2; tab[ 3] = a1^a2; | |
| 63 tab[ 4] = a4; tab[ 5] = a1^a4; tab[ 6] = a2^a4; tab[ 7] = a1^a2^a4; | |
| 64 tab[ 8] = a8; tab[ 9] = a1^a8; tab[10] = a2^a8; tab[11] = a1^a2^a8; | |
| 65 tab[12] = a4^a8; tab[13] = a1^a4^a8; tab[14] = a2^a4^a8; tab[15] = a1^a2^a4^
a8; | |
| 66 | |
| 67 s = tab[b & 0xF]; l = s; | |
| 68 s = tab[b >> 4 & 0xF]; l ^= s << 4; h = s >> 60; | |
| 69 s = tab[b >> 8 & 0xF]; l ^= s << 8; h ^= s >> 56; | |
| 70 s = tab[b >> 12 & 0xF]; l ^= s << 12; h ^= s >> 52; | |
| 71 s = tab[b >> 16 & 0xF]; l ^= s << 16; h ^= s >> 48; | |
| 72 s = tab[b >> 20 & 0xF]; l ^= s << 20; h ^= s >> 44; | |
| 73 s = tab[b >> 24 & 0xF]; l ^= s << 24; h ^= s >> 40; | |
| 74 s = tab[b >> 28 & 0xF]; l ^= s << 28; h ^= s >> 36; | |
| 75 s = tab[b >> 32 & 0xF]; l ^= s << 32; h ^= s >> 32; | |
| 76 s = tab[b >> 36 & 0xF]; l ^= s << 36; h ^= s >> 28; | |
| 77 s = tab[b >> 40 & 0xF]; l ^= s << 40; h ^= s >> 24; | |
| 78 s = tab[b >> 44 & 0xF]; l ^= s << 44; h ^= s >> 20; | |
| 79 s = tab[b >> 48 & 0xF]; l ^= s << 48; h ^= s >> 16; | |
| 80 s = tab[b >> 52 & 0xF]; l ^= s << 52; h ^= s >> 12; | |
| 81 s = tab[b >> 56 & 0xF]; l ^= s << 56; h ^= s >> 8; | |
| 82 s = tab[b >> 60 ]; l ^= s << 60; h ^= s >> 4; | |
| 83 | |
| 84 /* compensate for the top three bits of a */ | |
| 85 | |
| 86 if (top3b & 01) { l ^= b << 61; h ^= b >> 3; } | |
| 87 if (top3b & 02) { l ^= b << 62; h ^= b >> 2; } | |
| 88 if (top3b & 04) { l ^= b << 63; h ^= b >> 1; } | |
| 89 | |
| 90 *rh = h; *rl = l; | |
| 91 } | |
| 92 #endif | |
| 93 | |
| 94 /* Compute xor-multiply of two binary polynomials (a1, a0) x (b1, b0) | |
| 95 * result is a binary polynomial in 4 mp_digits r[4]. | |
| 96 * The caller MUST ensure that r has the right amount of space allocated. | |
| 97 */ | |
| 98 void | |
| 99 s_bmul_2x2(mp_digit *r, const mp_digit a1, const mp_digit a0, const mp_digit b1, | |
| 100 const mp_digit b0) | |
| 101 { | |
| 102 mp_digit m1, m0; | |
| 103 /* r[3] = h1, r[2] = h0; r[1] = l1; r[0] = l0 */ | |
| 104 s_bmul_1x1(r+3, r+2, a1, b1); | |
| 105 s_bmul_1x1(r+1, r, a0, b0); | |
| 106 s_bmul_1x1(&m1, &m0, a0 ^ a1, b0 ^ b1); | |
| 107 /* Correction on m1 ^= l1 ^ h1; m0 ^= l0 ^ h0; */ | |
| 108 r[2] ^= m1 ^ r[1] ^ r[3]; /* h0 ^= m1 ^ l1 ^ h1; */ | |
| 109 r[1] = r[3] ^ r[2] ^ r[0] ^ m1 ^ m0; /* l1 ^= l0 ^ h0 ^ m0; */ | |
| 110 } | |
| 111 | |
| 112 /* Compute xor-multiply of two binary polynomials (a2, a1, a0) x (b2, b1, b0) | |
| 113 * result is a binary polynomial in 6 mp_digits r[6]. | |
| 114 * The caller MUST ensure that r has the right amount of space allocated. | |
| 115 */ | |
| 116 void | |
| 117 s_bmul_3x3(mp_digit *r, const mp_digit a2, const mp_digit a1, const mp_digit a0,
| |
| 118 const mp_digit b2, const mp_digit b1, const mp_digit b0) | |
| 119 { | |
| 120 mp_digit zm[4]; | |
| 121 | |
| 122 s_bmul_1x1(r+5, r+4, a2, b2); /* fill top 2 words */ | |
| 123 s_bmul_2x2(zm, a1, a2^a0, b1, b2^b0); /* fill middle 4 words */ | |
| 124 s_bmul_2x2(r, a1, a0, b1, b0); /* fill bottom 4 words */ | |
| 125 | |
| 126 zm[3] ^= r[3]; | |
| 127 zm[2] ^= r[2]; | |
| 128 zm[1] ^= r[1] ^ r[5]; | |
| 129 zm[0] ^= r[0] ^ r[4]; | |
| 130 | |
| 131 r[5] ^= zm[3]; | |
| 132 r[4] ^= zm[2]; | |
| 133 r[3] ^= zm[1]; | |
| 134 r[2] ^= zm[0]; | |
| 135 } | |
| 136 | |
| 137 /* Compute xor-multiply of two binary polynomials (a3, a2, a1, a0) x (b3, b2, b
1, b0) | |
| 138 * result is a binary polynomial in 8 mp_digits r[8]. | |
| 139 * The caller MUST ensure that r has the right amount of space allocated. | |
| 140 */ | |
| 141 void s_bmul_4x4(mp_digit *r, const mp_digit a3, const mp_digit a2, const mp_digi
t a1, | |
| 142 const mp_digit a0, const mp_digit b3, const mp_digit b2, const mp_digit
b1, | |
| 143 const mp_digit b0) | |
| 144 { | |
| 145 mp_digit zm[4]; | |
| 146 | |
| 147 s_bmul_2x2(r+4, a3, a2, b3, b2); /* fill top 4 words */ | |
| 148 s_bmul_2x2(zm, a3^a1, a2^a0, b3^b1, b2^b0); /* fill middle 4 words */ | |
| 149 s_bmul_2x2(r, a1, a0, b1, b0); /* fill bottom 4 words */ | |
| 150 | |
| 151 zm[3] ^= r[3] ^ r[7]; | |
| 152 zm[2] ^= r[2] ^ r[6]; | |
| 153 zm[1] ^= r[1] ^ r[5]; | |
| 154 zm[0] ^= r[0] ^ r[4]; | |
| 155 | |
| 156 r[5] ^= zm[3]; | |
| 157 r[4] ^= zm[2]; | |
| 158 r[3] ^= zm[1]; | |
| 159 r[2] ^= zm[0]; | |
| 160 } | |
| 161 | |
| 162 /* Compute addition of two binary polynomials a and b, | |
| 163 * store result in c; c could be a or b, a and b could be equal; | |
| 164 * c is the bitwise XOR of a and b. | |
| 165 */ | |
| 166 mp_err | |
| 167 mp_badd(const mp_int *a, const mp_int *b, mp_int *c) | |
| 168 { | |
| 169 mp_digit *pa, *pb, *pc; | |
| 170 mp_size ix; | |
| 171 mp_size used_pa, used_pb; | |
| 172 mp_err res = MP_OKAY; | |
| 173 | |
| 174 /* Add all digits up to the precision of b. If b had more | |
| 175 * precision than a initially, swap a, b first | |
| 176 */ | |
| 177 if (MP_USED(a) >= MP_USED(b)) { | |
| 178 pa = MP_DIGITS(a); | |
| 179 pb = MP_DIGITS(b); | |
| 180 used_pa = MP_USED(a); | |
| 181 used_pb = MP_USED(b); | |
| 182 } else { | |
| 183 pa = MP_DIGITS(b); | |
| 184 pb = MP_DIGITS(a); | |
| 185 used_pa = MP_USED(b); | |
| 186 used_pb = MP_USED(a); | |
| 187 } | |
| 188 | |
| 189 /* Make sure c has enough precision for the output value */ | |
| 190 MP_CHECKOK( s_mp_pad(c, used_pa) ); | |
| 191 | |
| 192 /* Do word-by-word xor */ | |
| 193 pc = MP_DIGITS(c); | |
| 194 for (ix = 0; ix < used_pb; ix++) { | |
| 195 (*pc++) = (*pa++) ^ (*pb++); | |
| 196 } | |
| 197 | |
| 198 /* Finish the rest of digits until we're actually done */ | |
| 199 for (; ix < used_pa; ++ix) { | |
| 200 *pc++ = *pa++; | |
| 201 } | |
| 202 | |
| 203 MP_USED(c) = used_pa; | |
| 204 MP_SIGN(c) = ZPOS; | |
| 205 s_mp_clamp(c); | |
| 206 | |
| 207 CLEANUP: | |
| 208 return res; | |
| 209 } | |
| 210 | |
| 211 #define s_mp_div2(a) MP_CHECKOK( mpl_rsh((a), (a), 1) ); | |
| 212 | |
| 213 /* Compute binary polynomial multiply d = a * b */ | |
| 214 static void | |
| 215 s_bmul_d(const mp_digit *a, mp_size a_len, mp_digit b, mp_digit *d) | |
| 216 { | |
| 217 mp_digit a_i, a0b0, a1b1, carry = 0; | |
| 218 while (a_len--) { | |
| 219 a_i = *a++; | |
| 220 s_bmul_1x1(&a1b1, &a0b0, a_i, b); | |
| 221 *d++ = a0b0 ^ carry; | |
| 222 carry = a1b1; | |
| 223 } | |
| 224 *d = carry; | |
| 225 } | |
| 226 | |
| 227 /* Compute binary polynomial xor multiply accumulate d ^= a * b */ | |
| 228 static void | |
| 229 s_bmul_d_add(const mp_digit *a, mp_size a_len, mp_digit b, mp_digit *d) | |
| 230 { | |
| 231 mp_digit a_i, a0b0, a1b1, carry = 0; | |
| 232 while (a_len--) { | |
| 233 a_i = *a++; | |
| 234 s_bmul_1x1(&a1b1, &a0b0, a_i, b); | |
| 235 *d++ ^= a0b0 ^ carry; | |
| 236 carry = a1b1; | |
| 237 } | |
| 238 *d ^= carry; | |
| 239 } | |
| 240 | |
| 241 /* Compute binary polynomial xor multiply c = a * b. | |
| 242 * All parameters may be identical. | |
| 243 */ | |
| 244 mp_err | |
| 245 mp_bmul(const mp_int *a, const mp_int *b, mp_int *c) | |
| 246 { | |
| 247 mp_digit *pb, b_i; | |
| 248 mp_int tmp; | |
| 249 mp_size ib, a_used, b_used; | |
| 250 mp_err res = MP_OKAY; | |
| 251 | |
| 252 MP_DIGITS(&tmp) = 0; | |
| 253 | |
| 254 ARGCHK(a != NULL && b != NULL && c != NULL, MP_BADARG); | |
| 255 | |
| 256 if (a == c) { | |
| 257 MP_CHECKOK( mp_init_copy(&tmp, a) ); | |
| 258 if (a == b) | |
| 259 b = &tmp; | |
| 260 a = &tmp; | |
| 261 } else if (b == c) { | |
| 262 MP_CHECKOK( mp_init_copy(&tmp, b) ); | |
| 263 b = &tmp; | |
| 264 } | |
| 265 | |
| 266 if (MP_USED(a) < MP_USED(b)) { | |
| 267 const mp_int *xch = b; /* switch a and b if b longer */ | |
| 268 b = a; | |
| 269 a = xch; | |
| 270 } | |
| 271 | |
| 272 MP_USED(c) = 1; MP_DIGIT(c, 0) = 0; | |
| 273 MP_CHECKOK( s_mp_pad(c, USED(a) + USED(b)) ); | |
| 274 | |
| 275 pb = MP_DIGITS(b); | |
| 276 s_bmul_d(MP_DIGITS(a), MP_USED(a), *pb++, MP_DIGITS(c)); | |
| 277 | |
| 278 /* Outer loop: Digits of b */ | |
| 279 a_used = MP_USED(a); | |
| 280 b_used = MP_USED(b); | |
| 281 MP_USED(c) = a_used + b_used; | |
| 282 for (ib = 1; ib < b_used; ib++) { | |
| 283 b_i = *pb++; | |
| 284 | |
| 285 /* Inner product: Digits of a */ | |
| 286 if (b_i) | |
| 287 s_bmul_d_add(MP_DIGITS(a), a_used, b_i, MP_DIGITS(c) + ib); | |
| 288 else | |
| 289 MP_DIGIT(c, ib + a_used) = b_i; | |
| 290 } | |
| 291 | |
| 292 s_mp_clamp(c); | |
| 293 | |
| 294 SIGN(c) = ZPOS; | |
| 295 | |
| 296 CLEANUP: | |
| 297 mp_clear(&tmp); | |
| 298 return res; | |
| 299 } | |
| 300 | |
| 301 | |
| 302 /* Compute modular reduction of a and store result in r. | |
| 303 * r could be a. | |
| 304 * For modular arithmetic, the irreducible polynomial f(t) is represented | |
| 305 * as an array of int[], where f(t) is of the form: | |
| 306 * f(t) = t^p[0] + t^p[1] + ... + t^p[k] | |
| 307 * where m = p[0] > p[1] > ... > p[k] = 0. | |
| 308 */ | |
| 309 mp_err | |
| 310 mp_bmod(const mp_int *a, const unsigned int p[], mp_int *r) | |
| 311 { | |
| 312 int j, k; | |
| 313 int n, dN, d0, d1; | |
| 314 mp_digit zz, *z, tmp; | |
| 315 mp_size used; | |
| 316 mp_err res = MP_OKAY; | |
| 317 | |
| 318 /* The algorithm does the reduction in place in r, | |
| 319 * if a != r, copy a into r first so reduction can be done in r | |
| 320 */ | |
| 321 if (a != r) { | |
| 322 MP_CHECKOK( mp_copy(a, r) ); | |
| 323 } | |
| 324 z = MP_DIGITS(r); | |
| 325 | |
| 326 /* start reduction */ | |
| 327 /*dN = p[0] / MP_DIGIT_BITS; */ | |
| 328 dN = p[0] >> MP_DIGIT_BITS_LOG_2; | |
| 329 used = MP_USED(r); | |
| 330 | |
| 331 for (j = used - 1; j > dN;) { | |
| 332 | |
| 333 zz = z[j]; | |
| 334 if (zz == 0) { | |
| 335 j--; continue; | |
| 336 } | |
| 337 z[j] = 0; | |
| 338 | |
| 339 for (k = 1; p[k] > 0; k++) { | |
| 340 /* reducing component t^p[k] */ | |
| 341 n = p[0] - p[k]; | |
| 342 /*d0 = n % MP_DIGIT_BITS; */ | |
| 343 d0 = n & MP_DIGIT_BITS_MASK; | |
| 344 d1 = MP_DIGIT_BITS - d0; | |
| 345 /*n /= MP_DIGIT_BITS; */ | |
| 346 n >>= MP_DIGIT_BITS_LOG_2; | |
| 347 z[j-n] ^= (zz>>d0); | |
| 348 if (d0) | |
| 349 z[j-n-1] ^= (zz<<d1); | |
| 350 } | |
| 351 | |
| 352 /* reducing component t^0 */ | |
| 353 n = dN; | |
| 354 /*d0 = p[0] % MP_DIGIT_BITS;*/ | |
| 355 d0 = p[0] & MP_DIGIT_BITS_MASK; | |
| 356 d1 = MP_DIGIT_BITS - d0; | |
| 357 z[j-n] ^= (zz >> d0); | |
| 358 if (d0) | |
| 359 z[j-n-1] ^= (zz << d1); | |
| 360 | |
| 361 } | |
| 362 | |
| 363 /* final round of reduction */ | |
| 364 while (j == dN) { | |
| 365 | |
| 366 /* d0 = p[0] % MP_DIGIT_BITS; */ | |
| 367 d0 = p[0] & MP_DIGIT_BITS_MASK; | |
| 368 zz = z[dN] >> d0; | |
| 369 if (zz == 0) break; | |
| 370 d1 = MP_DIGIT_BITS - d0; | |
| 371 | |
| 372 /* clear up the top d1 bits */ | |
| 373 if (d0) { | |
| 374 z[dN] = (z[dN] << d1) >> d1; | |
| 375 } else { | |
| 376 z[dN] = 0; | |
| 377 } | |
| 378 *z ^= zz; /* reduction t^0 component */ | |
| 379 | |
| 380 for (k = 1; p[k] > 0; k++) { | |
| 381 /* reducing component t^p[k]*/ | |
| 382 /* n = p[k] / MP_DIGIT_BITS; */ | |
| 383 n = p[k] >> MP_DIGIT_BITS_LOG_2; | |
| 384 /* d0 = p[k] % MP_DIGIT_BITS; */ | |
| 385 d0 = p[k] & MP_DIGIT_BITS_MASK; | |
| 386 d1 = MP_DIGIT_BITS - d0; | |
| 387 z[n] ^= (zz << d0); | |
| 388 tmp = zz >> d1; | |
| 389 if (d0 && tmp) | |
| 390 z[n+1] ^= tmp; | |
| 391 } | |
| 392 } | |
| 393 | |
| 394 s_mp_clamp(r); | |
| 395 CLEANUP: | |
| 396 return res; | |
| 397 } | |
| 398 | |
| 399 /* Compute the product of two polynomials a and b, reduce modulo p, | |
| 400 * Store the result in r. r could be a or b; a could be b. | |
| 401 */ | |
| 402 mp_err | |
| 403 mp_bmulmod(const mp_int *a, const mp_int *b, const unsigned int p[], mp_int *r) | |
| 404 { | |
| 405 mp_err res; | |
| 406 | |
| 407 if (a == b) return mp_bsqrmod(a, p, r); | |
| 408 if ((res = mp_bmul(a, b, r) ) != MP_OKAY) | |
| 409 return res; | |
| 410 return mp_bmod(r, p, r); | |
| 411 } | |
| 412 | |
| 413 /* Compute binary polynomial squaring c = a*a mod p . | |
| 414 * Parameter r and a can be identical. | |
| 415 */ | |
| 416 | |
| 417 mp_err | |
| 418 mp_bsqrmod(const mp_int *a, const unsigned int p[], mp_int *r) | |
| 419 { | |
| 420 mp_digit *pa, *pr, a_i; | |
| 421 mp_int tmp; | |
| 422 mp_size ia, a_used; | |
| 423 mp_err res; | |
| 424 | |
| 425 ARGCHK(a != NULL && r != NULL, MP_BADARG); | |
| 426 MP_DIGITS(&tmp) = 0; | |
| 427 | |
| 428 if (a == r) { | |
| 429 MP_CHECKOK( mp_init_copy(&tmp, a) ); | |
| 430 a = &tmp; | |
| 431 } | |
| 432 | |
| 433 MP_USED(r) = 1; MP_DIGIT(r, 0) = 0; | |
| 434 MP_CHECKOK( s_mp_pad(r, 2*USED(a)) ); | |
| 435 | |
| 436 pa = MP_DIGITS(a); | |
| 437 pr = MP_DIGITS(r); | |
| 438 a_used = MP_USED(a); | |
| 439 MP_USED(r) = 2 * a_used; | |
| 440 | |
| 441 for (ia = 0; ia < a_used; ia++) { | |
| 442 a_i = *pa++; | |
| 443 *pr++ = gf2m_SQR0(a_i); | |
| 444 *pr++ = gf2m_SQR1(a_i); | |
| 445 } | |
| 446 | |
| 447 MP_CHECKOK( mp_bmod(r, p, r) ); | |
| 448 s_mp_clamp(r); | |
| 449 SIGN(r) = ZPOS; | |
| 450 | |
| 451 CLEANUP: | |
| 452 mp_clear(&tmp); | |
| 453 return res; | |
| 454 } | |
| 455 | |
| 456 /* Compute binary polynomial y/x mod p, y divided by x, reduce modulo p. | |
| 457 * Store the result in r. r could be x or y, and x could equal y. | |
| 458 * Uses algorithm Modular_Division_GF(2^m) from | |
| 459 * Chang-Shantz, S. "From Euclid's GCD to Montgomery Multiplication to | |
| 460 * the Great Divide". | |
| 461 */ | |
| 462 int | |
| 463 mp_bdivmod(const mp_int *y, const mp_int *x, const mp_int *pp, | |
| 464 const unsigned int p[], mp_int *r) | |
| 465 { | |
| 466 mp_int aa, bb, uu; | |
| 467 mp_int *a, *b, *u, *v; | |
| 468 mp_err res = MP_OKAY; | |
| 469 | |
| 470 MP_DIGITS(&aa) = 0; | |
| 471 MP_DIGITS(&bb) = 0; | |
| 472 MP_DIGITS(&uu) = 0; | |
| 473 | |
| 474 MP_CHECKOK( mp_init_copy(&aa, x) ); | |
| 475 MP_CHECKOK( mp_init_copy(&uu, y) ); | |
| 476 MP_CHECKOK( mp_init_copy(&bb, pp) ); | |
| 477 MP_CHECKOK( s_mp_pad(r, USED(pp)) ); | |
| 478 MP_USED(r) = 1; MP_DIGIT(r, 0) = 0; | |
| 479 | |
| 480 a = &aa; b= &bb; u=&uu; v=r; | |
| 481 /* reduce x and y mod p */ | |
| 482 MP_CHECKOK( mp_bmod(a, p, a) ); | |
| 483 MP_CHECKOK( mp_bmod(u, p, u) ); | |
| 484 | |
| 485 while (!mp_isodd(a)) { | |
| 486 s_mp_div2(a); | |
| 487 if (mp_isodd(u)) { | |
| 488 MP_CHECKOK( mp_badd(u, pp, u) ); | |
| 489 } | |
| 490 s_mp_div2(u); | |
| 491 } | |
| 492 | |
| 493 do { | |
| 494 if (mp_cmp_mag(b, a) > 0) { | |
| 495 MP_CHECKOK( mp_badd(b, a, b) ); | |
| 496 MP_CHECKOK( mp_badd(v, u, v) ); | |
| 497 do { | |
| 498 s_mp_div2(b); | |
| 499 if (mp_isodd(v)) { | |
| 500 MP_CHECKOK( mp_badd(v, pp, v) ); | |
| 501 } | |
| 502 s_mp_div2(v); | |
| 503 } while (!mp_isodd(b)); | |
| 504 } | |
| 505 else if ((MP_DIGIT(a,0) == 1) && (MP_USED(a) == 1)) | |
| 506 break; | |
| 507 else { | |
| 508 MP_CHECKOK( mp_badd(a, b, a) ); | |
| 509 MP_CHECKOK( mp_badd(u, v, u) ); | |
| 510 do { | |
| 511 s_mp_div2(a); | |
| 512 if (mp_isodd(u)) { | |
| 513 MP_CHECKOK( mp_badd(u, pp, u) ); | |
| 514 } | |
| 515 s_mp_div2(u); | |
| 516 } while (!mp_isodd(a)); | |
| 517 } | |
| 518 } while (1); | |
| 519 | |
| 520 MP_CHECKOK( mp_copy(u, r) ); | |
| 521 | |
| 522 CLEANUP: | |
| 523 mp_clear(&aa); | |
| 524 mp_clear(&bb); | |
| 525 mp_clear(&uu); | |
| 526 return res; | |
| 527 | |
| 528 } | |
| 529 | |
| 530 /* Convert the bit-string representation of a polynomial a into an array | |
| 531 * of integers corresponding to the bits with non-zero coefficient. | |
| 532 * Up to max elements of the array will be filled. Return value is total | |
| 533 * number of coefficients that would be extracted if array was large enough. | |
| 534 */ | |
| 535 int | |
| 536 mp_bpoly2arr(const mp_int *a, unsigned int p[], int max) | |
| 537 { | |
| 538 int i, j, k; | |
| 539 mp_digit top_bit, mask; | |
| 540 | |
| 541 top_bit = 1; | |
| 542 top_bit <<= MP_DIGIT_BIT - 1; | |
| 543 | |
| 544 for (k = 0; k < max; k++) p[k] = 0; | |
| 545 k = 0; | |
| 546 | |
| 547 for (i = MP_USED(a) - 1; i >= 0; i--) { | |
| 548 mask = top_bit; | |
| 549 for (j = MP_DIGIT_BIT - 1; j >= 0; j--) { | |
| 550 if (MP_DIGITS(a)[i] & mask) { | |
| 551 if (k < max) p[k] = MP_DIGIT_BIT * i + j; | |
| 552 k++; | |
| 553 } | |
| 554 mask >>= 1; | |
| 555 } | |
| 556 } | |
| 557 | |
| 558 return k; | |
| 559 } | |
| 560 | |
| 561 /* Convert the coefficient array representation of a polynomial to a | |
| 562 * bit-string. The array must be terminated by 0. | |
| 563 */ | |
| 564 mp_err | |
| 565 mp_barr2poly(const unsigned int p[], mp_int *a) | |
| 566 { | |
| 567 | |
| 568 mp_err res = MP_OKAY; | |
| 569 int i; | |
| 570 | |
| 571 mp_zero(a); | |
| 572 for (i = 0; p[i] > 0; i++) { | |
| 573 MP_CHECKOK( mpl_set_bit(a, p[i], 1) ); | |
| 574 } | |
| 575 MP_CHECKOK( mpl_set_bit(a, 0, 1) ); | |
| 576 | |
| 577 CLEANUP: | |
| 578 return res; | |
| 579 } | |
| 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