diff options
Diffstat (limited to '')
-rw-r--r-- | security/nss/lib/freebl/ecl/ecl_gf.c | 958 |
1 files changed, 958 insertions, 0 deletions
diff --git a/security/nss/lib/freebl/ecl/ecl_gf.c b/security/nss/lib/freebl/ecl/ecl_gf.c new file mode 100644 index 0000000000..81b0077055 --- /dev/null +++ b/security/nss/lib/freebl/ecl/ecl_gf.c @@ -0,0 +1,958 @@ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#include "mpi.h" +#include "mp_gf2m.h" +#include "ecl-priv.h" +#include "mpi-priv.h" +#include <stdlib.h> + +/* Allocate memory for a new GFMethod object. */ +GFMethod * +GFMethod_new() +{ + mp_err res = MP_OKAY; + GFMethod *meth; + meth = (GFMethod *)malloc(sizeof(GFMethod)); + if (meth == NULL) + return NULL; + meth->constructed = MP_YES; + MP_DIGITS(&meth->irr) = 0; + meth->extra_free = NULL; + MP_CHECKOK(mp_init(&meth->irr)); + +CLEANUP: + if (res != MP_OKAY) { + GFMethod_free(meth); + return NULL; + } + return meth; +} + +/* Construct a generic GFMethod for arithmetic over prime fields with + * irreducible irr. */ +GFMethod * +GFMethod_consGFp(const mp_int *irr) +{ + mp_err res = MP_OKAY; + GFMethod *meth = NULL; + + meth = GFMethod_new(); + if (meth == NULL) + return NULL; + + MP_CHECKOK(mp_copy(irr, &meth->irr)); + meth->irr_arr[0] = mpl_significant_bits(irr); + meth->irr_arr[1] = meth->irr_arr[2] = meth->irr_arr[3] = + meth->irr_arr[4] = 0; + switch (MP_USED(&meth->irr)) { + /* maybe we need 1 and 2 words here as well?*/ + case 3: + meth->field_add = &ec_GFp_add_3; + meth->field_sub = &ec_GFp_sub_3; + break; + case 4: + meth->field_add = &ec_GFp_add_4; + meth->field_sub = &ec_GFp_sub_4; + break; + case 5: + meth->field_add = &ec_GFp_add_5; + meth->field_sub = &ec_GFp_sub_5; + break; + case 6: + meth->field_add = &ec_GFp_add_6; + meth->field_sub = &ec_GFp_sub_6; + break; + default: + meth->field_add = &ec_GFp_add; + meth->field_sub = &ec_GFp_sub; + } + meth->field_neg = &ec_GFp_neg; + meth->field_mod = &ec_GFp_mod; + meth->field_mul = &ec_GFp_mul; + meth->field_sqr = &ec_GFp_sqr; + meth->field_div = &ec_GFp_div; + meth->field_enc = NULL; + meth->field_dec = NULL; + meth->extra1 = NULL; + meth->extra2 = NULL; + meth->extra_free = NULL; + +CLEANUP: + if (res != MP_OKAY) { + GFMethod_free(meth); + return NULL; + } + return meth; +} + +/* Free the memory allocated (if any) to a GFMethod object. */ +void +GFMethod_free(GFMethod *meth) +{ + if (meth == NULL) + return; + if (meth->constructed == MP_NO) + return; + mp_clear(&meth->irr); + if (meth->extra_free != NULL) + meth->extra_free(meth); + free(meth); +} + +/* Wrapper functions for generic prime field arithmetic. */ + +/* Add two field elements. Assumes that 0 <= a, b < meth->irr */ +mp_err +ec_GFp_add(const mp_int *a, const mp_int *b, mp_int *r, + const GFMethod *meth) +{ + /* PRE: 0 <= a, b < p = meth->irr POST: 0 <= r < p, r = a + b (mod p) */ + mp_err res; + + if ((res = mp_add(a, b, r)) != MP_OKAY) { + return res; + } + if (mp_cmp(r, &meth->irr) >= 0) { + return mp_sub(r, &meth->irr, r); + } + return res; +} + +/* Negates a field element. Assumes that 0 <= a < meth->irr */ +mp_err +ec_GFp_neg(const mp_int *a, mp_int *r, const GFMethod *meth) +{ + /* PRE: 0 <= a < p = meth->irr POST: 0 <= r < p, r = -a (mod p) */ + + if (mp_cmp_z(a) == 0) { + mp_zero(r); + return MP_OKAY; + } + return mp_sub(&meth->irr, a, r); +} + +/* Subtracts two field elements. Assumes that 0 <= a, b < meth->irr */ +mp_err +ec_GFp_sub(const mp_int *a, const mp_int *b, mp_int *r, + const GFMethod *meth) +{ + mp_err res = MP_OKAY; + + /* PRE: 0 <= a, b < p = meth->irr POST: 0 <= r < p, r = a - b (mod p) */ + res = mp_sub(a, b, r); + if (res == MP_RANGE) { + MP_CHECKOK(mp_sub(b, a, r)); + if (mp_cmp_z(r) < 0) { + MP_CHECKOK(mp_add(r, &meth->irr, r)); + } + MP_CHECKOK(ec_GFp_neg(r, r, meth)); + } + if (mp_cmp_z(r) < 0) { + MP_CHECKOK(mp_add(r, &meth->irr, r)); + } +CLEANUP: + return res; +} +/* + * Inline adds for small curve lengths. + */ +/* 3 words */ +mp_err +ec_GFp_add_3(const mp_int *a, const mp_int *b, mp_int *r, + const GFMethod *meth) +{ + mp_err res = MP_OKAY; + mp_digit a0 = 0, a1 = 0, a2 = 0; + mp_digit r0 = 0, r1 = 0, r2 = 0; + mp_digit carry; + + switch (MP_USED(a)) { + case 3: + a2 = MP_DIGIT(a, 2); + case 2: + a1 = MP_DIGIT(a, 1); + case 1: + a0 = MP_DIGIT(a, 0); + } + switch (MP_USED(b)) { + case 3: + r2 = MP_DIGIT(b, 2); + case 2: + r1 = MP_DIGIT(b, 1); + case 1: + r0 = MP_DIGIT(b, 0); + } + +#ifndef MPI_AMD64_ADD + carry = 0; + MP_ADD_CARRY(a0, r0, r0, carry); + MP_ADD_CARRY(a1, r1, r1, carry); + MP_ADD_CARRY(a2, r2, r2, carry); +#else + __asm__( + "xorq %3,%3 \n\t" + "addq %4,%0 \n\t" + "adcq %5,%1 \n\t" + "adcq %6,%2 \n\t" + "adcq $0,%3 \n\t" + : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(carry) + : "r"(a0), "r"(a1), "r"(a2), + "0"(r0), "1"(r1), "2"(r2) + : "%cc"); +#endif + + MP_CHECKOK(s_mp_pad(r, 3)); + MP_DIGIT(r, 2) = r2; + MP_DIGIT(r, 1) = r1; + MP_DIGIT(r, 0) = r0; + MP_SIGN(r) = MP_ZPOS; + MP_USED(r) = 3; + + /* Do quick 'subract' if we've gone over + * (add the 2's complement of the curve field) */ + a2 = MP_DIGIT(&meth->irr, 2); + if (carry || r2 > a2 || + ((r2 == a2) && mp_cmp(r, &meth->irr) != MP_LT)) { + a1 = MP_DIGIT(&meth->irr, 1); + a0 = MP_DIGIT(&meth->irr, 0); +#ifndef MPI_AMD64_ADD + carry = 0; + MP_SUB_BORROW(r0, a0, r0, carry); + MP_SUB_BORROW(r1, a1, r1, carry); + MP_SUB_BORROW(r2, a2, r2, carry); +#else + __asm__( + "subq %3,%0 \n\t" + "sbbq %4,%1 \n\t" + "sbbq %5,%2 \n\t" + : "=r"(r0), "=r"(r1), "=r"(r2) + : "r"(a0), "r"(a1), "r"(a2), + "0"(r0), "1"(r1), "2"(r2) + : "%cc"); +#endif + MP_DIGIT(r, 2) = r2; + MP_DIGIT(r, 1) = r1; + MP_DIGIT(r, 0) = r0; + } + + s_mp_clamp(r); + +CLEANUP: + return res; +} + +/* 4 words */ +mp_err +ec_GFp_add_4(const mp_int *a, const mp_int *b, mp_int *r, + const GFMethod *meth) +{ + mp_err res = MP_OKAY; + mp_digit a0 = 0, a1 = 0, a2 = 0, a3 = 0; + mp_digit r0 = 0, r1 = 0, r2 = 0, r3 = 0; + mp_digit carry; + + switch (MP_USED(a)) { + case 4: + a3 = MP_DIGIT(a, 3); + case 3: + a2 = MP_DIGIT(a, 2); + case 2: + a1 = MP_DIGIT(a, 1); + case 1: + a0 = MP_DIGIT(a, 0); + } + switch (MP_USED(b)) { + case 4: + r3 = MP_DIGIT(b, 3); + case 3: + r2 = MP_DIGIT(b, 2); + case 2: + r1 = MP_DIGIT(b, 1); + case 1: + r0 = MP_DIGIT(b, 0); + } + +#ifndef MPI_AMD64_ADD + carry = 0; + MP_ADD_CARRY(a0, r0, r0, carry); + MP_ADD_CARRY(a1, r1, r1, carry); + MP_ADD_CARRY(a2, r2, r2, carry); + MP_ADD_CARRY(a3, r3, r3, carry); +#else + __asm__( + "xorq %4,%4 \n\t" + "addq %5,%0 \n\t" + "adcq %6,%1 \n\t" + "adcq %7,%2 \n\t" + "adcq %8,%3 \n\t" + "adcq $0,%4 \n\t" + : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(r3), "=r"(carry) + : "r"(a0), "r"(a1), "r"(a2), "r"(a3), + "0"(r0), "1"(r1), "2"(r2), "3"(r3) + : "%cc"); +#endif + + MP_CHECKOK(s_mp_pad(r, 4)); + MP_DIGIT(r, 3) = r3; + MP_DIGIT(r, 2) = r2; + MP_DIGIT(r, 1) = r1; + MP_DIGIT(r, 0) = r0; + MP_SIGN(r) = MP_ZPOS; + MP_USED(r) = 4; + + /* Do quick 'subract' if we've gone over + * (add the 2's complement of the curve field) */ + a3 = MP_DIGIT(&meth->irr, 3); + if (carry || r3 > a3 || + ((r3 == a3) && mp_cmp(r, &meth->irr) != MP_LT)) { + a2 = MP_DIGIT(&meth->irr, 2); + a1 = MP_DIGIT(&meth->irr, 1); + a0 = MP_DIGIT(&meth->irr, 0); +#ifndef MPI_AMD64_ADD + carry = 0; + MP_SUB_BORROW(r0, a0, r0, carry); + MP_SUB_BORROW(r1, a1, r1, carry); + MP_SUB_BORROW(r2, a2, r2, carry); + MP_SUB_BORROW(r3, a3, r3, carry); +#else + __asm__( + "subq %4,%0 \n\t" + "sbbq %5,%1 \n\t" + "sbbq %6,%2 \n\t" + "sbbq %7,%3 \n\t" + : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(r3) + : "r"(a0), "r"(a1), "r"(a2), "r"(a3), + "0"(r0), "1"(r1), "2"(r2), "3"(r3) + : "%cc"); +#endif + MP_DIGIT(r, 3) = r3; + MP_DIGIT(r, 2) = r2; + MP_DIGIT(r, 1) = r1; + MP_DIGIT(r, 0) = r0; + } + + s_mp_clamp(r); + +CLEANUP: + return res; +} + +/* 5 words */ +mp_err +ec_GFp_add_5(const mp_int *a, const mp_int *b, mp_int *r, + const GFMethod *meth) +{ + mp_err res = MP_OKAY; + mp_digit a0 = 0, a1 = 0, a2 = 0, a3 = 0, a4 = 0; + mp_digit r0 = 0, r1 = 0, r2 = 0, r3 = 0, r4 = 0; + mp_digit carry; + + switch (MP_USED(a)) { + case 5: + a4 = MP_DIGIT(a, 4); + case 4: + a3 = MP_DIGIT(a, 3); + case 3: + a2 = MP_DIGIT(a, 2); + case 2: + a1 = MP_DIGIT(a, 1); + case 1: + a0 = MP_DIGIT(a, 0); + } + switch (MP_USED(b)) { + case 5: + r4 = MP_DIGIT(b, 4); + case 4: + r3 = MP_DIGIT(b, 3); + case 3: + r2 = MP_DIGIT(b, 2); + case 2: + r1 = MP_DIGIT(b, 1); + case 1: + r0 = MP_DIGIT(b, 0); + } + + carry = 0; + MP_ADD_CARRY(a0, r0, r0, carry); + MP_ADD_CARRY(a1, r1, r1, carry); + MP_ADD_CARRY(a2, r2, r2, carry); + MP_ADD_CARRY(a3, r3, r3, carry); + MP_ADD_CARRY(a4, r4, r4, carry); + + MP_CHECKOK(s_mp_pad(r, 5)); + MP_DIGIT(r, 4) = r4; + MP_DIGIT(r, 3) = r3; + MP_DIGIT(r, 2) = r2; + MP_DIGIT(r, 1) = r1; + MP_DIGIT(r, 0) = r0; + MP_SIGN(r) = MP_ZPOS; + MP_USED(r) = 5; + + /* Do quick 'subract' if we've gone over + * (add the 2's complement of the curve field) */ + a4 = MP_DIGIT(&meth->irr, 4); + if (carry || r4 > a4 || + ((r4 == a4) && mp_cmp(r, &meth->irr) != MP_LT)) { + a3 = MP_DIGIT(&meth->irr, 3); + a2 = MP_DIGIT(&meth->irr, 2); + a1 = MP_DIGIT(&meth->irr, 1); + a0 = MP_DIGIT(&meth->irr, 0); + carry = 0; + MP_SUB_BORROW(r0, a0, r0, carry); + MP_SUB_BORROW(r1, a1, r1, carry); + MP_SUB_BORROW(r2, a2, r2, carry); + MP_SUB_BORROW(r3, a3, r3, carry); + MP_SUB_BORROW(r4, a4, r4, carry); + MP_DIGIT(r, 4) = r4; + MP_DIGIT(r, 3) = r3; + MP_DIGIT(r, 2) = r2; + MP_DIGIT(r, 1) = r1; + MP_DIGIT(r, 0) = r0; + } + + s_mp_clamp(r); + +CLEANUP: + return res; +} + +/* 6 words */ +mp_err +ec_GFp_add_6(const mp_int *a, const mp_int *b, mp_int *r, + const GFMethod *meth) +{ + mp_err res = MP_OKAY; + mp_digit a0 = 0, a1 = 0, a2 = 0, a3 = 0, a4 = 0, a5 = 0; + mp_digit r0 = 0, r1 = 0, r2 = 0, r3 = 0, r4 = 0, r5 = 0; + mp_digit carry; + + switch (MP_USED(a)) { + case 6: + a5 = MP_DIGIT(a, 5); + case 5: + a4 = MP_DIGIT(a, 4); + case 4: + a3 = MP_DIGIT(a, 3); + case 3: + a2 = MP_DIGIT(a, 2); + case 2: + a1 = MP_DIGIT(a, 1); + case 1: + a0 = MP_DIGIT(a, 0); + } + switch (MP_USED(b)) { + case 6: + r5 = MP_DIGIT(b, 5); + case 5: + r4 = MP_DIGIT(b, 4); + case 4: + r3 = MP_DIGIT(b, 3); + case 3: + r2 = MP_DIGIT(b, 2); + case 2: + r1 = MP_DIGIT(b, 1); + case 1: + r0 = MP_DIGIT(b, 0); + } + + carry = 0; + MP_ADD_CARRY(a0, r0, r0, carry); + MP_ADD_CARRY(a1, r1, r1, carry); + MP_ADD_CARRY(a2, r2, r2, carry); + MP_ADD_CARRY(a3, r3, r3, carry); + MP_ADD_CARRY(a4, r4, r4, carry); + MP_ADD_CARRY(a5, r5, r5, carry); + + MP_CHECKOK(s_mp_pad(r, 6)); + MP_DIGIT(r, 5) = r5; + MP_DIGIT(r, 4) = r4; + MP_DIGIT(r, 3) = r3; + MP_DIGIT(r, 2) = r2; + MP_DIGIT(r, 1) = r1; + MP_DIGIT(r, 0) = r0; + MP_SIGN(r) = MP_ZPOS; + MP_USED(r) = 6; + + /* Do quick 'subract' if we've gone over + * (add the 2's complement of the curve field) */ + a5 = MP_DIGIT(&meth->irr, 5); + if (carry || r5 > a5 || + ((r5 == a5) && mp_cmp(r, &meth->irr) != MP_LT)) { + a4 = MP_DIGIT(&meth->irr, 4); + a3 = MP_DIGIT(&meth->irr, 3); + a2 = MP_DIGIT(&meth->irr, 2); + a1 = MP_DIGIT(&meth->irr, 1); + a0 = MP_DIGIT(&meth->irr, 0); + carry = 0; + MP_SUB_BORROW(r0, a0, r0, carry); + MP_SUB_BORROW(r1, a1, r1, carry); + MP_SUB_BORROW(r2, a2, r2, carry); + MP_SUB_BORROW(r3, a3, r3, carry); + MP_SUB_BORROW(r4, a4, r4, carry); + MP_SUB_BORROW(r5, a5, r5, carry); + MP_DIGIT(r, 5) = r5; + MP_DIGIT(r, 4) = r4; + MP_DIGIT(r, 3) = r3; + MP_DIGIT(r, 2) = r2; + MP_DIGIT(r, 1) = r1; + MP_DIGIT(r, 0) = r0; + } + + s_mp_clamp(r); + +CLEANUP: + return res; +} + +/* + * The following subraction functions do in-line subractions based + * on our curve size. + * + * ... 3 words + */ +mp_err +ec_GFp_sub_3(const mp_int *a, const mp_int *b, mp_int *r, + const GFMethod *meth) +{ + mp_err res = MP_OKAY; + mp_digit b0 = 0, b1 = 0, b2 = 0; + mp_digit r0 = 0, r1 = 0, r2 = 0; + mp_digit borrow; + + switch (MP_USED(a)) { + case 3: + r2 = MP_DIGIT(a, 2); + case 2: + r1 = MP_DIGIT(a, 1); + case 1: + r0 = MP_DIGIT(a, 0); + } + switch (MP_USED(b)) { + case 3: + b2 = MP_DIGIT(b, 2); + case 2: + b1 = MP_DIGIT(b, 1); + case 1: + b0 = MP_DIGIT(b, 0); + } + +#ifndef MPI_AMD64_ADD + borrow = 0; + MP_SUB_BORROW(r0, b0, r0, borrow); + MP_SUB_BORROW(r1, b1, r1, borrow); + MP_SUB_BORROW(r2, b2, r2, borrow); +#else + __asm__( + "xorq %3,%3 \n\t" + "subq %4,%0 \n\t" + "sbbq %5,%1 \n\t" + "sbbq %6,%2 \n\t" + "adcq $0,%3 \n\t" + : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(borrow) + : "r"(b0), "r"(b1), "r"(b2), + "0"(r0), "1"(r1), "2"(r2) + : "%cc"); +#endif + + /* Do quick 'add' if we've gone under 0 + * (subtract the 2's complement of the curve field) */ + if (borrow) { + b2 = MP_DIGIT(&meth->irr, 2); + b1 = MP_DIGIT(&meth->irr, 1); + b0 = MP_DIGIT(&meth->irr, 0); +#ifndef MPI_AMD64_ADD + borrow = 0; + MP_ADD_CARRY(b0, r0, r0, borrow); + MP_ADD_CARRY(b1, r1, r1, borrow); + MP_ADD_CARRY(b2, r2, r2, borrow); +#else + __asm__( + "addq %3,%0 \n\t" + "adcq %4,%1 \n\t" + "adcq %5,%2 \n\t" + : "=r"(r0), "=r"(r1), "=r"(r2) + : "r"(b0), "r"(b1), "r"(b2), + "0"(r0), "1"(r1), "2"(r2) + : "%cc"); +#endif + } + +#ifdef MPI_AMD64_ADD + /* compiler fakeout? */ + if ((r2 == b0) && (r1 == b0) && (r0 == b0)) { + MP_CHECKOK(s_mp_pad(r, 4)); + } +#endif + MP_CHECKOK(s_mp_pad(r, 3)); + MP_DIGIT(r, 2) = r2; + MP_DIGIT(r, 1) = r1; + MP_DIGIT(r, 0) = r0; + MP_SIGN(r) = MP_ZPOS; + MP_USED(r) = 3; + s_mp_clamp(r); + +CLEANUP: + return res; +} + +/* 4 words */ +mp_err +ec_GFp_sub_4(const mp_int *a, const mp_int *b, mp_int *r, + const GFMethod *meth) +{ + mp_err res = MP_OKAY; + mp_digit b0 = 0, b1 = 0, b2 = 0, b3 = 0; + mp_digit r0 = 0, r1 = 0, r2 = 0, r3 = 0; + mp_digit borrow; + + switch (MP_USED(a)) { + case 4: + r3 = MP_DIGIT(a, 3); + case 3: + r2 = MP_DIGIT(a, 2); + case 2: + r1 = MP_DIGIT(a, 1); + case 1: + r0 = MP_DIGIT(a, 0); + } + switch (MP_USED(b)) { + case 4: + b3 = MP_DIGIT(b, 3); + case 3: + b2 = MP_DIGIT(b, 2); + case 2: + b1 = MP_DIGIT(b, 1); + case 1: + b0 = MP_DIGIT(b, 0); + } + +#ifndef MPI_AMD64_ADD + borrow = 0; + MP_SUB_BORROW(r0, b0, r0, borrow); + MP_SUB_BORROW(r1, b1, r1, borrow); + MP_SUB_BORROW(r2, b2, r2, borrow); + MP_SUB_BORROW(r3, b3, r3, borrow); +#else + __asm__( + "xorq %4,%4 \n\t" + "subq %5,%0 \n\t" + "sbbq %6,%1 \n\t" + "sbbq %7,%2 \n\t" + "sbbq %8,%3 \n\t" + "adcq $0,%4 \n\t" + : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(r3), "=r"(borrow) + : "r"(b0), "r"(b1), "r"(b2), "r"(b3), + "0"(r0), "1"(r1), "2"(r2), "3"(r3) + : "%cc"); +#endif + + /* Do quick 'add' if we've gone under 0 + * (subtract the 2's complement of the curve field) */ + if (borrow) { + b3 = MP_DIGIT(&meth->irr, 3); + b2 = MP_DIGIT(&meth->irr, 2); + b1 = MP_DIGIT(&meth->irr, 1); + b0 = MP_DIGIT(&meth->irr, 0); +#ifndef MPI_AMD64_ADD + borrow = 0; + MP_ADD_CARRY(b0, r0, r0, borrow); + MP_ADD_CARRY(b1, r1, r1, borrow); + MP_ADD_CARRY(b2, r2, r2, borrow); + MP_ADD_CARRY(b3, r3, r3, borrow); +#else + __asm__( + "addq %4,%0 \n\t" + "adcq %5,%1 \n\t" + "adcq %6,%2 \n\t" + "adcq %7,%3 \n\t" + : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(r3) + : "r"(b0), "r"(b1), "r"(b2), "r"(b3), + "0"(r0), "1"(r1), "2"(r2), "3"(r3) + : "%cc"); +#endif + } +#ifdef MPI_AMD64_ADD + /* compiler fakeout? */ + if ((r3 == b0) && (r1 == b0) && (r0 == b0)) { + MP_CHECKOK(s_mp_pad(r, 4)); + } +#endif + MP_CHECKOK(s_mp_pad(r, 4)); + MP_DIGIT(r, 3) = r3; + MP_DIGIT(r, 2) = r2; + MP_DIGIT(r, 1) = r1; + MP_DIGIT(r, 0) = r0; + MP_SIGN(r) = MP_ZPOS; + MP_USED(r) = 4; + s_mp_clamp(r); + +CLEANUP: + return res; +} + +/* 5 words */ +mp_err +ec_GFp_sub_5(const mp_int *a, const mp_int *b, mp_int *r, + const GFMethod *meth) +{ + mp_err res = MP_OKAY; + mp_digit b0 = 0, b1 = 0, b2 = 0, b3 = 0, b4 = 0; + mp_digit r0 = 0, r1 = 0, r2 = 0, r3 = 0, r4 = 0; + mp_digit borrow; + + switch (MP_USED(a)) { + case 5: + r4 = MP_DIGIT(a, 4); + case 4: + r3 = MP_DIGIT(a, 3); + case 3: + r2 = MP_DIGIT(a, 2); + case 2: + r1 = MP_DIGIT(a, 1); + case 1: + r0 = MP_DIGIT(a, 0); + } + switch (MP_USED(b)) { + case 5: + b4 = MP_DIGIT(b, 4); + case 4: + b3 = MP_DIGIT(b, 3); + case 3: + b2 = MP_DIGIT(b, 2); + case 2: + b1 = MP_DIGIT(b, 1); + case 1: + b0 = MP_DIGIT(b, 0); + } + + borrow = 0; + MP_SUB_BORROW(r0, b0, r0, borrow); + MP_SUB_BORROW(r1, b1, r1, borrow); + MP_SUB_BORROW(r2, b2, r2, borrow); + MP_SUB_BORROW(r3, b3, r3, borrow); + MP_SUB_BORROW(r4, b4, r4, borrow); + + /* Do quick 'add' if we've gone under 0 + * (subtract the 2's complement of the curve field) */ + if (borrow) { + b4 = MP_DIGIT(&meth->irr, 4); + b3 = MP_DIGIT(&meth->irr, 3); + b2 = MP_DIGIT(&meth->irr, 2); + b1 = MP_DIGIT(&meth->irr, 1); + b0 = MP_DIGIT(&meth->irr, 0); + borrow = 0; + MP_ADD_CARRY(b0, r0, r0, borrow); + MP_ADD_CARRY(b1, r1, r1, borrow); + MP_ADD_CARRY(b2, r2, r2, borrow); + MP_ADD_CARRY(b3, r3, r3, borrow); + MP_ADD_CARRY(b4, r4, r4, borrow); + } + MP_CHECKOK(s_mp_pad(r, 5)); + MP_DIGIT(r, 4) = r4; + MP_DIGIT(r, 3) = r3; + MP_DIGIT(r, 2) = r2; + MP_DIGIT(r, 1) = r1; + MP_DIGIT(r, 0) = r0; + MP_SIGN(r) = MP_ZPOS; + MP_USED(r) = 5; + s_mp_clamp(r); + +CLEANUP: + return res; +} + +/* 6 words */ +mp_err +ec_GFp_sub_6(const mp_int *a, const mp_int *b, mp_int *r, + const GFMethod *meth) +{ + mp_err res = MP_OKAY; + mp_digit b0 = 0, b1 = 0, b2 = 0, b3 = 0, b4 = 0, b5 = 0; + mp_digit r0 = 0, r1 = 0, r2 = 0, r3 = 0, r4 = 0, r5 = 0; + mp_digit borrow; + + switch (MP_USED(a)) { + case 6: + r5 = MP_DIGIT(a, 5); + case 5: + r4 = MP_DIGIT(a, 4); + case 4: + r3 = MP_DIGIT(a, 3); + case 3: + r2 = MP_DIGIT(a, 2); + case 2: + r1 = MP_DIGIT(a, 1); + case 1: + r0 = MP_DIGIT(a, 0); + } + switch (MP_USED(b)) { + case 6: + b5 = MP_DIGIT(b, 5); + case 5: + b4 = MP_DIGIT(b, 4); + case 4: + b3 = MP_DIGIT(b, 3); + case 3: + b2 = MP_DIGIT(b, 2); + case 2: + b1 = MP_DIGIT(b, 1); + case 1: + b0 = MP_DIGIT(b, 0); + } + + borrow = 0; + MP_SUB_BORROW(r0, b0, r0, borrow); + MP_SUB_BORROW(r1, b1, r1, borrow); + MP_SUB_BORROW(r2, b2, r2, borrow); + MP_SUB_BORROW(r3, b3, r3, borrow); + MP_SUB_BORROW(r4, b4, r4, borrow); + MP_SUB_BORROW(r5, b5, r5, borrow); + + /* Do quick 'add' if we've gone under 0 + * (subtract the 2's complement of the curve field) */ + if (borrow) { + b5 = MP_DIGIT(&meth->irr, 5); + b4 = MP_DIGIT(&meth->irr, 4); + b3 = MP_DIGIT(&meth->irr, 3); + b2 = MP_DIGIT(&meth->irr, 2); + b1 = MP_DIGIT(&meth->irr, 1); + b0 = MP_DIGIT(&meth->irr, 0); + borrow = 0; + MP_ADD_CARRY(b0, r0, r0, borrow); + MP_ADD_CARRY(b1, r1, r1, borrow); + MP_ADD_CARRY(b2, r2, r2, borrow); + MP_ADD_CARRY(b3, r3, r3, borrow); + MP_ADD_CARRY(b4, r4, r4, borrow); + MP_ADD_CARRY(b5, r5, r5, borrow); + } + + MP_CHECKOK(s_mp_pad(r, 6)); + MP_DIGIT(r, 5) = r5; + MP_DIGIT(r, 4) = r4; + MP_DIGIT(r, 3) = r3; + MP_DIGIT(r, 2) = r2; + MP_DIGIT(r, 1) = r1; + MP_DIGIT(r, 0) = r0; + MP_SIGN(r) = MP_ZPOS; + MP_USED(r) = 6; + s_mp_clamp(r); + +CLEANUP: + return res; +} + +/* Reduces an integer to a field element. */ +mp_err +ec_GFp_mod(const mp_int *a, mp_int *r, const GFMethod *meth) +{ + return mp_mod(a, &meth->irr, r); +} + +/* Multiplies two field elements. */ +mp_err +ec_GFp_mul(const mp_int *a, const mp_int *b, mp_int *r, + const GFMethod *meth) +{ + return mp_mulmod(a, b, &meth->irr, r); +} + +/* Squares a field element. */ +mp_err +ec_GFp_sqr(const mp_int *a, mp_int *r, const GFMethod *meth) +{ + return mp_sqrmod(a, &meth->irr, r); +} + +/* Divides two field elements. If a is NULL, then returns the inverse of + * b. */ +mp_err +ec_GFp_div(const mp_int *a, const mp_int *b, mp_int *r, + const GFMethod *meth) +{ + mp_err res = MP_OKAY; + mp_int t; + + /* If a is NULL, then return the inverse of b, otherwise return a/b. */ + if (a == NULL) { + return mp_invmod(b, &meth->irr, r); + } else { + /* MPI doesn't support divmod, so we implement it using invmod and + * mulmod. */ + MP_CHECKOK(mp_init(&t)); + MP_CHECKOK(mp_invmod(b, &meth->irr, &t)); + MP_CHECKOK(mp_mulmod(a, &t, &meth->irr, r)); + CLEANUP: + mp_clear(&t); + return res; + } +} + +/* Wrapper functions for generic binary polynomial field arithmetic. */ + +/* Adds two field elements. */ +mp_err +ec_GF2m_add(const mp_int *a, const mp_int *b, mp_int *r, + const GFMethod *meth) +{ + return mp_badd(a, b, r); +} + +/* Negates a field element. Note that for binary polynomial fields, the + * negation of a field element is the field element itself. */ +mp_err +ec_GF2m_neg(const mp_int *a, mp_int *r, const GFMethod *meth) +{ + if (a == r) { + return MP_OKAY; + } else { + return mp_copy(a, r); + } +} + +/* Reduces a binary polynomial to a field element. */ +mp_err +ec_GF2m_mod(const mp_int *a, mp_int *r, const GFMethod *meth) +{ + return mp_bmod(a, meth->irr_arr, r); +} + +/* Multiplies two field elements. */ +mp_err +ec_GF2m_mul(const mp_int *a, const mp_int *b, mp_int *r, + const GFMethod *meth) +{ + return mp_bmulmod(a, b, meth->irr_arr, r); +} + +/* Squares a field element. */ +mp_err +ec_GF2m_sqr(const mp_int *a, mp_int *r, const GFMethod *meth) +{ + return mp_bsqrmod(a, meth->irr_arr, r); +} + +/* Divides two field elements. If a is NULL, then returns the inverse of + * b. */ +mp_err +ec_GF2m_div(const mp_int *a, const mp_int *b, mp_int *r, + const GFMethod *meth) +{ + mp_err res = MP_OKAY; + mp_int t; + + /* If a is NULL, then return the inverse of b, otherwise return a/b. */ + if (a == NULL) { + /* The GF(2^m) portion of MPI doesn't support invmod, so we + * compute 1/b. */ + MP_CHECKOK(mp_init(&t)); + MP_CHECKOK(mp_set_int(&t, 1)); + MP_CHECKOK(mp_bdivmod(&t, b, &meth->irr, meth->irr_arr, r)); + CLEANUP: + mp_clear(&t); + return res; + } else { + return mp_bdivmod(a, b, &meth->irr, meth->irr_arr, r); + } +} |