Back to index

lightning-sunbird  0.9+nobinonly
Functions
ecp_fp.c File Reference
#include "ecp_fp.h"
#include "ecl-priv.h"
#include <stdlib.h>

Go to the source code of this file.

Functions

void ecfp_tidyShort (double *t, const EC_group_fp *group)
void ecfp_tidyUpper (double *t, const EC_group_fp *group)
void ecfp_tidy (double *t, const double *alpha, const EC_group_fp *group)
void ecfp_positiveTidy (double *t, const EC_group_fp *group)
void ecfp_fp2i (mp_int *mpout, double *d, const ECGroup *ecgroup)
void ecfp_i2fp (double *out, const mp_int *x, const ECGroup *ecgroup)
mp_err ec_GFp_point_mul_jac_4w_fp (const mp_int *n, const mp_int *px, const mp_int *py, mp_int *rx, mp_int *ry, const ECGroup *ecgroup)
mp_err ec_GFp_pt_mul_jac_fp (const mp_int *n, const mp_int *px, const mp_int *py, mp_int *rx, mp_int *ry, const ECGroup *ecgroup)
mp_err ec_GFp_point_mul_wNAF_fp (const mp_int *n, const mp_int *px, const mp_int *py, mp_int *rx, mp_int *ry, const ECGroup *ecgroup)
void ec_GFp_extra_free_fp (ECGroup *group)
int ec_set_fp_precision (EC_group_fp *group)

Function Documentation

void ec_GFp_extra_free_fp ( ECGroup *  group)

Definition at line 542 of file ecp_fp.c.

{
       if (group->extra1 != NULL) {
              free(group->extra1);
              group->extra1 = NULL;
       }
}

Here is the caller graph for this function:

mp_err ec_GFp_point_mul_jac_4w_fp ( const mp_int n,
const mp_int px,
const mp_int py,
mp_int rx,
mp_int ry,
const ECGroup *  ecgroup 
)

Definition at line 307 of file ecp_fp.c.

{
       mp_err res = MP_OKAY;
       ecfp_jac_pt precomp[16], r;
       ecfp_aff_pt p;
       EC_group_fp *group;

       mp_int rz;
       int i, ni, d;

       ARGCHK(ecgroup != NULL, MP_BADARG);
       ARGCHK((n != NULL) && (px != NULL) && (py != NULL), MP_BADARG);

       group = (EC_group_fp *) ecgroup->extra1;
       MP_DIGITS(&rz) = 0;
       MP_CHECKOK(mp_init(&rz));

       /* init p, da */
       ecfp_i2fp(p.x, px, ecgroup);
       ecfp_i2fp(p.y, py, ecgroup);
       ecfp_i2fp(group->curvea, &ecgroup->curvea, ecgroup);

       /* Do precomputation */
       group->precompute_jac(precomp, &p, group);

       /* Do main body of calculations */
       d = (mpl_significant_bits(n) + 3) / 4;

       /* R = inf */
       for (i = 0; i < group->numDoubles; i++) {
              r.z[i] = 0;
       }

       for (i = d - 1; i >= 0; i--) {
              /* compute window ni */
              ni = MP_GET_BIT(n, 4 * i + 3);
              ni <<= 1;
              ni |= MP_GET_BIT(n, 4 * i + 2);
              ni <<= 1;
              ni |= MP_GET_BIT(n, 4 * i + 1);
              ni <<= 1;
              ni |= MP_GET_BIT(n, 4 * i);

              /* R = 2^4 * R */
              group->pt_dbl_jac(&r, &r, group);
              group->pt_dbl_jac(&r, &r, group);
              group->pt_dbl_jac(&r, &r, group);
              group->pt_dbl_jac(&r, &r, group);

              /* R = R + (ni * P) */
              group->pt_add_jac(&r, &precomp[ni], &r, group);
       }

       /* Convert back to integer */
       ecfp_fp2i(rx, r.x, ecgroup);
       ecfp_fp2i(ry, r.y, ecgroup);
       ecfp_fp2i(&rz, r.z, ecgroup);

       /* convert result S to affine coordinates */
       MP_CHECKOK(ec_GFp_pt_jac2aff(rx, ry, &rz, rx, ry, ecgroup));

  CLEANUP:
       mp_clear(&rz);
       return res;
}

Here is the caller graph for this function:

mp_err ec_GFp_point_mul_wNAF_fp ( const mp_int n,
const mp_int px,
const mp_int py,
mp_int rx,
mp_int ry,
const ECGroup *  ecgroup 
)

Definition at line 464 of file ecp_fp.c.

