1 /*
2 * Copyright (C) 2017 - This file is part of libecc project
3 *
4 * Authors:
5 * Ryad BENADJILA <ryadbenadjila@gmail.com>
6 * Arnaud EBALARD <arnaud.ebalard@ssi.gouv.fr>
7 * Jean-Pierre FLORI <jean-pierre.flori@ssi.gouv.fr>
8 *
9 * Contributors:
10 * Nicolas VIVET <nicolas.vivet@ssi.gouv.fr>
11 * Karim KHALFALLAH <karim.khalfallah@ssi.gouv.fr>
12 *
13 * This software is licensed under a dual BSD and GPL v2 license.
14 * See LICENSE file at the root folder of the project.
15 */
16 #include <libecc/libec.h>
17 /* We include the printf external dependency for printf output */
18 #include <libecc/external_deps/print.h>
19 /* We include the time external dependency for performance measurement */
20 #include <libecc/external_deps/time.h>
21
22 /* The followin function picks a random Fp element x, where Fp is the
23 * curve underlying prime field, and computes y in Fp such that:
24 * y^2 = x^3 + ax + b, where a and b are the input elliptic
25 * curve parameters.
26 *
27 * This means that (x, y) are the affine coordinates of a "random"
28 * point on our curve. The function then outputs the projective
29 * coordinates of (x, y), i.e. the triplet (x, y, 1).
30 * PS: all our operations on points are done with projective coordinates.
31 *
32 * Computing y means computing a quadratic residue in Fp, for which we
33 * use the Tonelli-Shanks algorithm implemented in the Fp source example
34 * (fp_square_residue.c).
35 */
36 ATTRIBUTE_WARN_UNUSED_RET int get_random_point_on_curve(ec_params *curve_params, prj_pt *out_point);
get_random_point_on_curve(ec_params * curve_params,prj_pt * out_point)37 int get_random_point_on_curve(ec_params *curve_params, prj_pt *out_point)
38 {
39 nn nn_tmp;
40 int ret, is_oncurve;
41
42 /* Inside our internal representation, curve_params->ec_curve
43 * contains the curve coefficients a and b.
44 * curve_params->ec_fp is the Fp context of the curve.
45 */
46 fp x, y, fp_tmp1, fp_tmp2;
47 fp_ctx_src_t ctx;
48
49 MUST_HAVE((curve_params != NULL), ret, err);
50
51 nn_tmp.magic = WORD(0);
52 x.magic = y.magic = fp_tmp1.magic = fp_tmp2.magic = WORD(0);
53
54 /* Initialize our x value with the curve Fp context */
55 ctx = &(curve_params->ec_fp);
56
57 ret = fp_init(&x, ctx); EG(ret, err);
58 ret = fp_init(&y, ctx); EG(ret, err);
59 ret = fp_init(&fp_tmp1, ctx); EG(ret, err);
60 ret = fp_init(&fp_tmp2, ctx); EG(ret, err);
61
62 ret = nn_init(&nn_tmp, 0); EG(ret, err);
63 ret = nn_set_word_value(&nn_tmp, WORD(3)); EG(ret, err);
64 while (1) {
65 /* Get a random Fp */
66 ret = fp_get_random(&x, ctx); EG(ret, err);
67 ret = fp_copy(&fp_tmp1, &x); EG(ret, err);
68 ret = fp_copy(&fp_tmp2, &x); EG(ret, err);
69 /* Compute x^3 + ax + b */
70 ret = fp_pow(&fp_tmp1, &fp_tmp1, &nn_tmp); EG(ret, err);
71 ret = fp_mul(&fp_tmp2, &fp_tmp2, &(curve_params->ec_curve.a)); EG(ret, err);
72 ret = fp_add(&fp_tmp1, &fp_tmp1, &fp_tmp2); EG(ret, err);
73 ret = fp_add(&fp_tmp1, &fp_tmp1, &(curve_params->ec_curve.b)); EG(ret, err);
74 /*
75 * Get any of the two square roots, corresponding to (x, y)
76 * and (x, -y) both on the curve. If no square root exist,
77 * go to next random Fp.
78 */
79 if (fp_sqrt(&y, &fp_tmp2, &fp_tmp1) == 0) {
80 /* Check that we indeed satisfy the curve equation */
81 ret = is_on_shortw_curve(&x, &y, &(curve_params->ec_curve), &is_oncurve); EG(ret, err);
82 if (!is_oncurve) {
83 /* This should not happen ... */
84 ext_printf("Error: Tonelli-Shanks found a bad "
85 "solution to curve equation ...\n");
86 continue;
87 }
88 break;
89 }
90 }
91 /* Now initialize our point with the coordinates (x, y, 1) */
92 ret = fp_one(&fp_tmp1); EG(ret, err);
93 ret = prj_pt_init_from_coords(out_point, &(curve_params->ec_curve), &x, &y,
94 &fp_tmp1); EG(ret, err);
95
96 err:
97 fp_uninit(&x);
98 fp_uninit(&y);
99 fp_uninit(&fp_tmp1);
100 fp_uninit(&fp_tmp2);
101 nn_uninit(&nn_tmp);
102
103 return ret;
104 }
105
106 #define PERF_SCALAR_MUL 40
107 ATTRIBUTE_WARN_UNUSED_RET int check_curve(const u8 *curve_name);
check_curve(const u8 * curve_name)108 int check_curve(const u8 *curve_name)
109 {
110 unsigned int i;
111 u64 t1, t2;
112 int ret, is_oncurve, isone, iszero;
113
114 nn nn_k;
115 /* libecc internal structure holding the curve parameters */
116 ec_params curve_params;
117 /* libecc internal structure holding projective points on curves */
118 prj_pt A, B, C, D;
119 prj_pt TMP;
120 aff_pt T;
121 u32 len;
122
123 /* Importing a specific curve parameters from the constant static
124 * buffers describing it:
125 * It is possible to import a curves parameters by its name.
126 */
127 const ec_str_params *the_curve_const_parameters;
128
129 nn_k.magic = WORD(0);
130 A.magic = B.magic = C.magic = D.magic = WORD(0);
131 TMP.magic = T.magic = WORD(0);
132
133 MUST_HAVE((curve_name != NULL), ret, err);
134
135 ret = local_strnlen((const char *)curve_name, MAX_CURVE_NAME_LEN, &len); EG(ret, err);
136 len += 1;
137 MUST_HAVE((len < 256), ret, err);
138 ret = ec_get_curve_params_by_name(curve_name,
139 (u8)len, &the_curve_const_parameters); EG(ret, err);
140
141
142 /* Get out if getting the parameters went wrong */
143 if (the_curve_const_parameters == NULL) {
144 ext_printf("Error: error when importing curve %s "
145 "parameters ...\n", curve_name);
146 ret = -1;
147 goto err;
148 }
149 /* Now map the curve parameters to our libecc internal representation */
150 ret = import_params(&curve_params, the_curve_const_parameters); EG(ret, err);
151 /* Get two random points on the curve */
152 ret = get_random_point_on_curve(&curve_params, &A); EG(ret, err);
153 ret = get_random_point_on_curve(&curve_params, &B); EG(ret, err);
154
155 /*
156 * Let's add the two points
157 * C = A + B with regular point addition
158 */
159 ret = prj_pt_add(&C, &A, &B); EG(ret, err);
160
161 /*
162 * Check that the resulting additive point C = A+B is indeed on the
163 * curve.
164 */
165 ret = prj_pt_to_aff(&T, &C); EG(ret, err);
166 ret = prj_pt_is_on_curve(&C, &is_oncurve); EG(ret, err);
167 if (!is_oncurve) {
168 ext_printf("Error: C = A+B is not on the %s curve!\n",
169 curve_params.curve_name);
170 ret = -1;
171 goto err;
172 }
173 ret = aff_pt_is_on_curve(&T, &is_oncurve); EG(ret, err);
174 if (!is_oncurve) {
175 ext_printf("Error: C = A+B is not on the %s curve!\n",
176 curve_params.curve_name);
177 ret = -1;
178 goto err;
179 }
180 /* Same check with doubling
181 * C = 2A = A+A
182 */
183 ret = prj_pt_dbl(&C, &A); EG(ret, err);
184
185 /* Check that the resulting point C = 2A is indeed on the curve.
186 *
187 */
188 ret = prj_pt_to_aff(&T, &C); EG(ret, err);
189 ret = prj_pt_is_on_curve(&C, &is_oncurve); EG(ret, err);
190 if (!is_oncurve) {
191 ext_printf("Error: C = A+B is not on the %s curve!\n",
192 curve_params.curve_name);
193 ret = -1;
194 goto err;
195 }
196 ret = aff_pt_is_on_curve(&T, &is_oncurve); EG(ret, err);
197 if (!is_oncurve) {
198 ext_printf("Error: C = A+B is not on the %s curve!\n",
199 curve_params.curve_name);
200 ret = -1;
201 goto err;
202 }
203 /*
204 * If the cofactor of the curve is 1, this means that the order of the
205 * generator is the cardinal of the curve (and hence the order of the
206 * curve points group). This means that for any point P on the curve,
207 * we should have qP = 0 (the inifinity point, i.e. the zero neutral
208 * element of the curve additive group).
209 */
210 ret = prj_pt_add(&C, &A, &B); EG(ret, err);
211 ret = prj_pt_dbl(&D, &A); EG(ret, err);
212 ret = nn_isone(&(curve_params.ec_gen_cofactor), &isone); EG(ret, err);
213 if (isone) {
214 ret = prj_pt_mul(&TMP, &(curve_params.ec_gen_order), &A); EG(ret, err);
215 ret = prj_pt_iszero(&TMP, &iszero); EG(ret, err);
216 if (!iszero) {
217 ext_printf("Error: qA is not 0! (regular mul)\n");
218 ret = -1;
219 goto err;
220 }
221 /**/
222 ret = prj_pt_mul_blind(&TMP, &(curve_params.ec_gen_order), &A); EG(ret, err);
223 ret = prj_pt_iszero(&TMP, &iszero); EG(ret, err);
224 if (!iszero) {
225 ext_printf("Error: qA is not 0! (regular blind mul)\n");
226 ret = -1;
227 goto err;
228 }
229 /**/
230 ret = prj_pt_mul(&TMP, &(curve_params.ec_gen_order), &B); EG(ret, err);
231 ret = prj_pt_iszero(&TMP, &iszero); EG(ret, err);
232 if (!iszero) {
233 ext_printf("Error: qB is not 0! (regular mul)\n");
234 ret = -1;
235 goto err;
236 }
237 /**/
238 ret = prj_pt_mul_blind(&TMP, &(curve_params.ec_gen_order), &B); EG(ret, err);
239 ret = prj_pt_iszero(&TMP, &iszero); EG(ret, err);
240 if (!iszero) {
241 ext_printf("Error: qB is not 0! (regular blind mul)\n");
242 ret = -1;
243 goto err;
244 }
245 /**/
246 ret = prj_pt_mul(&TMP, &(curve_params.ec_gen_order), &C); EG(ret, err);
247 ret = prj_pt_iszero(&TMP, &iszero); EG(ret, err);
248 if (!iszero) {
249 ext_printf("Error: qC is not 0! (regular mul)\n");
250 ret = -1;
251 goto err;
252 }
253 /**/
254 ret = prj_pt_mul_blind(&TMP, &(curve_params.ec_gen_order), &C); EG(ret, err);
255 ret = prj_pt_iszero(&TMP, &iszero); EG(ret, err);
256 if (!iszero) {
257 ext_printf("Error: qC is not 0! (regular bind mul)\n");
258 ret = -1;
259 goto err;
260 }
261 /**/
262 ret = prj_pt_mul(&TMP, &(curve_params.ec_gen_order), &D); EG(ret, err);
263 ret = prj_pt_iszero(&TMP, &iszero); EG(ret, err);
264 if (!iszero) {
265 ext_printf("Error: qD is not 0! (regular mul)\n");
266 ret = -1;
267 goto err;
268 }
269 /**/
270 ret = prj_pt_mul_blind(&TMP, &(curve_params.ec_gen_order), &D); EG(ret, err);
271 ret = prj_pt_iszero(&TMP, &iszero); EG(ret, err);
272 if (!iszero) {
273 ext_printf("Error: qD is not 0! (regular blind mul)\n");
274 ret = -1;
275 goto err;
276 }
277 }
278 /* Let's do some performance tests for point addition and doubling!
279 * We compute kA many times to have a decent performance measurement,
280 * where k is chose random at each iteration. We also check that kA
281 * is indeed on the curve.
282 */
283 ret = nn_init(&nn_k, 0); EG(ret, err);
284 /**/
285 if (get_ms_time(&t1)) {
286 ext_printf("Error: cannot get time with get_ms_time\n");
287 ret = -1;
288 goto err;
289 }
290 for (i = 0; i < PERF_SCALAR_MUL; i++) {
291 /* k = random mod (q) */
292 ret = nn_get_random_mod(&nn_k, &(curve_params.ec_gen_order)); EG(ret, err);
293 /* Compute kA with montgomery implementation w/o blinding */
294 ret = prj_pt_mul(&TMP, &nn_k, &A); EG(ret, err);
295 ret = prj_pt_to_aff(&T, &TMP); EG(ret, err);
296 ret = prj_pt_is_on_curve(&TMP, &is_oncurve); EG(ret, err);
297 if (!is_oncurve) {
298 ext_printf("Error: kA is not on the %s curve!\n",
299 curve_params.curve_name);
300 nn_print("k=", &nn_k);
301 ret = -1;
302 goto err;
303 }
304 ret = aff_pt_is_on_curve(&T, &is_oncurve); EG(ret, err);
305 if (!is_oncurve) {
306 ext_printf("Error: kA is not on the %s curve!\n",
307 curve_params.curve_name);
308 nn_print("k=", &nn_k);
309 ret = -1;
310 goto err;
311 }
312 }
313 if (get_ms_time(&t2)) {
314 ext_printf("Error: cannot get time with get_ms_time\n");
315 ret = -1;
316 goto err;
317 }
318 ext_printf(" [*] Regular EC scalar multiplication took %f seconds "
319 "on average\n",
320 (double)(t2 - t1) / (double)(PERF_SCALAR_MUL * 1000ULL));
321 /**/
322 if (get_ms_time(&t1)) {
323 ext_printf("Error: cannot get time with get_ms_time\n");
324 ret = -1;
325 goto err;
326 }
327 for (i = 0; i < PERF_SCALAR_MUL; i++) {
328 /* k = random mod (q) */
329 ret = nn_get_random_mod(&nn_k, &(curve_params.ec_gen_order)); EG(ret, err);
330 /* Compute kA using montgomery implementation w/ blinding */
331 ret = prj_pt_mul_blind(&TMP, &nn_k, &A); EG(ret, err);
332 ret = prj_pt_to_aff(&T, &TMP); EG(ret, err);
333 ret = prj_pt_is_on_curve(&TMP, &is_oncurve); EG(ret, err);
334 if (!is_oncurve) {
335 ext_printf("Error: kA is not on the %s curve!\n",
336 curve_params.curve_name);
337 nn_print("k=", &nn_k);
338 ret = -1;
339 goto err;
340 }
341 ret = aff_pt_is_on_curve(&T, &is_oncurve); EG(ret, err);
342 if (!is_oncurve) {
343 ext_printf("Error: kA is not on the %s curve!\n",
344 curve_params.curve_name);
345 nn_print("k=", &nn_k);
346 ret = -1;
347 goto err;
348 }
349 }
350 if (get_ms_time(&t2)) {
351 ext_printf("Error: cannot get time with get_ms_time\n");
352 ret = -1;
353 goto err;
354 }
355 ext_printf(" [*] Regular blind EC scalar multiplication took %f seconds "
356 "on average\n",
357 (double)(t2 - t1) / (double)(PERF_SCALAR_MUL * 1000ULL));
358
359 err:
360 prj_pt_uninit(&A);
361 prj_pt_uninit(&B);
362 prj_pt_uninit(&C);
363 prj_pt_uninit(&D);
364 prj_pt_uninit(&TMP);
365 aff_pt_uninit(&T);
366 nn_uninit(&nn_k);
367
368 return ret;
369 }
370
371 #ifdef CURVE_BASIC_EXAMPLES
main(int argc,char * argv[])372 int main(int argc, char *argv[])
373 {
374 unsigned int i;
375 u8 curve_name[MAX_CURVE_NAME_LEN] = { 0 };
376 FORCE_USED_VAR(argc);
377 FORCE_USED_VAR(argv);
378
379 /* Traverse all the possible curves we have at our disposal (known curves and
380 * user defined curves).
381 */
382 for (i = 0; i < EC_CURVES_NUM; i++) {
383 /* All our possible curves are in ../curves/curves_list.h
384 * We can get the curve name from its internal type.
385 */
386 if(ec_get_curve_name_by_type(ec_maps[i].type, curve_name,
387 sizeof(curve_name))){
388 ext_printf("Error when treating %s\n", curve_name);
389 return -1;
390 }
391 /* Check our curve! */
392 ext_printf("[+] Checking curve %s\n", curve_name);
393 if (check_curve(curve_name)) {
394 ext_printf("Error: error performing check on "
395 "curve %s\n", curve_name);
396 return -1;
397 }
398 }
399 return 0;
400 }
401 #endif
402