1 /* 2 * ***** BEGIN LICENSE BLOCK ***** 3 * Version: MPL 1.1/GPL 2.0/LGPL 2.1 4 * 5 * The contents of this file are subject to the Mozilla Public License Version 6 * 1.1 (the "License"); you may not use this file except in compliance with 7 * the License. You may obtain a copy of the License at 8 * http://www.mozilla.org/MPL/ 9 * 10 * Software distributed under the License is distributed on an "AS IS" basis, 11 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License 12 * for the specific language governing rights and limitations under the 13 * License. 14 * 15 * The Original Code is the elliptic curve math library for prime field curves. 16 * 17 * The Initial Developer of the Original Code is 18 * Sun Microsystems, Inc. 19 * Portions created by the Initial Developer are Copyright (C) 2003 20 * the Initial Developer. All Rights Reserved. 21 * 22 * Contributor(s): 23 * Douglas Stebila <douglas@stebila.ca>, Sun Microsystems Laboratories 24 * 25 * Alternatively, the contents of this file may be used under the terms of 26 * either the GNU General Public License Version 2 or later (the "GPL"), or 27 * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"), 28 * in which case the provisions of the GPL or the LGPL are applicable instead 29 * of those above. If you wish to allow use of your version of this file only 30 * under the terms of either the GPL or the LGPL, and not to allow others to 31 * use your version of this file under the terms of the MPL, indicate your 32 * decision by deleting the provisions above and replace them with the notice 33 * and other provisions required by the GPL or the LGPL. If you do not delete 34 * the provisions above, a recipient may use your version of this file under 35 * the terms of any one of the MPL, the GPL or the LGPL. 36 * 37 * ***** END LICENSE BLOCK ***** */ 38 /* 39 * Copyright 2007 Sun Microsystems, Inc. All rights reserved. 40 * Use is subject to license terms. 41 * 42 * Sun elects to use this software under the MPL license. 43 */ 44 45 #include "ecp.h" 46 #include "mpi.h" 47 #include "mplogic.h" 48 #include "mpi-priv.h" 49 #ifndef _KERNEL 50 #include <stdlib.h> 51 #endif 52 53 #define ECP192_DIGITS ECL_CURVE_DIGITS(192) 54 55 /* Fast modular reduction for p192 = 2^192 - 2^64 - 1. a can be r. Uses 56 * algorithm 7 from Brown, Hankerson, Lopez, Menezes. Software 57 * Implementation of the NIST Elliptic Curves over Prime Fields. */ 58 mp_err 59 ec_GFp_nistp192_mod(const mp_int *a, mp_int *r, const GFMethod *meth) 60 { 61 mp_err res = MP_OKAY; 62 mp_size a_used = MP_USED(a); 63 mp_digit r3; 64 #ifndef MPI_AMD64_ADD 65 mp_digit carry; 66 #endif 67 #ifdef ECL_THIRTY_TWO_BIT 68 mp_digit a5a = 0, a5b = 0, a4a = 0, a4b = 0, a3a = 0, a3b = 0; 69 mp_digit r0a, r0b, r1a, r1b, r2a, r2b; 70 #else 71 mp_digit a5 = 0, a4 = 0, a3 = 0; 72 mp_digit r0, r1, r2; 73 #endif 74 75 /* reduction not needed if a is not larger than field size */ 76 if (a_used < ECP192_DIGITS) { 77 if (a == r) { 78 return MP_OKAY; 79 } 80 return mp_copy(a, r); 81 } 82 83 /* for polynomials larger than twice the field size, use regular 84 * reduction */ 85 if (a_used > ECP192_DIGITS*2) { 86 MP_CHECKOK(mp_mod(a, &meth->irr, r)); 87 } else { 88 /* copy out upper words of a */ 89 90 #ifdef ECL_THIRTY_TWO_BIT 91 92 /* in all the math below, 93 * nXb is most signifiant, nXa is least significant */ 94 switch (a_used) { 95 case 12: 96 a5b = MP_DIGIT(a, 11); 97 /* FALLTHROUGH */ 98 case 11: 99 a5a = MP_DIGIT(a, 10); 100 /* FALLTHROUGH */ 101 case 10: 102 a4b = MP_DIGIT(a, 9); 103 /* FALLTHROUGH */ 104 case 9: 105 a4a = MP_DIGIT(a, 8); 106 /* FALLTHROUGH */ 107 case 8: 108 a3b = MP_DIGIT(a, 7); 109 /* FALLTHROUGH */ 110 case 7: 111 a3a = MP_DIGIT(a, 6); 112 } 113 114 115 r2b= MP_DIGIT(a, 5); 116 r2a= MP_DIGIT(a, 4); 117 r1b = MP_DIGIT(a, 3); 118 r1a = MP_DIGIT(a, 2); 119 r0b = MP_DIGIT(a, 1); 120 r0a = MP_DIGIT(a, 0); 121 122 /* implement r = (a2,a1,a0)+(a5,a5,a5)+(a4,a4,0)+(0,a3,a3) */ 123 MP_ADD_CARRY(r0a, a3a, r0a, 0, carry); 124 MP_ADD_CARRY(r0b, a3b, r0b, carry, carry); 125 MP_ADD_CARRY(r1a, a3a, r1a, carry, carry); 126 MP_ADD_CARRY(r1b, a3b, r1b, carry, carry); 127 MP_ADD_CARRY(r2a, a4a, r2a, carry, carry); 128 MP_ADD_CARRY(r2b, a4b, r2b, carry, carry); 129 r3 = carry; carry = 0; 130 MP_ADD_CARRY(r0a, a5a, r0a, 0, carry); 131 MP_ADD_CARRY(r0b, a5b, r0b, carry, carry); 132 MP_ADD_CARRY(r1a, a5a, r1a, carry, carry); 133 MP_ADD_CARRY(r1b, a5b, r1b, carry, carry); 134 MP_ADD_CARRY(r2a, a5a, r2a, carry, carry); 135 MP_ADD_CARRY(r2b, a5b, r2b, carry, carry); 136 r3 += carry; 137 MP_ADD_CARRY(r1a, a4a, r1a, 0, carry); 138 MP_ADD_CARRY(r1b, a4b, r1b, carry, carry); 139 MP_ADD_CARRY(r2a, 0, r2a, carry, carry); 140 MP_ADD_CARRY(r2b, 0, r2b, carry, carry); 141 r3 += carry; 142 143 /* reduce out the carry */ 144 while (r3) { 145 MP_ADD_CARRY(r0a, r3, r0a, 0, carry); 146 MP_ADD_CARRY(r0b, 0, r0b, carry, carry); 147 MP_ADD_CARRY(r1a, r3, r1a, carry, carry); 148 MP_ADD_CARRY(r1b, 0, r1b, carry, carry); 149 MP_ADD_CARRY(r2a, 0, r2a, carry, carry); 150 MP_ADD_CARRY(r2b, 0, r2b, carry, carry); 151 r3 = carry; 152 } 153 154 /* check for final reduction */ 155 /* 156 * our field is 0xffffffffffffffff, 0xfffffffffffffffe, 157 * 0xffffffffffffffff. That means we can only be over and need 158 * one more reduction 159 * if r2 == 0xffffffffffffffffff (same as r2+1 == 0) 160 * and 161 * r1 == 0xffffffffffffffffff or 162 * r1 == 0xfffffffffffffffffe and r0 = 0xfffffffffffffffff 163 * In all cases, we subtract the field (or add the 2's 164 * complement value (1,1,0)). (r0, r1, r2) 165 */ 166 if (((r2b == 0xffffffff) && (r2a == 0xffffffff) 167 && (r1b == 0xffffffff) ) && 168 ((r1a == 0xffffffff) || 169 (r1a == 0xfffffffe) && (r0a == 0xffffffff) && 170 (r0b == 0xffffffff)) ) { 171 /* do a quick subtract */ 172 MP_ADD_CARRY(r0a, 1, r0a, 0, carry); 173 MP_ADD_CARRY(r0b, 0, r0b, carry, carry); 174 r1a += 1 + carry; 175 r1b = r2a = r2b = 0; 176 } 177 178 /* set the lower words of r */ 179 if (a != r) { 180 MP_CHECKOK(s_mp_pad(r, 6)); 181 } 182 MP_DIGIT(r, 5) = r2b; 183 MP_DIGIT(r, 4) = r2a; 184 MP_DIGIT(r, 3) = r1b; 185 MP_DIGIT(r, 2) = r1a; 186 MP_DIGIT(r, 1) = r0b; 187 MP_DIGIT(r, 0) = r0a; 188 MP_USED(r) = 6; 189 #else 190 switch (a_used) { 191 case 6: 192 a5 = MP_DIGIT(a, 5); 193 /* FALLTHROUGH */ 194 case 5: 195 a4 = MP_DIGIT(a, 4); 196 /* FALLTHROUGH */ 197 case 4: 198 a3 = MP_DIGIT(a, 3); 199 } 200 201 r2 = MP_DIGIT(a, 2); 202 r1 = MP_DIGIT(a, 1); 203 r0 = MP_DIGIT(a, 0); 204 205 /* implement r = (a2,a1,a0)+(a5,a5,a5)+(a4,a4,0)+(0,a3,a3) */ 206 #ifndef MPI_AMD64_ADD 207 MP_ADD_CARRY(r0, a3, r0, 0, carry); 208 MP_ADD_CARRY(r1, a3, r1, carry, carry); 209 MP_ADD_CARRY(r2, a4, r2, carry, carry); 210 r3 = carry; 211 MP_ADD_CARRY(r0, a5, r0, 0, carry); 212 MP_ADD_CARRY(r1, a5, r1, carry, carry); 213 MP_ADD_CARRY(r2, a5, r2, carry, carry); 214 r3 += carry; 215 MP_ADD_CARRY(r1, a4, r1, 0, carry); 216 MP_ADD_CARRY(r2, 0, r2, carry, carry); 217 r3 += carry; 218 219 #else 220 r2 = MP_DIGIT(a, 2); 221 r1 = MP_DIGIT(a, 1); 222 r0 = MP_DIGIT(a, 0); 223 224 /* set the lower words of r */ 225 __asm__ ( 226 "xorq %3,%3 \n\t" 227 "addq %4,%0 \n\t" 228 "adcq %4,%1 \n\t" 229 "adcq %5,%2 \n\t" 230 "adcq $0,%3 \n\t" 231 "addq %6,%0 \n\t" 232 "adcq %6,%1 \n\t" 233 "adcq %6,%2 \n\t" 234 "adcq $0,%3 \n\t" 235 "addq %5,%1 \n\t" 236 "adcq $0,%2 \n\t" 237 "adcq $0,%3 \n\t" 238 : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(r3), "=r"(a3), 239 "=r"(a4), "=r"(a5) 240 : "0" (r0), "1" (r1), "2" (r2), "3" (r3), 241 "4" (a3), "5" (a4), "6"(a5) 242 : "%cc" ); 243 #endif 244 245 /* reduce out the carry */ 246 while (r3) { 247 #ifndef MPI_AMD64_ADD 248 MP_ADD_CARRY(r0, r3, r0, 0, carry); 249 MP_ADD_CARRY(r1, r3, r1, carry, carry); 250 MP_ADD_CARRY(r2, 0, r2, carry, carry); 251 r3 = carry; 252 #else 253 a3=r3; 254 __asm__ ( 255 "xorq %3,%3 \n\t" 256 "addq %4,%0 \n\t" 257 "adcq %4,%1 \n\t" 258 "adcq $0,%2 \n\t" 259 "adcq $0,%3 \n\t" 260 : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(r3), "=r"(a3) 261 : "0" (r0), "1" (r1), "2" (r2), "3" (r3), "4"(a3) 262 : "%cc" ); 263 #endif 264 } 265 266 /* check for final reduction */ 267 /* 268 * our field is 0xffffffffffffffff, 0xfffffffffffffffe, 269 * 0xffffffffffffffff. That means we can only be over and need 270 * one more reduction 271 * if r2 == 0xffffffffffffffffff (same as r2+1 == 0) 272 * and 273 * r1 == 0xffffffffffffffffff or 274 * r1 == 0xfffffffffffffffffe and r0 = 0xfffffffffffffffff 275 * In all cases, we subtract the field (or add the 2's 276 * complement value (1,1,0)). (r0, r1, r2) 277 */ 278 if (r3 || ((r2 == MP_DIGIT_MAX) && 279 ((r1 == MP_DIGIT_MAX) || 280 ((r1 == (MP_DIGIT_MAX-1)) && (r0 == MP_DIGIT_MAX))))) { 281 /* do a quick subtract */ 282 MP_ADD_CARRY(r0, 1, r0, 0, carry); 283 r1 += 1 + carry; 284 r2 = 0; 285 } 286 /* set the lower words of r */ 287 if (a != r) { 288 MP_CHECKOK(s_mp_pad(r, 3)); 289 } 290 MP_DIGIT(r, 2) = r2; 291 MP_DIGIT(r, 1) = r1; 292 MP_DIGIT(r, 0) = r0; 293 MP_USED(r) = 3; 294 #endif 295 } 296 297 s_mp_clamp(r); 298 CLEANUP: 299 return res; 300 } 301 302 #ifndef ECL_THIRTY_TWO_BIT 303 /* Compute the sum of 192 bit curves. Do the work in-line since the 304 * number of words are so small, we don't want to overhead of mp function 305 * calls. Uses optimized modular reduction for p192. 306 */ 307 mp_err 308 ec_GFp_nistp192_add(const mp_int *a, const mp_int *b, mp_int *r, 309 const GFMethod *meth) 310 { 311 mp_err res = MP_OKAY; 312 mp_digit a0 = 0, a1 = 0, a2 = 0; 313 mp_digit r0 = 0, r1 = 0, r2 = 0; 314 mp_digit carry; 315 316 switch(MP_USED(a)) { 317 case 3: 318 a2 = MP_DIGIT(a,2); 319 /* FALLTHROUGH */ 320 case 2: 321 a1 = MP_DIGIT(a,1); 322 /* FALLTHROUGH */ 323 case 1: 324 a0 = MP_DIGIT(a,0); 325 } 326 switch(MP_USED(b)) { 327 case 3: 328 r2 = MP_DIGIT(b,2); 329 /* FALLTHROUGH */ 330 case 2: 331 r1 = MP_DIGIT(b,1); 332 /* FALLTHROUGH */ 333 case 1: 334 r0 = MP_DIGIT(b,0); 335 } 336 337 #ifndef MPI_AMD64_ADD 338 MP_ADD_CARRY(a0, r0, r0, 0, carry); 339 MP_ADD_CARRY(a1, r1, r1, carry, carry); 340 MP_ADD_CARRY(a2, r2, r2, carry, carry); 341 #else 342 __asm__ ( 343 "xorq %3,%3 \n\t" 344 "addq %4,%0 \n\t" 345 "adcq %5,%1 \n\t" 346 "adcq %6,%2 \n\t" 347 "adcq $0,%3 \n\t" 348 : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(carry) 349 : "r" (a0), "r" (a1), "r" (a2), "0" (r0), 350 "1" (r1), "2" (r2) 351 : "%cc" ); 352 #endif 353 354 /* Do quick 'subract' if we've gone over 355 * (add the 2's complement of the curve field) */ 356 if (carry || ((r2 == MP_DIGIT_MAX) && 357 ((r1 == MP_DIGIT_MAX) || 358 ((r1 == (MP_DIGIT_MAX-1)) && (r0 == MP_DIGIT_MAX))))) { 359 #ifndef MPI_AMD64_ADD 360 MP_ADD_CARRY(r0, 1, r0, 0, carry); 361 MP_ADD_CARRY(r1, 1, r1, carry, carry); 362 MP_ADD_CARRY(r2, 0, r2, carry, carry); 363 #else 364 __asm__ ( 365 "addq $1,%0 \n\t" 366 "adcq $1,%1 \n\t" 367 "adcq $0,%2 \n\t" 368 : "=r"(r0), "=r"(r1), "=r"(r2) 369 : "0" (r0), "1" (r1), "2" (r2) 370 : "%cc" ); 371 #endif 372 } 373 374 375 MP_CHECKOK(s_mp_pad(r, 3)); 376 MP_DIGIT(r, 2) = r2; 377 MP_DIGIT(r, 1) = r1; 378 MP_DIGIT(r, 0) = r0; 379 MP_SIGN(r) = MP_ZPOS; 380 MP_USED(r) = 3; 381 s_mp_clamp(r); 382 383 384 CLEANUP: 385 return res; 386 } 387 388 /* Compute the diff of 192 bit curves. Do the work in-line since the 389 * number of words are so small, we don't want to overhead of mp function 390 * calls. Uses optimized modular reduction for p192. 391 */ 392 mp_err 393 ec_GFp_nistp192_sub(const mp_int *a, const mp_int *b, mp_int *r, 394 const GFMethod *meth) 395 { 396 mp_err res = MP_OKAY; 397 mp_digit b0 = 0, b1 = 0, b2 = 0; 398 mp_digit r0 = 0, r1 = 0, r2 = 0; 399 mp_digit borrow; 400 401 switch(MP_USED(a)) { 402 case 3: 403 r2 = MP_DIGIT(a,2); 404 /* FALLTHROUGH */ 405 case 2: 406 r1 = MP_DIGIT(a,1); 407 /* FALLTHROUGH */ 408 case 1: 409 r0 = MP_DIGIT(a,0); 410 } 411 412 switch(MP_USED(b)) { 413 case 3: 414 b2 = MP_DIGIT(b,2); 415 /* FALLTHROUGH */ 416 case 2: 417 b1 = MP_DIGIT(b,1); 418 /* FALLTHROUGH */ 419 case 1: 420 b0 = MP_DIGIT(b,0); 421 } 422 423 #ifndef MPI_AMD64_ADD 424 MP_SUB_BORROW(r0, b0, r0, 0, borrow); 425 MP_SUB_BORROW(r1, b1, r1, borrow, borrow); 426 MP_SUB_BORROW(r2, b2, r2, borrow, borrow); 427 #else 428 __asm__ ( 429 "xorq %3,%3 \n\t" 430 "subq %4,%0 \n\t" 431 "sbbq %5,%1 \n\t" 432 "sbbq %6,%2 \n\t" 433 "adcq $0,%3 \n\t" 434 : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(borrow) 435 : "r" (b0), "r" (b1), "r" (b2), "0" (r0), 436 "1" (r1), "2" (r2) 437 : "%cc" ); 438 #endif 439 440 /* Do quick 'add' if we've gone under 0 441 * (subtract the 2's complement of the curve field) */ 442 if (borrow) { 443 #ifndef MPI_AMD64_ADD 444 MP_SUB_BORROW(r0, 1, r0, 0, borrow); 445 MP_SUB_BORROW(r1, 1, r1, borrow, borrow); 446 MP_SUB_BORROW(r2, 0, r2, borrow, borrow); 447 #else 448 __asm__ ( 449 "subq $1,%0 \n\t" 450 "sbbq $1,%1 \n\t" 451 "sbbq $0,%2 \n\t" 452 : "=r"(r0), "=r"(r1), "=r"(r2) 453 : "0" (r0), "1" (r1), "2" (r2) 454 : "%cc" ); 455 #endif 456 } 457 458 MP_CHECKOK(s_mp_pad(r, 3)); 459 MP_DIGIT(r, 2) = r2; 460 MP_DIGIT(r, 1) = r1; 461 MP_DIGIT(r, 0) = r0; 462 MP_SIGN(r) = MP_ZPOS; 463 MP_USED(r) = 3; 464 s_mp_clamp(r); 465 466 CLEANUP: 467 return res; 468 } 469 470 #endif 471 472 /* Compute the square of polynomial a, reduce modulo p192. Store the 473 * result in r. r could be a. Uses optimized modular reduction for p192. 474 */ 475 mp_err 476 ec_GFp_nistp192_sqr(const mp_int *a, mp_int *r, const GFMethod *meth) 477 { 478 mp_err res = MP_OKAY; 479 480 MP_CHECKOK(mp_sqr(a, r)); 481 MP_CHECKOK(ec_GFp_nistp192_mod(r, r, meth)); 482 CLEANUP: 483 return res; 484 } 485 486 /* Compute the product of two polynomials a and b, reduce modulo p192. 487 * Store the result in r. r could be a or b; a could be b. Uses 488 * optimized modular reduction for p192. */ 489 mp_err 490 ec_GFp_nistp192_mul(const mp_int *a, const mp_int *b, mp_int *r, 491 const GFMethod *meth) 492 { 493 mp_err res = MP_OKAY; 494 495 MP_CHECKOK(mp_mul(a, b, r)); 496 MP_CHECKOK(ec_GFp_nistp192_mod(r, r, meth)); 497 CLEANUP: 498 return res; 499 } 500 501 /* Divides two field elements. If a is NULL, then returns the inverse of 502 * b. */ 503 mp_err 504 ec_GFp_nistp192_div(const mp_int *a, const mp_int *b, mp_int *r, 505 const GFMethod *meth) 506 { 507 mp_err res = MP_OKAY; 508 mp_int t; 509 510 /* If a is NULL, then return the inverse of b, otherwise return a/b. */ 511 if (a == NULL) { 512 return mp_invmod(b, &meth->irr, r); 513 } else { 514 /* MPI doesn't support divmod, so we implement it using invmod and 515 * mulmod. */ 516 MP_CHECKOK(mp_init(&t, FLAG(b))); 517 MP_CHECKOK(mp_invmod(b, &meth->irr, &t)); 518 MP_CHECKOK(mp_mul(a, &t, r)); 519 MP_CHECKOK(ec_GFp_nistp192_mod(r, r, meth)); 520 CLEANUP: 521 mp_clear(&t); 522 return res; 523 } 524 } 525 526 /* Wire in fast field arithmetic and precomputation of base point for 527 * named curves. */ 528 mp_err 529 ec_group_set_gfp192(ECGroup *group, ECCurveName name) 530 { 531 if (name == ECCurve_NIST_P192) { 532 group->meth->field_mod = &ec_GFp_nistp192_mod; 533 group->meth->field_mul = &ec_GFp_nistp192_mul; 534 group->meth->field_sqr = &ec_GFp_nistp192_sqr; 535 group->meth->field_div = &ec_GFp_nistp192_div; 536 #ifndef ECL_THIRTY_TWO_BIT 537 group->meth->field_add = &ec_GFp_nistp192_add; 538 group->meth->field_sub = &ec_GFp_nistp192_sub; 539 #endif 540 } 541 return MP_OKAY; 542 } 543