The Tor Browser: security/nss/lib/freebl/ecl/ecp

security/nss/lib/freebl/ecl/ecp_fp.c@6474c204b198 (annotated)

security/nss/lib/freebl/ecl/ecp_fp.c

Wed, 31 Dec 2014 06:09:35 +0100

author: Michael Schloh von Bennewitz <michael@schloh.com>
date: Wed, 31 Dec 2014 06:09:35 +0100
changeset 0: 6474c204b198
permissions: -rw-r--r--

Cloned upstream origin tor-browser at tor-browser-31.3.0esr-4.5-1-build1
revision ID fc1c9ff7c1b2defdbc039f12214767608f46423f for hacking purpose.

 /* 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 "ecp_fp.h"
 #include "ecl-priv.h"
 #include <stdlib.h>
 /* Performs tidying on a short multi-precision floating point integer (the
  * lower group->numDoubles floats). */
 void
 ecfp_tidyShort(double *t, const EC_group_fp * group)
 {
 	group->ecfp_tidy(t, group->alpha, group);
 }
 /* Performs tidying on only the upper float digits of a multi-precision
  * floating point integer, i.e. the digits beyond the regular length which
  * are removed in the reduction step. */
 void
 ecfp_tidyUpper(double *t, const EC_group_fp * group)
 {
 	group->ecfp_tidy(t + group->numDoubles,
 					 group->alpha + group->numDoubles, group);
 }
 /* Performs a "tidy" operation, which performs carrying, moving excess
  * bits from one double to the next double, so that the precision of the
  * doubles is reduced to the regular precision group->doubleBitSize. This
  * might result in some float digits being negative. Alternative C version
  * for portability. */
 void
 ecfp_tidy(double *t, const double *alpha, const EC_group_fp * group)
 {
 	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. */
 	}
 }
 /* Performs a more mathematically precise "tidying" so that each term is
  * positive.  This is slower than the regular tidying, and is used for
  * conversion from floating point to integer. */
 void
 ecfp_positiveTidy(double *t, const EC_group_fp * group)
 {
 	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);
 	}
 }
 /* Converts from a floating point representation into an mp_int. Expects
  * that d is already reduced. */
 void
 ecfp_fp2i(mp_int *mpout, double *d, const ECGroup *ecgroup)
 {
 	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);
 }
 /* Converts from an mpint into a floating point representation. */
 void
 ecfp_i2fp(double *out, const mp_int *x, const ECGroup *ecgroup)
 {
 	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
 }
 /* Computes R = nP where R is (rx, ry) and P is (px, py). The parameters
  * a, b and p are the elliptic curve coefficients and the prime that
  * determines the field GFp.  Elliptic curve points P and R can be
  * identical.  Uses Jacobian coordinates. Uses 4-bit window method. */
 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 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;
 }
 /* Uses mixed Jacobian-affine coordinates to perform a point
  * multiplication: R = n * P, n scalar. Uses mixed Jacobian-affine
  * coordinates (Jacobian coordinates for doubles and affine coordinates
  * for additions; based on recommendation from Brown et al.). Not very
  * time efficient but quite space efficient, no precomputation needed.
  * group contains the elliptic curve coefficients and the prime that
  * determines the field GFp.  Elliptic curve points P and R can be
  * identical. Performs calculations in floating point number format, since
  * this is faster than the integer operations on the ULTRASPARC III.
  * Uses left-to-right binary method (double & add) (algorithm 9) for
  * scalar-point multiplication from Brown, Hankerson, Lopez, Menezes.
  * Software Implementation of the NIST Elliptic Curves Over Prime Fields. */
 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 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;
 }
 /* Computes R = nP where R is (rx, ry) and P is the base point. Elliptic
  * curve points P and R can be identical. Uses mixed Modified-Jacobian
  * co-ordinates for doubling and Chudnovsky Jacobian coordinates for
  * additions. Uses 5-bit window NAF method (algorithm 11) for scalar-point
  * multiplication from Brown, Hankerson, Lopez, Menezes. Software
  * Implementation of the NIST Elliptic Curves Over Prime Fields. */
 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)
 {
 	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;
 }
 /* Cleans up extra memory allocated in ECGroup for this implementation. */
 void
 ec_GFp_extra_free_fp(ECGroup *group)
 {
 	if (group->extra1 != NULL) {
 		free(group->extra1);
 		group->extra1 = NULL;
 	}
 }
 /* Tests what precision floating point arithmetic is set to. This should
  * be either a 53-bit mantissa (IEEE standard) or a 64-bit mantissa
  * (extended precision on x86) and sets it into the EC_group_fp. Returns
  * either 53 or 64 accordingly. */
 int
 ec_set_fp_precision(EC_group_fp * group)
 {
 	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;
 }

The Tor Browser / annotate

security/nss/lib/freebl/ecl/ecp_fp.c@6474c204b198 (annotated)

security/nss/lib/freebl/ecl/ecp_fp.c