1 /*
2 * Copyright (c) 2007, 2011, Oracle and/or its affiliates. All rights reserved.
3 * Use is subject to license terms.
4 *
5 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Lesser General Public
7 * License as published by the Free Software Foundation; either
8 * version 2.1 of the License, or (at your option) any later version.
9 *
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * Lesser General Public License for more details.
14 *
15 * You should have received a copy of the GNU Lesser General Public License
16 * along with this library; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23
24 /* *********************************************************************
25 *
26 * The Original Code is the elliptic curve math library for prime field curves.
27 *
28 * The Initial Developer of the Original Code is
29 * Sun Microsystems, Inc.
30 * Portions created by the Initial Developer are Copyright (C) 2003
31 * the Initial Developer. All Rights Reserved.
32 *
33 * Contributor(s):
34 * Douglas Stebila <douglas@stebila.ca>
35 *
36 *********************************************************************** */
37
38 #include "ecp.h"
39 #include "mpi.h"
40 #include "mplogic.h"
41 #include "mpi-priv.h"
42 #ifndef _KERNEL
43 #include <stdlib.h>
44 #endif
45
46 /* Fast modular reduction for p256 = 2^256 - 2^224 + 2^192+ 2^96 - 1. a can be r.
47 * Uses algorithm 2.29 from Hankerson, Menezes, Vanstone. Guide to
48 * Elliptic Curve Cryptography. */
49 mp_err
ec_GFp_nistp256_mod(const mp_int * a,mp_int * r,const GFMethod * meth)50 ec_GFp_nistp256_mod(const mp_int *a, mp_int *r, const GFMethod *meth)
51 {
52 mp_err res = MP_OKAY;
53 mp_size a_used = MP_USED(a);
54 int a_bits = mpl_significant_bits(a);
55 mp_digit carry;
56
57 #ifdef ECL_THIRTY_TWO_BIT
58 mp_digit a8=0, a9=0, a10=0, a11=0, a12=0, a13=0, a14=0, a15=0;
59 mp_digit r0, r1, r2, r3, r4, r5, r6, r7;
60 int r8; /* must be a signed value ! */
61 #else
62 mp_digit a4=0, a5=0, a6=0, a7=0;
63 mp_digit a4h, a4l, a5h, a5l, a6h, a6l, a7h, a7l;
64 mp_digit r0, r1, r2, r3;
65 int r4; /* must be a signed value ! */
66 #endif
67 /* for polynomials larger than twice the field size
68 * use regular reduction */
69 if (a_bits < 256) {
70 if (a == r) return MP_OKAY;
71 return mp_copy(a,r);
72 }
73 if (a_bits > 512) {
74 MP_CHECKOK(mp_mod(a, &meth->irr, r));
75 } else {
76
77 #ifdef ECL_THIRTY_TWO_BIT
78 switch (a_used) {
79 case 16:
80 a15 = MP_DIGIT(a,15);
81 case 15:
82 a14 = MP_DIGIT(a,14);
83 case 14:
84 a13 = MP_DIGIT(a,13);
85 case 13:
86 a12 = MP_DIGIT(a,12);
87 case 12:
88 a11 = MP_DIGIT(a,11);
89 case 11:
90 a10 = MP_DIGIT(a,10);
91 case 10:
92 a9 = MP_DIGIT(a,9);
93 case 9:
94 a8 = MP_DIGIT(a,8);
95 }
96
97 r0 = MP_DIGIT(a,0);
98 r1 = MP_DIGIT(a,1);
99 r2 = MP_DIGIT(a,2);
100 r3 = MP_DIGIT(a,3);
101 r4 = MP_DIGIT(a,4);
102 r5 = MP_DIGIT(a,5);
103 r6 = MP_DIGIT(a,6);
104 r7 = MP_DIGIT(a,7);
105
106 /* sum 1 */
107 MP_ADD_CARRY(r3, a11, r3, 0, carry);
108 MP_ADD_CARRY(r4, a12, r4, carry, carry);
109 MP_ADD_CARRY(r5, a13, r5, carry, carry);
110 MP_ADD_CARRY(r6, a14, r6, carry, carry);
111 MP_ADD_CARRY(r7, a15, r7, carry, carry);
112 r8 = carry;
113 MP_ADD_CARRY(r3, a11, r3, 0, carry);
114 MP_ADD_CARRY(r4, a12, r4, carry, carry);
115 MP_ADD_CARRY(r5, a13, r5, carry, carry);
116 MP_ADD_CARRY(r6, a14, r6, carry, carry);
117 MP_ADD_CARRY(r7, a15, r7, carry, carry);
118 r8 += carry;
119 /* sum 2 */
120 MP_ADD_CARRY(r3, a12, r3, 0, carry);
121 MP_ADD_CARRY(r4, a13, r4, carry, carry);
122 MP_ADD_CARRY(r5, a14, r5, carry, carry);
123 MP_ADD_CARRY(r6, a15, r6, carry, carry);
124 MP_ADD_CARRY(r7, 0, r7, carry, carry);
125 r8 += carry;
126 /* combine last bottom of sum 3 with second sum 2 */
127 MP_ADD_CARRY(r0, a8, r0, 0, carry);
128 MP_ADD_CARRY(r1, a9, r1, carry, carry);
129 MP_ADD_CARRY(r2, a10, r2, carry, carry);
130 MP_ADD_CARRY(r3, a12, r3, carry, carry);
131 MP_ADD_CARRY(r4, a13, r4, carry, carry);
132 MP_ADD_CARRY(r5, a14, r5, carry, carry);
133 MP_ADD_CARRY(r6, a15, r6, carry, carry);
134 MP_ADD_CARRY(r7, a15, r7, carry, carry); /* from sum 3 */
135 r8 += carry;
136 /* sum 3 (rest of it)*/
137 MP_ADD_CARRY(r6, a14, r6, 0, carry);
138 MP_ADD_CARRY(r7, 0, r7, carry, carry);
139 r8 += carry;
140 /* sum 4 (rest of it)*/
141 MP_ADD_CARRY(r0, a9, r0, 0, carry);
142 MP_ADD_CARRY(r1, a10, r1, carry, carry);
143 MP_ADD_CARRY(r2, a11, r2, carry, carry);
144 MP_ADD_CARRY(r3, a13, r3, carry, carry);
145 MP_ADD_CARRY(r4, a14, r4, carry, carry);
146 MP_ADD_CARRY(r5, a15, r5, carry, carry);
147 MP_ADD_CARRY(r6, a13, r6, carry, carry);
148 MP_ADD_CARRY(r7, a8, r7, carry, carry);
149 r8 += carry;
150 /* diff 5 */
151 MP_SUB_BORROW(r0, a11, r0, 0, carry);
152 MP_SUB_BORROW(r1, a12, r1, carry, carry);
153 MP_SUB_BORROW(r2, a13, r2, carry, carry);
154 MP_SUB_BORROW(r3, 0, r3, carry, carry);
155 MP_SUB_BORROW(r4, 0, r4, carry, carry);
156 MP_SUB_BORROW(r5, 0, r5, carry, carry);
157 MP_SUB_BORROW(r6, a8, r6, carry, carry);
158 MP_SUB_BORROW(r7, a10, r7, carry, carry);
159 r8 -= carry;
160 /* diff 6 */
161 MP_SUB_BORROW(r0, a12, r0, 0, carry);
162 MP_SUB_BORROW(r1, a13, r1, carry, carry);
163 MP_SUB_BORROW(r2, a14, r2, carry, carry);
164 MP_SUB_BORROW(r3, a15, r3, carry, carry);
165 MP_SUB_BORROW(r4, 0, r4, carry, carry);
166 MP_SUB_BORROW(r5, 0, r5, carry, carry);
167 MP_SUB_BORROW(r6, a9, r6, carry, carry);
168 MP_SUB_BORROW(r7, a11, r7, carry, carry);
169 r8 -= carry;
170 /* diff 7 */
171 MP_SUB_BORROW(r0, a13, r0, 0, carry);
172 MP_SUB_BORROW(r1, a14, r1, carry, carry);
173 MP_SUB_BORROW(r2, a15, r2, carry, carry);
174 MP_SUB_BORROW(r3, a8, r3, carry, carry);
175 MP_SUB_BORROW(r4, a9, r4, carry, carry);
176 MP_SUB_BORROW(r5, a10, r5, carry, carry);
177 MP_SUB_BORROW(r6, 0, r6, carry, carry);
178 MP_SUB_BORROW(r7, a12, r7, carry, carry);
179 r8 -= carry;
180 /* diff 8 */
181 MP_SUB_BORROW(r0, a14, r0, 0, carry);
182 MP_SUB_BORROW(r1, a15, r1, carry, carry);
183 MP_SUB_BORROW(r2, 0, r2, carry, carry);
184 MP_SUB_BORROW(r3, a9, r3, carry, carry);
185 MP_SUB_BORROW(r4, a10, r4, carry, carry);
186 MP_SUB_BORROW(r5, a11, r5, carry, carry);
187 MP_SUB_BORROW(r6, 0, r6, carry, carry);
188 MP_SUB_BORROW(r7, a13, r7, carry, carry);
189 r8 -= carry;
190
191 /* reduce the overflows */
192 while (r8 > 0) {
193 mp_digit r8_d = r8;
194 MP_ADD_CARRY(r0, r8_d, r0, 0, carry);
195 MP_ADD_CARRY(r1, 0, r1, carry, carry);
196 MP_ADD_CARRY(r2, 0, r2, carry, carry);
197 MP_ADD_CARRY(r3, -r8_d, r3, carry, carry);
198 MP_ADD_CARRY(r4, MP_DIGIT_MAX, r4, carry, carry);
199 MP_ADD_CARRY(r5, MP_DIGIT_MAX, r5, carry, carry);
200 MP_ADD_CARRY(r6, -(r8_d+1), r6, carry, carry);
201 MP_ADD_CARRY(r7, (r8_d-1), r7, carry, carry);
202 r8 = carry;
203 }
204
205 /* reduce the underflows */
206 while (r8 < 0) {
207 mp_digit r8_d = -r8;
208 MP_SUB_BORROW(r0, r8_d, r0, 0, carry);
209 MP_SUB_BORROW(r1, 0, r1, carry, carry);
210 MP_SUB_BORROW(r2, 0, r2, carry, carry);
211 MP_SUB_BORROW(r3, -r8_d, r3, carry, carry);
212 MP_SUB_BORROW(r4, MP_DIGIT_MAX, r4, carry, carry);
213 MP_SUB_BORROW(r5, MP_DIGIT_MAX, r5, carry, carry);
214 MP_SUB_BORROW(r6, -(r8_d+1), r6, carry, carry);
215 MP_SUB_BORROW(r7, (r8_d-1), r7, carry, carry);
216 r8 = -carry;
217 }
218 if (a != r) {
219 MP_CHECKOK(s_mp_pad(r,8));
220 }
221 MP_SIGN(r) = MP_ZPOS;
222 MP_USED(r) = 8;
223
224 MP_DIGIT(r,7) = r7;
225 MP_DIGIT(r,6) = r6;
226 MP_DIGIT(r,5) = r5;
227 MP_DIGIT(r,4) = r4;
228 MP_DIGIT(r,3) = r3;
229 MP_DIGIT(r,2) = r2;
230 MP_DIGIT(r,1) = r1;
231 MP_DIGIT(r,0) = r0;
232
233 /* final reduction if necessary */
234 if ((r7 == MP_DIGIT_MAX) &&
235 ((r6 > 1) || ((r6 == 1) &&
236 (r5 || r4 || r3 ||
237 ((r2 == MP_DIGIT_MAX) && (r1 == MP_DIGIT_MAX)
238 && (r0 == MP_DIGIT_MAX)))))) {
239 MP_CHECKOK(mp_sub(r, &meth->irr, r));
240 }
241 #ifdef notdef
242
243
244 /* smooth the negatives */
245 while (MP_SIGN(r) != MP_ZPOS) {
246 MP_CHECKOK(mp_add(r, &meth->irr, r));
247 }
248 while (MP_USED(r) > 8) {
249 MP_CHECKOK(mp_sub(r, &meth->irr, r));
250 }
251
252 /* final reduction if necessary */
253 if (MP_DIGIT(r,7) >= MP_DIGIT(&meth->irr,7)) {
254 if (mp_cmp(r,&meth->irr) != MP_LT) {
255 MP_CHECKOK(mp_sub(r, &meth->irr, r));
256 }
257 }
258 #endif
259 s_mp_clamp(r);
260 #else
261 switch (a_used) {
262 case 8:
263 a7 = MP_DIGIT(a,7);
264 case 7:
265 a6 = MP_DIGIT(a,6);
266 case 6:
267 a5 = MP_DIGIT(a,5);
268 case 5:
269 a4 = MP_DIGIT(a,4);
270 }
271 a7l = a7 << 32;
272 a7h = a7 >> 32;
273 a6l = a6 << 32;
274 a6h = a6 >> 32;
275 a5l = a5 << 32;
276 a5h = a5 >> 32;
277 a4l = a4 << 32;
278 a4h = a4 >> 32;
279 r3 = MP_DIGIT(a,3);
280 r2 = MP_DIGIT(a,2);
281 r1 = MP_DIGIT(a,1);
282 r0 = MP_DIGIT(a,0);
283
284 /* sum 1 */
285 MP_ADD_CARRY_ZERO(r1, a5h << 32, r1, carry);
286 MP_ADD_CARRY(r2, a6, r2, carry, carry);
287 MP_ADD_CARRY(r3, a7, r3, carry, carry);
288 r4 = carry;
289 MP_ADD_CARRY_ZERO(r1, a5h << 32, r1, carry);
290 MP_ADD_CARRY(r2, a6, r2, carry, carry);
291 MP_ADD_CARRY(r3, a7, r3, carry, carry);
292 r4 += carry;
293 /* sum 2 */
294 MP_ADD_CARRY_ZERO(r1, a6l, r1, carry);
295 MP_ADD_CARRY(r2, a6h | a7l, r2, carry, carry);
296 MP_ADD_CARRY(r3, a7h, r3, carry, carry);
297 r4 += carry;
298 MP_ADD_CARRY_ZERO(r1, a6l, r1, carry);
299 MP_ADD_CARRY(r2, a6h | a7l, r2, carry, carry);
300 MP_ADD_CARRY(r3, a7h, r3, carry, carry);
301 r4 += carry;
302
303 /* sum 3 */
304 MP_ADD_CARRY_ZERO(r0, a4, r0, carry);
305 MP_ADD_CARRY(r1, a5l >> 32, r1, carry, carry);
306 MP_ADD_CARRY(r2, 0, r2, carry, carry);
307 MP_ADD_CARRY(r3, a7, r3, carry, carry);
308 r4 += carry;
309 /* sum 4 */
310 MP_ADD_CARRY_ZERO(r0, a4h | a5l, r0, carry);
311 MP_ADD_CARRY(r1, a5h|(a6h<<32), r1, carry, carry);
312 MP_ADD_CARRY(r2, a7, r2, carry, carry);
313 MP_ADD_CARRY(r3, a6h | a4l, r3, carry, carry);
314 r4 += carry;
315 /* diff 5 */
316 MP_SUB_BORROW(r0, a5h | a6l, r0, 0, carry);
317 MP_SUB_BORROW(r1, a6h, r1, carry, carry);
318 MP_SUB_BORROW(r2, 0, r2, carry, carry);
319 MP_SUB_BORROW(r3, (a4l>>32)|a5l,r3, carry, carry);
320 r4 -= carry;
321 /* diff 6 */
322 MP_SUB_BORROW(r0, a6, r0, 0, carry);
323 MP_SUB_BORROW(r1, a7, r1, carry, carry);
324 MP_SUB_BORROW(r2, 0, r2, carry, carry);
325 MP_SUB_BORROW(r3, a4h|(a5h<<32),r3, carry, carry);
326 r4 -= carry;
327 /* diff 7 */
328 MP_SUB_BORROW(r0, a6h|a7l, r0, 0, carry);
329 MP_SUB_BORROW(r1, a7h|a4l, r1, carry, carry);
330 MP_SUB_BORROW(r2, a4h|a5l, r2, carry, carry);
331 MP_SUB_BORROW(r3, a6l, r3, carry, carry);
332 r4 -= carry;
333 /* diff 8 */
334 MP_SUB_BORROW(r0, a7, r0, 0, carry);
335 MP_SUB_BORROW(r1, a4h<<32, r1, carry, carry);
336 MP_SUB_BORROW(r2, a5, r2, carry, carry);
337 MP_SUB_BORROW(r3, a6h<<32, r3, carry, carry);
338 r4 -= carry;
339
340 /* reduce the overflows */
341 while (r4 > 0) {
342 mp_digit r4_long = r4;
343 mp_digit r4l = (r4_long << 32);
344 MP_ADD_CARRY_ZERO(r0, r4_long, r0, carry);
345 MP_ADD_CARRY(r1, -r4l, r1, carry, carry);
346 MP_ADD_CARRY(r2, MP_DIGIT_MAX, r2, carry, carry);
347 MP_ADD_CARRY(r3, r4l-r4_long-1,r3, carry, carry);
348 r4 = carry;
349 }
350
351 /* reduce the underflows */
352 while (r4 < 0) {
353 mp_digit r4_long = -r4;
354 mp_digit r4l = (r4_long << 32);
355 MP_SUB_BORROW(r0, r4_long, r0, 0, carry);
356 MP_SUB_BORROW(r1, -r4l, r1, carry, carry);
357 MP_SUB_BORROW(r2, MP_DIGIT_MAX, r2, carry, carry);
358 MP_SUB_BORROW(r3, r4l-r4_long-1,r3, carry, carry);
359 r4 = -carry;
360 }
361
362 if (a != r) {
363 MP_CHECKOK(s_mp_pad(r,4));
364 }
365 MP_SIGN(r) = MP_ZPOS;
366 MP_USED(r) = 4;
367
368 MP_DIGIT(r,3) = r3;
369 MP_DIGIT(r,2) = r2;
370 MP_DIGIT(r,1) = r1;
371 MP_DIGIT(r,0) = r0;
372
373 /* final reduction if necessary */
374 if ((r3 > 0xFFFFFFFF00000001ULL) ||
375 ((r3 == 0xFFFFFFFF00000001ULL) &&
376 (r2 || (r1 >> 32)||
377 (r1 == 0xFFFFFFFFULL && r0 == MP_DIGIT_MAX)))) {
378 /* very rare, just use mp_sub */
379 MP_CHECKOK(mp_sub(r, &meth->irr, r));
380 }
381
382 s_mp_clamp(r);
383 #endif
384 }
385
386 CLEANUP:
387 return res;
388 }
389
390 /* Compute the square of polynomial a, reduce modulo p256. Store the
391 * result in r. r could be a. Uses optimized modular reduction for p256.
392 */
393 mp_err
ec_GFp_nistp256_sqr(const mp_int * a,mp_int * r,const GFMethod * meth)394 ec_GFp_nistp256_sqr(const mp_int *a, mp_int *r, const GFMethod *meth)
395 {
396 mp_err res = MP_OKAY;
397
398 MP_CHECKOK(mp_sqr(a, r));
399 MP_CHECKOK(ec_GFp_nistp256_mod(r, r, meth));
400 CLEANUP:
401 return res;
402 }
403
404 /* Compute the product of two polynomials a and b, reduce modulo p256.
405 * Store the result in r. r could be a or b; a could be b. Uses
406 * optimized modular reduction for p256. */
407 mp_err
ec_GFp_nistp256_mul(const mp_int * a,const mp_int * b,mp_int * r,const GFMethod * meth)408 ec_GFp_nistp256_mul(const mp_int *a, const mp_int *b, mp_int *r,
409 const GFMethod *meth)
410 {
411 mp_err res = MP_OKAY;
412
413 MP_CHECKOK(mp_mul(a, b, r));
414 MP_CHECKOK(ec_GFp_nistp256_mod(r, r, meth));
415 CLEANUP:
416 return res;
417 }
418
419 /* Wire in fast field arithmetic and precomputation of base point for
420 * named curves. */
421 mp_err
ec_group_set_gfp256(ECGroup * group,ECCurveName name)422 ec_group_set_gfp256(ECGroup *group, ECCurveName name)
423 {
424 if (name == ECCurve_NIST_P256) {
425 group->meth->field_mod = &ec_GFp_nistp256_mod;
426 group->meth->field_mul = &ec_GFp_nistp256_mul;
427 group->meth->field_sqr = &ec_GFp_nistp256_sqr;
428 }
429 return MP_OKAY;
430 }
431