| /* 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); |
| } |
| } |