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 #ifdef _KERNEL
46 #include <sys/types.h>
47 #include <sys/systm.h>
48 #include <sys/param.h>
49 #include <sys/modctl.h>
50 #include <sys/ddi.h>
51 #include <sys/crypto/spi.h>
52 #include <sys/sysmacros.h>
53 #include <sys/strsun.h>
54 #include <sys/md5.h>
55 #include <sys/sha1.h>
56 #include <sys/sha2.h>
57 #include <sys/random.h>
58 #include <sys/conf.h>
59 #include <sys/devops.h>
60 #include <sys/sunddi.h>
61 #include <sys/varargs.h>
62 #include <sys/kmem.h>
63 #include <sys/kstat.h>
64 #include <sys/crypto/common.h>
65 #else
66 #include <stdio.h>
67 #include <string.h>
68 #include <strings.h>
69 #include <assert.h>
70 #include <time.h>
71 #include <sys/time.h>
72 #include <sys/resource.h>
73 #endif /* _KERNEL */
74
75 #include "mpi.h"
76 #include "mplogic.h"
77 #include "mpprime.h"
78 #include "ecl.h"
79 #include "ecl-curve.h"
80 #include "ecp.h"
81 #include "ecc_impl.h"
82 #include "ec.h"
83
84 #ifndef KM_SLEEP
85 #define KM_SLEEP 0
86 #endif
87
88 #ifndef _KERNEL
89 /* Time k repetitions of operation op. */
90 #define M_TimeOperation(op, k) { \
91 double dStart, dNow, dUserTime; \
92 struct rusage ru; \
93 int i; \
94 getrusage(RUSAGE_SELF, &ru); \
95 dStart = (double)ru.ru_utime.tv_sec+(double)ru.ru_utime.tv_usec*0.000001; \
96 for (i = 0; i < k; i++) { \
97 { op; } \
98 }; \
99 getrusage(RUSAGE_SELF, &ru); \
100 dNow = (double)ru.ru_utime.tv_sec+(double)ru.ru_utime.tv_usec*0.000001; \
101 dUserTime = dNow-dStart; \
102 if (dUserTime) printf(" %-45s k: %6i, t: %6.2f sec\n", #op, k, dUserTime); \
103 }
104 #else
105 #define M_TimeOperation(op, k)
106 #endif
107
108 /* Test curve using generic field arithmetic. */
109 #define ECTEST_GENERIC_GFP(name_c, name) \
110 printf("Testing %s using generic implementation...\n", name_c); \
111 params = EC_GetNamedCurveParams(name, KM_SLEEP); \
112 if (params == NULL) { \
113 printf(" Error: could not construct params.\n"); \
114 res = MP_NO; \
115 goto CLEANUP; \
116 } \
117 ECGroup_free(group); \
118 group = ECGroup_fromHex(params, KM_SLEEP); \
119 if (group == NULL) { \
120 printf(" Error: could not construct group.\n"); \
121 res = MP_NO; \
122 goto CLEANUP; \
123 } \
124 MP_CHECKOK( ectest_curve_GFp(group, ectestPrint, ectestTime, 1, KM_SLEEP) ); \
125 printf("... okay.\n");
126
127 /* Test curve using specific field arithmetic. */
128 #define ECTEST_NAMED_GFP(name_c, name) \
129 printf("Testing %s using specific implementation...\n", name_c); \
130 ECGroup_free(group); \
131 group = ECGroup_fromName(name, KM_SLEEP); \
132 if (group == NULL) { \
133 printf(" Warning: could not construct group.\n"); \
134 printf("... failed; continuing with remaining tests.\n"); \
135 } else { \
136 MP_CHECKOK( ectest_curve_GFp(group, ectestPrint, ectestTime, 0, KM_SLEEP) ); \
137 printf("... okay.\n"); \
138 }
139
140 /* Performs basic tests of elliptic curve cryptography over prime fields.
141 * If tests fail, then it prints an error message, aborts, and returns an
142 * error code. Otherwise, returns 0. */
143 int
ectest_curve_GFp(ECGroup * group,int ectestPrint,int ectestTime,int generic,int kmflag)144 ectest_curve_GFp(ECGroup *group, int ectestPrint, int ectestTime,
145 int generic, int kmflag)
146 {
147
148 mp_int one, order_1, gx, gy, rx, ry, n;
149 int size;
150 mp_err res;
151 char s[1000];
152
153 /* initialize values */
154 MP_CHECKOK(mp_init(&one, kmflag));
155 MP_CHECKOK(mp_init(&order_1, kmflag));
156 MP_CHECKOK(mp_init(&gx, kmflag));
157 MP_CHECKOK(mp_init(&gy, kmflag));
158 MP_CHECKOK(mp_init(&rx, kmflag));
159 MP_CHECKOK(mp_init(&ry, kmflag));
160 MP_CHECKOK(mp_init(&n, kmflag));
161
162 MP_CHECKOK(mp_set_int(&one, 1));
163 MP_CHECKOK(mp_sub(&group->order, &one, &order_1));
164
165 /* encode base point */
166 if (group->meth->field_dec) {
167 MP_CHECKOK(group->meth->field_dec(&group->genx, &gx, group->meth));
168 MP_CHECKOK(group->meth->field_dec(&group->geny, &gy, group->meth));
169 } else {
170 MP_CHECKOK(mp_copy(&group->genx, &gx));
171 MP_CHECKOK(mp_copy(&group->geny, &gy));
172 }
173 if (ectestPrint) {
174 /* output base point */
175 printf(" base point P:\n");
176 MP_CHECKOK(mp_toradix(&gx, s, 16));
177 printf(" %s\n", s);
178 MP_CHECKOK(mp_toradix(&gy, s, 16));
179 printf(" %s\n", s);
180 if (group->meth->field_enc) {
181 printf(" base point P (encoded):\n");
182 MP_CHECKOK(mp_toradix(&group->genx, s, 16));
183 printf(" %s\n", s);
184 MP_CHECKOK(mp_toradix(&group->geny, s, 16));
185 printf(" %s\n", s);
186 }
187 }
188
189 #ifdef ECL_ENABLE_GFP_PT_MUL_AFF
190 /* multiply base point by order - 1 and check for negative of base
191 * point */
192 MP_CHECKOK(ec_GFp_pt_mul_aff
193 (&order_1, &group->genx, &group->geny, &rx, &ry, group));
194 if (ectestPrint) {
195 printf(" (order-1)*P (affine):\n");
196 MP_CHECKOK(mp_toradix(&rx, s, 16));
197 printf(" %s\n", s);
198 MP_CHECKOK(mp_toradix(&ry, s, 16));
199 printf(" %s\n", s);
200 }
201 MP_CHECKOK(group->meth->field_neg(&ry, &ry, group->meth));
202 if ((mp_cmp(&rx, &group->genx) != 0)
203 || (mp_cmp(&ry, &group->geny) != 0)) {
204 printf(" Error: invalid result (expected (- base point)).\n");
205 res = MP_NO;
206 goto CLEANUP;
207 }
208 #endif
209
210 #ifdef ECL_ENABLE_GFP_PT_MUL_AFF
211 /* multiply base point by order - 1 and check for negative of base
212 * point */
213 MP_CHECKOK(ec_GFp_pt_mul_jac
214 (&order_1, &group->genx, &group->geny, &rx, &ry, group));
215 if (ectestPrint) {
216 printf(" (order-1)*P (jacobian):\n");
217 MP_CHECKOK(mp_toradix(&rx, s, 16));
218 printf(" %s\n", s);
219 MP_CHECKOK(mp_toradix(&ry, s, 16));
220 printf(" %s\n", s);
221 }
222 MP_CHECKOK(group->meth->field_neg(&ry, &ry, group->meth));
223 if ((mp_cmp(&rx, &group->genx) != 0)
224 || (mp_cmp(&ry, &group->geny) != 0)) {
225 printf(" Error: invalid result (expected (- base point)).\n");
226 res = MP_NO;
227 goto CLEANUP;
228 }
229 #endif
230
231 /* multiply base point by order - 1 and check for negative of base
232 * point */
233 MP_CHECKOK(ECPoint_mul(group, &order_1, NULL, NULL, &rx, &ry));
234 if (ectestPrint) {
235 printf(" (order-1)*P (ECPoint_mul):\n");
236 MP_CHECKOK(mp_toradix(&rx, s, 16));
237 printf(" %s\n", s);
238 MP_CHECKOK(mp_toradix(&ry, s, 16));
239 printf(" %s\n", s);
240 }
241 MP_CHECKOK(mp_submod(&group->meth->irr, &ry, &group->meth->irr, &ry));
242 if ((mp_cmp(&rx, &gx) != 0) || (mp_cmp(&ry, &gy) != 0)) {
243 printf(" Error: invalid result (expected (- base point)).\n");
244 res = MP_NO;
245 goto CLEANUP;
246 }
247
248 /* multiply base point by order - 1 and check for negative of base
249 * point */
250 MP_CHECKOK(ECPoint_mul(group, &order_1, &gx, &gy, &rx, &ry));
251 if (ectestPrint) {
252 printf(" (order-1)*P (ECPoint_mul):\n");
253 MP_CHECKOK(mp_toradix(&rx, s, 16));
254 printf(" %s\n", s);
255 MP_CHECKOK(mp_toradix(&ry, s, 16));
256 printf(" %s\n", s);
257 }
258 MP_CHECKOK(mp_submod(&group->meth->irr, &ry, &group->meth->irr, &ry));
259 if ((mp_cmp(&rx, &gx) != 0) || (mp_cmp(&ry, &gy) != 0)) {
260 printf(" Error: invalid result (expected (- base point)).\n");
261 res = MP_NO;
262 goto CLEANUP;
263 }
264
265 #ifdef ECL_ENABLE_GFP_PT_MUL_AFF
266 /* multiply base point by order and check for point at infinity */
267 MP_CHECKOK(ec_GFp_pt_mul_aff
268 (&group->order, &group->genx, &group->geny, &rx, &ry,
269 group));
270 if (ectestPrint) {
271 printf(" (order)*P (affine):\n");
272 MP_CHECKOK(mp_toradix(&rx, s, 16));
273 printf(" %s\n", s);
274 MP_CHECKOK(mp_toradix(&ry, s, 16));
275 printf(" %s\n", s);
276 }
277 if (ec_GFp_pt_is_inf_aff(&rx, &ry) != MP_YES) {
278 printf(" Error: invalid result (expected point at infinity).\n");
279 res = MP_NO;
280 goto CLEANUP;
281 }
282 #endif
283
284 #ifdef ECL_ENABLE_GFP_PT_MUL_JAC
285 /* multiply base point by order and check for point at infinity */
286 MP_CHECKOK(ec_GFp_pt_mul_jac
287 (&group->order, &group->genx, &group->geny, &rx, &ry,
288 group));
289 if (ectestPrint) {
290 printf(" (order)*P (jacobian):\n");
291 MP_CHECKOK(mp_toradix(&rx, s, 16));
292 printf(" %s\n", s);
293 MP_CHECKOK(mp_toradix(&ry, s, 16));
294 printf(" %s\n", s);
295 }
296 if (ec_GFp_pt_is_inf_aff(&rx, &ry) != MP_YES) {
297 printf(" Error: invalid result (expected point at infinity).\n");
298 res = MP_NO;
299 goto CLEANUP;
300 }
301 #endif
302
303 /* multiply base point by order and check for point at infinity */
304 MP_CHECKOK(ECPoint_mul(group, &group->order, NULL, NULL, &rx, &ry));
305 if (ectestPrint) {
306 printf(" (order)*P (ECPoint_mul):\n");
307 MP_CHECKOK(mp_toradix(&rx, s, 16));
308 printf(" %s\n", s);
309 MP_CHECKOK(mp_toradix(&ry, s, 16));
310 printf(" %s\n", s);
311 }
312 if (ec_GFp_pt_is_inf_aff(&rx, &ry) != MP_YES) {
313 printf(" Error: invalid result (expected point at infinity).\n");
314 res = MP_NO;
315 goto CLEANUP;
316 }
317
318 /* multiply base point by order and check for point at infinity */
319 MP_CHECKOK(ECPoint_mul(group, &group->order, &gx, &gy, &rx, &ry));
320 if (ectestPrint) {
321 printf(" (order)*P (ECPoint_mul):\n");
322 MP_CHECKOK(mp_toradix(&rx, s, 16));
323 printf(" %s\n", s);
324 MP_CHECKOK(mp_toradix(&ry, s, 16));
325 printf(" %s\n", s);
326 }
327 if (ec_GFp_pt_is_inf_aff(&rx, &ry) != MP_YES) {
328 printf(" Error: invalid result (expected point at infinity).\n");
329 res = MP_NO;
330 goto CLEANUP;
331 }
332
333 /* check that (order-1)P + (order-1)P + P == (order-1)P */
334 MP_CHECKOK(ECPoints_mul
335 (group, &order_1, &order_1, &gx, &gy, &rx, &ry));
336 MP_CHECKOK(ECPoints_mul(group, &one, &one, &rx, &ry, &rx, &ry));
337 if (ectestPrint) {
338 printf
339 (" (order-1)*P + (order-1)*P + P == (order-1)*P (ECPoints_mul):\n");
340 MP_CHECKOK(mp_toradix(&rx, s, 16));
341 printf(" %s\n", s);
342 MP_CHECKOK(mp_toradix(&ry, s, 16));
343 printf(" %s\n", s);
344 }
345 MP_CHECKOK(mp_submod(&group->meth->irr, &ry, &group->meth->irr, &ry));
346 if ((mp_cmp(&rx, &gx) != 0) || (mp_cmp(&ry, &gy) != 0)) {
347 printf(" Error: invalid result (expected (- base point)).\n");
348 res = MP_NO;
349 goto CLEANUP;
350 }
351
352 /* test validate_point function */
353 if (ECPoint_validate(group, &gx, &gy) != MP_YES) {
354 printf(" Error: validate point on base point failed.\n");
355 res = MP_NO;
356 goto CLEANUP;
357 }
358 MP_CHECKOK(mp_add_d(&gy, 1, &ry));
359 if (ECPoint_validate(group, &gx, &ry) != MP_NO) {
360 printf(" Error: validate point on invalid point passed.\n");
361 res = MP_NO;
362 goto CLEANUP;
363 }
364
365 if (ectestTime) {
366 /* compute random scalar */
367 size = mpl_significant_bits(&group->meth->irr);
368 if (size < MP_OKAY) {
369 goto CLEANUP;
370 }
371 MP_CHECKOK(mpp_random_size(&n, (size + ECL_BITS - 1) / ECL_BITS));
372 MP_CHECKOK(group->meth->field_mod(&n, &n, group->meth));
373 /* timed test */
374 if (generic) {
375 #ifdef ECL_ENABLE_GFP_PT_MUL_AFF
376 M_TimeOperation(MP_CHECKOK
377 (ec_GFp_pt_mul_aff
378 (&n, &group->genx, &group->geny, &rx, &ry,
379 group)), 100);
380 #endif
381 M_TimeOperation(MP_CHECKOK
382 (ECPoint_mul(group, &n, NULL, NULL, &rx, &ry)),
383 100);
384 M_TimeOperation(MP_CHECKOK
385 (ECPoints_mul
386 (group, &n, &n, &gx, &gy, &rx, &ry)), 100);
387 } else {
388 M_TimeOperation(MP_CHECKOK
389 (ECPoint_mul(group, &n, NULL, NULL, &rx, &ry)),
390 100);
391 M_TimeOperation(MP_CHECKOK
392 (ECPoint_mul(group, &n, &gx, &gy, &rx, &ry)),
393 100);
394 M_TimeOperation(MP_CHECKOK
395 (ECPoints_mul
396 (group, &n, &n, &gx, &gy, &rx, &ry)), 100);
397 }
398 }
399
400 CLEANUP:
401 mp_clear(&one);
402 mp_clear(&order_1);
403 mp_clear(&gx);
404 mp_clear(&gy);
405 mp_clear(&rx);
406 mp_clear(&ry);
407 mp_clear(&n);
408 if (res != MP_OKAY) {
409 #ifdef _KERNEL
410 printf(" Error: exiting with error value 0x%x\n", res);
411 #else
412 printf(" Error: exiting with error value %i\n", res);
413 #endif
414 }
415 return res;
416 }
417
418 /* Performs tests of elliptic curve cryptography over prime fields If
419 * tests fail, then it prints an error message, aborts, and returns an
420 * error code. Otherwise, returns 0. */
421 int
ecp_test()422 ecp_test()
423 {
424
425 int ectestTime = 0;
426 int ectestPrint = 0;
427 int i;
428 ECGroup *group = NULL;
429 ECCurveParams *params = NULL;
430 mp_err res;
431
432 /* generic arithmetic tests */
433 ECTEST_GENERIC_GFP("SECP-160R1", ECCurve_SECG_PRIME_160R1);
434
435 /* specific arithmetic tests */
436 ECTEST_NAMED_GFP("NIST-P192", ECCurve_NIST_P192);
437 ECTEST_NAMED_GFP("NIST-P224", ECCurve_NIST_P224);
438 ECTEST_NAMED_GFP("NIST-P256", ECCurve_NIST_P256);
439 ECTEST_NAMED_GFP("NIST-P384", ECCurve_NIST_P384);
440 ECTEST_NAMED_GFP("NIST-P521", ECCurve_NIST_P521);
441 ECTEST_NAMED_GFP("ANSI X9.62 PRIME192v1", ECCurve_X9_62_PRIME_192V1);
442 ECTEST_NAMED_GFP("ANSI X9.62 PRIME192v2", ECCurve_X9_62_PRIME_192V2);
443 ECTEST_NAMED_GFP("ANSI X9.62 PRIME192v3", ECCurve_X9_62_PRIME_192V3);
444 ECTEST_NAMED_GFP("ANSI X9.62 PRIME239v1", ECCurve_X9_62_PRIME_239V1);
445 ECTEST_NAMED_GFP("ANSI X9.62 PRIME239v2", ECCurve_X9_62_PRIME_239V2);
446 ECTEST_NAMED_GFP("ANSI X9.62 PRIME239v3", ECCurve_X9_62_PRIME_239V3);
447 ECTEST_NAMED_GFP("ANSI X9.62 PRIME256v1", ECCurve_X9_62_PRIME_256V1);
448 ECTEST_NAMED_GFP("SECP-112R1", ECCurve_SECG_PRIME_112R1);
449 ECTEST_NAMED_GFP("SECP-112R2", ECCurve_SECG_PRIME_112R2);
450 ECTEST_NAMED_GFP("SECP-128R1", ECCurve_SECG_PRIME_128R1);
451 ECTEST_NAMED_GFP("SECP-128R2", ECCurve_SECG_PRIME_128R2);
452 ECTEST_NAMED_GFP("SECP-160K1", ECCurve_SECG_PRIME_160K1);
453 ECTEST_NAMED_GFP("SECP-160R1", ECCurve_SECG_PRIME_160R1);
454 ECTEST_NAMED_GFP("SECP-160R2", ECCurve_SECG_PRIME_160R2);
455 ECTEST_NAMED_GFP("SECP-192K1", ECCurve_SECG_PRIME_192K1);
456 ECTEST_NAMED_GFP("SECP-192R1", ECCurve_SECG_PRIME_192R1);
457 ECTEST_NAMED_GFP("SECP-224K1", ECCurve_SECG_PRIME_224K1);
458 ECTEST_NAMED_GFP("SECP-224R1", ECCurve_SECG_PRIME_224R1);
459 ECTEST_NAMED_GFP("SECP-256K1", ECCurve_SECG_PRIME_256K1);
460 ECTEST_NAMED_GFP("SECP-256R1", ECCurve_SECG_PRIME_256R1);
461 ECTEST_NAMED_GFP("SECP-384R1", ECCurve_SECG_PRIME_384R1);
462 ECTEST_NAMED_GFP("SECP-521R1", ECCurve_SECG_PRIME_521R1);
463 ECTEST_NAMED_GFP("WTLS-6 (112)", ECCurve_WTLS_6);
464 ECTEST_NAMED_GFP("WTLS-7 (160)", ECCurve_WTLS_7);
465 ECTEST_NAMED_GFP("WTLS-8 (112)", ECCurve_WTLS_8);
466 ECTEST_NAMED_GFP("WTLS-9 (160)", ECCurve_WTLS_9);
467 ECTEST_NAMED_GFP("WTLS-12 (224)", ECCurve_WTLS_12);
468
469 CLEANUP:
470 EC_FreeCurveParams(params);
471 ECGroup_free(group);
472 if (res != MP_OKAY) {
473 #ifdef _KERNEL
474 printf("Error: exiting with error value 0x%x\n", res);
475 #else
476 printf("Error: exiting with error value %i\n", res);
477 #endif
478 }
479 return res;
480 }
481