michael@0: /* This Source Code Form is subject to the terms of the Mozilla Public michael@0: * License, v. 2.0. If a copy of the MPL was not distributed with this michael@0: * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ michael@0: michael@0: #include "ecp.h" michael@0: #include "mpi.h" michael@0: #include "mplogic.h" michael@0: #include "mpi-priv.h" michael@0: michael@0: #define ECP192_DIGITS ECL_CURVE_DIGITS(192) michael@0: michael@0: /* Fast modular reduction for p192 = 2^192 - 2^64 - 1. a can be r. Uses michael@0: * algorithm 7 from Brown, Hankerson, Lopez, Menezes. Software michael@0: * Implementation of the NIST Elliptic Curves over Prime Fields. */ michael@0: static mp_err michael@0: ec_GFp_nistp192_mod(const mp_int *a, mp_int *r, const GFMethod *meth) michael@0: { michael@0: mp_err res = MP_OKAY; michael@0: mp_size a_used = MP_USED(a); michael@0: mp_digit r3; michael@0: #ifndef MPI_AMD64_ADD michael@0: mp_digit carry; michael@0: #endif michael@0: #ifdef ECL_THIRTY_TWO_BIT michael@0: mp_digit a5a = 0, a5b = 0, a4a = 0, a4b = 0, a3a = 0, a3b = 0; michael@0: mp_digit r0a, r0b, r1a, r1b, r2a, r2b; michael@0: #else michael@0: mp_digit a5 = 0, a4 = 0, a3 = 0; michael@0: mp_digit r0, r1, r2; michael@0: #endif michael@0: michael@0: /* reduction not needed if a is not larger than field size */ michael@0: if (a_used < ECP192_DIGITS) { michael@0: if (a == r) { michael@0: return MP_OKAY; michael@0: } michael@0: return mp_copy(a, r); michael@0: } michael@0: michael@0: /* for polynomials larger than twice the field size, use regular michael@0: * reduction */ michael@0: if (a_used > ECP192_DIGITS*2) { michael@0: MP_CHECKOK(mp_mod(a, &meth->irr, r)); michael@0: } else { michael@0: /* copy out upper words of a */ michael@0: michael@0: #ifdef ECL_THIRTY_TWO_BIT michael@0: michael@0: /* in all the math below, michael@0: * nXb is most signifiant, nXa is least significant */ michael@0: switch (a_used) { michael@0: case 12: michael@0: a5b = MP_DIGIT(a, 11); michael@0: case 11: michael@0: a5a = MP_DIGIT(a, 10); michael@0: case 10: michael@0: a4b = MP_DIGIT(a, 9); michael@0: case 9: michael@0: a4a = MP_DIGIT(a, 8); michael@0: case 8: michael@0: a3b = MP_DIGIT(a, 7); michael@0: case 7: michael@0: a3a = MP_DIGIT(a, 6); michael@0: } michael@0: michael@0: michael@0: r2b= MP_DIGIT(a, 5); michael@0: r2a= MP_DIGIT(a, 4); michael@0: r1b = MP_DIGIT(a, 3); michael@0: r1a = MP_DIGIT(a, 2); michael@0: r0b = MP_DIGIT(a, 1); michael@0: r0a = MP_DIGIT(a, 0); michael@0: michael@0: /* implement r = (a2,a1,a0)+(a5,a5,a5)+(a4,a4,0)+(0,a3,a3) */ michael@0: MP_ADD_CARRY(r0a, a3a, r0a, 0, carry); michael@0: MP_ADD_CARRY(r0b, a3b, r0b, carry, carry); michael@0: MP_ADD_CARRY(r1a, a3a, r1a, carry, carry); michael@0: MP_ADD_CARRY(r1b, a3b, r1b, carry, carry); michael@0: MP_ADD_CARRY(r2a, a4a, r2a, carry, carry); michael@0: MP_ADD_CARRY(r2b, a4b, r2b, carry, carry); michael@0: r3 = carry; carry = 0; michael@0: MP_ADD_CARRY(r0a, a5a, r0a, 0, carry); michael@0: MP_ADD_CARRY(r0b, a5b, r0b, carry, carry); michael@0: MP_ADD_CARRY(r1a, a5a, r1a, carry, carry); michael@0: MP_ADD_CARRY(r1b, a5b, r1b, carry, carry); michael@0: MP_ADD_CARRY(r2a, a5a, r2a, carry, carry); michael@0: MP_ADD_CARRY(r2b, a5b, r2b, carry, carry); michael@0: r3 += carry; michael@0: MP_ADD_CARRY(r1a, a4a, r1a, 0, carry); michael@0: MP_ADD_CARRY(r1b, a4b, r1b, carry, carry); michael@0: MP_ADD_CARRY(r2a, 0, r2a, carry, carry); michael@0: MP_ADD_CARRY(r2b, 0, r2b, carry, carry); michael@0: r3 += carry; michael@0: michael@0: /* reduce out the carry */ michael@0: while (r3) { michael@0: MP_ADD_CARRY(r0a, r3, r0a, 0, carry); michael@0: MP_ADD_CARRY(r0b, 0, r0b, carry, carry); michael@0: MP_ADD_CARRY(r1a, r3, r1a, carry, carry); michael@0: MP_ADD_CARRY(r1b, 0, r1b, carry, carry); michael@0: MP_ADD_CARRY(r2a, 0, r2a, carry, carry); michael@0: MP_ADD_CARRY(r2b, 0, r2b, carry, carry); michael@0: r3 = carry; michael@0: } michael@0: michael@0: /* check for final reduction */ michael@0: /* michael@0: * our field is 0xffffffffffffffff, 0xfffffffffffffffe, michael@0: * 0xffffffffffffffff. That means we can only be over and need michael@0: * one more reduction michael@0: * if r2 == 0xffffffffffffffffff (same as r2+1 == 0) michael@0: * and michael@0: * r1 == 0xffffffffffffffffff or michael@0: * r1 == 0xfffffffffffffffffe and r0 = 0xfffffffffffffffff michael@0: * In all cases, we subtract the field (or add the 2's michael@0: * complement value (1,1,0)). (r0, r1, r2) michael@0: */ michael@0: if (((r2b == 0xffffffff) && (r2a == 0xffffffff) michael@0: && (r1b == 0xffffffff) ) && michael@0: ((r1a == 0xffffffff) || michael@0: (r1a == 0xfffffffe) && (r0a == 0xffffffff) && michael@0: (r0b == 0xffffffff)) ) { michael@0: /* do a quick subtract */ michael@0: MP_ADD_CARRY(r0a, 1, r0a, 0, carry); michael@0: MP_ADD_CARRY(r0b, carry, r0a, 0, carry); michael@0: r1a += 1+carry; michael@0: r1b = r2a = r2b = 0; michael@0: } michael@0: michael@0: /* set the lower words of r */ michael@0: if (a != r) { michael@0: MP_CHECKOK(s_mp_pad(r, 6)); michael@0: } michael@0: MP_DIGIT(r, 5) = r2b; michael@0: MP_DIGIT(r, 4) = r2a; michael@0: MP_DIGIT(r, 3) = r1b; michael@0: MP_DIGIT(r, 2) = r1a; michael@0: MP_DIGIT(r, 1) = r0b; michael@0: MP_DIGIT(r, 0) = r0a; michael@0: MP_USED(r) = 6; michael@0: #else michael@0: switch (a_used) { michael@0: case 6: michael@0: a5 = MP_DIGIT(a, 5); michael@0: case 5: michael@0: a4 = MP_DIGIT(a, 4); michael@0: case 4: michael@0: a3 = MP_DIGIT(a, 3); michael@0: } michael@0: michael@0: r2 = MP_DIGIT(a, 2); michael@0: r1 = MP_DIGIT(a, 1); michael@0: r0 = MP_DIGIT(a, 0); michael@0: michael@0: /* implement r = (a2,a1,a0)+(a5,a5,a5)+(a4,a4,0)+(0,a3,a3) */ michael@0: #ifndef MPI_AMD64_ADD michael@0: MP_ADD_CARRY(r0, a3, r0, 0, carry); michael@0: MP_ADD_CARRY(r1, a3, r1, carry, carry); michael@0: MP_ADD_CARRY(r2, a4, r2, carry, carry); michael@0: r3 = carry; michael@0: MP_ADD_CARRY(r0, a5, r0, 0, carry); michael@0: MP_ADD_CARRY(r1, a5, r1, carry, carry); michael@0: MP_ADD_CARRY(r2, a5, r2, carry, carry); michael@0: r3 += carry; michael@0: MP_ADD_CARRY(r1, a4, r1, 0, carry); michael@0: MP_ADD_CARRY(r2, 0, r2, carry, carry); michael@0: r3 += carry; michael@0: michael@0: #else michael@0: r2 = MP_DIGIT(a, 2); michael@0: r1 = MP_DIGIT(a, 1); michael@0: r0 = MP_DIGIT(a, 0); michael@0: michael@0: /* set the lower words of r */ michael@0: __asm__ ( michael@0: "xorq %3,%3 \n\t" michael@0: "addq %4,%0 \n\t" michael@0: "adcq %4,%1 \n\t" michael@0: "adcq %5,%2 \n\t" michael@0: "adcq $0,%3 \n\t" michael@0: "addq %6,%0 \n\t" michael@0: "adcq %6,%1 \n\t" michael@0: "adcq %6,%2 \n\t" michael@0: "adcq $0,%3 \n\t" michael@0: "addq %5,%1 \n\t" michael@0: "adcq $0,%2 \n\t" michael@0: "adcq $0,%3 \n\t" michael@0: : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(r3), "=r"(a3), michael@0: "=r"(a4), "=r"(a5) michael@0: : "0" (r0), "1" (r1), "2" (r2), "3" (r3), michael@0: "4" (a3), "5" (a4), "6"(a5) michael@0: : "%cc" ); michael@0: #endif michael@0: michael@0: /* reduce out the carry */ michael@0: while (r3) { michael@0: #ifndef MPI_AMD64_ADD michael@0: MP_ADD_CARRY(r0, r3, r0, 0, carry); michael@0: MP_ADD_CARRY(r1, r3, r1, carry, carry); michael@0: MP_ADD_CARRY(r2, 0, r2, carry, carry); michael@0: r3 = carry; michael@0: #else michael@0: a3=r3; michael@0: __asm__ ( michael@0: "xorq %3,%3 \n\t" michael@0: "addq %4,%0 \n\t" michael@0: "adcq %4,%1 \n\t" michael@0: "adcq $0,%2 \n\t" michael@0: "adcq $0,%3 \n\t" michael@0: : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(r3), "=r"(a3) michael@0: : "0" (r0), "1" (r1), "2" (r2), "3" (r3), "4"(a3) michael@0: : "%cc" ); michael@0: #endif michael@0: } michael@0: michael@0: /* check for final reduction */ michael@0: /* michael@0: * our field is 0xffffffffffffffff, 0xfffffffffffffffe, michael@0: * 0xffffffffffffffff. That means we can only be over and need michael@0: * one more reduction michael@0: * if r2 == 0xffffffffffffffffff (same as r2+1 == 0) michael@0: * and michael@0: * r1 == 0xffffffffffffffffff or michael@0: * r1 == 0xfffffffffffffffffe and r0 = 0xfffffffffffffffff michael@0: * In all cases, we subtract the field (or add the 2's michael@0: * complement value (1,1,0)). (r0, r1, r2) michael@0: */ michael@0: if (r3 || ((r2 == MP_DIGIT_MAX) && michael@0: ((r1 == MP_DIGIT_MAX) || michael@0: ((r1 == (MP_DIGIT_MAX-1)) && (r0 == MP_DIGIT_MAX))))) { michael@0: /* do a quick subtract */ michael@0: MP_ADD_CARRY(r0, 1, r0, 0, carry); michael@0: r1 += 1+carry; michael@0: r2 = 0; michael@0: } michael@0: /* set the lower words of r */ michael@0: if (a != r) { michael@0: MP_CHECKOK(s_mp_pad(r, 3)); michael@0: } michael@0: MP_DIGIT(r, 2) = r2; michael@0: MP_DIGIT(r, 1) = r1; michael@0: MP_DIGIT(r, 0) = r0; michael@0: MP_USED(r) = 3; michael@0: #endif michael@0: } michael@0: s_mp_clamp(r); michael@0: CLEANUP: michael@0: return res; michael@0: } michael@0: michael@0: #ifndef ECL_THIRTY_TWO_BIT michael@0: /* Compute the sum of 192 bit curves. Do the work in-line since the michael@0: * number of words are so small, we don't want to overhead of mp function michael@0: * calls. Uses optimized modular reduction for p192. michael@0: */ michael@0: static mp_err michael@0: ec_GFp_nistp192_add(const mp_int *a, const mp_int *b, mp_int *r, michael@0: const GFMethod *meth) michael@0: { michael@0: mp_err res = MP_OKAY; michael@0: mp_digit a0 = 0, a1 = 0, a2 = 0; michael@0: mp_digit r0 = 0, r1 = 0, r2 = 0; michael@0: mp_digit carry; michael@0: michael@0: switch(MP_USED(a)) { michael@0: case 3: michael@0: a2 = MP_DIGIT(a,2); michael@0: case 2: michael@0: a1 = MP_DIGIT(a,1); michael@0: case 1: michael@0: a0 = MP_DIGIT(a,0); michael@0: } michael@0: switch(MP_USED(b)) { michael@0: case 3: michael@0: r2 = MP_DIGIT(b,2); michael@0: case 2: michael@0: r1 = MP_DIGIT(b,1); michael@0: case 1: michael@0: r0 = MP_DIGIT(b,0); michael@0: } michael@0: michael@0: #ifndef MPI_AMD64_ADD michael@0: MP_ADD_CARRY(a0, r0, r0, 0, carry); michael@0: MP_ADD_CARRY(a1, r1, r1, carry, carry); michael@0: MP_ADD_CARRY(a2, r2, r2, carry, carry); michael@0: #else michael@0: __asm__ ( michael@0: "xorq %3,%3 \n\t" michael@0: "addq %4,%0 \n\t" michael@0: "adcq %5,%1 \n\t" michael@0: "adcq %6,%2 \n\t" michael@0: "adcq $0,%3 \n\t" michael@0: : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(carry) michael@0: : "r" (a0), "r" (a1), "r" (a2), "0" (r0), michael@0: "1" (r1), "2" (r2) michael@0: : "%cc" ); michael@0: #endif michael@0: michael@0: /* Do quick 'subract' if we've gone over michael@0: * (add the 2's complement of the curve field) */ michael@0: if (carry || ((r2 == MP_DIGIT_MAX) && michael@0: ((r1 == MP_DIGIT_MAX) || michael@0: ((r1 == (MP_DIGIT_MAX-1)) && (r0 == MP_DIGIT_MAX))))) { michael@0: #ifndef MPI_AMD64_ADD michael@0: MP_ADD_CARRY(r0, 1, r0, 0, carry); michael@0: MP_ADD_CARRY(r1, 1, r1, carry, carry); michael@0: MP_ADD_CARRY(r2, 0, r2, carry, carry); michael@0: #else michael@0: __asm__ ( michael@0: "addq $1,%0 \n\t" michael@0: "adcq $1,%1 \n\t" michael@0: "adcq $0,%2 \n\t" michael@0: : "=r"(r0), "=r"(r1), "=r"(r2) michael@0: : "0" (r0), "1" (r1), "2" (r2) michael@0: : "%cc" ); michael@0: #endif michael@0: } michael@0: michael@0: michael@0: MP_CHECKOK(s_mp_pad(r, 3)); michael@0: MP_DIGIT(r, 2) = r2; michael@0: MP_DIGIT(r, 1) = r1; michael@0: MP_DIGIT(r, 0) = r0; michael@0: MP_SIGN(r) = MP_ZPOS; michael@0: MP_USED(r) = 3; michael@0: s_mp_clamp(r); michael@0: michael@0: michael@0: CLEANUP: michael@0: return res; michael@0: } michael@0: michael@0: /* Compute the diff of 192 bit curves. Do the work in-line since the michael@0: * number of words are so small, we don't want to overhead of mp function michael@0: * calls. Uses optimized modular reduction for p192. michael@0: */ michael@0: static mp_err michael@0: ec_GFp_nistp192_sub(const mp_int *a, const mp_int *b, mp_int *r, michael@0: const GFMethod *meth) michael@0: { michael@0: mp_err res = MP_OKAY; michael@0: mp_digit b0 = 0, b1 = 0, b2 = 0; michael@0: mp_digit r0 = 0, r1 = 0, r2 = 0; michael@0: mp_digit borrow; michael@0: michael@0: switch(MP_USED(a)) { michael@0: case 3: michael@0: r2 = MP_DIGIT(a,2); michael@0: case 2: michael@0: r1 = MP_DIGIT(a,1); michael@0: case 1: michael@0: r0 = MP_DIGIT(a,0); michael@0: } michael@0: michael@0: switch(MP_USED(b)) { michael@0: case 3: michael@0: b2 = MP_DIGIT(b,2); michael@0: case 2: michael@0: b1 = MP_DIGIT(b,1); michael@0: case 1: michael@0: b0 = MP_DIGIT(b,0); michael@0: } michael@0: michael@0: #ifndef MPI_AMD64_ADD michael@0: MP_SUB_BORROW(r0, b0, r0, 0, borrow); michael@0: MP_SUB_BORROW(r1, b1, r1, borrow, borrow); michael@0: MP_SUB_BORROW(r2, b2, r2, borrow, borrow); michael@0: #else michael@0: __asm__ ( michael@0: "xorq %3,%3 \n\t" michael@0: "subq %4,%0 \n\t" michael@0: "sbbq %5,%1 \n\t" michael@0: "sbbq %6,%2 \n\t" michael@0: "adcq $0,%3 \n\t" michael@0: : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(borrow) michael@0: : "r" (b0), "r" (b1), "r" (b2), "0" (r0), michael@0: "1" (r1), "2" (r2) michael@0: : "%cc" ); michael@0: #endif michael@0: michael@0: /* Do quick 'add' if we've gone under 0 michael@0: * (subtract the 2's complement of the curve field) */ michael@0: if (borrow) { michael@0: #ifndef MPI_AMD64_ADD michael@0: MP_SUB_BORROW(r0, 1, r0, 0, borrow); michael@0: MP_SUB_BORROW(r1, 1, r1, borrow, borrow); michael@0: MP_SUB_BORROW(r2, 0, r2, borrow, borrow); michael@0: #else michael@0: __asm__ ( michael@0: "subq $1,%0 \n\t" michael@0: "sbbq $1,%1 \n\t" michael@0: "sbbq $0,%2 \n\t" michael@0: : "=r"(r0), "=r"(r1), "=r"(r2) michael@0: : "0" (r0), "1" (r1), "2" (r2) michael@0: : "%cc" ); michael@0: #endif michael@0: } michael@0: michael@0: MP_CHECKOK(s_mp_pad(r, 3)); michael@0: MP_DIGIT(r, 2) = r2; michael@0: MP_DIGIT(r, 1) = r1; michael@0: MP_DIGIT(r, 0) = r0; michael@0: MP_SIGN(r) = MP_ZPOS; michael@0: MP_USED(r) = 3; michael@0: s_mp_clamp(r); michael@0: michael@0: CLEANUP: michael@0: return res; michael@0: } michael@0: michael@0: #endif michael@0: michael@0: /* Compute the square of polynomial a, reduce modulo p192. Store the michael@0: * result in r. r could be a. Uses optimized modular reduction for p192. michael@0: */ michael@0: static mp_err michael@0: ec_GFp_nistp192_sqr(const mp_int *a, mp_int *r, const GFMethod *meth) michael@0: { michael@0: mp_err res = MP_OKAY; michael@0: michael@0: MP_CHECKOK(mp_sqr(a, r)); michael@0: MP_CHECKOK(ec_GFp_nistp192_mod(r, r, meth)); michael@0: CLEANUP: michael@0: return res; michael@0: } michael@0: michael@0: /* Compute the product of two polynomials a and b, reduce modulo p192. michael@0: * Store the result in r. r could be a or b; a could be b. Uses michael@0: * optimized modular reduction for p192. */ michael@0: static mp_err michael@0: ec_GFp_nistp192_mul(const mp_int *a, const mp_int *b, mp_int *r, michael@0: const GFMethod *meth) michael@0: { michael@0: mp_err res = MP_OKAY; michael@0: michael@0: MP_CHECKOK(mp_mul(a, b, r)); michael@0: MP_CHECKOK(ec_GFp_nistp192_mod(r, r, meth)); michael@0: CLEANUP: michael@0: return res; michael@0: } michael@0: michael@0: /* Divides two field elements. If a is NULL, then returns the inverse of michael@0: * b. */ michael@0: static mp_err michael@0: ec_GFp_nistp192_div(const mp_int *a, const mp_int *b, mp_int *r, michael@0: const GFMethod *meth) michael@0: { michael@0: mp_err res = MP_OKAY; michael@0: mp_int t; michael@0: michael@0: /* If a is NULL, then return the inverse of b, otherwise return a/b. */ michael@0: if (a == NULL) { michael@0: return mp_invmod(b, &meth->irr, r); michael@0: } else { michael@0: /* MPI doesn't support divmod, so we implement it using invmod and michael@0: * mulmod. */ michael@0: MP_CHECKOK(mp_init(&t)); michael@0: MP_CHECKOK(mp_invmod(b, &meth->irr, &t)); michael@0: MP_CHECKOK(mp_mul(a, &t, r)); michael@0: MP_CHECKOK(ec_GFp_nistp192_mod(r, r, meth)); michael@0: CLEANUP: michael@0: mp_clear(&t); michael@0: return res; michael@0: } michael@0: } michael@0: michael@0: /* Wire in fast field arithmetic and precomputation of base point for michael@0: * named curves. */ michael@0: mp_err michael@0: ec_group_set_gfp192(ECGroup *group, ECCurveName name) michael@0: { michael@0: if (name == ECCurve_NIST_P192) { michael@0: group->meth->field_mod = &ec_GFp_nistp192_mod; michael@0: group->meth->field_mul = &ec_GFp_nistp192_mul; michael@0: group->meth->field_sqr = &ec_GFp_nistp192_sqr; michael@0: group->meth->field_div = &ec_GFp_nistp192_div; michael@0: #ifndef ECL_THIRTY_TWO_BIT michael@0: group->meth->field_add = &ec_GFp_nistp192_add; michael@0: group->meth->field_sub = &ec_GFp_nistp192_sub; michael@0: #endif michael@0: } michael@0: return MP_OKAY; michael@0: }