curve_basic_examples.c
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); 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); 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 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