1/* 2 * Copyright (c) 2007, 2011, Oracle and/or its affiliates. All rights reserved. 3 * Use is subject to license terms. 4 * 5 * This library is free software; you can redistribute it and/or 6 * modify it under the terms of the GNU Lesser General Public 7 * License as published by the Free Software Foundation; either 8 * version 2.1 of the License, or (at your option) any later version. 9 * 10 * This library is distributed in the hope that it will be useful, 11 * but WITHOUT ANY WARRANTY; without even the implied warranty of 12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 13 * Lesser General Public License for more details. 14 * 15 * You should have received a copy of the GNU Lesser General Public License 16 * along with this library; if not, write to the Free Software Foundation, 17 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. 18 * 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20 * or visit www.oracle.com if you need additional information or have any 21 * questions. 22 */ 23 24/* ********************************************************************* 25 * 26 * The Original Code is the elliptic curve math library. 27 * 28 * The Initial Developer of the Original Code is 29 * Sun Microsystems, Inc. 30 * Portions created by the Initial Developer are Copyright (C) 2003 31 * the Initial Developer. All Rights Reserved. 32 * 33 * Contributor(s): 34 * Stephen Fung <fungstep@hotmail.com> and 35 * Douglas Stebila <douglas@stebila.ca>, Sun Microsystems Laboratories 36 * 37 *********************************************************************** */ 38 39#include "mpi.h" 40#include "mp_gf2m.h" 41#include "ecl-priv.h" 42#include "mpi-priv.h" 43#ifndef _KERNEL 44#include <stdlib.h> 45#endif 46 47/* Allocate memory for a new GFMethod object. */ 48GFMethod * 49GFMethod_new(int kmflag) 50{ 51 mp_err res = MP_OKAY; 52 GFMethod *meth; 53#ifdef _KERNEL 54 meth = (GFMethod *) kmem_alloc(sizeof(GFMethod), kmflag); 55#else 56 meth = (GFMethod *) malloc(sizeof(GFMethod)); 57 if (meth == NULL) 58 return NULL; 59#endif 60 meth->constructed = MP_YES; 61 MP_DIGITS(&meth->irr) = 0; 62 meth->extra_free = NULL; 63 MP_CHECKOK(mp_init(&meth->irr, kmflag)); 64 65 CLEANUP: 66 if (res != MP_OKAY) { 67 GFMethod_free(meth); 68 return NULL; 69 } 70 return meth; 71} 72 73/* Construct a generic GFMethod for arithmetic over prime fields with 74 * irreducible irr. */ 75GFMethod * 76GFMethod_consGFp(const mp_int *irr) 77{ 78 mp_err res = MP_OKAY; 79 GFMethod *meth = NULL; 80 81 meth = GFMethod_new(FLAG(irr)); 82 if (meth == NULL) 83 return NULL; 84 85 MP_CHECKOK(mp_copy(irr, &meth->irr)); 86 meth->irr_arr[0] = mpl_significant_bits(irr); 87 meth->irr_arr[1] = meth->irr_arr[2] = meth->irr_arr[3] = 88 meth->irr_arr[4] = 0; 89 switch(MP_USED(&meth->irr)) { 90 /* maybe we need 1 and 2 words here as well?*/ 91 case 3: 92 meth->field_add = &ec_GFp_add_3; 93 meth->field_sub = &ec_GFp_sub_3; 94 break; 95 case 4: 96 meth->field_add = &ec_GFp_add_4; 97 meth->field_sub = &ec_GFp_sub_4; 98 break; 99 case 5: 100 meth->field_add = &ec_GFp_add_5; 101 meth->field_sub = &ec_GFp_sub_5; 102 break; 103 case 6: 104 meth->field_add = &ec_GFp_add_6; 105 meth->field_sub = &ec_GFp_sub_6; 106 break; 107 default: 108 meth->field_add = &ec_GFp_add; 109 meth->field_sub = &ec_GFp_sub; 110 } 111 meth->field_neg = &ec_GFp_neg; 112 meth->field_mod = &ec_GFp_mod; 113 meth->field_mul = &ec_GFp_mul; 114 meth->field_sqr = &ec_GFp_sqr; 115 meth->field_div = &ec_GFp_div; 116 meth->field_enc = NULL; 117 meth->field_dec = NULL; 118 meth->extra1 = NULL; 119 meth->extra2 = NULL; 120 meth->extra_free = NULL; 121 122 CLEANUP: 123 if (res != MP_OKAY) { 124 GFMethod_free(meth); 125 return NULL; 126 } 127 return meth; 128} 129 130/* Construct a generic GFMethod for arithmetic over binary polynomial 131 * fields with irreducible irr that has array representation irr_arr (see 132 * ecl-priv.h for description of the representation). If irr_arr is NULL, 133 * then it is constructed from the bitstring representation. */ 134GFMethod * 135GFMethod_consGF2m(const mp_int *irr, const unsigned int irr_arr[5]) 136{ 137 mp_err res = MP_OKAY; 138 int ret; 139 GFMethod *meth = NULL; 140 141 meth = GFMethod_new(FLAG(irr)); 142 if (meth == NULL) 143 return NULL; 144 145 MP_CHECKOK(mp_copy(irr, &meth->irr)); 146 if (irr_arr != NULL) { 147 /* Irreducible polynomials are either trinomials or pentanomials. */ 148 meth->irr_arr[0] = irr_arr[0]; 149 meth->irr_arr[1] = irr_arr[1]; 150 meth->irr_arr[2] = irr_arr[2]; 151 if (irr_arr[2] > 0) { 152 meth->irr_arr[3] = irr_arr[3]; 153 meth->irr_arr[4] = irr_arr[4]; 154 } else { 155 meth->irr_arr[3] = meth->irr_arr[4] = 0; 156 } 157 } else { 158 ret = mp_bpoly2arr(irr, meth->irr_arr, 5); 159 /* Irreducible polynomials are either trinomials or pentanomials. */ 160 if ((ret != 5) && (ret != 3)) { 161 res = MP_UNDEF; 162 goto CLEANUP; 163 } 164 } 165 meth->field_add = &ec_GF2m_add; 166 meth->field_neg = &ec_GF2m_neg; 167 meth->field_sub = &ec_GF2m_add; 168 meth->field_mod = &ec_GF2m_mod; 169 meth->field_mul = &ec_GF2m_mul; 170 meth->field_sqr = &ec_GF2m_sqr; 171 meth->field_div = &ec_GF2m_div; 172 meth->field_enc = NULL; 173 meth->field_dec = NULL; 174 meth->extra1 = NULL; 175 meth->extra2 = NULL; 176 meth->extra_free = NULL; 177 178 CLEANUP: 179 if (res != MP_OKAY) { 180 GFMethod_free(meth); 181 return NULL; 182 } 183 return meth; 184} 185 186/* Free the memory allocated (if any) to a GFMethod object. */ 187void 188GFMethod_free(GFMethod *meth) 189{ 190 if (meth == NULL) 191 return; 192 if (meth->constructed == MP_NO) 193 return; 194 mp_clear(&meth->irr); 195 if (meth->extra_free != NULL) 196 meth->extra_free(meth); 197#ifdef _KERNEL 198 kmem_free(meth, sizeof(GFMethod)); 199#else 200 free(meth); 201#endif 202} 203 204/* Wrapper functions for generic prime field arithmetic. */ 205 206/* Add two field elements. Assumes that 0 <= a, b < meth->irr */ 207mp_err 208ec_GFp_add(const mp_int *a, const mp_int *b, mp_int *r, 209 const GFMethod *meth) 210{ 211 /* PRE: 0 <= a, b < p = meth->irr POST: 0 <= r < p, r = a + b (mod p) */ 212 mp_err res; 213 214 if ((res = mp_add(a, b, r)) != MP_OKAY) { 215 return res; 216 } 217 if (mp_cmp(r, &meth->irr) >= 0) { 218 return mp_sub(r, &meth->irr, r); 219 } 220 return res; 221} 222 223/* Negates a field element. Assumes that 0 <= a < meth->irr */ 224mp_err 225ec_GFp_neg(const mp_int *a, mp_int *r, const GFMethod *meth) 226{ 227 /* PRE: 0 <= a < p = meth->irr POST: 0 <= r < p, r = -a (mod p) */ 228 229 if (mp_cmp_z(a) == 0) { 230 mp_zero(r); 231 return MP_OKAY; 232 } 233 return mp_sub(&meth->irr, a, r); 234} 235 236/* Subtracts two field elements. Assumes that 0 <= a, b < meth->irr */ 237mp_err 238ec_GFp_sub(const mp_int *a, const mp_int *b, mp_int *r, 239 const GFMethod *meth) 240{ 241 mp_err res = MP_OKAY; 242 243 /* PRE: 0 <= a, b < p = meth->irr POST: 0 <= r < p, r = a - b (mod p) */ 244 res = mp_sub(a, b, r); 245 if (res == MP_RANGE) { 246 MP_CHECKOK(mp_sub(b, a, r)); 247 if (mp_cmp_z(r) < 0) { 248 MP_CHECKOK(mp_add(r, &meth->irr, r)); 249 } 250 MP_CHECKOK(ec_GFp_neg(r, r, meth)); 251 } 252 if (mp_cmp_z(r) < 0) { 253 MP_CHECKOK(mp_add(r, &meth->irr, r)); 254 } 255 CLEANUP: 256 return res; 257} 258/* 259 * Inline adds for small curve lengths. 260 */ 261/* 3 words */ 262mp_err 263ec_GFp_add_3(const mp_int *a, const mp_int *b, mp_int *r, 264 const GFMethod *meth) 265{ 266 mp_err res = MP_OKAY; 267 mp_digit a0 = 0, a1 = 0, a2 = 0; 268 mp_digit r0 = 0, r1 = 0, r2 = 0; 269 mp_digit carry; 270 271 switch(MP_USED(a)) { 272 case 3: 273 a2 = MP_DIGIT(a,2); 274 case 2: 275 a1 = MP_DIGIT(a,1); 276 case 1: 277 a0 = MP_DIGIT(a,0); 278 } 279 switch(MP_USED(b)) { 280 case 3: 281 r2 = MP_DIGIT(b,2); 282 case 2: 283 r1 = MP_DIGIT(b,1); 284 case 1: 285 r0 = MP_DIGIT(b,0); 286 } 287 288#ifndef MPI_AMD64_ADD 289 MP_ADD_CARRY_ZERO(a0, r0, r0, carry); 290 MP_ADD_CARRY(a1, r1, r1, carry, carry); 291 MP_ADD_CARRY(a2, r2, r2, carry, carry); 292#else 293 __asm__ ( 294 "xorq %3,%3 \n\t" 295 "addq %4,%0 \n\t" 296 "adcq %5,%1 \n\t" 297 "adcq %6,%2 \n\t" 298 "adcq $0,%3 \n\t" 299 : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(carry) 300 : "r" (a0), "r" (a1), "r" (a2), 301 "0" (r0), "1" (r1), "2" (r2) 302 : "%cc" ); 303#endif 304 305 MP_CHECKOK(s_mp_pad(r, 3)); 306 MP_DIGIT(r, 2) = r2; 307 MP_DIGIT(r, 1) = r1; 308 MP_DIGIT(r, 0) = r0; 309 MP_SIGN(r) = MP_ZPOS; 310 MP_USED(r) = 3; 311 312 /* Do quick 'subract' if we've gone over 313 * (add the 2's complement of the curve field) */ 314 a2 = MP_DIGIT(&meth->irr,2); 315 if (carry || r2 > a2 || 316 ((r2 == a2) && mp_cmp(r,&meth->irr) != MP_LT)) { 317 a1 = MP_DIGIT(&meth->irr,1); 318 a0 = MP_DIGIT(&meth->irr,0); 319#ifndef MPI_AMD64_ADD 320 MP_SUB_BORROW(r0, a0, r0, 0, carry); 321 MP_SUB_BORROW(r1, a1, r1, carry, carry); 322 MP_SUB_BORROW(r2, a2, r2, carry, carry); 323#else 324 __asm__ ( 325 "subq %3,%0 \n\t" 326 "sbbq %4,%1 \n\t" 327 "sbbq %5,%2 \n\t" 328 : "=r"(r0), "=r"(r1), "=r"(r2) 329 : "r" (a0), "r" (a1), "r" (a2), 330 "0" (r0), "1" (r1), "2" (r2) 331 : "%cc" ); 332#endif 333 MP_DIGIT(r, 2) = r2; 334 MP_DIGIT(r, 1) = r1; 335 MP_DIGIT(r, 0) = r0; 336 } 337 338 s_mp_clamp(r); 339 340 CLEANUP: 341 return res; 342} 343 344/* 4 words */ 345mp_err 346ec_GFp_add_4(const mp_int *a, const mp_int *b, mp_int *r, 347 const GFMethod *meth) 348{ 349 mp_err res = MP_OKAY; 350 mp_digit a0 = 0, a1 = 0, a2 = 0, a3 = 0; 351 mp_digit r0 = 0, r1 = 0, r2 = 0, r3 = 0; 352 mp_digit carry; 353 354 switch(MP_USED(a)) { 355 case 4: 356 a3 = MP_DIGIT(a,3); 357 case 3: 358 a2 = MP_DIGIT(a,2); 359 case 2: 360 a1 = MP_DIGIT(a,1); 361 case 1: 362 a0 = MP_DIGIT(a,0); 363 } 364 switch(MP_USED(b)) { 365 case 4: 366 r3 = MP_DIGIT(b,3); 367 case 3: 368 r2 = MP_DIGIT(b,2); 369 case 2: 370 r1 = MP_DIGIT(b,1); 371 case 1: 372 r0 = MP_DIGIT(b,0); 373 } 374 375#ifndef MPI_AMD64_ADD 376 MP_ADD_CARRY_ZERO(a0, r0, r0, carry); 377 MP_ADD_CARRY(a1, r1, r1, carry, carry); 378 MP_ADD_CARRY(a2, r2, r2, carry, carry); 379 MP_ADD_CARRY(a3, r3, r3, carry, carry); 380#else 381 __asm__ ( 382 "xorq %4,%4 \n\t" 383 "addq %5,%0 \n\t" 384 "adcq %6,%1 \n\t" 385 "adcq %7,%2 \n\t" 386 "adcq %8,%3 \n\t" 387 "adcq $0,%4 \n\t" 388 : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(r3), "=r"(carry) 389 : "r" (a0), "r" (a1), "r" (a2), "r" (a3), 390 "0" (r0), "1" (r1), "2" (r2), "3" (r3) 391 : "%cc" ); 392#endif 393 394 MP_CHECKOK(s_mp_pad(r, 4)); 395 MP_DIGIT(r, 3) = r3; 396 MP_DIGIT(r, 2) = r2; 397 MP_DIGIT(r, 1) = r1; 398 MP_DIGIT(r, 0) = r0; 399 MP_SIGN(r) = MP_ZPOS; 400 MP_USED(r) = 4; 401 402 /* Do quick 'subract' if we've gone over 403 * (add the 2's complement of the curve field) */ 404 a3 = MP_DIGIT(&meth->irr,3); 405 if (carry || r3 > a3 || 406 ((r3 == a3) && mp_cmp(r,&meth->irr) != MP_LT)) { 407 a2 = MP_DIGIT(&meth->irr,2); 408 a1 = MP_DIGIT(&meth->irr,1); 409 a0 = MP_DIGIT(&meth->irr,0); 410#ifndef MPI_AMD64_ADD 411 MP_SUB_BORROW(r0, a0, r0, 0, carry); 412 MP_SUB_BORROW(r1, a1, r1, carry, carry); 413 MP_SUB_BORROW(r2, a2, r2, carry, carry); 414 MP_SUB_BORROW(r3, a3, r3, carry, carry); 415#else 416 __asm__ ( 417 "subq %4,%0 \n\t" 418 "sbbq %5,%1 \n\t" 419 "sbbq %6,%2 \n\t" 420 "sbbq %7,%3 \n\t" 421 : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(r3) 422 : "r" (a0), "r" (a1), "r" (a2), "r" (a3), 423 "0" (r0), "1" (r1), "2" (r2), "3" (r3) 424 : "%cc" ); 425#endif 426 MP_DIGIT(r, 3) = r3; 427 MP_DIGIT(r, 2) = r2; 428 MP_DIGIT(r, 1) = r1; 429 MP_DIGIT(r, 0) = r0; 430 } 431 432 s_mp_clamp(r); 433 434 CLEANUP: 435 return res; 436} 437 438/* 5 words */ 439mp_err 440ec_GFp_add_5(const mp_int *a, const mp_int *b, mp_int *r, 441 const GFMethod *meth) 442{ 443 mp_err res = MP_OKAY; 444 mp_digit a0 = 0, a1 = 0, a2 = 0, a3 = 0, a4 = 0; 445 mp_digit r0 = 0, r1 = 0, r2 = 0, r3 = 0, r4 = 0; 446 mp_digit carry; 447 448 switch(MP_USED(a)) { 449 case 5: 450 a4 = MP_DIGIT(a,4); 451 case 4: 452 a3 = MP_DIGIT(a,3); 453 case 3: 454 a2 = MP_DIGIT(a,2); 455 case 2: 456 a1 = MP_DIGIT(a,1); 457 case 1: 458 a0 = MP_DIGIT(a,0); 459 } 460 switch(MP_USED(b)) { 461 case 5: 462 r4 = MP_DIGIT(b,4); 463 case 4: 464 r3 = MP_DIGIT(b,3); 465 case 3: 466 r2 = MP_DIGIT(b,2); 467 case 2: 468 r1 = MP_DIGIT(b,1); 469 case 1: 470 r0 = MP_DIGIT(b,0); 471 } 472 473 MP_ADD_CARRY_ZERO(a0, r0, r0, carry); 474 MP_ADD_CARRY(a1, r1, r1, carry, carry); 475 MP_ADD_CARRY(a2, r2, r2, carry, carry); 476 MP_ADD_CARRY(a3, r3, r3, carry, carry); 477 MP_ADD_CARRY(a4, r4, r4, carry, carry); 478 479 MP_CHECKOK(s_mp_pad(r, 5)); 480 MP_DIGIT(r, 4) = r4; 481 MP_DIGIT(r, 3) = r3; 482 MP_DIGIT(r, 2) = r2; 483 MP_DIGIT(r, 1) = r1; 484 MP_DIGIT(r, 0) = r0; 485 MP_SIGN(r) = MP_ZPOS; 486 MP_USED(r) = 5; 487 488 /* Do quick 'subract' if we've gone over 489 * (add the 2's complement of the curve field) */ 490 a4 = MP_DIGIT(&meth->irr,4); 491 if (carry || r4 > a4 || 492 ((r4 == a4) && mp_cmp(r,&meth->irr) != MP_LT)) { 493 a3 = MP_DIGIT(&meth->irr,3); 494 a2 = MP_DIGIT(&meth->irr,2); 495 a1 = MP_DIGIT(&meth->irr,1); 496 a0 = MP_DIGIT(&meth->irr,0); 497 MP_SUB_BORROW(r0, a0, r0, 0, carry); 498 MP_SUB_BORROW(r1, a1, r1, carry, carry); 499 MP_SUB_BORROW(r2, a2, r2, carry, carry); 500 MP_SUB_BORROW(r3, a3, r3, carry, carry); 501 MP_SUB_BORROW(r4, a4, r4, carry, carry); 502 MP_DIGIT(r, 4) = r4; 503 MP_DIGIT(r, 3) = r3; 504 MP_DIGIT(r, 2) = r2; 505 MP_DIGIT(r, 1) = r1; 506 MP_DIGIT(r, 0) = r0; 507 } 508 509 s_mp_clamp(r); 510 511 CLEANUP: 512 return res; 513} 514 515/* 6 words */ 516mp_err 517ec_GFp_add_6(const mp_int *a, const mp_int *b, mp_int *r, 518 const GFMethod *meth) 519{ 520 mp_err res = MP_OKAY; 521 mp_digit a0 = 0, a1 = 0, a2 = 0, a3 = 0, a4 = 0, a5 = 0; 522 mp_digit r0 = 0, r1 = 0, r2 = 0, r3 = 0, r4 = 0, r5 = 0; 523 mp_digit carry; 524 525 switch(MP_USED(a)) { 526 case 6: 527 a5 = MP_DIGIT(a,5); 528 case 5: 529 a4 = MP_DIGIT(a,4); 530 case 4: 531 a3 = MP_DIGIT(a,3); 532 case 3: 533 a2 = MP_DIGIT(a,2); 534 case 2: 535 a1 = MP_DIGIT(a,1); 536 case 1: 537 a0 = MP_DIGIT(a,0); 538 } 539 switch(MP_USED(b)) { 540 case 6: 541 r5 = MP_DIGIT(b,5); 542 case 5: 543 r4 = MP_DIGIT(b,4); 544 case 4: 545 r3 = MP_DIGIT(b,3); 546 case 3: 547 r2 = MP_DIGIT(b,2); 548 case 2: 549 r1 = MP_DIGIT(b,1); 550 case 1: 551 r0 = MP_DIGIT(b,0); 552 } 553 554 MP_ADD_CARRY_ZERO(a0, r0, r0, carry); 555 MP_ADD_CARRY(a1, r1, r1, carry, carry); 556 MP_ADD_CARRY(a2, r2, r2, carry, carry); 557 MP_ADD_CARRY(a3, r3, r3, carry, carry); 558 MP_ADD_CARRY(a4, r4, r4, carry, carry); 559 MP_ADD_CARRY(a5, r5, r5, carry, carry); 560 561 MP_CHECKOK(s_mp_pad(r, 6)); 562 MP_DIGIT(r, 5) = r5; 563 MP_DIGIT(r, 4) = r4; 564 MP_DIGIT(r, 3) = r3; 565 MP_DIGIT(r, 2) = r2; 566 MP_DIGIT(r, 1) = r1; 567 MP_DIGIT(r, 0) = r0; 568 MP_SIGN(r) = MP_ZPOS; 569 MP_USED(r) = 6; 570 571 /* Do quick 'subract' if we've gone over 572 * (add the 2's complement of the curve field) */ 573 a5 = MP_DIGIT(&meth->irr,5); 574 if (carry || r5 > a5 || 575 ((r5 == a5) && mp_cmp(r,&meth->irr) != MP_LT)) { 576 a4 = MP_DIGIT(&meth->irr,4); 577 a3 = MP_DIGIT(&meth->irr,3); 578 a2 = MP_DIGIT(&meth->irr,2); 579 a1 = MP_DIGIT(&meth->irr,1); 580 a0 = MP_DIGIT(&meth->irr,0); 581 MP_SUB_BORROW(r0, a0, r0, 0, carry); 582 MP_SUB_BORROW(r1, a1, r1, carry, carry); 583 MP_SUB_BORROW(r2, a2, r2, carry, carry); 584 MP_SUB_BORROW(r3, a3, r3, carry, carry); 585 MP_SUB_BORROW(r4, a4, r4, carry, carry); 586 MP_SUB_BORROW(r5, a5, r5, carry, carry); 587 MP_DIGIT(r, 5) = r5; 588 MP_DIGIT(r, 4) = r4; 589 MP_DIGIT(r, 3) = r3; 590 MP_DIGIT(r, 2) = r2; 591 MP_DIGIT(r, 1) = r1; 592 MP_DIGIT(r, 0) = r0; 593 } 594 595 s_mp_clamp(r); 596 597 CLEANUP: 598 return res; 599} 600 601/* 602 * The following subraction functions do in-line subractions based 603 * on our curve size. 604 * 605 * ... 3 words 606 */ 607mp_err 608ec_GFp_sub_3(const mp_int *a, const mp_int *b, mp_int *r, 609 const GFMethod *meth) 610{ 611 mp_err res = MP_OKAY; 612 mp_digit b0 = 0, b1 = 0, b2 = 0; 613 mp_digit r0 = 0, r1 = 0, r2 = 0; 614 mp_digit borrow; 615 616 switch(MP_USED(a)) { 617 case 3: 618 r2 = MP_DIGIT(a,2); 619 case 2: 620 r1 = MP_DIGIT(a,1); 621 case 1: 622 r0 = MP_DIGIT(a,0); 623 } 624 switch(MP_USED(b)) { 625 case 3: 626 b2 = MP_DIGIT(b,2); 627 case 2: 628 b1 = MP_DIGIT(b,1); 629 case 1: 630 b0 = MP_DIGIT(b,0); 631 } 632 633#ifndef MPI_AMD64_ADD 634 MP_SUB_BORROW(r0, b0, r0, 0, borrow); 635 MP_SUB_BORROW(r1, b1, r1, borrow, borrow); 636 MP_SUB_BORROW(r2, b2, r2, borrow, borrow); 637#else 638 __asm__ ( 639 "xorq %3,%3 \n\t" 640 "subq %4,%0 \n\t" 641 "sbbq %5,%1 \n\t" 642 "sbbq %6,%2 \n\t" 643 "adcq $0,%3 \n\t" 644 : "=r"(r0), "=r"(r1), "=r"(r2), "=r" (borrow) 645 : "r" (b0), "r" (b1), "r" (b2), 646 "0" (r0), "1" (r1), "2" (r2) 647 : "%cc" ); 648#endif 649 650 /* Do quick 'add' if we've gone under 0 651 * (subtract the 2's complement of the curve field) */ 652 if (borrow) { 653 b2 = MP_DIGIT(&meth->irr,2); 654 b1 = MP_DIGIT(&meth->irr,1); 655 b0 = MP_DIGIT(&meth->irr,0); 656#ifndef MPI_AMD64_ADD 657 MP_ADD_CARRY_ZERO(b0, r0, r0, borrow); 658 MP_ADD_CARRY(b1, r1, r1, borrow, borrow); 659 MP_ADD_CARRY(b2, r2, r2, borrow, borrow); 660#else 661 __asm__ ( 662 "addq %3,%0 \n\t" 663 "adcq %4,%1 \n\t" 664 "adcq %5,%2 \n\t" 665 : "=r"(r0), "=r"(r1), "=r"(r2) 666 : "r" (b0), "r" (b1), "r" (b2), 667 "0" (r0), "1" (r1), "2" (r2) 668 : "%cc" ); 669#endif 670 } 671 672#ifdef MPI_AMD64_ADD 673 /* compiler fakeout? */ 674 if ((r2 == b0) && (r1 == b0) && (r0 == b0)) { 675 MP_CHECKOK(s_mp_pad(r, 4)); 676 } 677#endif 678 MP_CHECKOK(s_mp_pad(r, 3)); 679 MP_DIGIT(r, 2) = r2; 680 MP_DIGIT(r, 1) = r1; 681 MP_DIGIT(r, 0) = r0; 682 MP_SIGN(r) = MP_ZPOS; 683 MP_USED(r) = 3; 684 s_mp_clamp(r); 685 686 CLEANUP: 687 return res; 688} 689 690/* 4 words */ 691mp_err 692ec_GFp_sub_4(const mp_int *a, const mp_int *b, mp_int *r, 693 const GFMethod *meth) 694{ 695 mp_err res = MP_OKAY; 696 mp_digit b0 = 0, b1 = 0, b2 = 0, b3 = 0; 697 mp_digit r0 = 0, r1 = 0, r2 = 0, r3 = 0; 698 mp_digit borrow; 699 700 switch(MP_USED(a)) { 701 case 4: 702 r3 = MP_DIGIT(a,3); 703 case 3: 704 r2 = MP_DIGIT(a,2); 705 case 2: 706 r1 = MP_DIGIT(a,1); 707 case 1: 708 r0 = MP_DIGIT(a,0); 709 } 710 switch(MP_USED(b)) { 711 case 4: 712 b3 = MP_DIGIT(b,3); 713 case 3: 714 b2 = MP_DIGIT(b,2); 715 case 2: 716 b1 = MP_DIGIT(b,1); 717 case 1: 718 b0 = MP_DIGIT(b,0); 719 } 720 721#ifndef MPI_AMD64_ADD 722 MP_SUB_BORROW(r0, b0, r0, 0, borrow); 723 MP_SUB_BORROW(r1, b1, r1, borrow, borrow); 724 MP_SUB_BORROW(r2, b2, r2, borrow, borrow); 725 MP_SUB_BORROW(r3, b3, r3, borrow, borrow); 726#else 727 __asm__ ( 728 "xorq %4,%4 \n\t" 729 "subq %5,%0 \n\t" 730 "sbbq %6,%1 \n\t" 731 "sbbq %7,%2 \n\t" 732 "sbbq %8,%3 \n\t" 733 "adcq $0,%4 \n\t" 734 : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(r3), "=r" (borrow) 735 : "r" (b0), "r" (b1), "r" (b2), "r" (b3), 736 "0" (r0), "1" (r1), "2" (r2), "3" (r3) 737 : "%cc" ); 738#endif 739 740 /* Do quick 'add' if we've gone under 0 741 * (subtract the 2's complement of the curve field) */ 742 if (borrow) { 743 b3 = MP_DIGIT(&meth->irr,3); 744 b2 = MP_DIGIT(&meth->irr,2); 745 b1 = MP_DIGIT(&meth->irr,1); 746 b0 = MP_DIGIT(&meth->irr,0); 747#ifndef MPI_AMD64_ADD 748 MP_ADD_CARRY_ZERO(b0, r0, r0, borrow); 749 MP_ADD_CARRY(b1, r1, r1, borrow, borrow); 750 MP_ADD_CARRY(b2, r2, r2, borrow, borrow); 751 MP_ADD_CARRY(b3, r3, r3, borrow, borrow); 752#else 753 __asm__ ( 754 "addq %4,%0 \n\t" 755 "adcq %5,%1 \n\t" 756 "adcq %6,%2 \n\t" 757 "adcq %7,%3 \n\t" 758 : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(r3) 759 : "r" (b0), "r" (b1), "r" (b2), "r" (b3), 760 "0" (r0), "1" (r1), "2" (r2), "3" (r3) 761 : "%cc" ); 762#endif 763 } 764#ifdef MPI_AMD64_ADD 765 /* compiler fakeout? */ 766 if ((r3 == b0) && (r1 == b0) && (r0 == b0)) { 767 MP_CHECKOK(s_mp_pad(r, 4)); 768 } 769#endif 770 MP_CHECKOK(s_mp_pad(r, 4)); 771 MP_DIGIT(r, 3) = r3; 772 MP_DIGIT(r, 2) = r2; 773 MP_DIGIT(r, 1) = r1; 774 MP_DIGIT(r, 0) = r0; 775 MP_SIGN(r) = MP_ZPOS; 776 MP_USED(r) = 4; 777 s_mp_clamp(r); 778 779 CLEANUP: 780 return res; 781} 782 783/* 5 words */ 784mp_err 785ec_GFp_sub_5(const mp_int *a, const mp_int *b, mp_int *r, 786 const GFMethod *meth) 787{ 788 mp_err res = MP_OKAY; 789 mp_digit b0 = 0, b1 = 0, b2 = 0, b3 = 0, b4 = 0; 790 mp_digit r0 = 0, r1 = 0, r2 = 0, r3 = 0, r4 = 0; 791 mp_digit borrow; 792 793 switch(MP_USED(a)) { 794 case 5: 795 r4 = MP_DIGIT(a,4); 796 case 4: 797 r3 = MP_DIGIT(a,3); 798 case 3: 799 r2 = MP_DIGIT(a,2); 800 case 2: 801 r1 = MP_DIGIT(a,1); 802 case 1: 803 r0 = MP_DIGIT(a,0); 804 } 805 switch(MP_USED(b)) { 806 case 5: 807 b4 = MP_DIGIT(b,4); 808 case 4: 809 b3 = MP_DIGIT(b,3); 810 case 3: 811 b2 = MP_DIGIT(b,2); 812 case 2: 813 b1 = MP_DIGIT(b,1); 814 case 1: 815 b0 = MP_DIGIT(b,0); 816 } 817 818 MP_SUB_BORROW(r0, b0, r0, 0, borrow); 819 MP_SUB_BORROW(r1, b1, r1, borrow, borrow); 820 MP_SUB_BORROW(r2, b2, r2, borrow, borrow); 821 MP_SUB_BORROW(r3, b3, r3, borrow, borrow); 822 MP_SUB_BORROW(r4, b4, r4, borrow, borrow); 823 824 /* Do quick 'add' if we've gone under 0 825 * (subtract the 2's complement of the curve field) */ 826 if (borrow) { 827 b4 = MP_DIGIT(&meth->irr,4); 828 b3 = MP_DIGIT(&meth->irr,3); 829 b2 = MP_DIGIT(&meth->irr,2); 830 b1 = MP_DIGIT(&meth->irr,1); 831 b0 = MP_DIGIT(&meth->irr,0); 832 MP_ADD_CARRY_ZERO(b0, r0, r0, borrow); 833 MP_ADD_CARRY(b1, r1, r1, borrow, borrow); 834 MP_ADD_CARRY(b2, r2, r2, borrow, borrow); 835 MP_ADD_CARRY(b3, r3, r3, borrow, borrow); 836 } 837 MP_CHECKOK(s_mp_pad(r, 5)); 838 MP_DIGIT(r, 4) = r4; 839 MP_DIGIT(r, 3) = r3; 840 MP_DIGIT(r, 2) = r2; 841 MP_DIGIT(r, 1) = r1; 842 MP_DIGIT(r, 0) = r0; 843 MP_SIGN(r) = MP_ZPOS; 844 MP_USED(r) = 5; 845 s_mp_clamp(r); 846 847 CLEANUP: 848 return res; 849} 850 851/* 6 words */ 852mp_err 853ec_GFp_sub_6(const mp_int *a, const mp_int *b, mp_int *r, 854 const GFMethod *meth) 855{ 856 mp_err res = MP_OKAY; 857 mp_digit b0 = 0, b1 = 0, b2 = 0, b3 = 0, b4 = 0, b5 = 0; 858 mp_digit r0 = 0, r1 = 0, r2 = 0, r3 = 0, r4 = 0, r5 = 0; 859 mp_digit borrow; 860 861 switch(MP_USED(a)) { 862 case 6: 863 r5 = MP_DIGIT(a,5); 864 case 5: 865 r4 = MP_DIGIT(a,4); 866 case 4: 867 r3 = MP_DIGIT(a,3); 868 case 3: 869 r2 = MP_DIGIT(a,2); 870 case 2: 871 r1 = MP_DIGIT(a,1); 872 case 1: 873 r0 = MP_DIGIT(a,0); 874 } 875 switch(MP_USED(b)) { 876 case 6: 877 b5 = MP_DIGIT(b,5); 878 case 5: 879 b4 = MP_DIGIT(b,4); 880 case 4: 881 b3 = MP_DIGIT(b,3); 882 case 3: 883 b2 = MP_DIGIT(b,2); 884 case 2: 885 b1 = MP_DIGIT(b,1); 886 case 1: 887 b0 = MP_DIGIT(b,0); 888 } 889 890 MP_SUB_BORROW(r0, b0, r0, 0, borrow); 891 MP_SUB_BORROW(r1, b1, r1, borrow, borrow); 892 MP_SUB_BORROW(r2, b2, r2, borrow, borrow); 893 MP_SUB_BORROW(r3, b3, r3, borrow, borrow); 894 MP_SUB_BORROW(r4, b4, r4, borrow, borrow); 895 MP_SUB_BORROW(r5, b5, r5, borrow, borrow); 896 897 /* Do quick 'add' if we've gone under 0 898 * (subtract the 2's complement of the curve field) */ 899 if (borrow) { 900 b5 = MP_DIGIT(&meth->irr,5); 901 b4 = MP_DIGIT(&meth->irr,4); 902 b3 = MP_DIGIT(&meth->irr,3); 903 b2 = MP_DIGIT(&meth->irr,2); 904 b1 = MP_DIGIT(&meth->irr,1); 905 b0 = MP_DIGIT(&meth->irr,0); 906 MP_ADD_CARRY_ZERO(b0, r0, r0, borrow); 907 MP_ADD_CARRY(b1, r1, r1, borrow, borrow); 908 MP_ADD_CARRY(b2, r2, r2, borrow, borrow); 909 MP_ADD_CARRY(b3, r3, r3, borrow, borrow); 910 MP_ADD_CARRY(b4, r4, r4, borrow, borrow); 911 } 912 913 MP_CHECKOK(s_mp_pad(r, 6)); 914 MP_DIGIT(r, 5) = r5; 915 MP_DIGIT(r, 4) = r4; 916 MP_DIGIT(r, 3) = r3; 917 MP_DIGIT(r, 2) = r2; 918 MP_DIGIT(r, 1) = r1; 919 MP_DIGIT(r, 0) = r0; 920 MP_SIGN(r) = MP_ZPOS; 921 MP_USED(r) = 6; 922 s_mp_clamp(r); 923 924 CLEANUP: 925 return res; 926} 927 928 929/* Reduces an integer to a field element. */ 930mp_err 931ec_GFp_mod(const mp_int *a, mp_int *r, const GFMethod *meth) 932{ 933 return mp_mod(a, &meth->irr, r); 934} 935 936/* Multiplies two field elements. */ 937mp_err 938ec_GFp_mul(const mp_int *a, const mp_int *b, mp_int *r, 939 const GFMethod *meth) 940{ 941 return mp_mulmod(a, b, &meth->irr, r); 942} 943 944/* Squares a field element. */ 945mp_err 946ec_GFp_sqr(const mp_int *a, mp_int *r, const GFMethod *meth) 947{ 948 return mp_sqrmod(a, &meth->irr, r); 949} 950 951/* Divides two field elements. If a is NULL, then returns the inverse of 952 * b. */ 953mp_err 954ec_GFp_div(const mp_int *a, const mp_int *b, mp_int *r, 955 const GFMethod *meth) 956{ 957 mp_err res = MP_OKAY; 958 mp_int t; 959 960 /* If a is NULL, then return the inverse of b, otherwise return a/b. */ 961 if (a == NULL) { 962 return mp_invmod(b, &meth->irr, r); 963 } else { 964 /* MPI doesn't support divmod, so we implement it using invmod and 965 * mulmod. */ 966 MP_CHECKOK(mp_init(&t, FLAG(b))); 967 MP_CHECKOK(mp_invmod(b, &meth->irr, &t)); 968 MP_CHECKOK(mp_mulmod(a, &t, &meth->irr, r)); 969 CLEANUP: 970 mp_clear(&t); 971 return res; 972 } 973} 974 975/* Wrapper functions for generic binary polynomial field arithmetic. */ 976 977/* Adds two field elements. */ 978mp_err 979ec_GF2m_add(const mp_int *a, const mp_int *b, mp_int *r, 980 const GFMethod *meth) 981{ 982 return mp_badd(a, b, r); 983} 984 985/* Negates a field element. Note that for binary polynomial fields, the 986 * negation of a field element is the field element itself. */ 987mp_err 988ec_GF2m_neg(const mp_int *a, mp_int *r, const GFMethod *meth) 989{ 990 if (a == r) { 991 return MP_OKAY; 992 } else { 993 return mp_copy(a, r); 994 } 995} 996 997/* Reduces a binary polynomial to a field element. */ 998mp_err 999ec_GF2m_mod(const mp_int *a, mp_int *r, const GFMethod *meth) 1000{ 1001 return mp_bmod(a, meth->irr_arr, r); 1002} 1003 1004/* Multiplies two field elements. */ 1005mp_err 1006ec_GF2m_mul(const mp_int *a, const mp_int *b, mp_int *r, 1007 const GFMethod *meth) 1008{ 1009 return mp_bmulmod(a, b, meth->irr_arr, r); 1010} 1011 1012/* Squares a field element. */ 1013mp_err 1014ec_GF2m_sqr(const mp_int *a, mp_int *r, const GFMethod *meth) 1015{ 1016 return mp_bsqrmod(a, meth->irr_arr, r); 1017} 1018 1019/* Divides two field elements. If a is NULL, then returns the inverse of 1020 * b. */ 1021mp_err 1022ec_GF2m_div(const mp_int *a, const mp_int *b, mp_int *r, 1023 const GFMethod *meth) 1024{ 1025 mp_err res = MP_OKAY; 1026 mp_int t; 1027 1028 /* If a is NULL, then return the inverse of b, otherwise return a/b. */ 1029 if (a == NULL) { 1030 /* The GF(2^m) portion of MPI doesn't support invmod, so we 1031 * compute 1/b. */ 1032 MP_CHECKOK(mp_init(&t, FLAG(b))); 1033 MP_CHECKOK(mp_set_int(&t, 1)); 1034 MP_CHECKOK(mp_bdivmod(&t, b, &meth->irr, meth->irr_arr, r)); 1035 CLEANUP: 1036 mp_clear(&t); 1037 return res; 1038 } else { 1039 return mp_bdivmod(a, b, &meth->irr, meth->irr_arr, r); 1040 } 1041} 1042