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