2  *  Copyright (C) 2017 - This file is part of libecc project
7  *      Jean-Pierre FLORI <jean-pierre.flori@ssi.gouv.fr>
28  *	- r = 2^p_rounded_bitlen mod (p), where
31  *	- r_square = r^2 mod (p)
32  *	- mpinv = -p^-1 mod (2^WORDSIZE).
37  * The function returns 0 on success, -1 on error. out parameters 'r',
71 	/* _mpinv = 2^wlen - (modinv(prime, 2^wlen)) */  in nn_compute_redc1_coefs()
117  * and mpinv is -p^(-1) mod (2^WORDSIZE).
122  * The function returns 0 on success, -1 on error.
124 ATTRIBUTE_WARN_UNUSED_RET static int _nn_mul_redc1(nn_t out, nn_src_t in1, nn_src_t in2, nn_src_t p,  in _nn_mul_redc1()  argument
141 	SHOULD_HAVE((!nn_cmp(in2, p, &cmp)) && (cmp < 0), ret, err);  in _nn_mul_redc1()
145 	/* Check which one of in1 or in2 is the biggest */  in _nn_mul_redc1()
146 	a = (in1->wlen <= in2->wlen) ? in2 : in1;  in _nn_mul_redc1()
147 	b = (in1->wlen <= in2->wlen) ? in1 : in2;  in _nn_mul_redc1()
156 	ret = nn_set_wlen(out, p->wlen); EG(ret, err);  in _nn_mul_redc1()
158 	len = out->wlen;  in _nn_mul_redc1()
159 	len_mul = b->wlen;  in _nn_mul_redc1()
164 	MUST_HAVE(((WORD_BITS * (out->wlen + 1)) <= NN_MAX_BIT_LEN), ret, err);  in _nn_mul_redc1()
165 	old_wlen = out->wlen;  in _nn_mul_redc1()
166 	out->wlen = (u8)(out->wlen + 1);  in _nn_mul_redc1()
172 	for (i = 0; i < out->wlen; i++) {  in _nn_mul_redc1()
173 		out->val[i] = 0;  in _nn_mul_redc1()
178 			WORD_MUL(prod_high, prod_low, a->val[i], b->val[j]);  in _nn_mul_redc1()
181 			out->val[j] = (word_t)(out->val[j] + prod_low);  in _nn_mul_redc1()
182 			carry = (word_t)(prod_high + (out->val[j] < prod_low));  in _nn_mul_redc1()
185 			out->val[j] = (word_t)(out->val[j] + carry);  in _nn_mul_redc1()
186 			carry = (word_t)(out->val[j] < carry);  in _nn_mul_redc1()
188 		out->val[j] = (word_t)(out->val[j] + carry);  in _nn_mul_redc1()
189 		acc = (word_t)(out->val[j] < carry);  in _nn_mul_redc1()
191 		m = (word_t)(out->val[0] * mpinv);  in _nn_mul_redc1()
192 		WORD_MUL(prod_high, prod_low, m, p->val[0]);  in _nn_mul_redc1()
193 		prod_low = (word_t)(prod_low + out->val[0]);  in _nn_mul_redc1()
194 		carry = (word_t)(prod_high + (prod_low < out->val[0]));  in _nn_mul_redc1()
196 			WORD_MUL(prod_high, prod_low, m, p->val[j]);  in _nn_mul_redc1()
199 			out->val[j - 1] = (word_t)(prod_low + out->val[j]);  in _nn_mul_redc1()
200 			carry = (word_t)(prod_high + (out->val[j - 1] < prod_low));  in _nn_mul_redc1()
202 		out->val[j - 1] = (word_t)(carry + out->val[j]);  in _nn_mul_redc1()
203 		carry = (word_t)(out->val[j - 1] < out->val[j]);  in _nn_mul_redc1()
204 		out->val[j] = (word_t)(acc + carry);  in _nn_mul_redc1()
214 	out->wlen = old_wlen;  in _nn_mul_redc1()
225 ATTRIBUTE_WARN_UNUSED_RET static int _nn_mul_redc1_aliased(nn_t out, nn_src_t in1, nn_src_t in2,  in _nn_mul_redc1_aliased()  argument
232 	ret = _nn_mul_redc1(&out_cpy, in1, in2, p, mpinv); EG(ret, err);  in _nn_mul_redc1_aliased()
246 int nn_mul_redc1(nn_t out, nn_src_t in1, nn_src_t in2, nn_src_t p,  in nn_mul_redc1()  argument
252 	ret = nn_check_initialized(in2); EG(ret, err);  in nn_mul_redc1()
256 	if ((out == in1) || (out == in2) || (out == p)) {  in nn_mul_redc1()
257 		ret = _nn_mul_redc1_aliased(out, in1, in2, p, mpinv);  in nn_mul_redc1()
259 		ret = _nn_mul_redc1(out, in1, in2, p, mpinv);  in nn_mul_redc1()
267  * Compute in1 * in2 mod p where in1 and in2 are numbers < p.
268  * When p is an odd number, the function redcifies in1 and in2
276  *   nn_mul(&tmp2, in1, in2);
284  * The function returns 0 on success, -1 on error.
286 int nn_mod_mul(nn_t out, nn_src_t in1, nn_src_t in2, nn_src_t p_in)  in nn_mod_mul()  argument
298 		ret = nn_mul(out, in1, in2); EG(ret, err);  in nn_mod_mul()
320 		/* redcify in1 and in2 */  in nn_mod_mul()
322 		ret = nn_mul_redc1(&in2_tmp, in2, &r_square, &p, mpinv); EG(ret, err);  in nn_mod_mul()
324 		/* Compute in1 * in2 mod p in montgomery world.  in nn_mod_mul()