xref: /illumos-gate/usr/src/common/crypto/ecc/ecl_gf.c (revision 55fea89dcaa64928bed4327112404dcb3e07b79f)
1 /*
2  * ***** BEGIN LICENSE BLOCK *****
3  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
4  *
5  * The contents of this file are subject to the Mozilla Public License Version
6  * 1.1 (the "License"); you may not use this file except in compliance with
7  * the License. You may obtain a copy of the License at
8  * http://www.mozilla.org/MPL/
9  *
10  * Software distributed under the License is distributed on an "AS IS" basis,
11  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
12  * for the specific language governing rights and limitations under the
13  * License.
14  *
15  * The Original Code is the elliptic curve math library.
16  *
17  * The Initial Developer of the Original Code is
18  * Sun Microsystems, Inc.
19  * Portions created by the Initial Developer are Copyright (C) 2003
20  * the Initial Developer. All Rights Reserved.
21  *
22  * Contributor(s):
23  *   Stephen Fung <fungstep@hotmail.com> and
24  *   Douglas Stebila <douglas@stebila.ca>, Sun Microsystems Laboratories
25  *
26  * Alternatively, the contents of this file may be used under the terms of
27  * either the GNU General Public License Version 2 or later (the "GPL"), or
28  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
29  * in which case the provisions of the GPL or the LGPL are applicable instead
30  * of those above. If you wish to allow use of your version of this file only
31  * under the terms of either the GPL or the LGPL, and not to allow others to
32  * use your version of this file under the terms of the MPL, indicate your
33  * decision by deleting the provisions above and replace them with the notice
34  * and other provisions required by the GPL or the LGPL. If you do not delete
35  * the provisions above, a recipient may use your version of this file under
36  * the terms of any one of the MPL, the GPL or the LGPL.
37  *
38  * ***** END LICENSE BLOCK ***** */
39 /*
40  * Copyright 2007 Sun Microsystems, Inc.  All rights reserved.
41  * Use is subject to license terms.
42  *
43  * Sun elects to use this software under the MPL license.
44  */
45 
46 #include "mpi.h"
47 #include "mp_gf2m.h"
48 #include "ecl-priv.h"
49 #include "mpi-priv.h"
50 #ifndef _KERNEL
51 #include <stdlib.h>
52 #endif
53 
54 /* Allocate memory for a new GFMethod object. */
55 GFMethod *
GFMethod_new(int kmflag)56 GFMethod_new(int kmflag)
57 {
58 	mp_err res = MP_OKAY;
59 	GFMethod *meth;
60 #ifdef _KERNEL
61 	meth = (GFMethod *) kmem_alloc(sizeof(GFMethod), kmflag);
62 #else
63 	meth = (GFMethod *) malloc(sizeof(GFMethod));
64 	if (meth == NULL)
65 		return NULL;
66 #endif
67 	meth->constructed = MP_YES;
68 	MP_DIGITS(&meth->irr) = 0;
69 	meth->extra_free = NULL;
70 	MP_CHECKOK(mp_init(&meth->irr, kmflag));
71 
72   CLEANUP:
73 	if (res != MP_OKAY) {
74 		GFMethod_free(meth);
75 		return NULL;
76 	}
77 	return meth;
78 }
79 
80 /* Construct a generic GFMethod for arithmetic over prime fields with
81  * irreducible irr. */
82 GFMethod *
GFMethod_consGFp(const mp_int * irr)83 GFMethod_consGFp(const mp_int *irr)
84 {
85 	mp_err res = MP_OKAY;
86 	GFMethod *meth = NULL;
87 
88 	meth = GFMethod_new(FLAG(irr));
89 	if (meth == NULL)
90 		return NULL;
91 
92 	MP_CHECKOK(mp_copy(irr, &meth->irr));
93 	meth->irr_arr[0] = mpl_significant_bits(irr);
94 	meth->irr_arr[1] = meth->irr_arr[2] = meth->irr_arr[3] =
95 		meth->irr_arr[4] = 0;
96 	switch(MP_USED(&meth->irr)) {
97 	/* maybe we need 1 and 2 words here as well?*/
98 	case 3:
99 		meth->field_add = &ec_GFp_add_3;
100 		meth->field_sub = &ec_GFp_sub_3;
101 		break;
102 	case 4:
103 		meth->field_add = &ec_GFp_add_4;
104 		meth->field_sub = &ec_GFp_sub_4;
105 		break;
106 	case 5:
107 		meth->field_add = &ec_GFp_add_5;
108 		meth->field_sub = &ec_GFp_sub_5;
109 		break;
110 	case 6:
111 		meth->field_add = &ec_GFp_add_6;
112 		meth->field_sub = &ec_GFp_sub_6;
113 		break;
114 	default:
115 		meth->field_add = &ec_GFp_add;
116 		meth->field_sub = &ec_GFp_sub;
117 	}
118 	meth->field_neg = &ec_GFp_neg;
119 	meth->field_mod = &ec_GFp_mod;
120 	meth->field_mul = &ec_GFp_mul;
121 	meth->field_sqr = &ec_GFp_sqr;
122 	meth->field_div = &ec_GFp_div;
123 	meth->field_enc = NULL;
124 	meth->field_dec = NULL;
125 	meth->extra1 = NULL;
126 	meth->extra2 = NULL;
127 	meth->extra_free = NULL;
128 
129   CLEANUP:
130 	if (res != MP_OKAY) {
131 		GFMethod_free(meth);
132 		return NULL;
133 	}
134 	return meth;
135 }
136 
137 /* Construct a generic GFMethod for arithmetic over binary polynomial
138  * fields with irreducible irr that has array representation irr_arr (see
139  * ecl-priv.h for description of the representation).  If irr_arr is NULL,
140  * then it is constructed from the bitstring representation. */
141 GFMethod *
GFMethod_consGF2m(const mp_int * irr,const unsigned int irr_arr[5])142 GFMethod_consGF2m(const mp_int *irr, const unsigned int irr_arr[5])
143 {
144 	mp_err res = MP_OKAY;
145 	int ret;
146 	GFMethod *meth = NULL;
147 
148 	meth = GFMethod_new(FLAG(irr));
149 	if (meth == NULL)
150 		return NULL;
151 
152 	MP_CHECKOK(mp_copy(irr, &meth->irr));
153 	if (irr_arr != NULL) {
154 		/* Irreducible polynomials are either trinomials or pentanomials. */
155 		meth->irr_arr[0] = irr_arr[0];
156 		meth->irr_arr[1] = irr_arr[1];
157 		meth->irr_arr[2] = irr_arr[2];
158 		if (irr_arr[2] > 0) {
159 			meth->irr_arr[3] = irr_arr[3];
160 			meth->irr_arr[4] = irr_arr[4];
161 		} else {
162 			meth->irr_arr[3] = meth->irr_arr[4] = 0;
163 		}
164 	} else {
165 		ret = mp_bpoly2arr(irr, meth->irr_arr, 5);
166 		/* Irreducible polynomials are either trinomials or pentanomials. */
167 		if ((ret != 5) && (ret != 3)) {
168 			res = MP_UNDEF;
169 			goto CLEANUP;
170 		}
171 	}
172 	meth->field_add = &ec_GF2m_add;
173 	meth->field_neg = &ec_GF2m_neg;
174 	meth->field_sub = &ec_GF2m_add;
175 	meth->field_mod = &ec_GF2m_mod;
176 	meth->field_mul = &ec_GF2m_mul;
177 	meth->field_sqr = &ec_GF2m_sqr;
178 	meth->field_div = &ec_GF2m_div;
179 	meth->field_enc = NULL;
180 	meth->field_dec = NULL;
181 	meth->extra1 = NULL;
182 	meth->extra2 = NULL;
183 	meth->extra_free = NULL;
184 
185   CLEANUP:
186 	if (res != MP_OKAY) {
187 		GFMethod_free(meth);
188 		return NULL;
189 	}
190 	return meth;
191 }
192 
193 /* Free the memory allocated (if any) to a GFMethod object. */
194 void
GFMethod_free(GFMethod * meth)195 GFMethod_free(GFMethod *meth)
196 {
197 	if (meth == NULL)
198 		return;
199 	if (meth->constructed == MP_NO)
200 		return;
201 	mp_clear(&meth->irr);
202 	if (meth->extra_free != NULL)
203 		meth->extra_free(meth);
204 #ifdef _KERNEL
205 	kmem_free(meth, sizeof(GFMethod));
206 #else
207 	free(meth);
208 #endif
209 }
210 
211 /* Wrapper functions for generic prime field arithmetic. */
212 
213 /* Add two field elements.  Assumes that 0 <= a, b < meth->irr */
214 mp_err
ec_GFp_add(const mp_int * a,const mp_int * b,mp_int * r,const GFMethod * meth)215 ec_GFp_add(const mp_int *a, const mp_int *b, mp_int *r,
216 		   const GFMethod *meth)
217 {
218 	/* PRE: 0 <= a, b < p = meth->irr POST: 0 <= r < p, r = a + b (mod p) */
219 	mp_err res;
220 
221 	if ((res = mp_add(a, b, r)) != MP_OKAY) {
222 		return res;
223 	}
224 	if (mp_cmp(r, &meth->irr) >= 0) {
225 		return mp_sub(r, &meth->irr, r);
226 	}
227 	return res;
228 }
229 
230 /* Negates a field element.  Assumes that 0 <= a < meth->irr */
231 mp_err
ec_GFp_neg(const mp_int * a,mp_int * r,const GFMethod * meth)232 ec_GFp_neg(const mp_int *a, mp_int *r, const GFMethod *meth)
233 {
234 	/* PRE: 0 <= a < p = meth->irr POST: 0 <= r < p, r = -a (mod p) */
235 
236 	if (mp_cmp_z(a) == 0) {
237 		mp_zero(r);
238 		return MP_OKAY;
239 	}
240 	return mp_sub(&meth->irr, a, r);
241 }
242 
243 /* Subtracts two field elements.  Assumes that 0 <= a, b < meth->irr */
244 mp_err
ec_GFp_sub(const mp_int * a,const mp_int * b,mp_int * r,const GFMethod * meth)245 ec_GFp_sub(const mp_int *a, const mp_int *b, mp_int *r,
246 		   const GFMethod *meth)
247 {
248 	mp_err res = MP_OKAY;
249 
250 	/* PRE: 0 <= a, b < p = meth->irr POST: 0 <= r < p, r = a - b (mod p) */
251 	res = mp_sub(a, b, r);
252 	if (res == MP_RANGE) {
253 		MP_CHECKOK(mp_sub(b, a, r));
254 		if (mp_cmp_z(r) < 0) {
255 			MP_CHECKOK(mp_add(r, &meth->irr, r));
256 		}
257 		MP_CHECKOK(ec_GFp_neg(r, r, meth));
258 	}
259 	if (mp_cmp_z(r) < 0) {
260 		MP_CHECKOK(mp_add(r, &meth->irr, r));
261 	}
262   CLEANUP:
263 	return res;
264 }
265 /*
266  * Inline adds for small curve lengths.
267  */
268 /* 3 words */
269 mp_err
ec_GFp_add_3(const mp_int * a,const mp_int * b,mp_int * r,const GFMethod * meth)270 ec_GFp_add_3(const mp_int *a, const mp_int *b, mp_int *r,
271 			const GFMethod *meth)
272 {
273 	mp_err res = MP_OKAY;
274 	mp_digit a0 = 0, a1 = 0, a2 = 0;
275 	mp_digit r0 = 0, r1 = 0, r2 = 0;
276 	mp_digit carry;
277 
278 	switch(MP_USED(a)) {
279 	case 3:
280 		a2 = MP_DIGIT(a,2);
281 		/* FALLTHROUGH */
282 	case 2:
283 		a1 = MP_DIGIT(a,1);
284 		/* FALLTHROUGH */
285 	case 1:
286 		a0 = MP_DIGIT(a,0);
287 	}
288 	switch(MP_USED(b)) {
289 	case 3:
290 		r2 = MP_DIGIT(b,2);
291 		/* FALLTHROUGH */
292 	case 2:
293 		r1 = MP_DIGIT(b,1);
294 		/* FALLTHROUGH */
295 	case 1:
296 		r0 = MP_DIGIT(b,0);
297 	}
298 
299 #ifndef MPI_AMD64_ADD
300 	MP_ADD_CARRY(a0, r0, r0, 0,     carry);
301 	MP_ADD_CARRY(a1, r1, r1, carry, carry);
302 	MP_ADD_CARRY(a2, r2, r2, carry, carry);
303 #else
304 	__asm__ (
305                 "xorq   %3,%3           \n\t"
306                 "addq   %4,%0           \n\t"
307                 "adcq   %5,%1           \n\t"
308                 "adcq   %6,%2           \n\t"
309                 "adcq   $0,%3           \n\t"
310                 : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(carry)
311                 : "r" (a0), "r" (a1), "r" (a2),
312 		  "0" (r0), "1" (r1), "2" (r2)
313                 : "%cc" );
314 #endif
315 
316 	MP_CHECKOK(s_mp_pad(r, 3));
317 	MP_DIGIT(r, 2) = r2;
318 	MP_DIGIT(r, 1) = r1;
319 	MP_DIGIT(r, 0) = r0;
320 	MP_SIGN(r) = MP_ZPOS;
321 	MP_USED(r) = 3;
322 
323 	/* Do quick 'subract' if we've gone over
324 	 * (add the 2's complement of the curve field) */
325 	 a2 = MP_DIGIT(&meth->irr,2);
326 	if (carry ||  r2 >  a2 ||
327 		((r2 == a2) && mp_cmp(r,&meth->irr) != MP_LT)) {
328 		a1 = MP_DIGIT(&meth->irr,1);
329 		a0 = MP_DIGIT(&meth->irr,0);
330 #ifndef MPI_AMD64_ADD
331 		MP_SUB_BORROW(r0, a0, r0, 0,     carry);
332 		MP_SUB_BORROW(r1, a1, r1, carry, carry);
333 		MP_SUB_BORROW(r2, a2, r2, carry, carry);
334 #else
335 		__asm__ (
336 			"subq   %3,%0           \n\t"
337 			"sbbq   %4,%1           \n\t"
338 			"sbbq   %5,%2           \n\t"
339 			: "=r"(r0), "=r"(r1), "=r"(r2)
340 			: "r" (a0), "r" (a1), "r" (a2),
341 			  "0" (r0), "1" (r1), "2" (r2)
342 			: "%cc" );
343 #endif
344 		MP_DIGIT(r, 2) = r2;
345 		MP_DIGIT(r, 1) = r1;
346 		MP_DIGIT(r, 0) = r0;
347 	}
348 
349 	s_mp_clamp(r);
350 
351   CLEANUP:
352 	return res;
353 }
354 
355 /* 4 words */
356 mp_err
ec_GFp_add_4(const mp_int * a,const mp_int * b,mp_int * r,const GFMethod * meth)357 ec_GFp_add_4(const mp_int *a, const mp_int *b, mp_int *r,
358 			const GFMethod *meth)
359 {
360 	mp_err res = MP_OKAY;
361 	mp_digit a0 = 0, a1 = 0, a2 = 0, a3 = 0;
362 	mp_digit r0 = 0, r1 = 0, r2 = 0, r3 = 0;
363 	mp_digit carry;
364 
365 	switch(MP_USED(a)) {
366 	case 4:
367 		a3 = MP_DIGIT(a,3);
368 		/* FALLTHROUGH */
369 	case 3:
370 		a2 = MP_DIGIT(a,2);
371 		/* FALLTHROUGH */
372 	case 2:
373 		a1 = MP_DIGIT(a,1);
374 		/* FALLTHROUGH */
375 	case 1:
376 		a0 = MP_DIGIT(a,0);
377 	}
378 	switch(MP_USED(b)) {
379 	case 4:
380 		r3 = MP_DIGIT(b,3);
381 		/* FALLTHROUGH */
382 	case 3:
383 		r2 = MP_DIGIT(b,2);
384 		/* FALLTHROUGH */
385 	case 2:
386 		r1 = MP_DIGIT(b,1);
387 		/* FALLTHROUGH */
388 	case 1:
389 		r0 = MP_DIGIT(b,0);
390 	}
391 
392 #ifndef MPI_AMD64_ADD
393 	MP_ADD_CARRY(a0, r0, r0, 0,     carry);
394 	MP_ADD_CARRY(a1, r1, r1, carry, carry);
395 	MP_ADD_CARRY(a2, r2, r2, carry, carry);
396 	MP_ADD_CARRY(a3, r3, r3, carry, carry);
397 #else
398 	__asm__ (
399                 "xorq   %4,%4           \n\t"
400                 "addq   %5,%0           \n\t"
401                 "adcq   %6,%1           \n\t"
402                 "adcq   %7,%2           \n\t"
403                 "adcq   %8,%3           \n\t"
404                 "adcq   $0,%4           \n\t"
405                 : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(r3), "=r"(carry)
406                 : "r" (a0), "r" (a1), "r" (a2), "r" (a3),
407 		  "0" (r0), "1" (r1), "2" (r2), "3" (r3)
408                 : "%cc" );
409 #endif
410 
411 	MP_CHECKOK(s_mp_pad(r, 4));
412 	MP_DIGIT(r, 3) = r3;
413 	MP_DIGIT(r, 2) = r2;
414 	MP_DIGIT(r, 1) = r1;
415 	MP_DIGIT(r, 0) = r0;
416 	MP_SIGN(r) = MP_ZPOS;
417 	MP_USED(r) = 4;
418 
419 	/* Do quick 'subract' if we've gone over
420 	 * (add the 2's complement of the curve field) */
421 	 a3 = MP_DIGIT(&meth->irr,3);
422 	if (carry ||  r3 >  a3 ||
423 		((r3 == a3) && mp_cmp(r,&meth->irr) != MP_LT)) {
424 		a2 = MP_DIGIT(&meth->irr,2);
425 		a1 = MP_DIGIT(&meth->irr,1);
426 		a0 = MP_DIGIT(&meth->irr,0);
427 #ifndef MPI_AMD64_ADD
428 		MP_SUB_BORROW(r0, a0, r0, 0,     carry);
429 		MP_SUB_BORROW(r1, a1, r1, carry, carry);
430 		MP_SUB_BORROW(r2, a2, r2, carry, carry);
431 		MP_SUB_BORROW(r3, a3, r3, carry, carry);
432 #else
433 		__asm__ (
434 			"subq   %4,%0           \n\t"
435 			"sbbq   %5,%1           \n\t"
436 			"sbbq   %6,%2           \n\t"
437 			"sbbq   %7,%3           \n\t"
438 			: "=r"(r0), "=r"(r1), "=r"(r2), "=r"(r3)
439 			: "r" (a0), "r" (a1), "r" (a2), "r" (a3),
440 			  "0" (r0), "1" (r1), "2" (r2), "3" (r3)
441 			: "%cc" );
442 #endif
443 		MP_DIGIT(r, 3) = r3;
444 		MP_DIGIT(r, 2) = r2;
445 		MP_DIGIT(r, 1) = r1;
446 		MP_DIGIT(r, 0) = r0;
447 	}
448 
449 	s_mp_clamp(r);
450 
451   CLEANUP:
452 	return res;
453 }
454 
455 /* 5 words */
456 mp_err
ec_GFp_add_5(const mp_int * a,const mp_int * b,mp_int * r,const GFMethod * meth)457 ec_GFp_add_5(const mp_int *a, const mp_int *b, mp_int *r,
458 			const GFMethod *meth)
459 {
460 	mp_err res = MP_OKAY;
461 	mp_digit a0 = 0, a1 = 0, a2 = 0, a3 = 0, a4 = 0;
462 	mp_digit r0 = 0, r1 = 0, r2 = 0, r3 = 0, r4 = 0;
463 	mp_digit carry;
464 
465 	switch(MP_USED(a)) {
466 	case 5:
467 		a4 = MP_DIGIT(a,4);
468 		/* FALLTHROUGH */
469 	case 4:
470 		a3 = MP_DIGIT(a,3);
471 		/* FALLTHROUGH */
472 	case 3:
473 		a2 = MP_DIGIT(a,2);
474 		/* FALLTHROUGH */
475 	case 2:
476 		a1 = MP_DIGIT(a,1);
477 		/* FALLTHROUGH */
478 	case 1:
479 		a0 = MP_DIGIT(a,0);
480 	}
481 	switch(MP_USED(b)) {
482 	case 5:
483 		r4 = MP_DIGIT(b,4);
484 		/* FALLTHROUGH */
485 	case 4:
486 		r3 = MP_DIGIT(b,3);
487 		/* FALLTHROUGH */
488 	case 3:
489 		r2 = MP_DIGIT(b,2);
490 		/* FALLTHROUGH */
491 	case 2:
492 		r1 = MP_DIGIT(b,1);
493 		/* FALLTHROUGH */
494 	case 1:
495 		r0 = MP_DIGIT(b,0);
496 	}
497 
498 	MP_ADD_CARRY(a0, r0, r0, 0,     carry);
499 	MP_ADD_CARRY(a1, r1, r1, carry, carry);
500 	MP_ADD_CARRY(a2, r2, r2, carry, carry);
501 	MP_ADD_CARRY(a3, r3, r3, carry, carry);
502 	MP_ADD_CARRY(a4, r4, r4, carry, carry);
503 
504 	MP_CHECKOK(s_mp_pad(r, 5));
505 	MP_DIGIT(r, 4) = r4;
506 	MP_DIGIT(r, 3) = r3;
507 	MP_DIGIT(r, 2) = r2;
508 	MP_DIGIT(r, 1) = r1;
509 	MP_DIGIT(r, 0) = r0;
510 	MP_SIGN(r) = MP_ZPOS;
511 	MP_USED(r) = 5;
512 
513 	/* Do quick 'subract' if we've gone over
514 	 * (add the 2's complement of the curve field) */
515 	 a4 = MP_DIGIT(&meth->irr,4);
516 	if (carry ||  r4 >  a4 ||
517 		((r4 == a4) && mp_cmp(r,&meth->irr) != MP_LT)) {
518 		a3 = MP_DIGIT(&meth->irr,3);
519 		a2 = MP_DIGIT(&meth->irr,2);
520 		a1 = MP_DIGIT(&meth->irr,1);
521 		a0 = MP_DIGIT(&meth->irr,0);
522 		MP_SUB_BORROW(r0, a0, r0, 0,     carry);
523 		MP_SUB_BORROW(r1, a1, r1, carry, carry);
524 		MP_SUB_BORROW(r2, a2, r2, carry, carry);
525 		MP_SUB_BORROW(r3, a3, r3, carry, carry);
526 		MP_SUB_BORROW(r4, a4, r4, carry, carry);
527 		MP_DIGIT(r, 4) = r4;
528 		MP_DIGIT(r, 3) = r3;
529 		MP_DIGIT(r, 2) = r2;
530 		MP_DIGIT(r, 1) = r1;
531 		MP_DIGIT(r, 0) = r0;
532 	}
533 
534 	s_mp_clamp(r);
535 
536   CLEANUP:
537 	return res;
538 }
539 
540 /* 6 words */
541 mp_err
ec_GFp_add_6(const mp_int * a,const mp_int * b,mp_int * r,const GFMethod * meth)542 ec_GFp_add_6(const mp_int *a, const mp_int *b, mp_int *r,
543 			const GFMethod *meth)
544 {
545 	mp_err res = MP_OKAY;
546 	mp_digit a0 = 0, a1 = 0, a2 = 0, a3 = 0, a4 = 0, a5 = 0;
547 	mp_digit r0 = 0, r1 = 0, r2 = 0, r3 = 0, r4 = 0, r5 = 0;
548 	mp_digit carry;
549 
550 	switch(MP_USED(a)) {
551 	case 6:
552 		a5 = MP_DIGIT(a,5);
553 		/* FALLTHROUGH */
554 	case 5:
555 		a4 = MP_DIGIT(a,4);
556 		/* FALLTHROUGH */
557 	case 4:
558 		a3 = MP_DIGIT(a,3);
559 		/* FALLTHROUGH */
560 	case 3:
561 		a2 = MP_DIGIT(a,2);
562 		/* FALLTHROUGH */
563 	case 2:
564 		a1 = MP_DIGIT(a,1);
565 		/* FALLTHROUGH */
566 	case 1:
567 		a0 = MP_DIGIT(a,0);
568 	}
569 	switch(MP_USED(b)) {
570 	case 6:
571 		r5 = MP_DIGIT(b,5);
572 		/* FALLTHROUGH */
573 	case 5:
574 		r4 = MP_DIGIT(b,4);
575 		/* FALLTHROUGH */
576 	case 4:
577 		r3 = MP_DIGIT(b,3);
578 		/* FALLTHROUGH */
579 	case 3:
580 		r2 = MP_DIGIT(b,2);
581 		/* FALLTHROUGH */
582 	case 2:
583 		r1 = MP_DIGIT(b,1);
584 		/* FALLTHROUGH */
585 	case 1:
586 		r0 = MP_DIGIT(b,0);
587 	}
588 
589 	MP_ADD_CARRY(a0, r0, r0, 0,     carry);
590 	MP_ADD_CARRY(a1, r1, r1, carry, carry);
591 	MP_ADD_CARRY(a2, r2, r2, carry, carry);
592 	MP_ADD_CARRY(a3, r3, r3, carry, carry);
593 	MP_ADD_CARRY(a4, r4, r4, carry, carry);
594 	MP_ADD_CARRY(a5, r5, r5, carry, carry);
595 
596 	MP_CHECKOK(s_mp_pad(r, 6));
597 	MP_DIGIT(r, 5) = r5;
598 	MP_DIGIT(r, 4) = r4;
599 	MP_DIGIT(r, 3) = r3;
600 	MP_DIGIT(r, 2) = r2;
601 	MP_DIGIT(r, 1) = r1;
602 	MP_DIGIT(r, 0) = r0;
603 	MP_SIGN(r) = MP_ZPOS;
604 	MP_USED(r) = 6;
605 
606 	/* Do quick 'subract' if we've gone over
607 	 * (add the 2's complement of the curve field) */
608 	a5 = MP_DIGIT(&meth->irr,5);
609 	if (carry ||  r5 >  a5 ||
610 		((r5 == a5) && mp_cmp(r,&meth->irr) != MP_LT)) {
611 		a4 = MP_DIGIT(&meth->irr,4);
612 		a3 = MP_DIGIT(&meth->irr,3);
613 		a2 = MP_DIGIT(&meth->irr,2);
614 		a1 = MP_DIGIT(&meth->irr,1);
615 		a0 = MP_DIGIT(&meth->irr,0);
616 		MP_SUB_BORROW(r0, a0, r0, 0,     carry);
617 		MP_SUB_BORROW(r1, a1, r1, carry, carry);
618 		MP_SUB_BORROW(r2, a2, r2, carry, carry);
619 		MP_SUB_BORROW(r3, a3, r3, carry, carry);
620 		MP_SUB_BORROW(r4, a4, r4, carry, carry);
621 		MP_SUB_BORROW(r5, a5, r5, carry, carry);
622 		MP_DIGIT(r, 5) = r5;
623 		MP_DIGIT(r, 4) = r4;
624 		MP_DIGIT(r, 3) = r3;
625 		MP_DIGIT(r, 2) = r2;
626 		MP_DIGIT(r, 1) = r1;
627 		MP_DIGIT(r, 0) = r0;
628 	}
629 
630 	s_mp_clamp(r);
631 
632   CLEANUP:
633 	return res;
634 }
635 
636 /*
637  * The following subraction functions do in-line subractions based
638  * on our curve size.
639  *
640  * ... 3 words
641  */
642 mp_err
ec_GFp_sub_3(const mp_int * a,const mp_int * b,mp_int * r,const GFMethod * meth)643 ec_GFp_sub_3(const mp_int *a, const mp_int *b, mp_int *r,
644 			const GFMethod *meth)
645 {
646 	mp_err res = MP_OKAY;
647 	mp_digit b0 = 0, b1 = 0, b2 = 0;
648 	mp_digit r0 = 0, r1 = 0, r2 = 0;
649 	mp_digit borrow;
650 
651 	switch(MP_USED(a)) {
652 	case 3:
653 		r2 = MP_DIGIT(a,2);
654 		/* FALLTHROUGH */
655 	case 2:
656 		r1 = MP_DIGIT(a,1);
657 		/* FALLTHROUGH */
658 	case 1:
659 		r0 = MP_DIGIT(a,0);
660 	}
661 	switch(MP_USED(b)) {
662 	case 3:
663 		b2 = MP_DIGIT(b,2);
664 		/* FALLTHROUGH */
665 	case 2:
666 		b1 = MP_DIGIT(b,1);
667 		/* FALLTHROUGH */
668 	case 1:
669 		b0 = MP_DIGIT(b,0);
670 	}
671 
672 #ifndef MPI_AMD64_ADD
673 	MP_SUB_BORROW(r0, b0, r0, 0,     borrow);
674 	MP_SUB_BORROW(r1, b1, r1, borrow, borrow);
675 	MP_SUB_BORROW(r2, b2, r2, borrow, borrow);
676 #else
677 	__asm__ (
678                 "xorq   %3,%3           \n\t"
679                 "subq   %4,%0           \n\t"
680                 "sbbq   %5,%1           \n\t"
681                 "sbbq   %6,%2           \n\t"
682                 "adcq   $0,%3           \n\t"
683                 : "=r"(r0), "=r"(r1), "=r"(r2), "=r" (borrow)
684                 : "r" (b0), "r" (b1), "r" (b2),
685 		  "0" (r0), "1" (r1), "2" (r2)
686                 : "%cc" );
687 #endif
688 
689 	/* Do quick 'add' if we've gone under 0
690 	 * (subtract the 2's complement of the curve field) */
691 	if (borrow) {
692 	 	b2 = MP_DIGIT(&meth->irr,2);
693 		b1 = MP_DIGIT(&meth->irr,1);
694 		b0 = MP_DIGIT(&meth->irr,0);
695 #ifndef MPI_AMD64_ADD
696 		MP_ADD_CARRY(b0, r0, r0, 0,      borrow);
697 		MP_ADD_CARRY(b1, r1, r1, borrow, borrow);
698 		MP_ADD_CARRY(b2, r2, r2, borrow, borrow);
699 #else
700 		__asm__ (
701 			"addq   %3,%0           \n\t"
702 			"adcq   %4,%1           \n\t"
703 			"adcq   %5,%2           \n\t"
704 			: "=r"(r0), "=r"(r1), "=r"(r2)
705 			: "r" (b0), "r" (b1), "r" (b2),
706   			  "0" (r0), "1" (r1), "2" (r2)
707 			: "%cc" );
708 #endif
709 	}
710 
711 #ifdef MPI_AMD64_ADD
712 	/* compiler fakeout? */
713 	if ((r2 == b0) && (r1 == b0) && (r0 == b0)) {
714 		MP_CHECKOK(s_mp_pad(r, 4));
715 	}
716 #endif
717 	MP_CHECKOK(s_mp_pad(r, 3));
718 	MP_DIGIT(r, 2) = r2;
719 	MP_DIGIT(r, 1) = r1;
720 	MP_DIGIT(r, 0) = r0;
721 	MP_SIGN(r) = MP_ZPOS;
722 	MP_USED(r) = 3;
723 	s_mp_clamp(r);
724 
725   CLEANUP:
726 	return res;
727 }
728 
729 /* 4 words */
730 mp_err
ec_GFp_sub_4(const mp_int * a,const mp_int * b,mp_int * r,const GFMethod * meth)731 ec_GFp_sub_4(const mp_int *a, const mp_int *b, mp_int *r,
732 			const GFMethod *meth)
733 {
734 	mp_err res = MP_OKAY;
735 	mp_digit b0 = 0, b1 = 0, b2 = 0, b3 = 0;
736 	mp_digit r0 = 0, r1 = 0, r2 = 0, r3 = 0;
737 	mp_digit borrow;
738 
739 	switch(MP_USED(a)) {
740 	case 4:
741 		r3 = MP_DIGIT(a,3);
742 		/* FALLTHROUGH */
743 	case 3:
744 		r2 = MP_DIGIT(a,2);
745 		/* FALLTHROUGH */
746 	case 2:
747 		r1 = MP_DIGIT(a,1);
748 		/* FALLTHROUGH */
749 	case 1:
750 		r0 = MP_DIGIT(a,0);
751 	}
752 	switch(MP_USED(b)) {
753 	case 4:
754 		b3 = MP_DIGIT(b,3);
755 		/* FALLTHROUGH */
756 	case 3:
757 		b2 = MP_DIGIT(b,2);
758 		/* FALLTHROUGH */
759 	case 2:
760 		b1 = MP_DIGIT(b,1);
761 		/* FALLTHROUGH */
762 	case 1:
763 		b0 = MP_DIGIT(b,0);
764 	}
765 
766 #ifndef MPI_AMD64_ADD
767 	MP_SUB_BORROW(r0, b0, r0, 0,     borrow);
768 	MP_SUB_BORROW(r1, b1, r1, borrow, borrow);
769 	MP_SUB_BORROW(r2, b2, r2, borrow, borrow);
770 	MP_SUB_BORROW(r3, b3, r3, borrow, borrow);
771 #else
772 	__asm__ (
773                 "xorq   %4,%4           \n\t"
774                 "subq   %5,%0           \n\t"
775                 "sbbq   %6,%1           \n\t"
776                 "sbbq   %7,%2           \n\t"
777                 "sbbq   %8,%3           \n\t"
778                 "adcq   $0,%4           \n\t"
779                 : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(r3), "=r" (borrow)
780                 : "r" (b0), "r" (b1), "r" (b2), "r" (b3),
781 		  "0" (r0), "1" (r1), "2" (r2), "3" (r3)
782                 : "%cc" );
783 #endif
784 
785 	/* Do quick 'add' if we've gone under 0
786 	 * (subtract the 2's complement of the curve field) */
787 	if (borrow) {
788 	 	b3 = MP_DIGIT(&meth->irr,3);
789 	 	b2 = MP_DIGIT(&meth->irr,2);
790 		b1 = MP_DIGIT(&meth->irr,1);
791 		b0 = MP_DIGIT(&meth->irr,0);
792 #ifndef MPI_AMD64_ADD
793 		MP_ADD_CARRY(b0, r0, r0, 0,      borrow);
794 		MP_ADD_CARRY(b1, r1, r1, borrow, borrow);
795 		MP_ADD_CARRY(b2, r2, r2, borrow, borrow);
796 		MP_ADD_CARRY(b3, r3, r3, borrow, borrow);
797 #else
798 		__asm__ (
799 			"addq   %4,%0           \n\t"
800 			"adcq   %5,%1           \n\t"
801 			"adcq   %6,%2           \n\t"
802 			"adcq   %7,%3           \n\t"
803 			: "=r"(r0), "=r"(r1), "=r"(r2), "=r"(r3)
804 			: "r" (b0), "r" (b1), "r" (b2), "r" (b3),
805   			  "0" (r0), "1" (r1), "2" (r2), "3" (r3)
806 			: "%cc" );
807 #endif
808 	}
809 #ifdef MPI_AMD64_ADD
810 	/* compiler fakeout? */
811 	if ((r3 == b0) && (r1 == b0) && (r0 == b0)) {
812 		MP_CHECKOK(s_mp_pad(r, 4));
813 	}
814 #endif
815 	MP_CHECKOK(s_mp_pad(r, 4));
816 	MP_DIGIT(r, 3) = r3;
817 	MP_DIGIT(r, 2) = r2;
818 	MP_DIGIT(r, 1) = r1;
819 	MP_DIGIT(r, 0) = r0;
820 	MP_SIGN(r) = MP_ZPOS;
821 	MP_USED(r) = 4;
822 	s_mp_clamp(r);
823 
824   CLEANUP:
825 	return res;
826 }
827 
828 /* 5 words */
829 mp_err
ec_GFp_sub_5(const mp_int * a,const mp_int * b,mp_int * r,const GFMethod * meth)830 ec_GFp_sub_5(const mp_int *a, const mp_int *b, mp_int *r,
831 			const GFMethod *meth)
832 {
833 	mp_err res = MP_OKAY;
834 	mp_digit b0 = 0, b1 = 0, b2 = 0, b3 = 0, b4 = 0;
835 	mp_digit r0 = 0, r1 = 0, r2 = 0, r3 = 0, r4 = 0;
836 	mp_digit borrow;
837 
838 	switch(MP_USED(a)) {
839 	case 5:
840 		r4 = MP_DIGIT(a,4);
841 		/* FALLTHROUGH */
842 	case 4:
843 		r3 = MP_DIGIT(a,3);
844 		/* FALLTHROUGH */
845 	case 3:
846 		r2 = MP_DIGIT(a,2);
847 		/* FALLTHROUGH */
848 	case 2:
849 		r1 = MP_DIGIT(a,1);
850 		/* FALLTHROUGH */
851 	case 1:
852 		r0 = MP_DIGIT(a,0);
853 	}
854 	switch(MP_USED(b)) {
855 	case 5:
856 		b4 = MP_DIGIT(b,4);
857 		/* FALLTHROUGH */
858 	case 4:
859 		b3 = MP_DIGIT(b,3);
860 		/* FALLTHROUGH */
861 	case 3:
862 		b2 = MP_DIGIT(b,2);
863 		/* FALLTHROUGH */
864 	case 2:
865 		b1 = MP_DIGIT(b,1);
866 		/* FALLTHROUGH */
867 	case 1:
868 		b0 = MP_DIGIT(b,0);
869 	}
870 
871 	MP_SUB_BORROW(r0, b0, r0, 0,     borrow);
872 	MP_SUB_BORROW(r1, b1, r1, borrow, borrow);
873 	MP_SUB_BORROW(r2, b2, r2, borrow, borrow);
874 	MP_SUB_BORROW(r3, b3, r3, borrow, borrow);
875 	MP_SUB_BORROW(r4, b4, r4, borrow, borrow);
876 
877 	/* Do quick 'add' if we've gone under 0
878 	 * (subtract the 2's complement of the curve field) */
879 	if (borrow) {
880 	 	b4 = MP_DIGIT(&meth->irr,4);
881 	 	b3 = MP_DIGIT(&meth->irr,3);
882 	 	b2 = MP_DIGIT(&meth->irr,2);
883 		b1 = MP_DIGIT(&meth->irr,1);
884 		b0 = MP_DIGIT(&meth->irr,0);
885 		MP_ADD_CARRY(b0, r0, r0, 0,      borrow);
886 		MP_ADD_CARRY(b1, r1, r1, borrow, borrow);
887 		MP_ADD_CARRY(b2, r2, r2, borrow, borrow);
888 		MP_ADD_CARRY(b3, r3, r3, borrow, borrow);
889 	}
890 	MP_CHECKOK(s_mp_pad(r, 5));
891 	MP_DIGIT(r, 4) = r4;
892 	MP_DIGIT(r, 3) = r3;
893 	MP_DIGIT(r, 2) = r2;
894 	MP_DIGIT(r, 1) = r1;
895 	MP_DIGIT(r, 0) = r0;
896 	MP_SIGN(r) = MP_ZPOS;
897 	MP_USED(r) = 5;
898 	s_mp_clamp(r);
899 
900   CLEANUP:
901 	return res;
902 }
903 
904 /* 6 words */
905 mp_err
ec_GFp_sub_6(const mp_int * a,const mp_int * b,mp_int * r,const GFMethod * meth)906 ec_GFp_sub_6(const mp_int *a, const mp_int *b, mp_int *r,
907 			const GFMethod *meth)
908 {
909 	mp_err res = MP_OKAY;
910 	mp_digit b0 = 0, b1 = 0, b2 = 0, b3 = 0, b4 = 0, b5 = 0;
911 	mp_digit r0 = 0, r1 = 0, r2 = 0, r3 = 0, r4 = 0, r5 = 0;
912 	mp_digit borrow;
913 
914 	switch(MP_USED(a)) {
915 	case 6:
916 		r5 = MP_DIGIT(a,5);
917 		/* FALLTHROUGH */
918 	case 5:
919 		r4 = MP_DIGIT(a,4);
920 		/* FALLTHROUGH */
921 	case 4:
922 		r3 = MP_DIGIT(a,3);
923 		/* FALLTHROUGH */
924 	case 3:
925 		r2 = MP_DIGIT(a,2);
926 		/* FALLTHROUGH */
927 	case 2:
928 		r1 = MP_DIGIT(a,1);
929 		/* FALLTHROUGH */
930 	case 1:
931 		r0 = MP_DIGIT(a,0);
932 	}
933 	switch(MP_USED(b)) {
934 	case 6:
935 		b5 = MP_DIGIT(b,5);
936 		/* FALLTHROUGH */
937 	case 5:
938 		b4 = MP_DIGIT(b,4);
939 		/* FALLTHROUGH */
940 	case 4:
941 		b3 = MP_DIGIT(b,3);
942 		/* FALLTHROUGH */
943 	case 3:
944 		b2 = MP_DIGIT(b,2);
945 		/* FALLTHROUGH */
946 	case 2:
947 		b1 = MP_DIGIT(b,1);
948 		/* FALLTHROUGH */
949 	case 1:
950 		b0 = MP_DIGIT(b,0);
951 	}
952 
953 	MP_SUB_BORROW(r0, b0, r0, 0,     borrow);
954 	MP_SUB_BORROW(r1, b1, r1, borrow, borrow);
955 	MP_SUB_BORROW(r2, b2, r2, borrow, borrow);
956 	MP_SUB_BORROW(r3, b3, r3, borrow, borrow);
957 	MP_SUB_BORROW(r4, b4, r4, borrow, borrow);
958 	MP_SUB_BORROW(r5, b5, r5, borrow, borrow);
959 
960 	/* Do quick 'add' if we've gone under 0
961 	 * (subtract the 2's complement of the curve field) */
962 	if (borrow) {
963 	 	b5 = MP_DIGIT(&meth->irr,5);
964 	 	b4 = MP_DIGIT(&meth->irr,4);
965 	 	b3 = MP_DIGIT(&meth->irr,3);
966 	 	b2 = MP_DIGIT(&meth->irr,2);
967 		b1 = MP_DIGIT(&meth->irr,1);
968 		b0 = MP_DIGIT(&meth->irr,0);
969 		MP_ADD_CARRY(b0, r0, r0, 0,      borrow);
970 		MP_ADD_CARRY(b1, r1, r1, borrow, borrow);
971 		MP_ADD_CARRY(b2, r2, r2, borrow, borrow);
972 		MP_ADD_CARRY(b3, r3, r3, borrow, borrow);
973 		MP_ADD_CARRY(b4, r4, r4, borrow, borrow);
974 	}
975 
976 	MP_CHECKOK(s_mp_pad(r, 6));
977 	MP_DIGIT(r, 5) = r5;
978 	MP_DIGIT(r, 4) = r4;
979 	MP_DIGIT(r, 3) = r3;
980 	MP_DIGIT(r, 2) = r2;
981 	MP_DIGIT(r, 1) = r1;
982 	MP_DIGIT(r, 0) = r0;
983 	MP_SIGN(r) = MP_ZPOS;
984 	MP_USED(r) = 6;
985 	s_mp_clamp(r);
986 
987   CLEANUP:
988 	return res;
989 }
990 
991 
992 /* Reduces an integer to a field element. */
993 mp_err
ec_GFp_mod(const mp_int * a,mp_int * r,const GFMethod * meth)994 ec_GFp_mod(const mp_int *a, mp_int *r, const GFMethod *meth)
995 {
996 	return mp_mod(a, &meth->irr, r);
997 }
998 
999 /* Multiplies two field elements. */
1000 mp_err
ec_GFp_mul(const mp_int * a,const mp_int * b,mp_int * r,const GFMethod * meth)1001 ec_GFp_mul(const mp_int *a, const mp_int *b, mp_int *r,
1002 		   const GFMethod *meth)
1003 {
1004 	return mp_mulmod(a, b, &meth->irr, r);
1005 }
1006 
1007 /* Squares a field element. */
1008 mp_err
ec_GFp_sqr(const mp_int * a,mp_int * r,const GFMethod * meth)1009 ec_GFp_sqr(const mp_int *a, mp_int *r, const GFMethod *meth)
1010 {
1011 	return mp_sqrmod(a, &meth->irr, r);
1012 }
1013 
1014 /* Divides two field elements. If a is NULL, then returns the inverse of
1015  * b. */
1016 mp_err
ec_GFp_div(const mp_int * a,const mp_int * b,mp_int * r,const GFMethod * meth)1017 ec_GFp_div(const mp_int *a, const mp_int *b, mp_int *r,
1018 		   const GFMethod *meth)
1019 {
1020 	mp_err res = MP_OKAY;
1021 	mp_int t;
1022 
1023 	/* If a is NULL, then return the inverse of b, otherwise return a/b. */
1024 	if (a == NULL) {
1025 		return mp_invmod(b, &meth->irr, r);
1026 	} else {
1027 		/* MPI doesn't support divmod, so we implement it using invmod and
1028 		 * mulmod. */
1029 		MP_CHECKOK(mp_init(&t, FLAG(b)));
1030 		MP_CHECKOK(mp_invmod(b, &meth->irr, &t));
1031 		MP_CHECKOK(mp_mulmod(a, &t, &meth->irr, r));
1032 	  CLEANUP:
1033 		mp_clear(&t);
1034 		return res;
1035 	}
1036 }
1037 
1038 /* Wrapper functions for generic binary polynomial field arithmetic. */
1039 
1040 /* Adds two field elements. */
1041 mp_err
ec_GF2m_add(const mp_int * a,const mp_int * b,mp_int * r,const GFMethod * meth)1042 ec_GF2m_add(const mp_int *a, const mp_int *b, mp_int *r,
1043 			const GFMethod *meth)
1044 {
1045 	return mp_badd(a, b, r);
1046 }
1047 
1048 /* Negates a field element. Note that for binary polynomial fields, the
1049  * negation of a field element is the field element itself. */
1050 mp_err
ec_GF2m_neg(const mp_int * a,mp_int * r,const GFMethod * meth)1051 ec_GF2m_neg(const mp_int *a, mp_int *r, const GFMethod *meth)
1052 {
1053 	if (a == r) {
1054 		return MP_OKAY;
1055 	} else {
1056 		return mp_copy(a, r);
1057 	}
1058 }
1059 
1060 /* Reduces a binary polynomial to a field element. */
1061 mp_err
ec_GF2m_mod(const mp_int * a,mp_int * r,const GFMethod * meth)1062 ec_GF2m_mod(const mp_int *a, mp_int *r, const GFMethod *meth)
1063 {
1064 	return mp_bmod(a, meth->irr_arr, r);
1065 }
1066 
1067 /* Multiplies two field elements. */
1068 mp_err
ec_GF2m_mul(const mp_int * a,const mp_int * b,mp_int * r,const GFMethod * meth)1069 ec_GF2m_mul(const mp_int *a, const mp_int *b, mp_int *r,
1070 			const GFMethod *meth)
1071 {
1072 	return mp_bmulmod(a, b, meth->irr_arr, r);
1073 }
1074 
1075 /* Squares a field element. */
1076 mp_err
ec_GF2m_sqr(const mp_int * a,mp_int * r,const GFMethod * meth)1077 ec_GF2m_sqr(const mp_int *a, mp_int *r, const GFMethod *meth)
1078 {
1079 	return mp_bsqrmod(a, meth->irr_arr, r);
1080 }
1081 
1082 /* Divides two field elements. If a is NULL, then returns the inverse of
1083  * b. */
1084 mp_err
ec_GF2m_div(const mp_int * a,const mp_int * b,mp_int * r,const GFMethod * meth)1085 ec_GF2m_div(const mp_int *a, const mp_int *b, mp_int *r,
1086 			const GFMethod *meth)
1087 {
1088 	mp_err res = MP_OKAY;
1089 	mp_int t;
1090 
1091 	/* If a is NULL, then return the inverse of b, otherwise return a/b. */
1092 	if (a == NULL) {
1093 		/* The GF(2^m) portion of MPI doesn't support invmod, so we
1094 		 * compute 1/b. */
1095 		MP_CHECKOK(mp_init(&t, FLAG(b)));
1096 		MP_CHECKOK(mp_set_int(&t, 1));
1097 		MP_CHECKOK(mp_bdivmod(&t, b, &meth->irr, meth->irr_arr, r));
1098 	  CLEANUP:
1099 		mp_clear(&t);
1100 		return res;
1101 	} else {
1102 		return mp_bdivmod(a, b, &meth->irr, meth->irr_arr, r);
1103 	}
1104 }
1105