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

Incorporate requested changes from Mozilla in review:
https://bugzilla.mozilla.org/show_bug.cgi?id=1123480#c6

     1 /* This Source Code Form is subject to the terms of the Mozilla Public

     2  * License, v. 2.0. If a copy of the MPL was not distributed with this

     3  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

     5 #include "ecp.h"

     6 #include "mpi.h"

     7 #include "mplogic.h"

     8 #include "mpi-priv.h"

    10 #define ECP521_DIGITS ECL_CURVE_DIGITS(521)

    12 /* Fast modular reduction for p521 = 2^521 - 1.  a can be r. Uses

    13  * algorithm 2.31 from Hankerson, Menezes, Vanstone. Guide to

    14  * Elliptic Curve Cryptography. */

    15 static mp_err

    16 ec_GFp_nistp521_mod(const mp_int *a, mp_int *r, const GFMethod *meth)

    17 {

    18 	mp_err res = MP_OKAY;

    19 	int a_bits = mpl_significant_bits(a);

    20 	int i;

    22 	/* m1, m2 are statically-allocated mp_int of exactly the size we need */

    23 	mp_int m1;

    25 	mp_digit s1[ECP521_DIGITS] = { 0 };

    27 	MP_SIGN(&m1) = MP_ZPOS;

    28 	MP_ALLOC(&m1) = ECP521_DIGITS;

    29 	MP_USED(&m1) = ECP521_DIGITS;

    30 	MP_DIGITS(&m1) = s1;

    32 	if (a_bits < 521) {

    33 		if (a==r) return MP_OKAY;

    34 		return mp_copy(a, r);

    35 	}

    36 	/* for polynomials larger than twice the field size or polynomials

    37 	 * not using all words, use regular reduction */

    38 	if (a_bits > (521*2)) {

    39 		MP_CHECKOK(mp_mod(a, &meth->irr, r));

    40 	} else {

    41 #define FIRST_DIGIT (ECP521_DIGITS-1)

    42 		for (i = FIRST_DIGIT; i < MP_USED(a)-1; i++) {

    43 			s1[i-FIRST_DIGIT] = (MP_DIGIT(a, i) >> 9)

    44 				| (MP_DIGIT(a, 1+i) << (MP_DIGIT_BIT-9));

    45 		}

    46 		s1[i-FIRST_DIGIT] = MP_DIGIT(a, i) >> 9;

    48 		if ( a != r ) {

    49 			MP_CHECKOK(s_mp_pad(r,ECP521_DIGITS));

    50 			for (i = 0; i < ECP521_DIGITS; i++) {

    51 				MP_DIGIT(r,i) = MP_DIGIT(a, i);

    52 			}

    53 		}

    54 		MP_USED(r) = ECP521_DIGITS;

    55 		MP_DIGIT(r,FIRST_DIGIT) &=  0x1FF;

    57 		MP_CHECKOK(s_mp_add(r, &m1));

    58 		if (MP_DIGIT(r, FIRST_DIGIT) & 0x200) {

    59 			MP_CHECKOK(s_mp_add_d(r,1));

    60 			MP_DIGIT(r,FIRST_DIGIT) &=  0x1FF;

    61 		} else if (s_mp_cmp(r, &meth->irr) == 0) {

    62 			mp_zero(r);

    63 		}

    64 		s_mp_clamp(r);

    65 	}

    67   CLEANUP:

    68 	return res;

    69 }

    71 /* Compute the square of polynomial a, reduce modulo p521. Store the

    72  * result in r.  r could be a.  Uses optimized modular reduction for p521.

    73  */

    74 static mp_err

    75 ec_GFp_nistp521_sqr(const mp_int *a, mp_int *r, const GFMethod *meth)

    76 {

    77 	mp_err res = MP_OKAY;

    79 	MP_CHECKOK(mp_sqr(a, r));

    80 	MP_CHECKOK(ec_GFp_nistp521_mod(r, r, meth));

    81   CLEANUP:

    82 	return res;

    83 }

    85 /* Compute the product of two polynomials a and b, reduce modulo p521.

    86  * Store the result in r.  r could be a or b; a could be b.  Uses

    87  * optimized modular reduction for p521. */

    88 static mp_err

    89 ec_GFp_nistp521_mul(const mp_int *a, const mp_int *b, mp_int *r,

    90 					const GFMethod *meth)

    91 {

    92 	mp_err res = MP_OKAY;

    94 	MP_CHECKOK(mp_mul(a, b, r));

    95 	MP_CHECKOK(ec_GFp_nistp521_mod(r, r, meth));

    96   CLEANUP:

    97 	return res;

    98 }

   100 /* Divides two field elements. If a is NULL, then returns the inverse of

   101  * b. */

   102 static mp_err

   103 ec_GFp_nistp521_div(const mp_int *a, const mp_int *b, mp_int *r,

   104 		   const GFMethod *meth)

   105 {

   106 	mp_err res = MP_OKAY;

   107 	mp_int t;

   109 	/* If a is NULL, then return the inverse of b, otherwise return a/b. */

   110 	if (a == NULL) {

   111 		return mp_invmod(b, &meth->irr, r);

   112 	} else {

   113 		/* MPI doesn't support divmod, so we implement it using invmod and

   114 		 * mulmod. */

   115 		MP_CHECKOK(mp_init(&t));

   116 		MP_CHECKOK(mp_invmod(b, &meth->irr, &t));

   117 		MP_CHECKOK(mp_mul(a, &t, r));

   118 		MP_CHECKOK(ec_GFp_nistp521_mod(r, r, meth));

   119 	  CLEANUP:

   120 		mp_clear(&t);

   121 		return res;

   122 	}

   123 }

   125 /* Wire in fast field arithmetic and precomputation of base point for

   126  * named curves. */

   127 mp_err

   128 ec_group_set_gfp521(ECGroup *group, ECCurveName name)

   129 {

   130 	if (name == ECCurve_NIST_P521) {

   131 		group->meth->field_mod = &ec_GFp_nistp521_mod;

   132 		group->meth->field_mul = &ec_GFp_nistp521_mul;

   133 		group->meth->field_sqr = &ec_GFp_nistp521_sqr;

   134 		group->meth->field_div = &ec_GFp_nistp521_div;

   135 	}

   136 	return MP_OKAY;

   137 }

The Tor Browser / file revision