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