| /* |
| * Copyright (c) 2007, 2018, Oracle and/or its affiliates. All rights reserved. |
| * Use is subject to license terms. |
| * |
| * This library is free software; you can redistribute it and/or |
| * modify it under the terms of the GNU Lesser General Public |
| * License as published by the Free Software Foundation; either |
| * version 2.1 of the License, or (at your option) any later version. |
| * |
| * This library is distributed in the hope that it will be useful, |
| * but WITHOUT ANY WARRANTY; without even the implied warranty of |
| * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
| * Lesser General Public License for more details. |
| * |
| * You should have received a copy of the GNU Lesser General Public License |
| * along with this library; if not, write to the Free Software Foundation, |
| * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. |
| * |
| * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
| * or visit www.oracle.com if you need additional information or have any |
| * questions. |
| */ |
| |
| /* ********************************************************************* |
| * |
| * The Original Code is the elliptic curve math library. |
| * |
| * The Initial Developer of the Original Code is |
| * Sun Microsystems, Inc. |
| * Portions created by the Initial Developer are Copyright (C) 2003 |
| * the Initial Developer. All Rights Reserved. |
| * |
| * Contributor(s): |
| * Stephen Fung <fungstep@hotmail.com> and |
| * Douglas Stebila <douglas@stebila.ca>, Sun Microsystems Laboratories |
| * |
| *********************************************************************** */ |
| |
| #include "mpi.h" |
| #include "mp_gf2m.h" |
| #include "ecl-priv.h" |
| #include "mpi-priv.h" |
| #ifndef _KERNEL |
| #include <stdlib.h> |
| #endif |
| |
| /* Allocate memory for a new GFMethod object. */ |
| GFMethod * |
| GFMethod_new(int kmflag) |
| { |
| mp_err res = MP_OKAY; |
| GFMethod *meth; |
| #ifdef _KERNEL |
| meth = (GFMethod *) kmem_alloc(sizeof(GFMethod), kmflag); |
| #else |
| meth = (GFMethod *) malloc(sizeof(GFMethod)); |
| if (meth == NULL) |
| return NULL; |
| #endif |
| meth->constructed = MP_YES; |
| MP_DIGITS(&meth->irr) = 0; |
| meth->extra_free = NULL; |
| MP_CHECKOK(mp_init(&meth->irr, kmflag)); |
| |
| 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(FLAG(irr)); |
| 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; |
| } |
| |
| /* Construct a generic GFMethod for arithmetic over binary polynomial |
| * fields with irreducible irr that has array representation irr_arr (see |
| * ecl-priv.h for description of the representation). If irr_arr is NULL, |
| * then it is constructed from the bitstring representation. */ |
| GFMethod * |
| GFMethod_consGF2m(const mp_int *irr, const unsigned int irr_arr[5]) |
| { |
| mp_err res = MP_OKAY; |
| int ret; |
| GFMethod *meth = NULL; |
| |
| meth = GFMethod_new(FLAG(irr)); |
| if (meth == NULL) |
| return NULL; |
| |
| MP_CHECKOK(mp_copy(irr, &meth->irr)); |
| if (irr_arr != NULL) { |
| /* Irreducible polynomials are either trinomials or pentanomials. */ |
| meth->irr_arr[0] = irr_arr[0]; |
| meth->irr_arr[1] = irr_arr[1]; |
| meth->irr_arr[2] = irr_arr[2]; |
| if (irr_arr[2] > 0) { |
| meth->irr_arr[3] = irr_arr[3]; |
| meth->irr_arr[4] = irr_arr[4]; |
| } else { |
| meth->irr_arr[3] = meth->irr_arr[4] = 0; |
| } |
| } else { |
| ret = mp_bpoly2arr(irr, meth->irr_arr, 5); |
| /* Irreducible polynomials are either trinomials or pentanomials. */ |
| if ((ret != 5) && (ret != 3)) { |
| res = MP_UNDEF; |
| goto CLEANUP; |
| } |
| } |
| meth->field_add = &ec_GF2m_add; |
| meth->field_neg = &ec_GF2m_neg; |
| meth->field_sub = &ec_GF2m_add; |
| meth->field_mod = &ec_GF2m_mod; |
| meth->field_mul = &ec_GF2m_mul; |
| meth->field_sqr = &ec_GF2m_sqr; |
| meth->field_div = &ec_GF2m_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); |
| #ifdef _KERNEL |
| kmem_free(meth, sizeof(GFMethod)); |
| #else |
| free(meth); |
| #endif |
| } |
| |
| /* 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 |
| MP_ADD_CARRY_ZERO(a0, r0, r0, carry); |
| MP_ADD_CARRY(a1, r1, r1, carry, carry); |
| MP_ADD_CARRY(a2, r2, r2, carry, 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 |
| MP_SUB_BORROW(r0, a0, r0, 0, carry); |
| MP_SUB_BORROW(r1, a1, r1, carry, carry); |
| MP_SUB_BORROW(r2, a2, r2, carry, 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 |
| MP_ADD_CARRY_ZERO(a0, r0, r0, carry); |
| MP_ADD_CARRY(a1, r1, r1, carry, carry); |
| MP_ADD_CARRY(a2, r2, r2, carry, carry); |
| MP_ADD_CARRY(a3, r3, r3, carry, 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 |
| MP_SUB_BORROW(r0, a0, r0, 0, carry); |
| MP_SUB_BORROW(r1, a1, r1, carry, carry); |
| MP_SUB_BORROW(r2, a2, r2, carry, carry); |
| MP_SUB_BORROW(r3, a3, r3, carry, 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); |
| } |
| |
| MP_ADD_CARRY_ZERO(a0, r0, r0, carry); |
| MP_ADD_CARRY(a1, r1, r1, carry, carry); |
| MP_ADD_CARRY(a2, r2, r2, carry, carry); |
| MP_ADD_CARRY(a3, r3, r3, carry, carry); |
| MP_ADD_CARRY(a4, r4, r4, carry, 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); |
| MP_SUB_BORROW(r0, a0, r0, 0, carry); |
| MP_SUB_BORROW(r1, a1, r1, carry, carry); |
| MP_SUB_BORROW(r2, a2, r2, carry, carry); |
| MP_SUB_BORROW(r3, a3, r3, carry, carry); |
| MP_SUB_BORROW(r4, a4, r4, carry, 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); |
| } |
| |
| MP_ADD_CARRY_ZERO(a0, r0, r0, carry); |
| MP_ADD_CARRY(a1, r1, r1, carry, carry); |
| MP_ADD_CARRY(a2, r2, r2, carry, carry); |
| MP_ADD_CARRY(a3, r3, r3, carry, carry); |
| MP_ADD_CARRY(a4, r4, r4, carry, carry); |
| MP_ADD_CARRY(a5, r5, r5, carry, 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); |
| MP_SUB_BORROW(r0, a0, r0, 0, carry); |
| MP_SUB_BORROW(r1, a1, r1, carry, carry); |
| MP_SUB_BORROW(r2, a2, r2, carry, carry); |
| MP_SUB_BORROW(r3, a3, r3, carry, carry); |
| MP_SUB_BORROW(r4, a4, r4, carry, carry); |
| MP_SUB_BORROW(r5, a5, r5, carry, 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 |
| MP_SUB_BORROW(r0, b0, r0, 0, borrow); |
| MP_SUB_BORROW(r1, b1, r1, borrow, borrow); |
| MP_SUB_BORROW(r2, b2, r2, borrow, 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 |
| MP_ADD_CARRY_ZERO(b0, r0, r0, borrow); |
| MP_ADD_CARRY(b1, r1, r1, borrow, borrow); |
| MP_ADD_CARRY(b2, r2, r2, borrow, 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 |
| MP_SUB_BORROW(r0, b0, r0, 0, borrow); |
| MP_SUB_BORROW(r1, b1, r1, borrow, borrow); |
| MP_SUB_BORROW(r2, b2, r2, borrow, borrow); |
| MP_SUB_BORROW(r3, b3, r3, borrow, 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 |
| MP_ADD_CARRY_ZERO(b0, r0, r0, borrow); |
| MP_ADD_CARRY(b1, r1, r1, borrow, borrow); |
| MP_ADD_CARRY(b2, r2, r2, borrow, borrow); |
| MP_ADD_CARRY(b3, r3, r3, borrow, 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); |
| } |
| |
| MP_SUB_BORROW(r0, b0, r0, 0, borrow); |
| MP_SUB_BORROW(r1, b1, r1, borrow, borrow); |
| MP_SUB_BORROW(r2, b2, r2, borrow, borrow); |
| MP_SUB_BORROW(r3, b3, r3, borrow, borrow); |
| MP_SUB_BORROW(r4, b4, r4, borrow, 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); |
| MP_ADD_CARRY_ZERO(b0, r0, r0, borrow); |
| MP_ADD_CARRY(b1, r1, r1, borrow, borrow); |
| MP_ADD_CARRY(b2, r2, r2, borrow, borrow); |
| MP_ADD_CARRY(b3, r3, r3, borrow, borrow); |
| MP_ADD_CARRY(b4, r4, r4, borrow, 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); |
| } |
| |
| MP_SUB_BORROW(r0, b0, r0, 0, borrow); |
| MP_SUB_BORROW(r1, b1, r1, borrow, borrow); |
| MP_SUB_BORROW(r2, b2, r2, borrow, borrow); |
| MP_SUB_BORROW(r3, b3, r3, borrow, borrow); |
| MP_SUB_BORROW(r4, b4, r4, borrow, borrow); |
| MP_SUB_BORROW(r5, b5, r5, borrow, 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); |
| MP_ADD_CARRY_ZERO(b0, r0, r0, borrow); |
| MP_ADD_CARRY(b1, r1, r1, borrow, borrow); |
| MP_ADD_CARRY(b2, r2, r2, borrow, borrow); |
| MP_ADD_CARRY(b3, r3, r3, borrow, borrow); |
| MP_ADD_CARRY(b4, r4, r4, borrow, borrow); |
| MP_ADD_CARRY(b5, r5, r5, borrow, 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, FLAG(b))); |
| 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, FLAG(b))); |
| 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); |
| } |
| } |
