The Tor Browser / file comparison
comparison: security/nss/lib/freebl/ecl/ecp_224.c
security/nss/lib/freebl/ecl/ecp_224.c
- changeset 0
- 6474c204b198
equal
deleted
inserted
replaced
| -1:000000000000 | 0:b65782e228e6 |
|---|---|
| 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 #define ECP224_DIGITS ECL_CURVE_DIGITS(224) | |
| 11 | |
| 12 /* Fast modular reduction for p224 = 2^224 - 2^96 + 1. a can be r. Uses | |
| 13 * algorithm 7 from Brown, Hankerson, Lopez, Menezes. Software | |
| 14 * Implementation of the NIST Elliptic Curves over Prime Fields. */ | |
| 15 static mp_err | |
| 16 ec_GFp_nistp224_mod(const mp_int *a, mp_int *r, const GFMethod *meth) | |
| 17 { | |
| 18 mp_err res = MP_OKAY; | |
| 19 mp_size a_used = MP_USED(a); | |
| 20 | |
| 21 int r3b; | |
| 22 mp_digit carry; | |
| 23 #ifdef ECL_THIRTY_TWO_BIT | |
| 24 mp_digit a6a = 0, a6b = 0, | |
| 25 a5a = 0, a5b = 0, a4a = 0, a4b = 0, a3a = 0, a3b = 0; | |
| 26 mp_digit r0a, r0b, r1a, r1b, r2a, r2b, r3a; | |
| 27 #else | |
| 28 mp_digit a6 = 0, a5 = 0, a4 = 0, a3b = 0, a5a = 0; | |
| 29 mp_digit a6b = 0, a6a_a5b = 0, a5b = 0, a5a_a4b = 0, a4a_a3b = 0; | |
| 30 mp_digit r0, r1, r2, r3; | |
| 31 #endif | |
| 32 | |
| 33 /* reduction not needed if a is not larger than field size */ | |
| 34 if (a_used < ECP224_DIGITS) { | |
| 35 if (a == r) return MP_OKAY; | |
| 36 return mp_copy(a, r); | |
| 37 } | |
| 38 /* for polynomials larger than twice the field size, use regular | |
| 39 * reduction */ | |
| 40 if (a_used > ECL_CURVE_DIGITS(224*2)) { | |
| 41 MP_CHECKOK(mp_mod(a, &meth->irr, r)); | |
| 42 } else { | |
| 43 #ifdef ECL_THIRTY_TWO_BIT | |
| 44 /* copy out upper words of a */ | |
| 45 switch (a_used) { | |
| 46 case 14: | |
| 47 a6b = MP_DIGIT(a, 13); | |
| 48 case 13: | |
| 49 a6a = MP_DIGIT(a, 12); | |
| 50 case 12: | |
| 51 a5b = MP_DIGIT(a, 11); | |
| 52 case 11: | |
| 53 a5a = MP_DIGIT(a, 10); | |
| 54 case 10: | |
| 55 a4b = MP_DIGIT(a, 9); | |
| 56 case 9: | |
| 57 a4a = MP_DIGIT(a, 8); | |
| 58 case 8: | |
| 59 a3b = MP_DIGIT(a, 7); | |
| 60 } | |
| 61 r3a = MP_DIGIT(a, 6); | |
| 62 r2b= MP_DIGIT(a, 5); | |
| 63 r2a= MP_DIGIT(a, 4); | |
| 64 r1b = MP_DIGIT(a, 3); | |
| 65 r1a = MP_DIGIT(a, 2); | |
| 66 r0b = MP_DIGIT(a, 1); | |
| 67 r0a = MP_DIGIT(a, 0); | |
| 68 | |
| 69 | |
| 70 /* implement r = (a3a,a2,a1,a0) | |
| 71 +(a5a, a4,a3b, 0) | |
| 72 +( 0, a6,a5b, 0) | |
| 73 -( 0 0, 0|a6b, a6a|a5b ) | |
| 74 -( a6b, a6a|a5b, a5a|a4b, a4a|a3b ) */ | |
| 75 MP_ADD_CARRY (r1b, a3b, r1b, 0, carry); | |
| 76 MP_ADD_CARRY (r2a, a4a, r2a, carry, carry); | |
| 77 MP_ADD_CARRY (r2b, a4b, r2b, carry, carry); | |
| 78 MP_ADD_CARRY (r3a, a5a, r3a, carry, carry); | |
| 79 r3b = carry; | |
| 80 MP_ADD_CARRY (r1b, a5b, r1b, 0, carry); | |
| 81 MP_ADD_CARRY (r2a, a6a, r2a, carry, carry); | |
| 82 MP_ADD_CARRY (r2b, a6b, r2b, carry, carry); | |
| 83 MP_ADD_CARRY (r3a, 0, r3a, carry, carry); | |
| 84 r3b += carry; | |
| 85 MP_SUB_BORROW(r0a, a3b, r0a, 0, carry); | |
| 86 MP_SUB_BORROW(r0b, a4a, r0b, carry, carry); | |
| 87 MP_SUB_BORROW(r1a, a4b, r1a, carry, carry); | |
| 88 MP_SUB_BORROW(r1b, a5a, r1b, carry, carry); | |
| 89 MP_SUB_BORROW(r2a, a5b, r2a, carry, carry); | |
| 90 MP_SUB_BORROW(r2b, a6a, r2b, carry, carry); | |
| 91 MP_SUB_BORROW(r3a, a6b, r3a, carry, carry); | |
| 92 r3b -= carry; | |
| 93 MP_SUB_BORROW(r0a, a5b, r0a, 0, carry); | |
| 94 MP_SUB_BORROW(r0b, a6a, r0b, carry, carry); | |
| 95 MP_SUB_BORROW(r1a, a6b, r1a, carry, carry); | |
| 96 if (carry) { | |
| 97 MP_SUB_BORROW(r1b, 0, r1b, carry, carry); | |
| 98 MP_SUB_BORROW(r2a, 0, r2a, carry, carry); | |
| 99 MP_SUB_BORROW(r2b, 0, r2b, carry, carry); | |
| 100 MP_SUB_BORROW(r3a, 0, r3a, carry, carry); | |
| 101 r3b -= carry; | |
| 102 } | |
| 103 | |
| 104 while (r3b > 0) { | |
| 105 int tmp; | |
| 106 MP_ADD_CARRY(r1b, r3b, r1b, 0, carry); | |
| 107 if (carry) { | |
| 108 MP_ADD_CARRY(r2a, 0, r2a, carry, carry); | |
| 109 MP_ADD_CARRY(r2b, 0, r2b, carry, carry); | |
| 110 MP_ADD_CARRY(r3a, 0, r3a, carry, carry); | |
| 111 } | |
| 112 tmp = carry; | |
| 113 MP_SUB_BORROW(r0a, r3b, r0a, 0, carry); | |
| 114 if (carry) { | |
| 115 MP_SUB_BORROW(r0b, 0, r0b, carry, carry); | |
| 116 MP_SUB_BORROW(r1a, 0, r1a, carry, carry); | |
| 117 MP_SUB_BORROW(r1b, 0, r1b, carry, carry); | |
| 118 MP_SUB_BORROW(r2a, 0, r2a, carry, carry); | |
| 119 MP_SUB_BORROW(r2b, 0, r2b, carry, carry); | |
| 120 MP_SUB_BORROW(r3a, 0, r3a, carry, carry); | |
| 121 tmp -= carry; | |
| 122 } | |
| 123 r3b = tmp; | |
| 124 } | |
| 125 | |
| 126 while (r3b < 0) { | |
| 127 mp_digit maxInt = MP_DIGIT_MAX; | |
| 128 MP_ADD_CARRY (r0a, 1, r0a, 0, carry); | |
| 129 MP_ADD_CARRY (r0b, 0, r0b, carry, carry); | |
| 130 MP_ADD_CARRY (r1a, 0, r1a, carry, carry); | |
| 131 MP_ADD_CARRY (r1b, maxInt, r1b, carry, carry); | |
| 132 MP_ADD_CARRY (r2a, maxInt, r2a, carry, carry); | |
| 133 MP_ADD_CARRY (r2b, maxInt, r2b, carry, carry); | |
| 134 MP_ADD_CARRY (r3a, maxInt, r3a, carry, carry); | |
| 135 r3b += carry; | |
| 136 } | |
| 137 /* check for final reduction */ | |
| 138 /* now the only way we are over is if the top 4 words are all ones */ | |
| 139 if ((r3a == MP_DIGIT_MAX) && (r2b == MP_DIGIT_MAX) | |
| 140 && (r2a == MP_DIGIT_MAX) && (r1b == MP_DIGIT_MAX) && | |
| 141 ((r1a != 0) || (r0b != 0) || (r0a != 0)) ) { | |
| 142 /* one last subraction */ | |
| 143 MP_SUB_BORROW(r0a, 1, r0a, 0, carry); | |
| 144 MP_SUB_BORROW(r0b, 0, r0b, carry, carry); | |
| 145 MP_SUB_BORROW(r1a, 0, r1a, carry, carry); | |
| 146 r1b = r2a = r2b = r3a = 0; | |
| 147 } | |
| 148 | |
| 149 | |
| 150 if (a != r) { | |
| 151 MP_CHECKOK(s_mp_pad(r, 7)); | |
| 152 } | |
| 153 /* set the lower words of r */ | |
| 154 MP_SIGN(r) = MP_ZPOS; | |
| 155 MP_USED(r) = 7; | |
| 156 MP_DIGIT(r, 6) = r3a; | |
| 157 MP_DIGIT(r, 5) = r2b; | |
| 158 MP_DIGIT(r, 4) = r2a; | |
| 159 MP_DIGIT(r, 3) = r1b; | |
| 160 MP_DIGIT(r, 2) = r1a; | |
| 161 MP_DIGIT(r, 1) = r0b; | |
| 162 MP_DIGIT(r, 0) = r0a; | |
| 163 #else | |
| 164 /* copy out upper words of a */ | |
| 165 switch (a_used) { | |
| 166 case 7: | |
| 167 a6 = MP_DIGIT(a, 6); | |
| 168 a6b = a6 >> 32; | |
| 169 a6a_a5b = a6 << 32; | |
| 170 case 6: | |
| 171 a5 = MP_DIGIT(a, 5); | |
| 172 a5b = a5 >> 32; | |
| 173 a6a_a5b |= a5b; | |
| 174 a5b = a5b << 32; | |
| 175 a5a_a4b = a5 << 32; | |
| 176 a5a = a5 & 0xffffffff; | |
| 177 case 5: | |
| 178 a4 = MP_DIGIT(a, 4); | |
| 179 a5a_a4b |= a4 >> 32; | |
| 180 a4a_a3b = a4 << 32; | |
| 181 case 4: | |
| 182 a3b = MP_DIGIT(a, 3) >> 32; | |
| 183 a4a_a3b |= a3b; | |
| 184 a3b = a3b << 32; | |
| 185 } | |
| 186 | |
| 187 r3 = MP_DIGIT(a, 3) & 0xffffffff; | |
| 188 r2 = MP_DIGIT(a, 2); | |
| 189 r1 = MP_DIGIT(a, 1); | |
| 190 r0 = MP_DIGIT(a, 0); | |
| 191 | |
| 192 /* implement r = (a3a,a2,a1,a0) | |
| 193 +(a5a, a4,a3b, 0) | |
| 194 +( 0, a6,a5b, 0) | |
| 195 -( 0 0, 0|a6b, a6a|a5b ) | |
| 196 -( a6b, a6a|a5b, a5a|a4b, a4a|a3b ) */ | |
| 197 MP_ADD_CARRY (r1, a3b, r1, 0, carry); | |
| 198 MP_ADD_CARRY (r2, a4 , r2, carry, carry); | |
| 199 MP_ADD_CARRY (r3, a5a, r3, carry, carry); | |
| 200 MP_ADD_CARRY (r1, a5b, r1, 0, carry); | |
| 201 MP_ADD_CARRY (r2, a6 , r2, carry, carry); | |
| 202 MP_ADD_CARRY (r3, 0, r3, carry, carry); | |
| 203 | |
| 204 MP_SUB_BORROW(r0, a4a_a3b, r0, 0, carry); | |
| 205 MP_SUB_BORROW(r1, a5a_a4b, r1, carry, carry); | |
| 206 MP_SUB_BORROW(r2, a6a_a5b, r2, carry, carry); | |
| 207 MP_SUB_BORROW(r3, a6b , r3, carry, carry); | |
| 208 MP_SUB_BORROW(r0, a6a_a5b, r0, 0, carry); | |
| 209 MP_SUB_BORROW(r1, a6b , r1, carry, carry); | |
| 210 if (carry) { | |
| 211 MP_SUB_BORROW(r2, 0, r2, carry, carry); | |
| 212 MP_SUB_BORROW(r3, 0, r3, carry, carry); | |
| 213 } | |
| 214 | |
| 215 | |
| 216 /* if the value is negative, r3 has a 2's complement | |
| 217 * high value */ | |
| 218 r3b = (int)(r3 >>32); | |
| 219 while (r3b > 0) { | |
| 220 r3 &= 0xffffffff; | |
| 221 MP_ADD_CARRY(r1,((mp_digit)r3b) << 32, r1, 0, carry); | |
| 222 if (carry) { | |
| 223 MP_ADD_CARRY(r2, 0, r2, carry, carry); | |
| 224 MP_ADD_CARRY(r3, 0, r3, carry, carry); | |
| 225 } | |
| 226 MP_SUB_BORROW(r0, r3b, r0, 0, carry); | |
| 227 if (carry) { | |
| 228 MP_SUB_BORROW(r1, 0, r1, carry, carry); | |
| 229 MP_SUB_BORROW(r2, 0, r2, carry, carry); | |
| 230 MP_SUB_BORROW(r3, 0, r3, carry, carry); | |
| 231 } | |
| 232 r3b = (int)(r3 >>32); | |
| 233 } | |
| 234 | |
| 235 while (r3b < 0) { | |
| 236 MP_ADD_CARRY (r0, 1, r0, 0, carry); | |
| 237 MP_ADD_CARRY (r1, MP_DIGIT_MAX <<32, r1, carry, carry); | |
| 238 MP_ADD_CARRY (r2, MP_DIGIT_MAX, r2, carry, carry); | |
| 239 MP_ADD_CARRY (r3, MP_DIGIT_MAX >> 32, r3, carry, carry); | |
| 240 r3b = (int)(r3 >>32); | |
| 241 } | |
| 242 /* check for final reduction */ | |
| 243 /* now the only way we are over is if the top 4 words are | |
| 244 * all ones. Subtract the curve. (curve is 2^224 - 2^96 +1) | |
| 245 */ | |
| 246 if ((r3 == (MP_DIGIT_MAX >> 32)) && (r2 == MP_DIGIT_MAX) | |
| 247 && ((r1 & MP_DIGIT_MAX << 32)== MP_DIGIT_MAX << 32) && | |
| 248 ((r1 != MP_DIGIT_MAX << 32 ) || (r0 != 0)) ) { | |
| 249 /* one last subraction */ | |
| 250 MP_SUB_BORROW(r0, 1, r0, 0, carry); | |
| 251 MP_SUB_BORROW(r1, MP_DIGIT_MAX << 32, r1, carry, carry); | |
| 252 r2 = r3 = 0; | |
| 253 } | |
| 254 | |
| 255 | |
| 256 if (a != r) { | |
| 257 MP_CHECKOK(s_mp_pad(r, 4)); | |
| 258 } | |
| 259 /* set the lower words of r */ | |
| 260 MP_SIGN(r) = MP_ZPOS; | |
| 261 MP_USED(r) = 4; | |
| 262 MP_DIGIT(r, 3) = r3; | |
| 263 MP_DIGIT(r, 2) = r2; | |
| 264 MP_DIGIT(r, 1) = r1; | |
| 265 MP_DIGIT(r, 0) = r0; | |
| 266 #endif | |
| 267 } | |
| 268 s_mp_clamp(r); | |
| 269 | |
| 270 CLEANUP: | |
| 271 return res; | |
| 272 } | |
| 273 | |
| 274 /* Compute the square of polynomial a, reduce modulo p224. Store the | |
| 275 * result in r. r could be a. Uses optimized modular reduction for p224. | |
| 276 */ | |
| 277 static mp_err | |
| 278 ec_GFp_nistp224_sqr(const mp_int *a, mp_int *r, const GFMethod *meth) | |
| 279 { | |
| 280 mp_err res = MP_OKAY; | |
| 281 | |
| 282 MP_CHECKOK(mp_sqr(a, r)); | |
| 283 MP_CHECKOK(ec_GFp_nistp224_mod(r, r, meth)); | |
| 284 CLEANUP: | |
| 285 return res; | |
| 286 } | |
| 287 | |
| 288 /* Compute the product of two polynomials a and b, reduce modulo p224. | |
| 289 * Store the result in r. r could be a or b; a could be b. Uses | |
| 290 * optimized modular reduction for p224. */ | |
| 291 static mp_err | |
| 292 ec_GFp_nistp224_mul(const mp_int *a, const mp_int *b, mp_int *r, | |
| 293 const GFMethod *meth) | |
| 294 { | |
| 295 mp_err res = MP_OKAY; | |
| 296 | |
| 297 MP_CHECKOK(mp_mul(a, b, r)); | |
| 298 MP_CHECKOK(ec_GFp_nistp224_mod(r, r, meth)); | |
| 299 CLEANUP: | |
| 300 return res; | |
| 301 } | |
| 302 | |
| 303 /* Divides two field elements. If a is NULL, then returns the inverse of | |
| 304 * b. */ | |
| 305 static mp_err | |
| 306 ec_GFp_nistp224_div(const mp_int *a, const mp_int *b, mp_int *r, | |
| 307 const GFMethod *meth) | |
| 308 { | |
| 309 mp_err res = MP_OKAY; | |
| 310 mp_int t; | |
| 311 | |
| 312 /* If a is NULL, then return the inverse of b, otherwise return a/b. */ | |
| 313 if (a == NULL) { | |
| 314 return mp_invmod(b, &meth->irr, r); | |
| 315 } else { | |
| 316 /* MPI doesn't support divmod, so we implement it using invmod and | |
| 317 * mulmod. */ | |
| 318 MP_CHECKOK(mp_init(&t)); | |
| 319 MP_CHECKOK(mp_invmod(b, &meth->irr, &t)); | |
| 320 MP_CHECKOK(mp_mul(a, &t, r)); | |
| 321 MP_CHECKOK(ec_GFp_nistp224_mod(r, r, meth)); | |
| 322 CLEANUP: | |
| 323 mp_clear(&t); | |
| 324 return res; | |
| 325 } | |
| 326 } | |
| 327 | |
| 328 /* Wire in fast field arithmetic and precomputation of base point for | |
| 329 * named curves. */ | |
| 330 mp_err | |
| 331 ec_group_set_gfp224(ECGroup *group, ECCurveName name) | |
| 332 { | |
| 333 if (name == ECCurve_NIST_P224) { | |
| 334 group->meth->field_mod = &ec_GFp_nistp224_mod; | |
| 335 group->meth->field_mul = &ec_GFp_nistp224_mul; | |
| 336 group->meth->field_sqr = &ec_GFp_nistp224_sqr; | |
| 337 group->meth->field_div = &ec_GFp_nistp224_div; | |
| 338 } | |
| 339 return MP_OKAY; | |
| 340 } |
