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