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