• file
• revisions
• annotate
• diff
• comparison
• raw

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

security/nss/lib/freebl/ecl/ecp_521.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.

michael@0	1	/* This Source Code Form is subject to the terms of the Mozilla Public
michael@0	2	* License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0	3	* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0	4
michael@0	5	#include "ecp.h"
michael@0	6	#include "mpi.h"
michael@0	7	#include "mplogic.h"
michael@0	8	#include "mpi-priv.h"
michael@0	9
michael@0	10	#define ECP521_DIGITS ECL_CURVE_DIGITS(521)
michael@0	11
michael@0	12	/* Fast modular reduction for p521 = 2^521 - 1. a can be r. Uses
michael@0	13	* algorithm 2.31 from Hankerson, Menezes, Vanstone. Guide to
michael@0	14	* Elliptic Curve Cryptography. */
michael@0	15	static mp_err
michael@0	16	ec_GFp_nistp521_mod(const mp_int *a, mp_int *r, const GFMethod *meth)
michael@0	17	{
michael@0	18	mp_err res = MP_OKAY;
michael@0	19	int a_bits = mpl_significant_bits(a);
michael@0	20	int i;
michael@0	21
michael@0	22	/* m1, m2 are statically-allocated mp_int of exactly the size we need */
michael@0	23	mp_int m1;
michael@0	24
michael@0	25	mp_digit s1[ECP521_DIGITS] = { 0 };
michael@0	26
michael@0	27	MP_SIGN(&m1) = MP_ZPOS;
michael@0	28	MP_ALLOC(&m1) = ECP521_DIGITS;
michael@0	29	MP_USED(&m1) = ECP521_DIGITS;
michael@0	30	MP_DIGITS(&m1) = s1;
michael@0	31
michael@0	32	if (a_bits < 521) {
michael@0	33	if (a==r) return MP_OKAY;
michael@0	34	return mp_copy(a, r);
michael@0	35	}
michael@0	36	/* for polynomials larger than twice the field size or polynomials
michael@0	37	* not using all words, use regular reduction */
michael@0	38	if (a_bits > (521*2)) {
michael@0	39	MP_CHECKOK(mp_mod(a, &meth->irr, r));
michael@0	40	} else {
michael@0	41	#define FIRST_DIGIT (ECP521_DIGITS-1)
michael@0	42	for (i = FIRST_DIGIT; i < MP_USED(a)-1; i++) {
michael@0	43	s1[i-FIRST_DIGIT] = (MP_DIGIT(a, i) >> 9)
michael@0	44	| (MP_DIGIT(a, 1+i) << (MP_DIGIT_BIT-9));
michael@0	45	}
michael@0	46	s1[i-FIRST_DIGIT] = MP_DIGIT(a, i) >> 9;
michael@0	47
michael@0	48	if ( a != r ) {
michael@0	49	MP_CHECKOK(s_mp_pad(r,ECP521_DIGITS));
michael@0	50	for (i = 0; i < ECP521_DIGITS; i++) {
michael@0	51	MP_DIGIT(r,i) = MP_DIGIT(a, i);
michael@0	52	}
michael@0	53	}
michael@0	54	MP_USED(r) = ECP521_DIGITS;
michael@0	55	MP_DIGIT(r,FIRST_DIGIT) &= 0x1FF;
michael@0	56
michael@0	57	MP_CHECKOK(s_mp_add(r, &m1));
michael@0	58	if (MP_DIGIT(r, FIRST_DIGIT) & 0x200) {
michael@0	59	MP_CHECKOK(s_mp_add_d(r,1));
michael@0	60	MP_DIGIT(r,FIRST_DIGIT) &= 0x1FF;
michael@0	61	} else if (s_mp_cmp(r, &meth->irr) == 0) {
michael@0	62	mp_zero(r);
michael@0	63	}
michael@0	64	s_mp_clamp(r);
michael@0	65	}
michael@0	66
michael@0	67	CLEANUP:
michael@0	68	return res;
michael@0	69	}
michael@0	70
michael@0	71	/* Compute the square of polynomial a, reduce modulo p521. Store the
michael@0	72	* result in r. r could be a. Uses optimized modular reduction for p521.
michael@0	73	*/
michael@0	74	static mp_err
michael@0	75	ec_GFp_nistp521_sqr(const mp_int *a, mp_int *r, const GFMethod *meth)
michael@0	76	{
michael@0	77	mp_err res = MP_OKAY;
michael@0	78
michael@0	79	MP_CHECKOK(mp_sqr(a, r));
michael@0	80	MP_CHECKOK(ec_GFp_nistp521_mod(r, r, meth));
michael@0	81	CLEANUP:
michael@0	82	return res;
michael@0	83	}
michael@0	84
michael@0	85	/* Compute the product of two polynomials a and b, reduce modulo p521.
michael@0	86	* Store the result in r. r could be a or b; a could be b. Uses
michael@0	87	* optimized modular reduction for p521. */
michael@0	88	static mp_err
michael@0	89	ec_GFp_nistp521_mul(const mp_int *a, const mp_int *b, mp_int *r,
michael@0	90	const GFMethod *meth)
michael@0	91	{
michael@0	92	mp_err res = MP_OKAY;
michael@0	93
michael@0	94	MP_CHECKOK(mp_mul(a, b, r));
michael@0	95	MP_CHECKOK(ec_GFp_nistp521_mod(r, r, meth));
michael@0	96	CLEANUP:
michael@0	97	return res;
michael@0	98	}
michael@0	99
michael@0	100	/* Divides two field elements. If a is NULL, then returns the inverse of
michael@0	101	* b. */
michael@0	102	static mp_err
michael@0	103	ec_GFp_nistp521_div(const mp_int *a, const mp_int *b, mp_int *r,
michael@0	104	const GFMethod *meth)
michael@0	105	{
michael@0	106	mp_err res = MP_OKAY;
michael@0	107	mp_int t;
michael@0	108
michael@0	109	/* If a is NULL, then return the inverse of b, otherwise return a/b. */
michael@0	110	if (a == NULL) {
michael@0	111	return mp_invmod(b, &meth->irr, r);
michael@0	112	} else {
michael@0	113	/* MPI doesn't support divmod, so we implement it using invmod and
michael@0	114	* mulmod. */
michael@0	115	MP_CHECKOK(mp_init(&t));
michael@0	116	MP_CHECKOK(mp_invmod(b, &meth->irr, &t));
michael@0	117	MP_CHECKOK(mp_mul(a, &t, r));
michael@0	118	MP_CHECKOK(ec_GFp_nistp521_mod(r, r, meth));
michael@0	119	CLEANUP:
michael@0	120	mp_clear(&t);
michael@0	121	return res;
michael@0	122	}
michael@0	123	}
michael@0	124
michael@0	125	/* Wire in fast field arithmetic and precomputation of base point for
michael@0	126	* named curves. */
michael@0	127	mp_err
michael@0	128	ec_group_set_gfp521(ECGroup *group, ECCurveName name)
michael@0	129	{
michael@0	130	if (name == ECCurve_NIST_P521) {
michael@0	131	group->meth->field_mod = &ec_GFp_nistp521_mod;
michael@0	132	group->meth->field_mul = &ec_GFp_nistp521_mul;
michael@0	133	group->meth->field_sqr = &ec_GFp_nistp521_sqr;
michael@0	134	group->meth->field_div = &ec_GFp_nistp521_div;
michael@0	135	}
michael@0	136	return MP_OKAY;
michael@0	137	}