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 for prime field curves.
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 * Douglas Stebila <douglas@stebila.ca>, Sun Microsystems Laboratories
24 *
25 * Alternatively, the contents of this file may be used under the terms of
26 * either the GNU General Public License Version 2 or later (the "GPL"), or
27 * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
28 * in which case the provisions of the GPL or the LGPL are applicable instead
29 * of those above. If you wish to allow use of your version of this file only
30 * under the terms of either the GPL or the LGPL, and not to allow others to
31 * use your version of this file under the terms of the MPL, indicate your
32 * decision by deleting the provisions above and replace them with the notice
33 * and other provisions required by the GPL or the LGPL. If you do not delete
34 * the provisions above, a recipient may use your version of this file under
35 * the terms of any one of the MPL, the GPL or the LGPL.
36 *
37 * ***** END LICENSE BLOCK ***** */
38 /*
39 * Copyright 2007 Sun Microsystems, Inc. All rights reserved.
40 * Use is subject to license terms.
41 *
42 * Sun elects to use this software under the MPL license.
43 */
44
45 #include "ecp.h"
46 #include "mpi.h"
47 #include "mplogic.h"
48 #include "mpi-priv.h"
49 #ifndef _KERNEL
50 #include <stdlib.h>
51 #endif
52
53 #define ECP192_DIGITS ECL_CURVE_DIGITS(192)
54
55 /* Fast modular reduction for p192 = 2^192 - 2^64 - 1. a can be r. Uses
56 * algorithm 7 from Brown, Hankerson, Lopez, Menezes. Software
57 * Implementation of the NIST Elliptic Curves over Prime Fields. */
58 mp_err
ec_GFp_nistp192_mod(const mp_int * a,mp_int * r,const GFMethod * meth)59 ec_GFp_nistp192_mod(const mp_int *a, mp_int *r, const GFMethod *meth)
60 {
61 mp_err res = MP_OKAY;
62 mp_size a_used = MP_USED(a);
63 mp_digit r3;
64 #ifndef MPI_AMD64_ADD
65 mp_digit carry;
66 #endif
67 #ifdef ECL_THIRTY_TWO_BIT
68 mp_digit a5a = 0, a5b = 0, a4a = 0, a4b = 0, a3a = 0, a3b = 0;
69 mp_digit r0a, r0b, r1a, r1b, r2a, r2b;
70 #else
71 mp_digit a5 = 0, a4 = 0, a3 = 0;
72 mp_digit r0, r1, r2;
73 #endif
74
75 /* reduction not needed if a is not larger than field size */
76 if (a_used < ECP192_DIGITS) {
77 if (a == r) {
78 return MP_OKAY;
79 }
80 return mp_copy(a, r);
81 }
82
83 /* for polynomials larger than twice the field size, use regular
84 * reduction */
85 if (a_used > ECP192_DIGITS*2) {
86 MP_CHECKOK(mp_mod(a, &meth->irr, r));
87 } else {
88 /* copy out upper words of a */
89
90 #ifdef ECL_THIRTY_TWO_BIT
91
92 /* in all the math below,
93 * nXb is most signifiant, nXa is least significant */
94 switch (a_used) {
95 case 12:
96 a5b = MP_DIGIT(a, 11);
97 /* FALLTHROUGH */
98 case 11:
99 a5a = MP_DIGIT(a, 10);
100 /* FALLTHROUGH */
101 case 10:
102 a4b = MP_DIGIT(a, 9);
103 /* FALLTHROUGH */
104 case 9:
105 a4a = MP_DIGIT(a, 8);
106 /* FALLTHROUGH */
107 case 8:
108 a3b = MP_DIGIT(a, 7);
109 /* FALLTHROUGH */
110 case 7:
111 a3a = MP_DIGIT(a, 6);
112 }
113
114
115 r2b= MP_DIGIT(a, 5);
116 r2a= MP_DIGIT(a, 4);
117 r1b = MP_DIGIT(a, 3);
118 r1a = MP_DIGIT(a, 2);
119 r0b = MP_DIGIT(a, 1);
120 r0a = MP_DIGIT(a, 0);
121
122 /* implement r = (a2,a1,a0)+(a5,a5,a5)+(a4,a4,0)+(0,a3,a3) */
123 MP_ADD_CARRY(r0a, a3a, r0a, 0, carry);
124 MP_ADD_CARRY(r0b, a3b, r0b, carry, carry);
125 MP_ADD_CARRY(r1a, a3a, r1a, carry, carry);
126 MP_ADD_CARRY(r1b, a3b, r1b, carry, carry);
127 MP_ADD_CARRY(r2a, a4a, r2a, carry, carry);
128 MP_ADD_CARRY(r2b, a4b, r2b, carry, carry);
129 r3 = carry; carry = 0;
130 MP_ADD_CARRY(r0a, a5a, r0a, 0, carry);
131 MP_ADD_CARRY(r0b, a5b, r0b, carry, carry);
132 MP_ADD_CARRY(r1a, a5a, r1a, carry, carry);
133 MP_ADD_CARRY(r1b, a5b, r1b, carry, carry);
134 MP_ADD_CARRY(r2a, a5a, r2a, carry, carry);
135 MP_ADD_CARRY(r2b, a5b, r2b, carry, carry);
136 r3 += carry;
137 MP_ADD_CARRY(r1a, a4a, r1a, 0, carry);
138 MP_ADD_CARRY(r1b, a4b, r1b, carry, carry);
139 MP_ADD_CARRY(r2a, 0, r2a, carry, carry);
140 MP_ADD_CARRY(r2b, 0, r2b, carry, carry);
141 r3 += carry;
142
143 /* reduce out the carry */
144 while (r3) {
145 MP_ADD_CARRY(r0a, r3, r0a, 0, carry);
146 MP_ADD_CARRY(r0b, 0, r0b, carry, carry);
147 MP_ADD_CARRY(r1a, r3, r1a, carry, carry);
148 MP_ADD_CARRY(r1b, 0, r1b, carry, carry);
149 MP_ADD_CARRY(r2a, 0, r2a, carry, carry);
150 MP_ADD_CARRY(r2b, 0, r2b, carry, carry);
151 r3 = carry;
152 }
153
154 /* check for final reduction */
155 /*
156 * our field is 0xffffffffffffffff, 0xfffffffffffffffe,
157 * 0xffffffffffffffff. That means we can only be over and need
158 * one more reduction
159 * if r2 == 0xffffffffffffffffff (same as r2+1 == 0)
160 * and
161 * r1 == 0xffffffffffffffffff or
162 * r1 == 0xfffffffffffffffffe and r0 = 0xfffffffffffffffff
163 * In all cases, we subtract the field (or add the 2's
164 * complement value (1,1,0)). (r0, r1, r2)
165 */
166 if (((r2b == 0xffffffff) && (r2a == 0xffffffff)
167 && (r1b == 0xffffffff) ) &&
168 ((r1a == 0xffffffff) ||
169 (r1a == 0xfffffffe) && (r0a == 0xffffffff) &&
170 (r0b == 0xffffffff)) ) {
171 /* do a quick subtract */
172 MP_ADD_CARRY(r0a, 1, r0a, 0, carry);
173 MP_ADD_CARRY(r0b, 0, r0b, carry, carry);
174 r1a += 1 + carry;
175 r1b = r2a = r2b = 0;
176 }
177
178 /* set the lower words of r */
179 if (a != r) {
180 MP_CHECKOK(s_mp_pad(r, 6));
181 }
182 MP_DIGIT(r, 5) = r2b;
183 MP_DIGIT(r, 4) = r2a;
184 MP_DIGIT(r, 3) = r1b;
185 MP_DIGIT(r, 2) = r1a;
186 MP_DIGIT(r, 1) = r0b;
187 MP_DIGIT(r, 0) = r0a;
188 MP_USED(r) = 6;
189 #else
190 switch (a_used) {
191 case 6:
192 a5 = MP_DIGIT(a, 5);
193 /* FALLTHROUGH */
194 case 5:
195 a4 = MP_DIGIT(a, 4);
196 /* FALLTHROUGH */
197 case 4:
198 a3 = MP_DIGIT(a, 3);
199 }
200
201 r2 = MP_DIGIT(a, 2);
202 r1 = MP_DIGIT(a, 1);
203 r0 = MP_DIGIT(a, 0);
204
205 /* implement r = (a2,a1,a0)+(a5,a5,a5)+(a4,a4,0)+(0,a3,a3) */
206 #ifndef MPI_AMD64_ADD
207 MP_ADD_CARRY(r0, a3, r0, 0, carry);
208 MP_ADD_CARRY(r1, a3, r1, carry, carry);
209 MP_ADD_CARRY(r2, a4, r2, carry, carry);
210 r3 = carry;
211 MP_ADD_CARRY(r0, a5, r0, 0, carry);
212 MP_ADD_CARRY(r1, a5, r1, carry, carry);
213 MP_ADD_CARRY(r2, a5, r2, carry, carry);
214 r3 += carry;
215 MP_ADD_CARRY(r1, a4, r1, 0, carry);
216 MP_ADD_CARRY(r2, 0, r2, carry, carry);
217 r3 += carry;
218
219 #else
220 r2 = MP_DIGIT(a, 2);
221 r1 = MP_DIGIT(a, 1);
222 r0 = MP_DIGIT(a, 0);
223
224 /* set the lower words of r */
225 __asm__ (
226 "xorq %3,%3 \n\t"
227 "addq %4,%0 \n\t"
228 "adcq %4,%1 \n\t"
229 "adcq %5,%2 \n\t"
230 "adcq $0,%3 \n\t"
231 "addq %6,%0 \n\t"
232 "adcq %6,%1 \n\t"
233 "adcq %6,%2 \n\t"
234 "adcq $0,%3 \n\t"
235 "addq %5,%1 \n\t"
236 "adcq $0,%2 \n\t"
237 "adcq $0,%3 \n\t"
238 : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(r3), "=r"(a3),
239 "=r"(a4), "=r"(a5)
240 : "0" (r0), "1" (r1), "2" (r2), "3" (r3),
241 "4" (a3), "5" (a4), "6"(a5)
242 : "%cc" );
243 #endif
244
245 /* reduce out the carry */
246 while (r3) {
247 #ifndef MPI_AMD64_ADD
248 MP_ADD_CARRY(r0, r3, r0, 0, carry);
249 MP_ADD_CARRY(r1, r3, r1, carry, carry);
250 MP_ADD_CARRY(r2, 0, r2, carry, carry);
251 r3 = carry;
252 #else
253 a3=r3;
254 __asm__ (
255 "xorq %3,%3 \n\t"
256 "addq %4,%0 \n\t"
257 "adcq %4,%1 \n\t"
258 "adcq $0,%2 \n\t"
259 "adcq $0,%3 \n\t"
260 : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(r3), "=r"(a3)
261 : "0" (r0), "1" (r1), "2" (r2), "3" (r3), "4"(a3)
262 : "%cc" );
263 #endif
264 }
265
266 /* check for final reduction */
267 /*
268 * our field is 0xffffffffffffffff, 0xfffffffffffffffe,
269 * 0xffffffffffffffff. That means we can only be over and need
270 * one more reduction
271 * if r2 == 0xffffffffffffffffff (same as r2+1 == 0)
272 * and
273 * r1 == 0xffffffffffffffffff or
274 * r1 == 0xfffffffffffffffffe and r0 = 0xfffffffffffffffff
275 * In all cases, we subtract the field (or add the 2's
276 * complement value (1,1,0)). (r0, r1, r2)
277 */
278 if (r3 || ((r2 == MP_DIGIT_MAX) &&
279 ((r1 == MP_DIGIT_MAX) ||
280 ((r1 == (MP_DIGIT_MAX-1)) && (r0 == MP_DIGIT_MAX))))) {
281 /* do a quick subtract */
282 MP_ADD_CARRY(r0, 1, r0, 0, carry);
283 r1 += 1 + carry;
284 r2 = 0;
285 }
286 /* set the lower words of r */
287 if (a != r) {
288 MP_CHECKOK(s_mp_pad(r, 3));
289 }
290 MP_DIGIT(r, 2) = r2;
291 MP_DIGIT(r, 1) = r1;
292 MP_DIGIT(r, 0) = r0;
293 MP_USED(r) = 3;
294 #endif
295 }
296
297 s_mp_clamp(r);
298 CLEANUP:
299 return res;
300 }
301
302 #ifndef ECL_THIRTY_TWO_BIT
303 /* Compute the sum of 192 bit curves. Do the work in-line since the
304 * number of words are so small, we don't want to overhead of mp function
305 * calls. Uses optimized modular reduction for p192.
306 */
307 mp_err
ec_GFp_nistp192_add(const mp_int * a,const mp_int * b,mp_int * r,const GFMethod * meth)308 ec_GFp_nistp192_add(const mp_int *a, const mp_int *b, mp_int *r,
309 const GFMethod *meth)
310 {
311 mp_err res = MP_OKAY;
312 mp_digit a0 = 0, a1 = 0, a2 = 0;
313 mp_digit r0 = 0, r1 = 0, r2 = 0;
314 mp_digit carry;
315
316 switch(MP_USED(a)) {
317 case 3:
318 a2 = MP_DIGIT(a,2);
319 /* FALLTHROUGH */
320 case 2:
321 a1 = MP_DIGIT(a,1);
322 /* FALLTHROUGH */
323 case 1:
324 a0 = MP_DIGIT(a,0);
325 }
326 switch(MP_USED(b)) {
327 case 3:
328 r2 = MP_DIGIT(b,2);
329 /* FALLTHROUGH */
330 case 2:
331 r1 = MP_DIGIT(b,1);
332 /* FALLTHROUGH */
333 case 1:
334 r0 = MP_DIGIT(b,0);
335 }
336
337 #ifndef MPI_AMD64_ADD
338 MP_ADD_CARRY(a0, r0, r0, 0, carry);
339 MP_ADD_CARRY(a1, r1, r1, carry, carry);
340 MP_ADD_CARRY(a2, r2, r2, carry, carry);
341 #else
342 __asm__ (
343 "xorq %3,%3 \n\t"
344 "addq %4,%0 \n\t"
345 "adcq %5,%1 \n\t"
346 "adcq %6,%2 \n\t"
347 "adcq $0,%3 \n\t"
348 : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(carry)
349 : "r" (a0), "r" (a1), "r" (a2), "0" (r0),
350 "1" (r1), "2" (r2)
351 : "%cc" );
352 #endif
353
354 /* Do quick 'subract' if we've gone over
355 * (add the 2's complement of the curve field) */
356 if (carry || ((r2 == MP_DIGIT_MAX) &&
357 ((r1 == MP_DIGIT_MAX) ||
358 ((r1 == (MP_DIGIT_MAX-1)) && (r0 == MP_DIGIT_MAX))))) {
359 #ifndef MPI_AMD64_ADD
360 MP_ADD_CARRY(r0, 1, r0, 0, carry);
361 MP_ADD_CARRY(r1, 1, r1, carry, carry);
362 MP_ADD_CARRY(r2, 0, r2, carry, carry);
363 #else
364 __asm__ (
365 "addq $1,%0 \n\t"
366 "adcq $1,%1 \n\t"
367 "adcq $0,%2 \n\t"
368 : "=r"(r0), "=r"(r1), "=r"(r2)
369 : "0" (r0), "1" (r1), "2" (r2)
370 : "%cc" );
371 #endif
372 }
373
374
375 MP_CHECKOK(s_mp_pad(r, 3));
376 MP_DIGIT(r, 2) = r2;
377 MP_DIGIT(r, 1) = r1;
378 MP_DIGIT(r, 0) = r0;
379 MP_SIGN(r) = MP_ZPOS;
380 MP_USED(r) = 3;
381 s_mp_clamp(r);
382
383
384 CLEANUP:
385 return res;
386 }
387
388 /* Compute the diff of 192 bit curves. Do the work in-line since the
389 * number of words are so small, we don't want to overhead of mp function
390 * calls. Uses optimized modular reduction for p192.
391 */
392 mp_err
ec_GFp_nistp192_sub(const mp_int * a,const mp_int * b,mp_int * r,const GFMethod * meth)393 ec_GFp_nistp192_sub(const mp_int *a, const mp_int *b, mp_int *r,
394 const GFMethod *meth)
395 {
396 mp_err res = MP_OKAY;
397 mp_digit b0 = 0, b1 = 0, b2 = 0;
398 mp_digit r0 = 0, r1 = 0, r2 = 0;
399 mp_digit borrow;
400
401 switch(MP_USED(a)) {
402 case 3:
403 r2 = MP_DIGIT(a,2);
404 /* FALLTHROUGH */
405 case 2:
406 r1 = MP_DIGIT(a,1);
407 /* FALLTHROUGH */
408 case 1:
409 r0 = MP_DIGIT(a,0);
410 }
411
412 switch(MP_USED(b)) {
413 case 3:
414 b2 = MP_DIGIT(b,2);
415 /* FALLTHROUGH */
416 case 2:
417 b1 = MP_DIGIT(b,1);
418 /* FALLTHROUGH */
419 case 1:
420 b0 = MP_DIGIT(b,0);
421 }
422
423 #ifndef MPI_AMD64_ADD
424 MP_SUB_BORROW(r0, b0, r0, 0, borrow);
425 MP_SUB_BORROW(r1, b1, r1, borrow, borrow);
426 MP_SUB_BORROW(r2, b2, r2, borrow, borrow);
427 #else
428 __asm__ (
429 "xorq %3,%3 \n\t"
430 "subq %4,%0 \n\t"
431 "sbbq %5,%1 \n\t"
432 "sbbq %6,%2 \n\t"
433 "adcq $0,%3 \n\t"
434 : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(borrow)
435 : "r" (b0), "r" (b1), "r" (b2), "0" (r0),
436 "1" (r1), "2" (r2)
437 : "%cc" );
438 #endif
439
440 /* Do quick 'add' if we've gone under 0
441 * (subtract the 2's complement of the curve field) */
442 if (borrow) {
443 #ifndef MPI_AMD64_ADD
444 MP_SUB_BORROW(r0, 1, r0, 0, borrow);
445 MP_SUB_BORROW(r1, 1, r1, borrow, borrow);
446 MP_SUB_BORROW(r2, 0, r2, borrow, borrow);
447 #else
448 __asm__ (
449 "subq $1,%0 \n\t"
450 "sbbq $1,%1 \n\t"
451 "sbbq $0,%2 \n\t"
452 : "=r"(r0), "=r"(r1), "=r"(r2)
453 : "0" (r0), "1" (r1), "2" (r2)
454 : "%cc" );
455 #endif
456 }
457
458 MP_CHECKOK(s_mp_pad(r, 3));
459 MP_DIGIT(r, 2) = r2;
460 MP_DIGIT(r, 1) = r1;
461 MP_DIGIT(r, 0) = r0;
462 MP_SIGN(r) = MP_ZPOS;
463 MP_USED(r) = 3;
464 s_mp_clamp(r);
465
466 CLEANUP:
467 return res;
468 }
469
470 #endif
471
472 /* Compute the square of polynomial a, reduce modulo p192. Store the
473 * result in r. r could be a. Uses optimized modular reduction for p192.
474 */
475 mp_err
ec_GFp_nistp192_sqr(const mp_int * a,mp_int * r,const GFMethod * meth)476 ec_GFp_nistp192_sqr(const mp_int *a, mp_int *r, const GFMethod *meth)
477 {
478 mp_err res = MP_OKAY;
479
480 MP_CHECKOK(mp_sqr(a, r));
481 MP_CHECKOK(ec_GFp_nistp192_mod(r, r, meth));
482 CLEANUP:
483 return res;
484 }
485
486 /* Compute the product of two polynomials a and b, reduce modulo p192.
487 * Store the result in r. r could be a or b; a could be b. Uses
488 * optimized modular reduction for p192. */
489 mp_err
ec_GFp_nistp192_mul(const mp_int * a,const mp_int * b,mp_int * r,const GFMethod * meth)490 ec_GFp_nistp192_mul(const mp_int *a, const mp_int *b, mp_int *r,
491 const GFMethod *meth)
492 {
493 mp_err res = MP_OKAY;
494
495 MP_CHECKOK(mp_mul(a, b, r));
496 MP_CHECKOK(ec_GFp_nistp192_mod(r, r, meth));
497 CLEANUP:
498 return res;
499 }
500
501 /* Divides two field elements. If a is NULL, then returns the inverse of
502 * b. */
503 mp_err
ec_GFp_nistp192_div(const mp_int * a,const mp_int * b,mp_int * r,const GFMethod * meth)504 ec_GFp_nistp192_div(const mp_int *a, const mp_int *b, mp_int *r,
505 const GFMethod *meth)
506 {
507 mp_err res = MP_OKAY;
508 mp_int t;
509
510 /* If a is NULL, then return the inverse of b, otherwise return a/b. */
511 if (a == NULL) {
512 return mp_invmod(b, &meth->irr, r);
513 } else {
514 /* MPI doesn't support divmod, so we implement it using invmod and
515 * mulmod. */
516 MP_CHECKOK(mp_init(&t, FLAG(b)));
517 MP_CHECKOK(mp_invmod(b, &meth->irr, &t));
518 MP_CHECKOK(mp_mul(a, &t, r));
519 MP_CHECKOK(ec_GFp_nistp192_mod(r, r, meth));
520 CLEANUP:
521 mp_clear(&t);
522 return res;
523 }
524 }
525
526 /* Wire in fast field arithmetic and precomputation of base point for
527 * named curves. */
528 mp_err
ec_group_set_gfp192(ECGroup * group,ECCurveName name)529 ec_group_set_gfp192(ECGroup *group, ECCurveName name)
530 {
531 if (name == ECCurve_NIST_P192) {
532 group->meth->field_mod = &ec_GFp_nistp192_mod;
533 group->meth->field_mul = &ec_GFp_nistp192_mul;
534 group->meth->field_sqr = &ec_GFp_nistp192_sqr;
535 group->meth->field_div = &ec_GFp_nistp192_div;
536 #ifndef ECL_THIRTY_TWO_BIT
537 group->meth->field_add = &ec_GFp_nistp192_add;
538 group->meth->field_sub = &ec_GFp_nistp192_sub;
539 #endif
540 }
541 return MP_OKAY;
542 }
543