{
       mp_err res = MP_OKAY;
       mp_int sx, sy, sz;
       EC_group_fp *group = (EC_group_fp *) ecgroup->extra1;
       ecfp_chud_pt precomp[16];

       ecfp_aff_pt p;
       ecfp_jm_pt r;

       signed char naf[group->orderBitSize + 1];
       int i;

       MP_DIGITS(&sx) = 0;
       MP_DIGITS(&sy) = 0;
       MP_DIGITS(&sz) = 0;
       MP_CHECKOK(mp_init(&sx));
       MP_CHECKOK(mp_init(&sy));
       MP_CHECKOK(mp_init(&sz));

       /* if n = 0 then r = inf */
       if (mp_cmp_z(n) == 0) {
              mp_zero(rx);
              mp_zero(ry);
              res = MP_OKAY;
              goto CLEANUP;
              /* if n < 0 then out of range error */
       } else if (mp_cmp_z(n) < 0) {
              res = MP_RANGE;
              goto CLEANUP;
       }

       /* Convert from integer to floating point */
       ecfp_i2fp(p.x, px, ecgroup);
       ecfp_i2fp(p.y, py, ecgroup);
       ecfp_i2fp(group->curvea, &(ecgroup->curvea), ecgroup);

       /* Perform precomputation */
       group->precompute_chud(precomp, &p, group);

       /* Compute 5NAF */
       ec_compute_wNAF(naf, group->orderBitSize, n, 5);

       /* Init R = pt at infinity */
       for (i = 0; i < group->numDoubles; i++) {
              r.z[i] = 0;
       }

       /* wNAF method */
       for (i = group->orderBitSize; i >= 0; i--) {
              /* R = 2R */
              group->pt_dbl_jm(&r, &r, group);

              if (naf[i] != 0) {
                     group->pt_add_jm_chud(&r, &precomp[(naf[i] + 15) / 2], &r,
                                                          group);
              }
       }

       /* Convert from floating point to integer */
       ecfp_fp2i(&sx, r.x, ecgroup);
       ecfp_fp2i(&sy, r.y, ecgroup);
       ecfp_fp2i(&sz, r.z, ecgroup);

       /* convert result R to affine coordinates */
       MP_CHECKOK(ec_GFp_pt_jac2aff(&sx, &sy, &sz, rx, ry, ecgroup));

  CLEANUP:
       mp_clear(&sx);
       mp_clear(&sy);
       mp_clear(&sz);
       return res;
}

Here is the caller graph for this function:

mp_err ec_GFp_pt_mul_jac_fp ( const mp_int n,
const mp_int px,
const mp_int py,
mp_int rx,
mp_int ry,
const ECGroup *  ecgroup 
)

Definition at line 388 of file ecp_fp.c.

{
       mp_err res;
       mp_int sx, sy, sz;

       ecfp_aff_pt p;
       ecfp_jac_pt r;
       EC_group_fp *group = (EC_group_fp *) ecgroup->extra1;

       int i, l;

       MP_DIGITS(&sx) = 0;
       MP_DIGITS(&sy) = 0;
       MP_DIGITS(&sz) = 0;
       MP_CHECKOK(mp_init(&sx));
       MP_CHECKOK(mp_init(&sy));
       MP_CHECKOK(mp_init(&sz));

       /* if n = 0 then r = inf */
       if (mp_cmp_z(n) == 0) {
              mp_zero(rx);
              mp_zero(ry);
              res = MP_OKAY;
              goto CLEANUP;
              /* if n < 0 then out of range error */
       } else if (mp_cmp_z(n) < 0) {
              res = MP_RANGE;
              goto CLEANUP;
       }

       /* Convert from integer to floating point */
       ecfp_i2fp(p.x, px, ecgroup);
       ecfp_i2fp(p.y, py, ecgroup);
       ecfp_i2fp(group->curvea, &(ecgroup->curvea), ecgroup);

       /* Init r to point at infinity */
       for (i = 0; i < group->numDoubles; i++) {
              r.z[i] = 0;
       }

       /* double and add method */
       l = mpl_significant_bits(n) - 1;

       for (i = l; i >= 0; i--) {
              /* R = 2R */
              group->pt_dbl_jac(&r, &r, group);

              /* if n_i = 1, then R = R + Q */
              if (MP_GET_BIT(n, i) != 0) {
                     group->pt_add_jac_aff(&r, &p, &r, group);
              }
       }

       /* Convert from floating point to integer */
       ecfp_fp2i(&sx, r.x, ecgroup);
       ecfp_fp2i(&sy, r.y, ecgroup);
       ecfp_fp2i(&sz, r.z, ecgroup);

       /* convert result R to affine coordinates */
       MP_CHECKOK(ec_GFp_pt_jac2aff(&sx, &sy, &sz, rx, ry, ecgroup));

  CLEANUP:
       mp_clear(&sx);
       mp_clear(&sy);
       mp_clear(&sz);
       return res;
}

