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>, Sun Microsystems Laboratories
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 #define ECP224_DIGITS ECL_CURVE_DIGITS(224)
47
48 /* Fast modular reduction for p224 = 2^224 - 2^96 + 1. a can be r. Uses
49 * algorithm 7 from Brown, Hankerson, Lopez, Menezes. Software
50 * Implementation of the NIST Elliptic Curves over Prime Fields. */
51 mp_err
ec_GFp_nistp224_mod(const mp_int * a,mp_int * r,const GFMethod * meth)52 ec_GFp_nistp224_mod(const mp_int *a, mp_int *r, const GFMethod *meth)
53 {
54 mp_err res = MP_OKAY;
55 mp_size a_used = MP_USED(a);
56
57 int r3b;
58 mp_digit carry;
59 #ifdef ECL_THIRTY_TWO_BIT
60 mp_digit a6a = 0, a6b = 0,
61 a5a = 0, a5b = 0, a4a = 0, a4b = 0, a3a = 0, a3b = 0;
62 mp_digit r0a, r0b, r1a, r1b, r2a, r2b, r3a;
63 #else
64 mp_digit a6 = 0, a5 = 0, a4 = 0, a3b = 0, a5a = 0;
65 mp_digit a6b = 0, a6a_a5b = 0, a5b = 0, a5a_a4b = 0, a4a_a3b = 0;
66 mp_digit r0, r1, r2, r3;
67 #endif
68
69 /* reduction not needed if a is not larger than field size */
70 if (a_used < ECP224_DIGITS) {
71 if (a == r) return MP_OKAY;
72 return mp_copy(a, r);
73 }
74 /* for polynomials larger than twice the field size, use regular
75 * reduction */
76 if (a_used > ECL_CURVE_DIGITS(224*2)) {
77 MP_CHECKOK(mp_mod(a, &meth->irr, r));
78 } else {
79 #ifdef ECL_THIRTY_TWO_BIT
80 /* copy out upper words of a */
81 switch (a_used) {
82 case 14:
83 a6b = MP_DIGIT(a, 13);
84 case 13:
85 a6a = MP_DIGIT(a, 12);
86 case 12:
87 a5b = MP_DIGIT(a, 11);
88 case 11:
89 a5a = MP_DIGIT(a, 10);
90 case 10:
91 a4b = MP_DIGIT(a, 9);
92 case 9:
93 a4a = MP_DIGIT(a, 8);
94 case 8:
95 a3b = MP_DIGIT(a, 7);
96 }
97 r3a = MP_DIGIT(a, 6);
98 r2b= MP_DIGIT(a, 5);
99 r2a= MP_DIGIT(a, 4);
100 r1b = MP_DIGIT(a, 3);
101 r1a = MP_DIGIT(a, 2);
102 r0b = MP_DIGIT(a, 1);
103 r0a = MP_DIGIT(a, 0);
104
105
106 /* implement r = (a3a,a2,a1,a0)
107 +(a5a, a4,a3b, 0)
108 +( 0, a6,a5b, 0)
109 -( 0 0, 0|a6b, a6a|a5b )
110 -( a6b, a6a|a5b, a5a|a4b, a4a|a3b ) */
111 MP_ADD_CARRY (r1b, a3b, r1b, 0, carry);
112 MP_ADD_CARRY (r2a, a4a, r2a, carry, carry);
113 MP_ADD_CARRY (r2b, a4b, r2b, carry, carry);
114 MP_ADD_CARRY (r3a, a5a, r3a, carry, carry);
115 r3b = carry;
116 MP_ADD_CARRY (r1b, a5b, r1b, 0, carry);
117 MP_ADD_CARRY (r2a, a6a, r2a, carry, carry);
118 MP_ADD_CARRY (r2b, a6b, r2b, carry, carry);
119 MP_ADD_CARRY (r3a, 0, r3a, carry, carry);
120 r3b += carry;
121 MP_SUB_BORROW(r0a, a3b, r0a, 0, carry);
122 MP_SUB_BORROW(r0b, a4a, r0b, carry, carry);
123 MP_SUB_BORROW(r1a, a4b, r1a, carry, carry);
124 MP_SUB_BORROW(r1b, a5a, r1b, carry, carry);
125 MP_SUB_BORROW(r2a, a5b, r2a, carry, carry);
126 MP_SUB_BORROW(r2b, a6a, r2b, carry, carry);
127 MP_SUB_BORROW(r3a, a6b, r3a, carry, carry);
128 r3b -= carry;
129 MP_SUB_BORROW(r0a, a5b, r0a, 0, carry);
130 MP_SUB_BORROW(r0b, a6a, r0b, carry, carry);
131 MP_SUB_BORROW(r1a, a6b, r1a, carry, carry);
132 if (carry) {
133 MP_SUB_BORROW(r1b, 0, r1b, carry, carry);
134 MP_SUB_BORROW(r2a, 0, r2a, carry, carry);
135 MP_SUB_BORROW(r2b, 0, r2b, carry, carry);
136 MP_SUB_BORROW(r3a, 0, r3a, carry, carry);
137 r3b -= carry;
138 }
139
140 while (r3b > 0) {
141 int tmp;
142 MP_ADD_CARRY(r1b, r3b, r1b, 0, carry);
143 if (carry) {
144 MP_ADD_CARRY(r2a, 0, r2a, carry, carry);
145 MP_ADD_CARRY(r2b, 0, r2b, carry, carry);
146 MP_ADD_CARRY(r3a, 0, r3a, carry, carry);
147 }
148 tmp = carry;
149 MP_SUB_BORROW(r0a, r3b, r0a, 0, carry);
150 if (carry) {
151 MP_SUB_BORROW(r0b, 0, r0b, carry, carry);
152 MP_SUB_BORROW(r1a, 0, r1a, carry, carry);
153 MP_SUB_BORROW(r1b, 0, r1b, carry, carry);
154 MP_SUB_BORROW(r2a, 0, r2a, carry, carry);
155 MP_SUB_BORROW(r2b, 0, r2b, carry, carry);
156 MP_SUB_BORROW(r3a, 0, r3a, carry, carry);
157 tmp -= carry;
158 }
159 r3b = tmp;
160 }
161
162 while (r3b < 0) {
163 mp_digit maxInt = MP_DIGIT_MAX;
164 MP_ADD_CARRY (r0a, 1, r0a, 0, carry);
165 MP_ADD_CARRY (r0b, 0, r0b, carry, carry);
166 MP_ADD_CARRY (r1a, 0, r1a, carry, carry);
167 MP_ADD_CARRY (r1b, maxInt, r1b, carry, carry);
168 MP_ADD_CARRY (r2a, maxInt, r2a, carry, carry);
169 MP_ADD_CARRY (r2b, maxInt, r2b, carry, carry);
170 MP_ADD_CARRY (r3a, maxInt, r3a, carry, carry);
171 r3b += carry;
172 }
173 /* check for final reduction */
174 /* now the only way we are over is if the top 4 words are all ones */
175 if ((r3a == MP_DIGIT_MAX) && (r2b == MP_DIGIT_MAX)
176 && (r2a == MP_DIGIT_MAX) && (r1b == MP_DIGIT_MAX) &&
177 ((r1a != 0) || (r0b != 0) || (r0a != 0)) ) {
178 /* one last subraction */
179 MP_SUB_BORROW(r0a, 1, r0a, 0, carry);
180 MP_SUB_BORROW(r0b, 0, r0b, carry, carry);
181 MP_SUB_BORROW(r1a, 0, r1a, carry, carry);
182 r1b = r2a = r2b = r3a = 0;
183 }
184
185
186 if (a != r) {
187 MP_CHECKOK(s_mp_pad(r, 7));
188 }
189 /* set the lower words of r */
190 MP_SIGN(r) = MP_ZPOS;
191 MP_USED(r) = 7;
192 MP_DIGIT(r, 6) = r3a;
193 MP_DIGIT(r, 5) = r2b;
194 MP_DIGIT(r, 4) = r2a;
195 MP_DIGIT(r, 3) = r1b;
196 MP_DIGIT(r, 2) = r1a;
197 MP_DIGIT(r, 1) = r0b;
198 MP_DIGIT(r, 0) = r0a;
199 #else
200 /* copy out upper words of a */
201 switch (a_used) {
202 case 7:
203 a6 = MP_DIGIT(a, 6);
204 a6b = a6 >> 32;
205 a6a_a5b = a6 << 32;
206 case 6:
207 a5 = MP_DIGIT(a, 5);
208 a5b = a5 >> 32;
209 a6a_a5b |= a5b;
210 a5b = a5b << 32;
211 a5a_a4b = a5 << 32;
212 a5a = a5 & 0xffffffff;
213 case 5:
214 a4 = MP_DIGIT(a, 4);
215 a5a_a4b |= a4 >> 32;
216 a4a_a3b = a4 << 32;
217 case 4:
218 a3b = MP_DIGIT(a, 3) >> 32;
219 a4a_a3b |= a3b;
220 a3b = a3b << 32;
221 }
222
223 r3 = MP_DIGIT(a, 3) & 0xffffffff;
224 r2 = MP_DIGIT(a, 2);
225 r1 = MP_DIGIT(a, 1);
226 r0 = MP_DIGIT(a, 0);
227
228 /* implement r = (a3a,a2,a1,a0)
229 +(a5a, a4,a3b, 0)
230 +( 0, a6,a5b, 0)
231 -( 0 0, 0|a6b, a6a|a5b )
232 -( a6b, a6a|a5b, a5a|a4b, a4a|a3b ) */
233 MP_ADD_CARRY_ZERO (r1, a3b, r1, carry);
234 MP_ADD_CARRY (r2, a4 , r2, carry, carry);
235 MP_ADD_CARRY (r3, a5a, r3, carry, carry);
236 MP_ADD_CARRY_ZERO (r1, a5b, r1, carry);
237 MP_ADD_CARRY (r2, a6 , r2, carry, carry);
238 MP_ADD_CARRY (r3, 0, r3, carry, carry);
239
240 MP_SUB_BORROW(r0, a4a_a3b, r0, 0, carry);
241 MP_SUB_BORROW(r1, a5a_a4b, r1, carry, carry);
242 MP_SUB_BORROW(r2, a6a_a5b, r2, carry, carry);
243 MP_SUB_BORROW(r3, a6b , r3, carry, carry);
244 MP_SUB_BORROW(r0, a6a_a5b, r0, 0, carry);
245 MP_SUB_BORROW(r1, a6b , r1, carry, carry);
246 if (carry) {
247 MP_SUB_BORROW(r2, 0, r2, carry, carry);
248 MP_SUB_BORROW(r3, 0, r3, carry, carry);
249 }
250
251
252 /* if the value is negative, r3 has a 2's complement
253 * high value */
254 r3b = (int)(r3 >>32);
255 while (r3b > 0) {
256 r3 &= 0xffffffff;
257 MP_ADD_CARRY_ZERO(r1,((mp_digit)r3b) << 32, r1, carry);
258 if (carry) {
259 MP_ADD_CARRY(r2, 0, r2, carry, carry);
260 MP_ADD_CARRY(r3, 0, r3, carry, carry);
261 }
262 MP_SUB_BORROW(r0, r3b, r0, 0, carry);
263 if (carry) {
264 MP_SUB_BORROW(r1, 0, r1, carry, carry);
265 MP_SUB_BORROW(r2, 0, r2, carry, carry);
266 MP_SUB_BORROW(r3, 0, r3, carry, carry);
267 }
268 r3b = (int)(r3 >>32);
269 }
270
271 while (r3b < 0) {
272 MP_ADD_CARRY_ZERO (r0, 1, r0, carry);
273 MP_ADD_CARRY (r1, MP_DIGIT_MAX <<32, r1, carry, carry);
274 MP_ADD_CARRY (r2, MP_DIGIT_MAX, r2, carry, carry);
275 MP_ADD_CARRY (r3, MP_DIGIT_MAX >> 32, r3, carry, carry);
276 r3b = (int)(r3 >>32);
277 }
278 /* check for final reduction */
279 /* now the only way we are over is if the top 4 words are all ones */
280 if ((r3 == (MP_DIGIT_MAX >> 32)) && (r2 == MP_DIGIT_MAX)
281 && ((r1 & MP_DIGIT_MAX << 32)== MP_DIGIT_MAX << 32) &&
282 ((r1 != MP_DIGIT_MAX << 32 ) || (r0 != 0)) ) {
283 /* one last subraction */
284 MP_SUB_BORROW(r0, 1, r0, 0, carry);
285 MP_SUB_BORROW(r1, 0, r1, carry, carry);
286 r2 = r3 = 0;
287 }
288
289
290 if (a != r) {
291 MP_CHECKOK(s_mp_pad(r, 4));
292 }
293 /* set the lower words of r */
294 MP_SIGN(r) = MP_ZPOS;
295 MP_USED(r) = 4;
296 MP_DIGIT(r, 3) = r3;
297 MP_DIGIT(r, 2) = r2;
298 MP_DIGIT(r, 1) = r1;
299 MP_DIGIT(r, 0) = r0;
300 #endif
301 }
302
303 CLEANUP:
304 return res;
305 }
306
307 /* Compute the square of polynomial a, reduce modulo p224. Store the
308 * result in r. r could be a. Uses optimized modular reduction for p224.
309 */
310 mp_err
ec_GFp_nistp224_sqr(const mp_int * a,mp_int * r,const GFMethod * meth)311 ec_GFp_nistp224_sqr(const mp_int *a, mp_int *r, const GFMethod *meth)
312 {
313 mp_err res = MP_OKAY;
314
315 MP_CHECKOK(mp_sqr(a, r));
316 MP_CHECKOK(ec_GFp_nistp224_mod(r, r, meth));
317 CLEANUP:
318 return res;
319 }
320
321 /* Compute the product of two polynomials a and b, reduce modulo p224.
322 * Store the result in r. r could be a or b; a could be b. Uses
323 * optimized modular reduction for p224. */
324 mp_err
ec_GFp_nistp224_mul(const mp_int * a,const mp_int * b,mp_int * r,const GFMethod * meth)325 ec_GFp_nistp224_mul(const mp_int *a, const mp_int *b, mp_int *r,
326 const GFMethod *meth)
327 {
328 mp_err res = MP_OKAY;
329
330 MP_CHECKOK(mp_mul(a, b, r));
331 MP_CHECKOK(ec_GFp_nistp224_mod(r, r, meth));
332 CLEANUP:
333 return res;
334 }
335
336 /* Divides two field elements. If a is NULL, then returns the inverse of
337 * b. */
338 mp_err
ec_GFp_nistp224_div(const mp_int * a,const mp_int * b,mp_int * r,const GFMethod * meth)339 ec_GFp_nistp224_div(const mp_int *a, const mp_int *b, mp_int *r,
340 const GFMethod *meth)
341 {
342 mp_err res = MP_OKAY;
343 mp_int t;
344
345 /* If a is NULL, then return the inverse of b, otherwise return a/b. */
346 if (a == NULL) {
347 return mp_invmod(b, &meth->irr, r);
348 } else {
349 /* MPI doesn't support divmod, so we implement it using invmod and
350 * mulmod. */
351 MP_CHECKOK(mp_init(&t, FLAG(b)));
352 MP_CHECKOK(mp_invmod(b, &meth->irr, &t));
353 MP_CHECKOK(mp_mul(a, &t, r));
354 MP_CHECKOK(ec_GFp_nistp224_mod(r, r, meth));
355 CLEANUP:
356 mp_clear(&t);
357 return res;
358 }
359 }
360
361 /* Wire in fast field arithmetic and precomputation of base point for
362 * named curves. */
363 mp_err
ec_group_set_gfp224(ECGroup * group,ECCurveName name)364 ec_group_set_gfp224(ECGroup *group, ECCurveName name)
365 {
366 if (name == ECCurve_NIST_P224) {
367 group->meth->field_mod = &ec_GFp_nistp224_mod;
368 group->meth->field_mul = &ec_GFp_nistp224_mul;
369 group->meth->field_sqr = &ec_GFp_nistp224_sqr;
370 group->meth->field_div = &ec_GFp_nistp224_div;
371 }
372 return MP_OKAY;
373 }
374