Source code
Revision control
Copy as Markdown
Other Tools
/* 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
#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);
}
}