Here is the caller graph for this function:

int ec_set_fp_precision ( EC_group_fp *  group)

Definition at line 555 of file ecp_fp.c.

{
       double a = 9007199254740992.0;     /* 2^53 */
       double b = a + 1;

       if (a == b) {
              group->fpPrecision = 53;
              group->alpha = ecfp_alpha_53;
              return 53;
       }
       group->fpPrecision = 64;
       group->alpha = ecfp_alpha_64;
       return 64;
}

Here is the caller graph for this function:

void ecfp_fp2i ( mp_int mpout,
double *  d,
const ECGroup *  ecgroup 
)

Definition at line 117 of file ecp_fp.c.

{
       EC_group_fp *group = (EC_group_fp *) ecgroup->extra1;
       unsigned short i16[(group->primeBitSize + 15) / 16];
       double q = 1;

#ifdef ECL_THIRTY_TWO_BIT
       /* TEST uint32_t z = 0; */
       unsigned int z = 0;
#else
       uint64_t z = 0;
#endif
       int zBits = 0;
       int copiedBits = 0;
       int i = 0;
       int j = 0;

       mp_digit *out;

       /* Result should always be >= 0, so set sign accordingly */
       MP_SIGN(mpout) = MP_ZPOS;

       /* Tidy up so we're just dealing with positive numbers */
       ecfp_positiveTidy(d, group);

       /* We might need to do this reduction step more than once if the
        * reduction adds smaller terms which carry-over to cause another
        * reduction. However, this should happen very rarely, if ever,
        * depending on the elliptic curve. */
       do {
              /* Init loop data */
              z = 0;
              zBits = 0;
              q = 1;
              i = 0;
              j = 0;
              copiedBits = 0;

              /* Might have to do a bit more reduction */
              group->ecfp_singleReduce(d, group);

              /* Grow the size of the mpint if it's too small */
              s_mp_grow(mpout, group->numInts);
              MP_USED(mpout) = group->numInts;
              out = MP_DIGITS(mpout);

              /* Convert double to 16 bit integers */
              while (copiedBits < group->primeBitSize) {
                     if (zBits < 16) {
                            z += d[i] * q;
                            i++;
                            ECFP_ASSERT(i < (group->primeBitSize + 15) / 16);
                            zBits += group->doubleBitSize;
                     }
                     i16[j] = z;
                     j++;
                     z >>= 16;
                     zBits -= 16;
                     q *= ecfp_twom16;
                     copiedBits += 16;
              }
       } while (z != 0);

       /* Convert 16 bit integers to mp_digit */
#ifdef ECL_THIRTY_TWO_BIT
       for (i = 0; i < (group->primeBitSize + 15) / 16; i += 2) {
              *out = 0;
              if (i + 1 < (group->primeBitSize + 15) / 16) {
                     *out = i16[i + 1];
                     *out <<= 16;
              }
              *out++ += i16[i];
       }
#else                                            /* 64 bit */
       for (i = 0; i < (group->primeBitSize + 15) / 16; i += 4) {
              *out = 0;
              if (i + 3 < (group->primeBitSize + 15) / 16) {
                     *out = i16[i + 3];
                     *out <<= 16;
              }
              if (i + 2 < (group->primeBitSize + 15) / 16) {
                     *out += i16[i + 2];
                     *out <<= 16;
              }
              if (i + 1 < (group->primeBitSize + 15) / 16) {
                     *out += i16[i + 1];
                     *out <<= 16;
              }
              *out++ += i16[i];
       }
#endif

       /* Perform final reduction.  mpout should already be the same number
        * of bits as p, but might not be less than p.  Make it so. Since
        * mpout has the same number of bits as p, and 2p has a larger bit
        * size, then mpout < 2p, so a single subtraction of p will suffice. */
       if (mp_cmp(mpout, &ecgroup->meth->irr) >= 0) {
              mp_sub(mpout, &ecgroup->meth->irr, mpout);
       }

       /* Shrink the size of the mp_int to the actual used size (required for 
        * mp_cmp_z == 0) */
       out = MP_DIGITS(mpout);
       for (i = group->numInts - 1; i > 0; i--) {
              if (out[i] != 0)
                     break;
       }
       MP_USED(mpout) = i + 1;

       /* Should be between 0 and p-1 */
       ECFP_ASSERT(mp_cmp(mpout, &ecgroup->meth->irr) < 0);
       ECFP_ASSERT(mp_cmp_z(mpout) >= 0);
}

