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