Here is the caller graph for this function:

void ecfp_i2fp ( double *  out,
const mp_int x,
const ECGroup *  ecgroup 
)

Definition at line 233 of file ecp_fp.c.

{
       int i;
       int j = 0;
       int size;
       double shift = 1;
       mp_digit *in;
       EC_group_fp *group = (EC_group_fp *) ecgroup->extra1;

#ifdef ECL_DEBUG
       /* if debug mode, convert result back using ecfp_fp2i into cmp, then
        * compare to x. */
       mp_int cmp;

       MP_DIGITS(&cmp) = NULL;
       mp_init(&cmp);
#endif

       ECFP_ASSERT(group != NULL);

       /* init output to 0 (since we skip over some terms) */
       for (i = 0; i < group->numDoubles; i++)
              out[i] = 0;
       i = 0;

       size = MP_USED(x);
       in = MP_DIGITS(x);

       /* Copy from int into doubles */
#ifdef ECL_THIRTY_TWO_BIT
       while (j < size) {
              while (group->doubleBitSize * (i + 1) <= 32 * j) {
                     i++;
              }
              ECFP_ASSERT(group->doubleBitSize * i <= 32 * j);
              out[i] = in[j];
              out[i] *= shift;
              shift *= ecfp_two32;
              j++;
       }
#else
       while (j < size) {
              while (group->doubleBitSize * (i + 1) <= 64 * j) {
                     i++;
              }
              ECFP_ASSERT(group->doubleBitSize * i <= 64 * j);
              out[i] = (in[j] & 0x00000000FFFFFFFF) * shift;

              while (group->doubleBitSize * (i + 1) <= 64 * j + 32) {
                     i++;
              }
              ECFP_ASSERT(24 * i <= 64 * j + 32);
              out[i] = (in[j] & 0xFFFFFFFF00000000) * shift;

              shift *= ecfp_two64;
              j++;
       }
#endif
       /* Realign bits to match double boundaries */
       ecfp_tidyShort(out, group);

#ifdef ECL_DEBUG
       /* Convert result back to mp_int, compare to original */
       ecfp_fp2i(&cmp, out, ecgroup);
       ECFP_ASSERT(mp_cmp(&cmp, x) == 0);
       mp_clear(&cmp);
#endif
}

Here is the caller graph for this function:

void ecfp_positiveTidy ( double *  t,
const EC_group_fp *  group 
)

Definition at line 92 of file ecp_fp.c.

{
       double q;
       int i;

       /* Do carrying */
       for (i = 0; i < group->numDoubles - 1; i++) {
              /* Subtract beta to force rounding down */
              q = t[i] - ecfp_beta[i + 1];
              q += group->alpha[i + 1];
              q -= group->alpha[i + 1];
              t[i] -= q;
              t[i + 1] += q;

              /* Due to subtracting ecfp_beta, we should have each term a
               * non-negative int */
              ECFP_ASSERT(t[i] / ecfp_exp[i] ==
                                   (unsigned long long) (t[i] / ecfp_exp[i]));
              ECFP_ASSERT(t[i] >= 0);
       }
}

Here is the caller graph for this function:

void ecfp_tidy ( double *  t,
const double *  alpha,
const EC_group_fp *  group 
)

Definition at line 70 of file ecp_fp.c.

{
       double q;
       int i;

       /* Do carrying */
       for (i = 0; i < group->numDoubles - 1; i++) {
              q = t[i] + alpha[i + 1];
              q -= alpha[i + 1];
              t[i] -= q;
              t[i + 1] += q;

              /* If we don't assume that truncation rounding is used, then q
               * might be 2^n bigger than expected (if it rounds up), then t[0]
               * could be negative and t[1] 2^n larger than expected. */
       }
}

Here is the caller graph for this function:

void ecfp_tidyShort ( double *  t,
const EC_group_fp *  group 
)

Definition at line 49 of file ecp_fp.c.

{
       group->ecfp_tidy(t, group->alpha, group);
}

Here is the caller graph for this function:

void ecfp_tidyUpper ( double *  t,
const EC_group_fp *  group 
)

Definition at line 58 of file ecp_fp.c.

{
       group->ecfp_tidy(t + group->numDoubles,
                                    group->alpha + group->numDoubles, group);
}

Here is the caller graph for this function: