summaryrefslogtreecommitdiff
path: root/src/lib/libcrypto/ec/ecp_nistp224.c
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--src/lib/libcrypto/ec/ecp_nistp224.c1016
1 files changed, 532 insertions, 484 deletions
diff --git a/src/lib/libcrypto/ec/ecp_nistp224.c b/src/lib/libcrypto/ec/ecp_nistp224.c
index 696024a549..057670cf04 100644
--- a/src/lib/libcrypto/ec/ecp_nistp224.c
+++ b/src/lib/libcrypto/ec/ecp_nistp224.c
@@ -280,37 +280,40 @@ EC_GFp_nistp224_method(void)
280} 280}
281 281
282/* Helper functions to convert field elements to/from internal representation */ 282/* Helper functions to convert field elements to/from internal representation */
283static void bin28_to_felem(felem out, const u8 in[28]) 283static void
284 { 284bin28_to_felem(felem out, const u8 in[28])
285 out[0] = *((const uint64_t *)(in)) & 0x00ffffffffffffff; 285{
286 out[1] = (*((const uint64_t *)(in+7))) & 0x00ffffffffffffff; 286 out[0] = *((const uint64_t *) (in)) & 0x00ffffffffffffff;
287 out[2] = (*((const uint64_t *)(in+14))) & 0x00ffffffffffffff; 287 out[1] = (*((const uint64_t *) (in + 7))) & 0x00ffffffffffffff;
288 out[3] = (*((const uint64_t *)(in+21))) & 0x00ffffffffffffff; 288 out[2] = (*((const uint64_t *) (in + 14))) & 0x00ffffffffffffff;
289 } 289 out[3] = (*((const uint64_t *) (in + 21))) & 0x00ffffffffffffff;
290}
290 291
291static void felem_to_bin28(u8 out[28], const felem in) 292static void
292 { 293felem_to_bin28(u8 out[28], const felem in)
294{
293 unsigned i; 295 unsigned i;
294 for (i = 0; i < 7; ++i) 296 for (i = 0; i < 7; ++i) {
295 { 297 out[i] = in[0] >> (8 * i);
296 out[i] = in[0]>>(8*i); 298 out[i + 7] = in[1] >> (8 * i);
297 out[i+7] = in[1]>>(8*i); 299 out[i + 14] = in[2] >> (8 * i);
298 out[i+14] = in[2]>>(8*i); 300 out[i + 21] = in[3] >> (8 * i);
299 out[i+21] = in[3]>>(8*i);
300 }
301 } 301 }
302}
302 303
303/* To preserve endianness when using BN_bn2bin and BN_bin2bn */ 304/* To preserve endianness when using BN_bn2bin and BN_bin2bn */
304static void flip_endian(u8 *out, const u8 *in, unsigned len) 305static void
305 { 306flip_endian(u8 * out, const u8 * in, unsigned len)
307{
306 unsigned i; 308 unsigned i;
307 for (i = 0; i < len; ++i) 309 for (i = 0; i < len; ++i)
308 out[i] = in[len-1-i]; 310 out[i] = in[len - 1 - i];
309 } 311}
310 312
311/* From OpenSSL BIGNUM to internal representation */ 313/* From OpenSSL BIGNUM to internal representation */
312static int BN_to_felem(felem out, const BIGNUM *bn) 314static int
313 { 315BN_to_felem(felem out, const BIGNUM * bn)
316{
314 felem_bytearray b_in; 317 felem_bytearray b_in;
315 felem_bytearray b_out; 318 felem_bytearray b_out;
316 unsigned num_bytes; 319 unsigned num_bytes;
@@ -318,30 +321,29 @@ static int BN_to_felem(felem out, const BIGNUM *bn)
318 /* BN_bn2bin eats leading zeroes */ 321 /* BN_bn2bin eats leading zeroes */
319 memset(b_out, 0, sizeof b_out); 322 memset(b_out, 0, sizeof b_out);
320 num_bytes = BN_num_bytes(bn); 323 num_bytes = BN_num_bytes(bn);
321 if (num_bytes > sizeof b_out) 324 if (num_bytes > sizeof b_out) {
322 {
323 ECerr(EC_F_BN_TO_FELEM, EC_R_BIGNUM_OUT_OF_RANGE); 325 ECerr(EC_F_BN_TO_FELEM, EC_R_BIGNUM_OUT_OF_RANGE);
324 return 0; 326 return 0;
325 } 327 }
326 if (BN_is_negative(bn)) 328 if (BN_is_negative(bn)) {
327 {
328 ECerr(EC_F_BN_TO_FELEM, EC_R_BIGNUM_OUT_OF_RANGE); 329 ECerr(EC_F_BN_TO_FELEM, EC_R_BIGNUM_OUT_OF_RANGE);
329 return 0; 330 return 0;
330 } 331 }
331 num_bytes = BN_bn2bin(bn, b_in); 332 num_bytes = BN_bn2bin(bn, b_in);
332 flip_endian(b_out, b_in, num_bytes); 333 flip_endian(b_out, b_in, num_bytes);
333 bin28_to_felem(out, b_out); 334 bin28_to_felem(out, b_out);
334 return 1; 335 return 1;
335 } 336}
336 337
337/* From internal representation to OpenSSL BIGNUM */ 338/* From internal representation to OpenSSL BIGNUM */
338static BIGNUM *felem_to_BN(BIGNUM *out, const felem in) 339static BIGNUM *
339 { 340felem_to_BN(BIGNUM * out, const felem in)
341{
340 felem_bytearray b_in, b_out; 342 felem_bytearray b_in, b_out;
341 felem_to_bin28(b_in, in); 343 felem_to_bin28(b_in, in);
342 flip_endian(b_out, b_in, sizeof b_out); 344 flip_endian(b_out, b_in, sizeof b_out);
343 return BN_bin2bn(b_out, sizeof b_out, out); 345 return BN_bin2bn(b_out, sizeof b_out, out);
344 } 346}
345 347
346/******************************************************************************/ 348/******************************************************************************/
347/* FIELD OPERATIONS 349/* FIELD OPERATIONS
@@ -353,55 +355,60 @@ static BIGNUM *felem_to_BN(BIGNUM *out, const felem in)
353 * 355 *
354 */ 356 */
355 357
356static void felem_one(felem out) 358static void
357 { 359felem_one(felem out)
360{
358 out[0] = 1; 361 out[0] = 1;
359 out[1] = 0; 362 out[1] = 0;
360 out[2] = 0; 363 out[2] = 0;
361 out[3] = 0; 364 out[3] = 0;
362 } 365}
363 366
364static void felem_assign(felem out, const felem in) 367static void
365 { 368felem_assign(felem out, const felem in)
369{
366 out[0] = in[0]; 370 out[0] = in[0];
367 out[1] = in[1]; 371 out[1] = in[1];
368 out[2] = in[2]; 372 out[2] = in[2];
369 out[3] = in[3]; 373 out[3] = in[3];
370 } 374}
371 375
372/* Sum two field elements: out += in */ 376/* Sum two field elements: out += in */
373static void felem_sum(felem out, const felem in) 377static void
374 { 378felem_sum(felem out, const felem in)
379{
375 out[0] += in[0]; 380 out[0] += in[0];
376 out[1] += in[1]; 381 out[1] += in[1];
377 out[2] += in[2]; 382 out[2] += in[2];
378 out[3] += in[3]; 383 out[3] += in[3];
379 } 384}
380 385
381/* Get negative value: out = -in */ 386/* Get negative value: out = -in */
382/* Assumes in[i] < 2^57 */ 387/* Assumes in[i] < 2^57 */
383static void felem_neg(felem out, const felem in) 388static void
384 { 389felem_neg(felem out, const felem in)
390{
385 static const limb two58p2 = (((limb) 1) << 58) + (((limb) 1) << 2); 391 static const limb two58p2 = (((limb) 1) << 58) + (((limb) 1) << 2);
386 static const limb two58m2 = (((limb) 1) << 58) - (((limb) 1) << 2); 392 static const limb two58m2 = (((limb) 1) << 58) - (((limb) 1) << 2);
387 static const limb two58m42m2 = (((limb) 1) << 58) - 393 static const limb two58m42m2 = (((limb) 1) << 58) -
388 (((limb) 1) << 42) - (((limb) 1) << 2); 394 (((limb) 1) << 42) - (((limb) 1) << 2);
389 395
390 /* Set to 0 mod 2^224-2^96+1 to ensure out > in */ 396 /* Set to 0 mod 2^224-2^96+1 to ensure out > in */
391 out[0] = two58p2 - in[0]; 397 out[0] = two58p2 - in[0];
392 out[1] = two58m42m2 - in[1]; 398 out[1] = two58m42m2 - in[1];
393 out[2] = two58m2 - in[2]; 399 out[2] = two58m2 - in[2];
394 out[3] = two58m2 - in[3]; 400 out[3] = two58m2 - in[3];
395 } 401}
396 402
397/* Subtract field elements: out -= in */ 403/* Subtract field elements: out -= in */
398/* Assumes in[i] < 2^57 */ 404/* Assumes in[i] < 2^57 */
399static void felem_diff(felem out, const felem in) 405static void
400 { 406felem_diff(felem out, const felem in)
407{
401 static const limb two58p2 = (((limb) 1) << 58) + (((limb) 1) << 2); 408 static const limb two58p2 = (((limb) 1) << 58) + (((limb) 1) << 2);
402 static const limb two58m2 = (((limb) 1) << 58) - (((limb) 1) << 2); 409 static const limb two58m2 = (((limb) 1) << 58) - (((limb) 1) << 2);
403 static const limb two58m42m2 = (((limb) 1) << 58) - 410 static const limb two58m42m2 = (((limb) 1) << 58) -
404 (((limb) 1) << 42) - (((limb) 1) << 2); 411 (((limb) 1) << 42) - (((limb) 1) << 2);
405 412
406 /* Add 0 mod 2^224-2^96+1 to ensure out > in */ 413 /* Add 0 mod 2^224-2^96+1 to ensure out > in */
407 out[0] += two58p2; 414 out[0] += two58p2;
@@ -413,17 +420,18 @@ static void felem_diff(felem out, const felem in)
413 out[1] -= in[1]; 420 out[1] -= in[1];
414 out[2] -= in[2]; 421 out[2] -= in[2];
415 out[3] -= in[3]; 422 out[3] -= in[3];
416 } 423}
417 424
418/* Subtract in unreduced 128-bit mode: out -= in */ 425/* Subtract in unreduced 128-bit mode: out -= in */
419/* Assumes in[i] < 2^119 */ 426/* Assumes in[i] < 2^119 */
420static void widefelem_diff(widefelem out, const widefelem in) 427static void
421 { 428widefelem_diff(widefelem out, const widefelem in)
429{
422 static const widelimb two120 = ((widelimb) 1) << 120; 430 static const widelimb two120 = ((widelimb) 1) << 120;
423 static const widelimb two120m64 = (((widelimb) 1) << 120) - 431 static const widelimb two120m64 = (((widelimb) 1) << 120) -
424 (((widelimb) 1) << 64); 432 (((widelimb) 1) << 64);
425 static const widelimb two120m104m64 = (((widelimb) 1) << 120) - 433 static const widelimb two120m104m64 = (((widelimb) 1) << 120) -
426 (((widelimb) 1) << 104) - (((widelimb) 1) << 64); 434 (((widelimb) 1) << 104) - (((widelimb) 1) << 64);
427 435
428 /* Add 0 mod 2^224-2^96+1 to ensure out > in */ 436 /* Add 0 mod 2^224-2^96+1 to ensure out > in */
429 out[0] += two120; 437 out[0] += two120;
@@ -441,18 +449,19 @@ static void widefelem_diff(widefelem out, const widefelem in)
441 out[4] -= in[4]; 449 out[4] -= in[4];
442 out[5] -= in[5]; 450 out[5] -= in[5];
443 out[6] -= in[6]; 451 out[6] -= in[6];
444 } 452}
445 453
446/* Subtract in mixed mode: out128 -= in64 */ 454/* Subtract in mixed mode: out128 -= in64 */
447/* in[i] < 2^63 */ 455/* in[i] < 2^63 */
448static void felem_diff_128_64(widefelem out, const felem in) 456static void
449 { 457felem_diff_128_64(widefelem out, const felem in)
458{
450 static const widelimb two64p8 = (((widelimb) 1) << 64) + 459 static const widelimb two64p8 = (((widelimb) 1) << 64) +
451 (((widelimb) 1) << 8); 460 (((widelimb) 1) << 8);
452 static const widelimb two64m8 = (((widelimb) 1) << 64) - 461 static const widelimb two64m8 = (((widelimb) 1) << 64) -
453 (((widelimb) 1) << 8); 462 (((widelimb) 1) << 8);
454 static const widelimb two64m48m8 = (((widelimb) 1) << 64) - 463 static const widelimb two64m48m8 = (((widelimb) 1) << 64) -
455 (((widelimb) 1) << 48) - (((widelimb) 1) << 8); 464 (((widelimb) 1) << 48) - (((widelimb) 1) << 8);
456 465
457 /* Add 0 mod 2^224-2^96+1 to ensure out > in */ 466 /* Add 0 mod 2^224-2^96+1 to ensure out > in */
458 out[0] += two64p8; 467 out[0] += two64p8;
@@ -464,22 +473,24 @@ static void felem_diff_128_64(widefelem out, const felem in)
464 out[1] -= in[1]; 473 out[1] -= in[1];
465 out[2] -= in[2]; 474 out[2] -= in[2];
466 out[3] -= in[3]; 475 out[3] -= in[3];
467 } 476}
468 477
469/* Multiply a field element by a scalar: out = out * scalar 478/* Multiply a field element by a scalar: out = out * scalar
470 * The scalars we actually use are small, so results fit without overflow */ 479 * The scalars we actually use are small, so results fit without overflow */
471static void felem_scalar(felem out, const limb scalar) 480static void
472 { 481felem_scalar(felem out, const limb scalar)
482{
473 out[0] *= scalar; 483 out[0] *= scalar;
474 out[1] *= scalar; 484 out[1] *= scalar;
475 out[2] *= scalar; 485 out[2] *= scalar;
476 out[3] *= scalar; 486 out[3] *= scalar;
477 } 487}
478 488
479/* Multiply an unreduced field element by a scalar: out = out * scalar 489/* Multiply an unreduced field element by a scalar: out = out * scalar
480 * The scalars we actually use are small, so results fit without overflow */ 490 * The scalars we actually use are small, so results fit without overflow */
481static void widefelem_scalar(widefelem out, const widelimb scalar) 491static void
482 { 492widefelem_scalar(widefelem out, const widelimb scalar)
493{
483 out[0] *= scalar; 494 out[0] *= scalar;
484 out[1] *= scalar; 495 out[1] *= scalar;
485 out[2] *= scalar; 496 out[2] *= scalar;
@@ -487,49 +498,54 @@ static void widefelem_scalar(widefelem out, const widelimb scalar)
487 out[4] *= scalar; 498 out[4] *= scalar;
488 out[5] *= scalar; 499 out[5] *= scalar;
489 out[6] *= scalar; 500 out[6] *= scalar;
490 } 501}
491 502
492/* Square a field element: out = in^2 */ 503/* Square a field element: out = in^2 */
493static void felem_square(widefelem out, const felem in) 504static void
494 { 505felem_square(widefelem out, const felem in)
506{
495 limb tmp0, tmp1, tmp2; 507 limb tmp0, tmp1, tmp2;
496 tmp0 = 2 * in[0]; tmp1 = 2 * in[1]; tmp2 = 2 * in[2]; 508 tmp0 = 2 * in[0];
509 tmp1 = 2 * in[1];
510 tmp2 = 2 * in[2];
497 out[0] = ((widelimb) in[0]) * in[0]; 511 out[0] = ((widelimb) in[0]) * in[0];
498 out[1] = ((widelimb) in[0]) * tmp1; 512 out[1] = ((widelimb) in[0]) * tmp1;
499 out[2] = ((widelimb) in[0]) * tmp2 + ((widelimb) in[1]) * in[1]; 513 out[2] = ((widelimb) in[0]) * tmp2 + ((widelimb) in[1]) * in[1];
500 out[3] = ((widelimb) in[3]) * tmp0 + 514 out[3] = ((widelimb) in[3]) * tmp0 +
501 ((widelimb) in[1]) * tmp2; 515 ((widelimb) in[1]) * tmp2;
502 out[4] = ((widelimb) in[3]) * tmp1 + ((widelimb) in[2]) * in[2]; 516 out[4] = ((widelimb) in[3]) * tmp1 + ((widelimb) in[2]) * in[2];
503 out[5] = ((widelimb) in[3]) * tmp2; 517 out[5] = ((widelimb) in[3]) * tmp2;
504 out[6] = ((widelimb) in[3]) * in[3]; 518 out[6] = ((widelimb) in[3]) * in[3];
505 } 519}
506 520
507/* Multiply two field elements: out = in1 * in2 */ 521/* Multiply two field elements: out = in1 * in2 */
508static void felem_mul(widefelem out, const felem in1, const felem in2) 522static void
509 { 523felem_mul(widefelem out, const felem in1, const felem in2)
524{
510 out[0] = ((widelimb) in1[0]) * in2[0]; 525 out[0] = ((widelimb) in1[0]) * in2[0];
511 out[1] = ((widelimb) in1[0]) * in2[1] + ((widelimb) in1[1]) * in2[0]; 526 out[1] = ((widelimb) in1[0]) * in2[1] + ((widelimb) in1[1]) * in2[0];
512 out[2] = ((widelimb) in1[0]) * in2[2] + ((widelimb) in1[1]) * in2[1] + 527 out[2] = ((widelimb) in1[0]) * in2[2] + ((widelimb) in1[1]) * in2[1] +
513 ((widelimb) in1[2]) * in2[0]; 528 ((widelimb) in1[2]) * in2[0];
514 out[3] = ((widelimb) in1[0]) * in2[3] + ((widelimb) in1[1]) * in2[2] + 529 out[3] = ((widelimb) in1[0]) * in2[3] + ((widelimb) in1[1]) * in2[2] +
515 ((widelimb) in1[2]) * in2[1] + ((widelimb) in1[3]) * in2[0]; 530 ((widelimb) in1[2]) * in2[1] + ((widelimb) in1[3]) * in2[0];
516 out[4] = ((widelimb) in1[1]) * in2[3] + ((widelimb) in1[2]) * in2[2] + 531 out[4] = ((widelimb) in1[1]) * in2[3] + ((widelimb) in1[2]) * in2[2] +
517 ((widelimb) in1[3]) * in2[1]; 532 ((widelimb) in1[3]) * in2[1];
518 out[5] = ((widelimb) in1[2]) * in2[3] + ((widelimb) in1[3]) * in2[2]; 533 out[5] = ((widelimb) in1[2]) * in2[3] + ((widelimb) in1[3]) * in2[2];
519 out[6] = ((widelimb) in1[3]) * in2[3]; 534 out[6] = ((widelimb) in1[3]) * in2[3];
520 } 535}
521 536
522/* Reduce seven 128-bit coefficients to four 64-bit coefficients. 537/* Reduce seven 128-bit coefficients to four 64-bit coefficients.
523 * Requires in[i] < 2^126, 538 * Requires in[i] < 2^126,
524 * ensures out[0] < 2^56, out[1] < 2^56, out[2] < 2^56, out[3] <= 2^56 + 2^16 */ 539 * ensures out[0] < 2^56, out[1] < 2^56, out[2] < 2^56, out[3] <= 2^56 + 2^16 */
525static void felem_reduce(felem out, const widefelem in) 540static void
526 { 541felem_reduce(felem out, const widefelem in)
542{
527 static const widelimb two127p15 = (((widelimb) 1) << 127) + 543 static const widelimb two127p15 = (((widelimb) 1) << 127) +
528 (((widelimb) 1) << 15); 544 (((widelimb) 1) << 15);
529 static const widelimb two127m71 = (((widelimb) 1) << 127) - 545 static const widelimb two127m71 = (((widelimb) 1) << 127) -
530 (((widelimb) 1) << 71); 546 (((widelimb) 1) << 71);
531 static const widelimb two127m71m55 = (((widelimb) 1) << 127) - 547 static const widelimb two127m71m55 = (((widelimb) 1) << 127) -
532 (((widelimb) 1) << 71) - (((widelimb) 1) << 55); 548 (((widelimb) 1) << 71) - (((widelimb) 1) << 55);
533 widelimb output[5]; 549 widelimb output[5];
534 550
535 /* Add 0 mod 2^224-2^96+1 to ensure all differences are positive */ 551 /* Add 0 mod 2^224-2^96+1 to ensure all differences are positive */
@@ -578,30 +594,34 @@ static void felem_reduce(felem out, const widefelem in)
578 /* output[3] <= 2^56 + 2^16 */ 594 /* output[3] <= 2^56 + 2^16 */
579 out[2] = output[2] & 0x00ffffffffffffff; 595 out[2] = output[2] & 0x00ffffffffffffff;
580 596
581 /* out[0] < 2^56, out[1] < 2^56, out[2] < 2^56, 597 /*
582 * out[3] <= 2^56 + 2^16 (due to final carry), 598 * out[0] < 2^56, out[1] < 2^56, out[2] < 2^56, out[3] <= 2^56 + 2^16
583 * so out < 2*p */ 599 * (due to final carry), so out < 2*p
600 */
584 out[3] = output[3]; 601 out[3] = output[3];
585 } 602}
586 603
587static void felem_square_reduce(felem out, const felem in) 604static void
588 { 605felem_square_reduce(felem out, const felem in)
606{
589 widefelem tmp; 607 widefelem tmp;
590 felem_square(tmp, in); 608 felem_square(tmp, in);
591 felem_reduce(out, tmp); 609 felem_reduce(out, tmp);
592 } 610}
593 611
594static void felem_mul_reduce(felem out, const felem in1, const felem in2) 612static void
595 { 613felem_mul_reduce(felem out, const felem in1, const felem in2)
614{
596 widefelem tmp; 615 widefelem tmp;
597 felem_mul(tmp, in1, in2); 616 felem_mul(tmp, in1, in2);
598 felem_reduce(out, tmp); 617 felem_reduce(out, tmp);
599 } 618}
600 619
601/* Reduce to unique minimal representation. 620/* Reduce to unique minimal representation.
602 * Requires 0 <= in < 2*p (always call felem_reduce first) */ 621 * Requires 0 <= in < 2*p (always call felem_reduce first) */
603static void felem_contract(felem out, const felem in) 622static void
604 { 623felem_contract(felem out, const felem in)
624{
605 static const int64_t two56 = ((limb) 1) << 56; 625 static const int64_t two56 = ((limb) 1) << 56;
606 /* 0 <= in < 2*p, p = 2^224 - 2^96 + 1 */ 626 /* 0 <= in < 2*p, p = 2^224 - 2^96 + 1 */
607 /* if in > p , reduce in = in - 2^224 + 2^96 - 1 */ 627 /* if in > p , reduce in = in - 2^224 + 2^96 - 1 */
@@ -615,21 +635,25 @@ static void felem_contract(felem out, const felem in)
615 tmp[0] -= a; 635 tmp[0] -= a;
616 tmp[1] += a << 40; 636 tmp[1] += a << 40;
617 tmp[3] &= 0x00ffffffffffffff; 637 tmp[3] &= 0x00ffffffffffffff;
618 /* Case 2: a = 0 iff p <= in < 2^224, i.e., 638 /*
619 * the high 128 bits are all 1 and the lower part is non-zero */ 639 * Case 2: a = 0 iff p <= in < 2^224, i.e., the high 128 bits are all
640 * 1 and the lower part is non-zero
641 */
620 a = ((in[3] & in[2] & (in[1] | 0x000000ffffffffff)) + 1) | 642 a = ((in[3] & in[2] & (in[1] | 0x000000ffffffffff)) + 1) |
621 (((int64_t)(in[0] + (in[1] & 0x000000ffffffffff)) - 1) >> 63); 643 (((int64_t) (in[0] + (in[1] & 0x000000ffffffffff)) - 1) >> 63);
622 a &= 0x00ffffffffffffff; 644 a &= 0x00ffffffffffffff;
623 /* turn a into an all-one mask (if a = 0) or an all-zero mask */ 645 /* turn a into an all-one mask (if a = 0) or an all-zero mask */
624 a = (a - 1) >> 63; 646 a = (a - 1) >> 63;
625 /* subtract 2^224 - 2^96 + 1 if a is all-one*/ 647 /* subtract 2^224 - 2^96 + 1 if a is all-one */
626 tmp[3] &= a ^ 0xffffffffffffffff; 648 tmp[3] &= a ^ 0xffffffffffffffff;
627 tmp[2] &= a ^ 0xffffffffffffffff; 649 tmp[2] &= a ^ 0xffffffffffffffff;
628 tmp[1] &= (a ^ 0xffffffffffffffff) | 0x000000ffffffffff; 650 tmp[1] &= (a ^ 0xffffffffffffffff) | 0x000000ffffffffff;
629 tmp[0] -= 1 & a; 651 tmp[0] -= 1 & a;
630 652
631 /* eliminate negative coefficients: if tmp[0] is negative, tmp[1] must 653 /*
632 * be non-zero, so we only need one step */ 654 * eliminate negative coefficients: if tmp[0] is negative, tmp[1]
655 * must be non-zero, so we only need one step
656 */
633 a = tmp[0] >> 63; 657 a = tmp[0] >> 63;
634 tmp[0] += two56 & a; 658 tmp[0] += two56 & a;
635 tmp[1] -= 1 & a; 659 tmp[1] -= 1 & a;
@@ -646,107 +670,131 @@ static void felem_contract(felem out, const felem in)
646 out[1] = tmp[1]; 670 out[1] = tmp[1];
647 out[2] = tmp[2]; 671 out[2] = tmp[2];
648 out[3] = tmp[3]; 672 out[3] = tmp[3];
649 } 673}
650 674
651/* Zero-check: returns 1 if input is 0, and 0 otherwise. 675/* Zero-check: returns 1 if input is 0, and 0 otherwise.
652 * We know that field elements are reduced to in < 2^225, 676 * We know that field elements are reduced to in < 2^225,
653 * so we only need to check three cases: 0, 2^224 - 2^96 + 1, 677 * so we only need to check three cases: 0, 2^224 - 2^96 + 1,
654 * and 2^225 - 2^97 + 2 */ 678 * and 2^225 - 2^97 + 2 */
655static limb felem_is_zero(const felem in) 679static limb
656 { 680felem_is_zero(const felem in)
681{
657 limb zero, two224m96p1, two225m97p2; 682 limb zero, two224m96p1, two225m97p2;
658 683
659 zero = in[0] | in[1] | in[2] | in[3]; 684 zero = in[0] | in[1] | in[2] | in[3];
660 zero = (((int64_t)(zero) - 1) >> 63) & 1; 685 zero = (((int64_t) (zero) - 1) >> 63) & 1;
661 two224m96p1 = (in[0] ^ 1) | (in[1] ^ 0x00ffff0000000000) 686 two224m96p1 = (in[0] ^ 1) | (in[1] ^ 0x00ffff0000000000)
662 | (in[2] ^ 0x00ffffffffffffff) | (in[3] ^ 0x00ffffffffffffff); 687 | (in[2] ^ 0x00ffffffffffffff) | (in[3] ^ 0x00ffffffffffffff);
663 two224m96p1 = (((int64_t)(two224m96p1) - 1) >> 63) & 1; 688 two224m96p1 = (((int64_t) (two224m96p1) - 1) >> 63) & 1;
664 two225m97p2 = (in[0] ^ 2) | (in[1] ^ 0x00fffe0000000000) 689 two225m97p2 = (in[0] ^ 2) | (in[1] ^ 0x00fffe0000000000)
665 | (in[2] ^ 0x00ffffffffffffff) | (in[3] ^ 0x01ffffffffffffff); 690 | (in[2] ^ 0x00ffffffffffffff) | (in[3] ^ 0x01ffffffffffffff);
666 two225m97p2 = (((int64_t)(two225m97p2) - 1) >> 63) & 1; 691 two225m97p2 = (((int64_t) (two225m97p2) - 1) >> 63) & 1;
667 return (zero | two224m96p1 | two225m97p2); 692 return (zero | two224m96p1 | two225m97p2);
668 } 693}
669 694
670static limb felem_is_zero_int(const felem in) 695static limb
671 { 696felem_is_zero_int(const felem in)
672 return (int) (felem_is_zero(in) & ((limb)1)); 697{
673 } 698 return (int) (felem_is_zero(in) & ((limb) 1));
699}
674 700
675/* Invert a field element */ 701/* Invert a field element */
676/* Computation chain copied from djb's code */ 702/* Computation chain copied from djb's code */
677static void felem_inv(felem out, const felem in) 703static void
678 { 704felem_inv(felem out, const felem in)
705{
679 felem ftmp, ftmp2, ftmp3, ftmp4; 706 felem ftmp, ftmp2, ftmp3, ftmp4;
680 widefelem tmp; 707 widefelem tmp;
681 unsigned i; 708 unsigned i;
682 709
683 felem_square(tmp, in); felem_reduce(ftmp, tmp); /* 2 */ 710 felem_square(tmp, in);
684 felem_mul(tmp, in, ftmp); felem_reduce(ftmp, tmp); /* 2^2 - 1 */ 711 felem_reduce(ftmp, tmp);/* 2 */
685 felem_square(tmp, ftmp); felem_reduce(ftmp, tmp); /* 2^3 - 2 */ 712 felem_mul(tmp, in, ftmp);
686 felem_mul(tmp, in, ftmp); felem_reduce(ftmp, tmp); /* 2^3 - 1 */ 713 felem_reduce(ftmp, tmp);/* 2^2 - 1 */
687 felem_square(tmp, ftmp); felem_reduce(ftmp2, tmp); /* 2^4 - 2 */ 714 felem_square(tmp, ftmp);
688 felem_square(tmp, ftmp2); felem_reduce(ftmp2, tmp); /* 2^5 - 4 */ 715 felem_reduce(ftmp, tmp);/* 2^3 - 2 */
689 felem_square(tmp, ftmp2); felem_reduce(ftmp2, tmp); /* 2^6 - 8 */ 716 felem_mul(tmp, in, ftmp);
690 felem_mul(tmp, ftmp2, ftmp); felem_reduce(ftmp, tmp); /* 2^6 - 1 */ 717 felem_reduce(ftmp, tmp);/* 2^3 - 1 */
691 felem_square(tmp, ftmp); felem_reduce(ftmp2, tmp); /* 2^7 - 2 */ 718 felem_square(tmp, ftmp);
692 for (i = 0; i < 5; ++i) /* 2^12 - 2^6 */ 719 felem_reduce(ftmp2, tmp); /* 2^4 - 2 */
693 { 720 felem_square(tmp, ftmp2);
694 felem_square(tmp, ftmp2); felem_reduce(ftmp2, tmp); 721 felem_reduce(ftmp2, tmp); /* 2^5 - 4 */
695 } 722 felem_square(tmp, ftmp2);
696 felem_mul(tmp, ftmp2, ftmp); felem_reduce(ftmp2, tmp); /* 2^12 - 1 */ 723 felem_reduce(ftmp2, tmp); /* 2^6 - 8 */
697 felem_square(tmp, ftmp2); felem_reduce(ftmp3, tmp); /* 2^13 - 2 */ 724 felem_mul(tmp, ftmp2, ftmp);
698 for (i = 0; i < 11; ++i) /* 2^24 - 2^12 */ 725 felem_reduce(ftmp, tmp);/* 2^6 - 1 */
699 { 726 felem_square(tmp, ftmp);
700 felem_square(tmp, ftmp3); felem_reduce(ftmp3, tmp); 727 felem_reduce(ftmp2, tmp); /* 2^7 - 2 */
701 } 728 for (i = 0; i < 5; ++i) { /* 2^12 - 2^6 */
702 felem_mul(tmp, ftmp3, ftmp2); felem_reduce(ftmp2, tmp); /* 2^24 - 1 */ 729 felem_square(tmp, ftmp2);
703 felem_square(tmp, ftmp2); felem_reduce(ftmp3, tmp); /* 2^25 - 2 */ 730 felem_reduce(ftmp2, tmp);
704 for (i = 0; i < 23; ++i) /* 2^48 - 2^24 */ 731 }
705 { 732 felem_mul(tmp, ftmp2, ftmp);
706 felem_square(tmp, ftmp3); felem_reduce(ftmp3, tmp); 733 felem_reduce(ftmp2, tmp); /* 2^12 - 1 */
707 } 734 felem_square(tmp, ftmp2);
708 felem_mul(tmp, ftmp3, ftmp2); felem_reduce(ftmp3, tmp); /* 2^48 - 1 */ 735 felem_reduce(ftmp3, tmp); /* 2^13 - 2 */
709 felem_square(tmp, ftmp3); felem_reduce(ftmp4, tmp); /* 2^49 - 2 */ 736 for (i = 0; i < 11; ++i) { /* 2^24 - 2^12 */
710 for (i = 0; i < 47; ++i) /* 2^96 - 2^48 */ 737 felem_square(tmp, ftmp3);
711 { 738 felem_reduce(ftmp3, tmp);
712 felem_square(tmp, ftmp4); felem_reduce(ftmp4, tmp); 739 }
713 } 740 felem_mul(tmp, ftmp3, ftmp2);
714 felem_mul(tmp, ftmp3, ftmp4); felem_reduce(ftmp3, tmp); /* 2^96 - 1 */ 741 felem_reduce(ftmp2, tmp); /* 2^24 - 1 */
715 felem_square(tmp, ftmp3); felem_reduce(ftmp4, tmp); /* 2^97 - 2 */ 742 felem_square(tmp, ftmp2);
716 for (i = 0; i < 23; ++i) /* 2^120 - 2^24 */ 743 felem_reduce(ftmp3, tmp); /* 2^25 - 2 */
717 { 744 for (i = 0; i < 23; ++i) { /* 2^48 - 2^24 */
718 felem_square(tmp, ftmp4); felem_reduce(ftmp4, tmp); 745 felem_square(tmp, ftmp3);
719 } 746 felem_reduce(ftmp3, tmp);
720 felem_mul(tmp, ftmp2, ftmp4); felem_reduce(ftmp2, tmp); /* 2^120 - 1 */ 747 }
721 for (i = 0; i < 6; ++i) /* 2^126 - 2^6 */ 748 felem_mul(tmp, ftmp3, ftmp2);
722 { 749 felem_reduce(ftmp3, tmp); /* 2^48 - 1 */
723 felem_square(tmp, ftmp2); felem_reduce(ftmp2, tmp); 750 felem_square(tmp, ftmp3);
724 } 751 felem_reduce(ftmp4, tmp); /* 2^49 - 2 */
725 felem_mul(tmp, ftmp2, ftmp); felem_reduce(ftmp, tmp); /* 2^126 - 1 */ 752 for (i = 0; i < 47; ++i) { /* 2^96 - 2^48 */
726 felem_square(tmp, ftmp); felem_reduce(ftmp, tmp); /* 2^127 - 2 */ 753 felem_square(tmp, ftmp4);
727 felem_mul(tmp, ftmp, in); felem_reduce(ftmp, tmp); /* 2^127 - 1 */ 754 felem_reduce(ftmp4, tmp);
728 for (i = 0; i < 97; ++i) /* 2^224 - 2^97 */ 755 }
729 { 756 felem_mul(tmp, ftmp3, ftmp4);
730 felem_square(tmp, ftmp); felem_reduce(ftmp, tmp); 757 felem_reduce(ftmp3, tmp); /* 2^96 - 1 */
731 } 758 felem_square(tmp, ftmp3);
732 felem_mul(tmp, ftmp, ftmp3); felem_reduce(out, tmp); /* 2^224 - 2^96 - 1 */ 759 felem_reduce(ftmp4, tmp); /* 2^97 - 2 */
760 for (i = 0; i < 23; ++i) { /* 2^120 - 2^24 */
761 felem_square(tmp, ftmp4);
762 felem_reduce(ftmp4, tmp);
763 }
764 felem_mul(tmp, ftmp2, ftmp4);
765 felem_reduce(ftmp2, tmp); /* 2^120 - 1 */
766 for (i = 0; i < 6; ++i) { /* 2^126 - 2^6 */
767 felem_square(tmp, ftmp2);
768 felem_reduce(ftmp2, tmp);
769 }
770 felem_mul(tmp, ftmp2, ftmp);
771 felem_reduce(ftmp, tmp);/* 2^126 - 1 */
772 felem_square(tmp, ftmp);
773 felem_reduce(ftmp, tmp);/* 2^127 - 2 */
774 felem_mul(tmp, ftmp, in);
775 felem_reduce(ftmp, tmp);/* 2^127 - 1 */
776 for (i = 0; i < 97; ++i) { /* 2^224 - 2^97 */
777 felem_square(tmp, ftmp);
778 felem_reduce(ftmp, tmp);
733 } 779 }
780 felem_mul(tmp, ftmp, ftmp3);
781 felem_reduce(out, tmp); /* 2^224 - 2^96 - 1 */
782}
734 783
735/* Copy in constant time: 784/* Copy in constant time:
736 * if icopy == 1, copy in to out, 785 * if icopy == 1, copy in to out,
737 * if icopy == 0, copy out to itself. */ 786 * if icopy == 0, copy out to itself. */
738static void 787static void
739copy_conditional(felem out, const felem in, limb icopy) 788copy_conditional(felem out, const felem in, limb icopy)
740 { 789{
741 unsigned i; 790 unsigned i;
742 /* icopy is a (64-bit) 0 or 1, so copy is either all-zero or all-one */ 791 /* icopy is a (64-bit) 0 or 1, so copy is either all-zero or all-one */
743 const limb copy = -icopy; 792 const limb copy = -icopy;
744 for (i = 0; i < 4; ++i) 793 for (i = 0; i < 4; ++i) {
745 {
746 const limb tmp = copy & (in[i] ^ out[i]); 794 const limb tmp = copy & (in[i] ^ out[i]);
747 out[i] ^= tmp; 795 out[i] ^= tmp;
748 }
749 } 796 }
797}
750 798
751/******************************************************************************/ 799/******************************************************************************/
752/* ELLIPTIC CURVE POINT OPERATIONS 800/* ELLIPTIC CURVE POINT OPERATIONS
@@ -766,8 +814,8 @@ copy_conditional(felem out, const felem in, limb icopy)
766 * while x_out == y_in is not (maybe this works, but it's not tested). */ 814 * while x_out == y_in is not (maybe this works, but it's not tested). */
767static void 815static void
768point_double(felem x_out, felem y_out, felem z_out, 816point_double(felem x_out, felem y_out, felem z_out,
769 const felem x_in, const felem y_in, const felem z_in) 817 const felem x_in, const felem y_in, const felem z_in)
770 { 818{
771 widefelem tmp, tmp2; 819 widefelem tmp, tmp2;
772 felem delta, gamma, beta, alpha, ftmp, ftmp2; 820 felem delta, gamma, beta, alpha, ftmp, ftmp2;
773 821
@@ -833,7 +881,7 @@ point_double(felem x_out, felem y_out, felem z_out,
833 widefelem_diff(tmp, tmp2); 881 widefelem_diff(tmp, tmp2);
834 /* tmp[i] < 2^119 + 2^120 < 2^121 */ 882 /* tmp[i] < 2^119 + 2^120 < 2^121 */
835 felem_reduce(y_out, tmp); 883 felem_reduce(y_out, tmp);
836 } 884}
837 885
838/* Add two elliptic curve points: 886/* Add two elliptic curve points:
839 * (X_1, Y_1, Z_1) + (X_2, Y_2, Z_2) = (X_3, Y_3, Z_3), where 887 * (X_1, Y_1, Z_1) + (X_2, Y_2, Z_2) = (X_3, Y_3, Z_3), where
@@ -851,16 +899,16 @@ point_double(felem x_out, felem y_out, felem z_out,
851 * (while not equal to the point at infinity). 899 * (while not equal to the point at infinity).
852 * This case never happens during single point multiplication, 900 * This case never happens during single point multiplication,
853 * so there is no timing leak for ECDH or ECDSA signing. */ 901 * so there is no timing leak for ECDH or ECDSA signing. */
854static void point_add(felem x3, felem y3, felem z3, 902static void
855 const felem x1, const felem y1, const felem z1, 903point_add(felem x3, felem y3, felem z3,
856 const int mixed, const felem x2, const felem y2, const felem z2) 904 const felem x1, const felem y1, const felem z1,
857 { 905 const int mixed, const felem x2, const felem y2, const felem z2)
906{
858 felem ftmp, ftmp2, ftmp3, ftmp4, ftmp5, x_out, y_out, z_out; 907 felem ftmp, ftmp2, ftmp3, ftmp4, ftmp5, x_out, y_out, z_out;
859 widefelem tmp, tmp2; 908 widefelem tmp, tmp2;
860 limb z1_is_zero, z2_is_zero, x_equal, y_equal; 909 limb z1_is_zero, z2_is_zero, x_equal, y_equal;
861 910
862 if (!mixed) 911 if (!mixed) {
863 {
864 /* ftmp2 = z2^2 */ 912 /* ftmp2 = z2^2 */
865 felem_square(tmp, z2); 913 felem_square(tmp, z2);
866 felem_reduce(ftmp2, tmp); 914 felem_reduce(ftmp2, tmp);
@@ -876,9 +924,7 @@ static void point_add(felem x3, felem y3, felem z3,
876 /* ftmp2 = z2^2*x1 */ 924 /* ftmp2 = z2^2*x1 */
877 felem_mul(tmp2, ftmp2, x1); 925 felem_mul(tmp2, ftmp2, x1);
878 felem_reduce(ftmp2, tmp2); 926 felem_reduce(ftmp2, tmp2);
879 } 927 } else {
880 else
881 {
882 /* We'll assume z2 = 1 (special case z2 = 0 is handled later) */ 928 /* We'll assume z2 = 1 (special case z2 = 0 is handled later) */
883 929
884 /* ftmp4 = z2^3*y1 */ 930 /* ftmp4 = z2^3*y1 */
@@ -886,7 +932,7 @@ static void point_add(felem x3, felem y3, felem z3,
886 932
887 /* ftmp2 = z2^2*x1 */ 933 /* ftmp2 = z2^2*x1 */
888 felem_assign(ftmp2, x1); 934 felem_assign(ftmp2, x1);
889 } 935 }
890 936
891 /* ftmp = z1^2 */ 937 /* ftmp = z1^2 */
892 felem_square(tmp, z1); 938 felem_square(tmp, z1);
@@ -914,30 +960,27 @@ static void point_add(felem x3, felem y3, felem z3,
914 /* tmp[i] < 2^116 + 2^64 + 8 < 2^117 */ 960 /* tmp[i] < 2^116 + 2^64 + 8 < 2^117 */
915 felem_reduce(ftmp, tmp); 961 felem_reduce(ftmp, tmp);
916 962
917 /* the formulae are incorrect if the points are equal 963 /*
918 * so we check for this and do doubling if this happens */ 964 * the formulae are incorrect if the points are equal so we check for
965 * this and do doubling if this happens
966 */
919 x_equal = felem_is_zero(ftmp); 967 x_equal = felem_is_zero(ftmp);
920 y_equal = felem_is_zero(ftmp3); 968 y_equal = felem_is_zero(ftmp3);
921 z1_is_zero = felem_is_zero(z1); 969 z1_is_zero = felem_is_zero(z1);
922 z2_is_zero = felem_is_zero(z2); 970 z2_is_zero = felem_is_zero(z2);
923 /* In affine coordinates, (X_1, Y_1) == (X_2, Y_2) */ 971 /* In affine coordinates, (X_1, Y_1) == (X_2, Y_2) */
924 if (x_equal && y_equal && !z1_is_zero && !z2_is_zero) 972 if (x_equal && y_equal && !z1_is_zero && !z2_is_zero) {
925 {
926 point_double(x3, y3, z3, x1, y1, z1); 973 point_double(x3, y3, z3, x1, y1, z1);
927 return; 974 return;
928 } 975 }
929
930 /* ftmp5 = z1*z2 */ 976 /* ftmp5 = z1*z2 */
931 if (!mixed) 977 if (!mixed) {
932 {
933 felem_mul(tmp, z1, z2); 978 felem_mul(tmp, z1, z2);
934 felem_reduce(ftmp5, tmp); 979 felem_reduce(ftmp5, tmp);
935 } 980 } else {
936 else
937 {
938 /* special case z2 = 0 is handled later */ 981 /* special case z2 = 0 is handled later */
939 felem_assign(ftmp5, z1); 982 felem_assign(ftmp5, z1);
940 } 983 }
941 984
942 /* z_out = (z1^2*x2 - z2^2*x1)*(z1*z2) */ 985 /* z_out = (z1^2*x2 - z2^2*x1)*(z1*z2) */
943 felem_mul(tmp, ftmp, ftmp5); 986 felem_mul(tmp, ftmp, ftmp5);
@@ -973,8 +1016,10 @@ static void point_add(felem x3, felem y3, felem z3,
973 felem_scalar(ftmp5, 2); 1016 felem_scalar(ftmp5, 2);
974 /* ftmp5[i] < 2 * 2^57 = 2^58 */ 1017 /* ftmp5[i] < 2 * 2^57 = 2^58 */
975 1018
976 /* x_out = (z1^3*y2 - z2^3*y1)^2 - (z1^2*x2 - z2^2*x1)^3 - 1019 /*
977 2*z2^2*x1*(z1^2*x2 - z2^2*x1)^2 */ 1020 * x_out = (z1^3*y2 - z2^3*y1)^2 - (z1^2*x2 - z2^2*x1)^3 -
1021 * 2*z2^2*x1*(z1^2*x2 - z2^2*x1)^2
1022 */
978 felem_diff_128_64(tmp2, ftmp5); 1023 felem_diff_128_64(tmp2, ftmp5);
979 /* tmp2[i] < 2^117 + 2^64 + 8 < 2^118 */ 1024 /* tmp2[i] < 2^117 + 2^64 + 8 < 2^118 */
980 felem_reduce(x_out, tmp2); 1025 felem_reduce(x_out, tmp2);
@@ -987,14 +1032,18 @@ static void point_add(felem x3, felem y3, felem z3,
987 felem_mul(tmp2, ftmp3, ftmp2); 1032 felem_mul(tmp2, ftmp3, ftmp2);
988 /* tmp2[i] < 4 * 2^57 * 2^59 = 2^118 */ 1033 /* tmp2[i] < 4 * 2^57 * 2^59 = 2^118 */
989 1034
990 /* y_out = (z1^3*y2 - z2^3*y1)*(z2^2*x1*(z1^2*x2 - z2^2*x1)^2 - x_out) - 1035 /*
991 z2^3*y1*(z1^2*x2 - z2^2*x1)^3 */ 1036 * y_out = (z1^3*y2 - z2^3*y1)*(z2^2*x1*(z1^2*x2 - z2^2*x1)^2 -
1037 * x_out) - z2^3*y1*(z1^2*x2 - z2^2*x1)^3
1038 */
992 widefelem_diff(tmp2, tmp); 1039 widefelem_diff(tmp2, tmp);
993 /* tmp2[i] < 2^118 + 2^120 < 2^121 */ 1040 /* tmp2[i] < 2^118 + 2^120 < 2^121 */
994 felem_reduce(y_out, tmp2); 1041 felem_reduce(y_out, tmp2);
995 1042
996 /* the result (x_out, y_out, z_out) is incorrect if one of the inputs is 1043 /*
997 * the point at infinity, so we need to check for this separately */ 1044 * the result (x_out, y_out, z_out) is incorrect if one of the inputs
1045 * is the point at infinity, so we need to check for this separately
1046 */
998 1047
999 /* if point 1 is at infinity, copy point 2 to output, and vice versa */ 1048 /* if point 1 is at infinity, copy point 2 to output, and vice versa */
1000 copy_conditional(x_out, x2, z1_is_zero); 1049 copy_conditional(x_out, x2, z1_is_zero);
@@ -1006,18 +1055,18 @@ static void point_add(felem x3, felem y3, felem z3,
1006 felem_assign(x3, x_out); 1055 felem_assign(x3, x_out);
1007 felem_assign(y3, y_out); 1056 felem_assign(y3, y_out);
1008 felem_assign(z3, z_out); 1057 felem_assign(z3, z_out);
1009 } 1058}
1010 1059
1011/* select_point selects the |idx|th point from a precomputation table and 1060/* select_point selects the |idx|th point from a precomputation table and
1012 * copies it to out. */ 1061 * copies it to out. */
1013static void select_point(const u64 idx, unsigned int size, const felem pre_comp[/*size*/][3], felem out[3]) 1062static void
1014 { 1063select_point(const u64 idx, unsigned int size, const felem pre_comp[ /* size */ ][3], felem out[3])
1064{
1015 unsigned i, j; 1065 unsigned i, j;
1016 limb *outlimbs = &out[0][0]; 1066 limb *outlimbs = &out[0][0];
1017 memset(outlimbs, 0, 3 * sizeof(felem)); 1067 memset(outlimbs, 0, 3 * sizeof(felem));
1018 1068
1019 for (i = 0; i < size; i++) 1069 for (i = 0; i < size; i++) {
1020 {
1021 const limb *inlimbs = &pre_comp[i][0][0]; 1070 const limb *inlimbs = &pre_comp[i][0][0];
1022 u64 mask = i ^ idx; 1071 u64 mask = i ^ idx;
1023 mask |= mask >> 4; 1072 mask |= mask >> 4;
@@ -1027,26 +1076,28 @@ static void select_point(const u64 idx, unsigned int size, const felem pre_comp[
1027 mask--; 1076 mask--;
1028 for (j = 0; j < 4 * 3; j++) 1077 for (j = 0; j < 4 * 3; j++)
1029 outlimbs[j] |= inlimbs[j] & mask; 1078 outlimbs[j] |= inlimbs[j] & mask;
1030 }
1031 } 1079 }
1080}
1032 1081
1033/* get_bit returns the |i|th bit in |in| */ 1082/* get_bit returns the |i|th bit in |in| */
1034static char get_bit(const felem_bytearray in, unsigned i) 1083static char
1035 { 1084get_bit(const felem_bytearray in, unsigned i)
1085{
1036 if (i >= 224) 1086 if (i >= 224)
1037 return 0; 1087 return 0;
1038 return (in[i >> 3] >> (i & 7)) & 1; 1088 return (in[i >> 3] >> (i & 7)) & 1;
1039 } 1089}
1040 1090
1041/* Interleaved point multiplication using precomputed point multiples: 1091/* Interleaved point multiplication using precomputed point multiples:
1042 * The small point multiples 0*P, 1*P, ..., 16*P are in pre_comp[], 1092 * The small point multiples 0*P, 1*P, ..., 16*P are in pre_comp[],
1043 * the scalars in scalars[]. If g_scalar is non-NULL, we also add this multiple 1093 * the scalars in scalars[]. If g_scalar is non-NULL, we also add this multiple
1044 * of the generator, using certain (large) precomputed multiples in g_pre_comp. 1094 * of the generator, using certain (large) precomputed multiples in g_pre_comp.
1045 * Output point (X, Y, Z) is stored in x_out, y_out, z_out */ 1095 * Output point (X, Y, Z) is stored in x_out, y_out, z_out */
1046static void batch_mul(felem x_out, felem y_out, felem z_out, 1096static void
1047 const felem_bytearray scalars[], const unsigned num_points, const u8 *g_scalar, 1097batch_mul(felem x_out, felem y_out, felem z_out,
1048 const int mixed, const felem pre_comp[][17][3], const felem g_pre_comp[2][16][3]) 1098 const felem_bytearray scalars[], const unsigned num_points, const u8 * g_scalar,
1049 { 1099 const int mixed, const felem pre_comp[][17][3], const felem g_pre_comp[2][16][3])
1100{
1050 int i, skip; 1101 int i, skip;
1051 unsigned num; 1102 unsigned num;
1052 unsigned gen_mul = (g_scalar != NULL); 1103 unsigned gen_mul = (g_scalar != NULL);
@@ -1057,20 +1108,20 @@ static void batch_mul(felem x_out, felem y_out, felem z_out,
1057 /* set nq to the point at infinity */ 1108 /* set nq to the point at infinity */
1058 memset(nq, 0, 3 * sizeof(felem)); 1109 memset(nq, 0, 3 * sizeof(felem));
1059 1110
1060 /* Loop over all scalars msb-to-lsb, interleaving additions 1111 /*
1061 * of multiples of the generator (two in each of the last 28 rounds) 1112 * Loop over all scalars msb-to-lsb, interleaving additions of
1062 * and additions of other points multiples (every 5th round). 1113 * multiples of the generator (two in each of the last 28 rounds) and
1114 * additions of other points multiples (every 5th round).
1063 */ 1115 */
1064 skip = 1; /* save two point operations in the first round */ 1116 skip = 1; /* save two point operations in the first
1065 for (i = (num_points ? 220 : 27); i >= 0; --i) 1117 * round */
1066 { 1118 for (i = (num_points ? 220 : 27); i >= 0; --i) {
1067 /* double */ 1119 /* double */
1068 if (!skip) 1120 if (!skip)
1069 point_double(nq[0], nq[1], nq[2], nq[0], nq[1], nq[2]); 1121 point_double(nq[0], nq[1], nq[2], nq[0], nq[1], nq[2]);
1070 1122
1071 /* add multiples of the generator */ 1123 /* add multiples of the generator */
1072 if (gen_mul && (i <= 27)) 1124 if (gen_mul && (i <= 27)) {
1073 {
1074 /* first, look 28 bits upwards */ 1125 /* first, look 28 bits upwards */
1075 bits = get_bit(g_scalar, i + 196) << 3; 1126 bits = get_bit(g_scalar, i + 196) << 3;
1076 bits |= get_bit(g_scalar, i + 140) << 2; 1127 bits |= get_bit(g_scalar, i + 140) << 2;
@@ -1079,17 +1130,14 @@ static void batch_mul(felem x_out, felem y_out, felem z_out,
1079 /* select the point to add, in constant time */ 1130 /* select the point to add, in constant time */
1080 select_point(bits, 16, g_pre_comp[1], tmp); 1131 select_point(bits, 16, g_pre_comp[1], tmp);
1081 1132
1082 if (!skip) 1133 if (!skip) {
1083 {
1084 point_add(nq[0], nq[1], nq[2], 1134 point_add(nq[0], nq[1], nq[2],
1085 nq[0], nq[1], nq[2], 1135 nq[0], nq[1], nq[2],
1086 1 /* mixed */, tmp[0], tmp[1], tmp[2]); 1136 1 /* mixed */ , tmp[0], tmp[1], tmp[2]);
1087 } 1137 } else {
1088 else
1089 {
1090 memcpy(nq, tmp, 3 * sizeof(felem)); 1138 memcpy(nq, tmp, 3 * sizeof(felem));
1091 skip = 0; 1139 skip = 0;
1092 } 1140 }
1093 1141
1094 /* second, look at the current position */ 1142 /* second, look at the current position */
1095 bits = get_bit(g_scalar, i + 168) << 3; 1143 bits = get_bit(g_scalar, i + 168) << 3;
@@ -1099,16 +1147,13 @@ static void batch_mul(felem x_out, felem y_out, felem z_out,
1099 /* select the point to add, in constant time */ 1147 /* select the point to add, in constant time */
1100 select_point(bits, 16, g_pre_comp[0], tmp); 1148 select_point(bits, 16, g_pre_comp[0], tmp);
1101 point_add(nq[0], nq[1], nq[2], 1149 point_add(nq[0], nq[1], nq[2],
1102 nq[0], nq[1], nq[2], 1150 nq[0], nq[1], nq[2],
1103 1 /* mixed */, tmp[0], tmp[1], tmp[2]); 1151 1 /* mixed */ , tmp[0], tmp[1], tmp[2]);
1104 } 1152 }
1105
1106 /* do other additions every 5 doublings */ 1153 /* do other additions every 5 doublings */
1107 if (num_points && (i % 5 == 0)) 1154 if (num_points && (i % 5 == 0)) {
1108 {
1109 /* loop over all scalars */ 1155 /* loop over all scalars */
1110 for (num = 0; num < num_points; ++num) 1156 for (num = 0; num < num_points; ++num) {
1111 {
1112 bits = get_bit(scalars[num], i + 4) << 5; 1157 bits = get_bit(scalars[num], i + 4) << 5;
1113 bits |= get_bit(scalars[num], i + 3) << 4; 1158 bits |= get_bit(scalars[num], i + 3) << 4;
1114 bits |= get_bit(scalars[num], i + 2) << 3; 1159 bits |= get_bit(scalars[num], i + 2) << 3;
@@ -1119,58 +1164,58 @@ static void batch_mul(felem x_out, felem y_out, felem z_out,
1119 1164
1120 /* select the point to add or subtract */ 1165 /* select the point to add or subtract */
1121 select_point(digit, 17, pre_comp[num], tmp); 1166 select_point(digit, 17, pre_comp[num], tmp);
1122 felem_neg(tmp[3], tmp[1]); /* (X, -Y, Z) is the negative point */ 1167 felem_neg(tmp[3], tmp[1]); /* (X, -Y, Z) is the
1168 * negative point */
1123 copy_conditional(tmp[1], tmp[3], sign); 1169 copy_conditional(tmp[1], tmp[3], sign);
1124 1170
1125 if (!skip) 1171 if (!skip) {
1126 {
1127 point_add(nq[0], nq[1], nq[2], 1172 point_add(nq[0], nq[1], nq[2],
1128 nq[0], nq[1], nq[2], 1173 nq[0], nq[1], nq[2],
1129 mixed, tmp[0], tmp[1], tmp[2]); 1174 mixed, tmp[0], tmp[1], tmp[2]);
1130 } 1175 } else {
1131 else
1132 {
1133 memcpy(nq, tmp, 3 * sizeof(felem)); 1176 memcpy(nq, tmp, 3 * sizeof(felem));
1134 skip = 0; 1177 skip = 0;
1135 }
1136 } 1178 }
1137 } 1179 }
1138 } 1180 }
1181 }
1139 felem_assign(x_out, nq[0]); 1182 felem_assign(x_out, nq[0]);
1140 felem_assign(y_out, nq[1]); 1183 felem_assign(y_out, nq[1]);
1141 felem_assign(z_out, nq[2]); 1184 felem_assign(z_out, nq[2]);
1142 } 1185}
1143 1186
1144/******************************************************************************/ 1187/******************************************************************************/
1145/* FUNCTIONS TO MANAGE PRECOMPUTATION 1188/* FUNCTIONS TO MANAGE PRECOMPUTATION
1146 */ 1189 */
1147 1190
1148static NISTP224_PRE_COMP *nistp224_pre_comp_new() 1191static NISTP224_PRE_COMP *
1149 { 1192nistp224_pre_comp_new()
1193{
1150 NISTP224_PRE_COMP *ret = NULL; 1194 NISTP224_PRE_COMP *ret = NULL;
1151 ret = (NISTP224_PRE_COMP *) malloc(sizeof *ret); 1195 ret = (NISTP224_PRE_COMP *) malloc(sizeof *ret);
1152 if (!ret) 1196 if (!ret) {
1153 {
1154 ECerr(EC_F_NISTP224_PRE_COMP_NEW, ERR_R_MALLOC_FAILURE); 1197 ECerr(EC_F_NISTP224_PRE_COMP_NEW, ERR_R_MALLOC_FAILURE);
1155 return ret; 1198 return ret;
1156 } 1199 }
1157 memset(ret->g_pre_comp, 0, sizeof(ret->g_pre_comp)); 1200 memset(ret->g_pre_comp, 0, sizeof(ret->g_pre_comp));
1158 ret->references = 1; 1201 ret->references = 1;
1159 return ret; 1202 return ret;
1160 } 1203}
1161 1204
1162static void *nistp224_pre_comp_dup(void *src_) 1205static void *
1163 { 1206nistp224_pre_comp_dup(void *src_)
1207{
1164 NISTP224_PRE_COMP *src = src_; 1208 NISTP224_PRE_COMP *src = src_;
1165 1209
1166 /* no need to actually copy, these objects never change! */ 1210 /* no need to actually copy, these objects never change! */
1167 CRYPTO_add(&src->references, 1, CRYPTO_LOCK_EC_PRE_COMP); 1211 CRYPTO_add(&src->references, 1, CRYPTO_LOCK_EC_PRE_COMP);
1168 1212
1169 return src_; 1213 return src_;
1170 } 1214}
1171 1215
1172static void nistp224_pre_comp_free(void *pre_) 1216static void
1173 { 1217nistp224_pre_comp_free(void *pre_)
1218{
1174 int i; 1219 int i;
1175 NISTP224_PRE_COMP *pre = pre_; 1220 NISTP224_PRE_COMP *pre = pre_;
1176 1221
@@ -1182,10 +1227,11 @@ static void nistp224_pre_comp_free(void *pre_)
1182 return; 1227 return;
1183 1228
1184 free(pre); 1229 free(pre);
1185 } 1230}
1186 1231
1187static void nistp224_pre_comp_clear_free(void *pre_) 1232static void
1188 { 1233nistp224_pre_comp_clear_free(void *pre_)
1234{
1189 int i; 1235 int i;
1190 NISTP224_PRE_COMP *pre = pre_; 1236 NISTP224_PRE_COMP *pre = pre_;
1191 1237
@@ -1198,43 +1244,46 @@ static void nistp224_pre_comp_clear_free(void *pre_)
1198 1244
1199 OPENSSL_cleanse(pre, sizeof *pre); 1245 OPENSSL_cleanse(pre, sizeof *pre);
1200 free(pre); 1246 free(pre);
1201 } 1247}
1202 1248
1203/******************************************************************************/ 1249/******************************************************************************/
1204/* OPENSSL EC_METHOD FUNCTIONS 1250/* OPENSSL EC_METHOD FUNCTIONS
1205 */ 1251 */
1206 1252
1207int ec_GFp_nistp224_group_init(EC_GROUP *group) 1253int
1208 { 1254ec_GFp_nistp224_group_init(EC_GROUP * group)
1255{
1209 int ret; 1256 int ret;
1210 ret = ec_GFp_simple_group_init(group); 1257 ret = ec_GFp_simple_group_init(group);
1211 group->a_is_minus3 = 1; 1258 group->a_is_minus3 = 1;
1212 return ret; 1259 return ret;
1213 } 1260}
1214 1261
1215int ec_GFp_nistp224_group_set_curve(EC_GROUP *group, const BIGNUM *p, 1262int
1216 const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) 1263ec_GFp_nistp224_group_set_curve(EC_GROUP * group, const BIGNUM * p,
1217 { 1264 const BIGNUM * a, const BIGNUM * b, BN_CTX * ctx)
1265{
1218 int ret = 0; 1266 int ret = 0;
1219 BN_CTX *new_ctx = NULL; 1267 BN_CTX *new_ctx = NULL;
1220 BIGNUM *curve_p, *curve_a, *curve_b; 1268 BIGNUM *curve_p, *curve_a, *curve_b;
1221 1269
1222 if (ctx == NULL) 1270 if (ctx == NULL)
1223 if ((ctx = new_ctx = BN_CTX_new()) == NULL) return 0; 1271 if ((ctx = new_ctx = BN_CTX_new()) == NULL)
1272 return 0;
1224 BN_CTX_start(ctx); 1273 BN_CTX_start(ctx);
1225 if (((curve_p = BN_CTX_get(ctx)) == NULL) || 1274 if (((curve_p = BN_CTX_get(ctx)) == NULL) ||
1226 ((curve_a = BN_CTX_get(ctx)) == NULL) || 1275 ((curve_a = BN_CTX_get(ctx)) == NULL) ||
1227 ((curve_b = BN_CTX_get(ctx)) == NULL)) goto err; 1276 ((curve_b = BN_CTX_get(ctx)) == NULL))
1277 goto err;
1228 BN_bin2bn(nistp224_curve_params[0], sizeof(felem_bytearray), curve_p); 1278 BN_bin2bn(nistp224_curve_params[0], sizeof(felem_bytearray), curve_p);
1229 BN_bin2bn(nistp224_curve_params[1], sizeof(felem_bytearray), curve_a); 1279 BN_bin2bn(nistp224_curve_params[1], sizeof(felem_bytearray), curve_a);
1230 BN_bin2bn(nistp224_curve_params[2], sizeof(felem_bytearray), curve_b); 1280 BN_bin2bn(nistp224_curve_params[2], sizeof(felem_bytearray), curve_b);
1231 if ((BN_cmp(curve_p, p)) || (BN_cmp(curve_a, a)) || 1281 if ((BN_cmp(curve_p, p)) || (BN_cmp(curve_a, a)) ||
1232 (BN_cmp(curve_b, b))) 1282 (BN_cmp(curve_b, b))) {
1233 {
1234 ECerr(EC_F_EC_GFP_NISTP224_GROUP_SET_CURVE, 1283 ECerr(EC_F_EC_GFP_NISTP224_GROUP_SET_CURVE,
1235 EC_R_WRONG_CURVE_PARAMETERS); 1284 EC_R_WRONG_CURVE_PARAMETERS);
1236 goto err; 1285 goto err;
1237 } 1286 }
1238 group->field_mod_func = BN_nist_mod_224; 1287 group->field_mod_func = BN_nist_mod_224;
1239 ret = ec_GFp_simple_group_set_curve(group, p, a, b, ctx); 1288 ret = ec_GFp_simple_group_set_curve(group, p, a, b, ctx);
1240err: 1289err:
@@ -1242,74 +1291,81 @@ err:
1242 if (new_ctx != NULL) 1291 if (new_ctx != NULL)
1243 BN_CTX_free(new_ctx); 1292 BN_CTX_free(new_ctx);
1244 return ret; 1293 return ret;
1245 } 1294}
1246 1295
1247/* Takes the Jacobian coordinates (X, Y, Z) of a point and returns 1296/* Takes the Jacobian coordinates (X, Y, Z) of a point and returns
1248 * (X', Y') = (X/Z^2, Y/Z^3) */ 1297 * (X', Y') = (X/Z^2, Y/Z^3) */
1249int ec_GFp_nistp224_point_get_affine_coordinates(const EC_GROUP *group, 1298int
1250 const EC_POINT *point, BIGNUM *x, BIGNUM *y, BN_CTX *ctx) 1299ec_GFp_nistp224_point_get_affine_coordinates(const EC_GROUP * group,
1251 { 1300 const EC_POINT * point, BIGNUM * x, BIGNUM * y, BN_CTX * ctx)
1301{
1252 felem z1, z2, x_in, y_in, x_out, y_out; 1302 felem z1, z2, x_in, y_in, x_out, y_out;
1253 widefelem tmp; 1303 widefelem tmp;
1254 1304
1255 if (EC_POINT_is_at_infinity(group, point)) 1305 if (EC_POINT_is_at_infinity(group, point)) {
1256 {
1257 ECerr(EC_F_EC_GFP_NISTP224_POINT_GET_AFFINE_COORDINATES, 1306 ECerr(EC_F_EC_GFP_NISTP224_POINT_GET_AFFINE_COORDINATES,
1258 EC_R_POINT_AT_INFINITY); 1307 EC_R_POINT_AT_INFINITY);
1259 return 0; 1308 return 0;
1260 } 1309 }
1261 if ((!BN_to_felem(x_in, &point->X)) || (!BN_to_felem(y_in, &point->Y)) || 1310 if ((!BN_to_felem(x_in, &point->X)) || (!BN_to_felem(y_in, &point->Y)) ||
1262 (!BN_to_felem(z1, &point->Z))) return 0; 1311 (!BN_to_felem(z1, &point->Z)))
1312 return 0;
1263 felem_inv(z2, z1); 1313 felem_inv(z2, z1);
1264 felem_square(tmp, z2); felem_reduce(z1, tmp); 1314 felem_square(tmp, z2);
1265 felem_mul(tmp, x_in, z1); felem_reduce(x_in, tmp); 1315 felem_reduce(z1, tmp);
1316 felem_mul(tmp, x_in, z1);
1317 felem_reduce(x_in, tmp);
1266 felem_contract(x_out, x_in); 1318 felem_contract(x_out, x_in);
1267 if (x != NULL) 1319 if (x != NULL) {
1268 {
1269 if (!felem_to_BN(x, x_out)) { 1320 if (!felem_to_BN(x, x_out)) {
1270 ECerr(EC_F_EC_GFP_NISTP224_POINT_GET_AFFINE_COORDINATES, 1321 ECerr(EC_F_EC_GFP_NISTP224_POINT_GET_AFFINE_COORDINATES,
1271 ERR_R_BN_LIB); 1322 ERR_R_BN_LIB);
1272 return 0; 1323 return 0;
1273 }
1274 } 1324 }
1275 felem_mul(tmp, z1, z2); felem_reduce(z1, tmp); 1325 }
1276 felem_mul(tmp, y_in, z1); felem_reduce(y_in, tmp); 1326 felem_mul(tmp, z1, z2);
1327 felem_reduce(z1, tmp);
1328 felem_mul(tmp, y_in, z1);
1329 felem_reduce(y_in, tmp);
1277 felem_contract(y_out, y_in); 1330 felem_contract(y_out, y_in);
1278 if (y != NULL) 1331 if (y != NULL) {
1279 {
1280 if (!felem_to_BN(y, y_out)) { 1332 if (!felem_to_BN(y, y_out)) {
1281 ECerr(EC_F_EC_GFP_NISTP224_POINT_GET_AFFINE_COORDINATES, 1333 ECerr(EC_F_EC_GFP_NISTP224_POINT_GET_AFFINE_COORDINATES,
1282 ERR_R_BN_LIB); 1334 ERR_R_BN_LIB);
1283 return 0; 1335 return 0;
1284 }
1285 } 1336 }
1286 return 1;
1287 } 1337 }
1338 return 1;
1339}
1288 1340
1289static void make_points_affine(size_t num, felem points[/*num*/][3], felem tmp_felems[/*num+1*/]) 1341static void
1290 { 1342make_points_affine(size_t num, felem points[ /* num */ ][3], felem tmp_felems[ /* num+1 */ ])
1291 /* Runs in constant time, unless an input is the point at infinity 1343{
1292 * (which normally shouldn't happen). */ 1344 /*
1345 * Runs in constant time, unless an input is the point at infinity
1346 * (which normally shouldn't happen).
1347 */
1293 ec_GFp_nistp_points_make_affine_internal( 1348 ec_GFp_nistp_points_make_affine_internal(
1294 num, 1349 num,
1295 points, 1350 points,
1296 sizeof(felem), 1351 sizeof(felem),
1297 tmp_felems, 1352 tmp_felems,
1298 (void (*)(void *)) felem_one, 1353 (void (*) (void *)) felem_one,
1299 (int (*)(const void *)) felem_is_zero_int, 1354 (int (*) (const void *)) felem_is_zero_int,
1300 (void (*)(void *, const void *)) felem_assign, 1355 (void (*) (void *, const void *)) felem_assign,
1301 (void (*)(void *, const void *)) felem_square_reduce, 1356 (void (*) (void *, const void *)) felem_square_reduce,
1302 (void (*)(void *, const void *, const void *)) felem_mul_reduce, 1357 (void (*) (void *, const void *, const void *)) felem_mul_reduce,
1303 (void (*)(void *, const void *)) felem_inv, 1358 (void (*) (void *, const void *)) felem_inv,
1304 (void (*)(void *, const void *)) felem_contract); 1359 (void (*) (void *, const void *)) felem_contract);
1305 } 1360}
1306 1361
1307/* Computes scalar*generator + \sum scalars[i]*points[i], ignoring NULL values 1362/* Computes scalar*generator + \sum scalars[i]*points[i], ignoring NULL values
1308 * Result is stored in r (r can equal one of the inputs). */ 1363 * Result is stored in r (r can equal one of the inputs). */
1309int ec_GFp_nistp224_points_mul(const EC_GROUP *group, EC_POINT *r, 1364int
1310 const BIGNUM *scalar, size_t num, const EC_POINT *points[], 1365ec_GFp_nistp224_points_mul(const EC_GROUP * group, EC_POINT * r,
1311 const BIGNUM *scalars[], BN_CTX *ctx) 1366 const BIGNUM * scalar, size_t num, const EC_POINT * points[],
1312 { 1367 const BIGNUM * scalars[], BN_CTX * ctx)
1368{
1313 int ret = 0; 1369 int ret = 0;
1314 int j; 1370 int j;
1315 unsigned i; 1371 unsigned i;
@@ -1318,7 +1374,7 @@ int ec_GFp_nistp224_points_mul(const EC_GROUP *group, EC_POINT *r,
1318 BIGNUM *x, *y, *z, *tmp_scalar; 1374 BIGNUM *x, *y, *z, *tmp_scalar;
1319 felem_bytearray g_secret; 1375 felem_bytearray g_secret;
1320 felem_bytearray *secrets = NULL; 1376 felem_bytearray *secrets = NULL;
1321 felem (*pre_comp)[17][3] = NULL; 1377 felem(*pre_comp)[17][3] = NULL;
1322 felem *tmp_felems = NULL; 1378 felem *tmp_felems = NULL;
1323 felem_bytearray tmp; 1379 felem_bytearray tmp;
1324 unsigned num_bytes; 1380 unsigned num_bytes;
@@ -1326,28 +1382,28 @@ int ec_GFp_nistp224_points_mul(const EC_GROUP *group, EC_POINT *r,
1326 size_t num_points = num; 1382 size_t num_points = num;
1327 felem x_in, y_in, z_in, x_out, y_out, z_out; 1383 felem x_in, y_in, z_in, x_out, y_out, z_out;
1328 NISTP224_PRE_COMP *pre = NULL; 1384 NISTP224_PRE_COMP *pre = NULL;
1329 const felem (*g_pre_comp)[16][3] = NULL; 1385 const felem(*g_pre_comp)[16][3] = NULL;
1330 EC_POINT *generator = NULL; 1386 EC_POINT *generator = NULL;
1331 const EC_POINT *p = NULL; 1387 const EC_POINT *p = NULL;
1332 const BIGNUM *p_scalar = NULL; 1388 const BIGNUM *p_scalar = NULL;
1333 1389
1334 if (ctx == NULL) 1390 if (ctx == NULL)
1335 if ((ctx = new_ctx = BN_CTX_new()) == NULL) return 0; 1391 if ((ctx = new_ctx = BN_CTX_new()) == NULL)
1392 return 0;
1336 BN_CTX_start(ctx); 1393 BN_CTX_start(ctx);
1337 if (((x = BN_CTX_get(ctx)) == NULL) || 1394 if (((x = BN_CTX_get(ctx)) == NULL) ||
1338 ((y = BN_CTX_get(ctx)) == NULL) || 1395 ((y = BN_CTX_get(ctx)) == NULL) ||
1339 ((z = BN_CTX_get(ctx)) == NULL) || 1396 ((z = BN_CTX_get(ctx)) == NULL) ||
1340 ((tmp_scalar = BN_CTX_get(ctx)) == NULL)) 1397 ((tmp_scalar = BN_CTX_get(ctx)) == NULL))
1341 goto err; 1398 goto err;
1342 1399
1343 if (scalar != NULL) 1400 if (scalar != NULL) {
1344 {
1345 pre = EC_EX_DATA_get_data(group->extra_data, 1401 pre = EC_EX_DATA_get_data(group->extra_data,
1346 nistp224_pre_comp_dup, nistp224_pre_comp_free, 1402 nistp224_pre_comp_dup, nistp224_pre_comp_free,
1347 nistp224_pre_comp_clear_free); 1403 nistp224_pre_comp_clear_free);
1348 if (pre) 1404 if (pre)
1349 /* we have precomputation, try to use it */ 1405 /* we have precomputation, try to use it */
1350 g_pre_comp = (const felem (*)[16][3]) pre->g_pre_comp; 1406 g_pre_comp = (const felem(*)[16][3]) pre->g_pre_comp;
1351 else 1407 else
1352 /* try to use the standard precomputation */ 1408 /* try to use the standard precomputation */
1353 g_pre_comp = &gmul[0]; 1409 g_pre_comp = &gmul[0];
@@ -1356,147 +1412,137 @@ int ec_GFp_nistp224_points_mul(const EC_GROUP *group, EC_POINT *r,
1356 goto err; 1412 goto err;
1357 /* get the generator from precomputation */ 1413 /* get the generator from precomputation */
1358 if (!felem_to_BN(x, g_pre_comp[0][1][0]) || 1414 if (!felem_to_BN(x, g_pre_comp[0][1][0]) ||
1359 !felem_to_BN(y, g_pre_comp[0][1][1]) || 1415 !felem_to_BN(y, g_pre_comp[0][1][1]) ||
1360 !felem_to_BN(z, g_pre_comp[0][1][2])) 1416 !felem_to_BN(z, g_pre_comp[0][1][2])) {
1361 {
1362 ECerr(EC_F_EC_GFP_NISTP224_POINTS_MUL, ERR_R_BN_LIB); 1417 ECerr(EC_F_EC_GFP_NISTP224_POINTS_MUL, ERR_R_BN_LIB);
1363 goto err; 1418 goto err;
1364 } 1419 }
1365 if (!EC_POINT_set_Jprojective_coordinates_GFp(group, 1420 if (!EC_POINT_set_Jprojective_coordinates_GFp(group,
1366 generator, x, y, z, ctx)) 1421 generator, x, y, z, ctx))
1367 goto err; 1422 goto err;
1368 if (0 == EC_POINT_cmp(group, generator, group->generator, ctx)) 1423 if (0 == EC_POINT_cmp(group, generator, group->generator, ctx))
1369 /* precomputation matches generator */ 1424 /* precomputation matches generator */
1370 have_pre_comp = 1; 1425 have_pre_comp = 1;
1371 else 1426 else
1372 /* we don't have valid precomputation: 1427 /*
1373 * treat the generator as a random point */ 1428 * we don't have valid precomputation: treat the
1429 * generator as a random point
1430 */
1374 num_points = num_points + 1; 1431 num_points = num_points + 1;
1375 } 1432 }
1376 1433 if (num_points > 0) {
1377 if (num_points > 0) 1434 if (num_points >= 3) {
1378 { 1435 /*
1379 if (num_points >= 3) 1436 * unless we precompute multiples for just one or two
1380 { 1437 * points, converting those into affine form is time
1381 /* unless we precompute multiples for just one or two points, 1438 * well spent
1382 * converting those into affine form is time well spent */ 1439 */
1383 mixed = 1; 1440 mixed = 1;
1384 } 1441 }
1385 secrets = malloc(num_points * sizeof(felem_bytearray)); 1442 secrets = malloc(num_points * sizeof(felem_bytearray));
1386 pre_comp = malloc(num_points * 17 * 3 * sizeof(felem)); 1443 pre_comp = malloc(num_points * 17 * 3 * sizeof(felem));
1387 if (mixed) 1444 if (mixed)
1388 tmp_felems = malloc((num_points * 17 + 1) * sizeof(felem)); 1445 tmp_felems = malloc((num_points * 17 + 1) * sizeof(felem));
1389 if ((secrets == NULL) || (pre_comp == NULL) || (mixed && (tmp_felems == NULL))) 1446 if ((secrets == NULL) || (pre_comp == NULL) || (mixed && (tmp_felems == NULL))) {
1390 {
1391 ECerr(EC_F_EC_GFP_NISTP224_POINTS_MUL, ERR_R_MALLOC_FAILURE); 1447 ECerr(EC_F_EC_GFP_NISTP224_POINTS_MUL, ERR_R_MALLOC_FAILURE);
1392 goto err; 1448 goto err;
1393 } 1449 }
1394 1450 /*
1395 /* we treat NULL scalars as 0, and NULL points as points at infinity, 1451 * we treat NULL scalars as 0, and NULL points as points at
1396 * i.e., they contribute nothing to the linear combination */ 1452 * infinity, i.e., they contribute nothing to the linear
1453 * combination
1454 */
1397 memset(secrets, 0, num_points * sizeof(felem_bytearray)); 1455 memset(secrets, 0, num_points * sizeof(felem_bytearray));
1398 memset(pre_comp, 0, num_points * 17 * 3 * sizeof(felem)); 1456 memset(pre_comp, 0, num_points * 17 * 3 * sizeof(felem));
1399 for (i = 0; i < num_points; ++i) 1457 for (i = 0; i < num_points; ++i) {
1400 {
1401 if (i == num) 1458 if (i == num)
1402 /* the generator */ 1459 /* the generator */
1403 { 1460 {
1404 p = EC_GROUP_get0_generator(group); 1461 p = EC_GROUP_get0_generator(group);
1405 p_scalar = scalar; 1462 p_scalar = scalar;
1406 } 1463 } else
1407 else
1408 /* the i^th point */ 1464 /* the i^th point */
1409 { 1465 {
1410 p = points[i]; 1466 p = points[i];
1411 p_scalar = scalars[i]; 1467 p_scalar = scalars[i];
1412 } 1468 }
1413 if ((p_scalar != NULL) && (p != NULL)) 1469 if ((p_scalar != NULL) && (p != NULL)) {
1414 {
1415 /* reduce scalar to 0 <= scalar < 2^224 */ 1470 /* reduce scalar to 0 <= scalar < 2^224 */
1416 if ((BN_num_bits(p_scalar) > 224) || (BN_is_negative(p_scalar))) 1471 if ((BN_num_bits(p_scalar) > 224) || (BN_is_negative(p_scalar))) {
1417 { 1472 /*
1418 /* this is an unusual input, and we don't guarantee 1473 * this is an unusual input, and we
1419 * constant-timeness */ 1474 * don't guarantee constant-timeness
1420 if (!BN_nnmod(tmp_scalar, p_scalar, &group->order, ctx)) 1475 */
1421 { 1476 if (!BN_nnmod(tmp_scalar, p_scalar, &group->order, ctx)) {
1422 ECerr(EC_F_EC_GFP_NISTP224_POINTS_MUL, ERR_R_BN_LIB); 1477 ECerr(EC_F_EC_GFP_NISTP224_POINTS_MUL, ERR_R_BN_LIB);
1423 goto err; 1478 goto err;
1424 }
1425 num_bytes = BN_bn2bin(tmp_scalar, tmp);
1426 } 1479 }
1427 else 1480 num_bytes = BN_bn2bin(tmp_scalar, tmp);
1481 } else
1428 num_bytes = BN_bn2bin(p_scalar, tmp); 1482 num_bytes = BN_bn2bin(p_scalar, tmp);
1429 flip_endian(secrets[i], tmp, num_bytes); 1483 flip_endian(secrets[i], tmp, num_bytes);
1430 /* precompute multiples */ 1484 /* precompute multiples */
1431 if ((!BN_to_felem(x_out, &p->X)) || 1485 if ((!BN_to_felem(x_out, &p->X)) ||
1432 (!BN_to_felem(y_out, &p->Y)) || 1486 (!BN_to_felem(y_out, &p->Y)) ||
1433 (!BN_to_felem(z_out, &p->Z))) goto err; 1487 (!BN_to_felem(z_out, &p->Z)))
1488 goto err;
1434 felem_assign(pre_comp[i][1][0], x_out); 1489 felem_assign(pre_comp[i][1][0], x_out);
1435 felem_assign(pre_comp[i][1][1], y_out); 1490 felem_assign(pre_comp[i][1][1], y_out);
1436 felem_assign(pre_comp[i][1][2], z_out); 1491 felem_assign(pre_comp[i][1][2], z_out);
1437 for (j = 2; j <= 16; ++j) 1492 for (j = 2; j <= 16; ++j) {
1438 { 1493 if (j & 1) {
1439 if (j & 1)
1440 {
1441 point_add( 1494 point_add(
1442 pre_comp[i][j][0], pre_comp[i][j][1], pre_comp[i][j][2], 1495 pre_comp[i][j][0], pre_comp[i][j][1], pre_comp[i][j][2],
1443 pre_comp[i][1][0], pre_comp[i][1][1], pre_comp[i][1][2], 1496 pre_comp[i][1][0], pre_comp[i][1][1], pre_comp[i][1][2],
1444 0, pre_comp[i][j-1][0], pre_comp[i][j-1][1], pre_comp[i][j-1][2]); 1497 0, pre_comp[i][j - 1][0], pre_comp[i][j - 1][1], pre_comp[i][j - 1][2]);
1445 } 1498 } else {
1446 else
1447 {
1448 point_double( 1499 point_double(
1449 pre_comp[i][j][0], pre_comp[i][j][1], pre_comp[i][j][2], 1500 pre_comp[i][j][0], pre_comp[i][j][1], pre_comp[i][j][2],
1450 pre_comp[i][j/2][0], pre_comp[i][j/2][1], pre_comp[i][j/2][2]); 1501 pre_comp[i][j / 2][0], pre_comp[i][j / 2][1], pre_comp[i][j / 2][2]);
1451 }
1452 } 1502 }
1453 } 1503 }
1454 } 1504 }
1505 }
1455 if (mixed) 1506 if (mixed)
1456 make_points_affine(num_points * 17, pre_comp[0], tmp_felems); 1507 make_points_affine(num_points * 17, pre_comp[0], tmp_felems);
1457 } 1508 }
1458
1459 /* the scalar for the generator */ 1509 /* the scalar for the generator */
1460 if ((scalar != NULL) && (have_pre_comp)) 1510 if ((scalar != NULL) && (have_pre_comp)) {
1461 {
1462 memset(g_secret, 0, sizeof g_secret); 1511 memset(g_secret, 0, sizeof g_secret);
1463 /* reduce scalar to 0 <= scalar < 2^224 */ 1512 /* reduce scalar to 0 <= scalar < 2^224 */
1464 if ((BN_num_bits(scalar) > 224) || (BN_is_negative(scalar))) 1513 if ((BN_num_bits(scalar) > 224) || (BN_is_negative(scalar))) {
1465 { 1514 /*
1466 /* this is an unusual input, and we don't guarantee 1515 * this is an unusual input, and we don't guarantee
1467 * constant-timeness */ 1516 * constant-timeness
1468 if (!BN_nnmod(tmp_scalar, scalar, &group->order, ctx)) 1517 */
1469 { 1518 if (!BN_nnmod(tmp_scalar, scalar, &group->order, ctx)) {
1470 ECerr(EC_F_EC_GFP_NISTP224_POINTS_MUL, ERR_R_BN_LIB); 1519 ECerr(EC_F_EC_GFP_NISTP224_POINTS_MUL, ERR_R_BN_LIB);
1471 goto err; 1520 goto err;
1472 }
1473 num_bytes = BN_bn2bin(tmp_scalar, tmp);
1474 } 1521 }
1475 else 1522 num_bytes = BN_bn2bin(tmp_scalar, tmp);
1523 } else
1476 num_bytes = BN_bn2bin(scalar, tmp); 1524 num_bytes = BN_bn2bin(scalar, tmp);
1477 flip_endian(g_secret, tmp, num_bytes); 1525 flip_endian(g_secret, tmp, num_bytes);
1478 /* do the multiplication with generator precomputation*/ 1526 /* do the multiplication with generator precomputation */
1479 batch_mul(x_out, y_out, z_out, 1527 batch_mul(x_out, y_out, z_out,
1480 (const felem_bytearray (*)) secrets, num_points, 1528 (const felem_bytearray(*)) secrets, num_points,
1481 g_secret, 1529 g_secret,
1482 mixed, (const felem (*)[17][3]) pre_comp, 1530 mixed, (const felem(*)[17][3]) pre_comp,
1483 g_pre_comp); 1531 g_pre_comp);
1484 } 1532 } else
1485 else
1486 /* do the multiplication without generator precomputation */ 1533 /* do the multiplication without generator precomputation */
1487 batch_mul(x_out, y_out, z_out, 1534 batch_mul(x_out, y_out, z_out,
1488 (const felem_bytearray (*)) secrets, num_points, 1535 (const felem_bytearray(*)) secrets, num_points,
1489 NULL, mixed, (const felem (*)[17][3]) pre_comp, NULL); 1536 NULL, mixed, (const felem(*)[17][3]) pre_comp, NULL);
1490 /* reduce the output to its unique minimal representation */ 1537 /* reduce the output to its unique minimal representation */
1491 felem_contract(x_in, x_out); 1538 felem_contract(x_in, x_out);
1492 felem_contract(y_in, y_out); 1539 felem_contract(y_in, y_out);
1493 felem_contract(z_in, z_out); 1540 felem_contract(z_in, z_out);
1494 if ((!felem_to_BN(x, x_in)) || (!felem_to_BN(y, y_in)) || 1541 if ((!felem_to_BN(x, x_in)) || (!felem_to_BN(y, y_in)) ||
1495 (!felem_to_BN(z, z_in))) 1542 (!felem_to_BN(z, z_in))) {
1496 {
1497 ECerr(EC_F_EC_GFP_NISTP224_POINTS_MUL, ERR_R_BN_LIB); 1543 ECerr(EC_F_EC_GFP_NISTP224_POINTS_MUL, ERR_R_BN_LIB);
1498 goto err; 1544 goto err;
1499 } 1545 }
1500 ret = EC_POINT_set_Jprojective_coordinates_GFp(group, r, x, y, z, ctx); 1546 ret = EC_POINT_set_Jprojective_coordinates_GFp(group, r, x, y, z, ctx);
1501 1547
1502err: 1548err:
@@ -1512,10 +1558,11 @@ err:
1512 if (tmp_felems != NULL) 1558 if (tmp_felems != NULL)
1513 free(tmp_felems); 1559 free(tmp_felems);
1514 return ret; 1560 return ret;
1515 } 1561}
1516 1562
1517int ec_GFp_nistp224_precompute_mult(EC_GROUP *group, BN_CTX *ctx) 1563int
1518 { 1564ec_GFp_nistp224_precompute_mult(EC_GROUP * group, BN_CTX * ctx)
1565{
1519 int ret = 0; 1566 int ret = 0;
1520 NISTP224_PRE_COMP *pre = NULL; 1567 NISTP224_PRE_COMP *pre = NULL;
1521 int i, j; 1568 int i, j;
@@ -1526,113 +1573,113 @@ int ec_GFp_nistp224_precompute_mult(EC_GROUP *group, BN_CTX *ctx)
1526 1573
1527 /* throw away old precomputation */ 1574 /* throw away old precomputation */
1528 EC_EX_DATA_free_data(&group->extra_data, nistp224_pre_comp_dup, 1575 EC_EX_DATA_free_data(&group->extra_data, nistp224_pre_comp_dup,
1529 nistp224_pre_comp_free, nistp224_pre_comp_clear_free); 1576 nistp224_pre_comp_free, nistp224_pre_comp_clear_free);
1530 if (ctx == NULL) 1577 if (ctx == NULL)
1531 if ((ctx = new_ctx = BN_CTX_new()) == NULL) return 0; 1578 if ((ctx = new_ctx = BN_CTX_new()) == NULL)
1579 return 0;
1532 BN_CTX_start(ctx); 1580 BN_CTX_start(ctx);
1533 if (((x = BN_CTX_get(ctx)) == NULL) || 1581 if (((x = BN_CTX_get(ctx)) == NULL) ||
1534 ((y = BN_CTX_get(ctx)) == NULL)) 1582 ((y = BN_CTX_get(ctx)) == NULL))
1535 goto err; 1583 goto err;
1536 /* get the generator */ 1584 /* get the generator */
1537 if (group->generator == NULL) goto err; 1585 if (group->generator == NULL)
1586 goto err;
1538 generator = EC_POINT_new(group); 1587 generator = EC_POINT_new(group);
1539 if (generator == NULL) 1588 if (generator == NULL)
1540 goto err; 1589 goto err;
1541 BN_bin2bn(nistp224_curve_params[3], sizeof (felem_bytearray), x); 1590 BN_bin2bn(nistp224_curve_params[3], sizeof(felem_bytearray), x);
1542 BN_bin2bn(nistp224_curve_params[4], sizeof (felem_bytearray), y); 1591 BN_bin2bn(nistp224_curve_params[4], sizeof(felem_bytearray), y);
1543 if (!EC_POINT_set_affine_coordinates_GFp(group, generator, x, y, ctx)) 1592 if (!EC_POINT_set_affine_coordinates_GFp(group, generator, x, y, ctx))
1544 goto err; 1593 goto err;
1545 if ((pre = nistp224_pre_comp_new()) == NULL) 1594 if ((pre = nistp224_pre_comp_new()) == NULL)
1546 goto err; 1595 goto err;
1547 /* if the generator is the standard one, use built-in precomputation */ 1596 /* if the generator is the standard one, use built-in precomputation */
1548 if (0 == EC_POINT_cmp(group, generator, group->generator, ctx)) 1597 if (0 == EC_POINT_cmp(group, generator, group->generator, ctx)) {
1549 {
1550 memcpy(pre->g_pre_comp, gmul, sizeof(pre->g_pre_comp)); 1598 memcpy(pre->g_pre_comp, gmul, sizeof(pre->g_pre_comp));
1551 ret = 1; 1599 ret = 1;
1552 goto err; 1600 goto err;
1553 } 1601 }
1554 if ((!BN_to_felem(pre->g_pre_comp[0][1][0], &group->generator->X)) || 1602 if ((!BN_to_felem(pre->g_pre_comp[0][1][0], &group->generator->X)) ||
1555 (!BN_to_felem(pre->g_pre_comp[0][1][1], &group->generator->Y)) || 1603 (!BN_to_felem(pre->g_pre_comp[0][1][1], &group->generator->Y)) ||
1556 (!BN_to_felem(pre->g_pre_comp[0][1][2], &group->generator->Z))) 1604 (!BN_to_felem(pre->g_pre_comp[0][1][2], &group->generator->Z)))
1557 goto err; 1605 goto err;
1558 /* compute 2^56*G, 2^112*G, 2^168*G for the first table, 1606 /*
1559 * 2^28*G, 2^84*G, 2^140*G, 2^196*G for the second one 1607 * compute 2^56*G, 2^112*G, 2^168*G for the first table, 2^28*G,
1608 * 2^84*G, 2^140*G, 2^196*G for the second one
1560 */ 1609 */
1561 for (i = 1; i <= 8; i <<= 1) 1610 for (i = 1; i <= 8; i <<= 1) {
1562 {
1563 point_double( 1611 point_double(
1564 pre->g_pre_comp[1][i][0], pre->g_pre_comp[1][i][1], pre->g_pre_comp[1][i][2], 1612 pre->g_pre_comp[1][i][0], pre->g_pre_comp[1][i][1], pre->g_pre_comp[1][i][2],
1565 pre->g_pre_comp[0][i][0], pre->g_pre_comp[0][i][1], pre->g_pre_comp[0][i][2]); 1613 pre->g_pre_comp[0][i][0], pre->g_pre_comp[0][i][1], pre->g_pre_comp[0][i][2]);
1566 for (j = 0; j < 27; ++j) 1614 for (j = 0; j < 27; ++j) {
1567 {
1568 point_double( 1615 point_double(
1569 pre->g_pre_comp[1][i][0], pre->g_pre_comp[1][i][1], pre->g_pre_comp[1][i][2], 1616 pre->g_pre_comp[1][i][0], pre->g_pre_comp[1][i][1], pre->g_pre_comp[1][i][2],
1570 pre->g_pre_comp[1][i][0], pre->g_pre_comp[1][i][1], pre->g_pre_comp[1][i][2]); 1617 pre->g_pre_comp[1][i][0], pre->g_pre_comp[1][i][1], pre->g_pre_comp[1][i][2]);
1571 } 1618 }
1572 if (i == 8) 1619 if (i == 8)
1573 break; 1620 break;
1574 point_double( 1621 point_double(
1575 pre->g_pre_comp[0][2*i][0], pre->g_pre_comp[0][2*i][1], pre->g_pre_comp[0][2*i][2], 1622 pre->g_pre_comp[0][2 * i][0], pre->g_pre_comp[0][2 * i][1], pre->g_pre_comp[0][2 * i][2],
1576 pre->g_pre_comp[1][i][0], pre->g_pre_comp[1][i][1], pre->g_pre_comp[1][i][2]); 1623 pre->g_pre_comp[1][i][0], pre->g_pre_comp[1][i][1], pre->g_pre_comp[1][i][2]);
1577 for (j = 0; j < 27; ++j) 1624 for (j = 0; j < 27; ++j) {
1578 {
1579 point_double( 1625 point_double(
1580 pre->g_pre_comp[0][2*i][0], pre->g_pre_comp[0][2*i][1], pre->g_pre_comp[0][2*i][2], 1626 pre->g_pre_comp[0][2 * i][0], pre->g_pre_comp[0][2 * i][1], pre->g_pre_comp[0][2 * i][2],
1581 pre->g_pre_comp[0][2*i][0], pre->g_pre_comp[0][2*i][1], pre->g_pre_comp[0][2*i][2]); 1627 pre->g_pre_comp[0][2 * i][0], pre->g_pre_comp[0][2 * i][1], pre->g_pre_comp[0][2 * i][2]);
1582 }
1583 } 1628 }
1584 for (i = 0; i < 2; i++) 1629 }
1585 { 1630 for (i = 0; i < 2; i++) {
1586 /* g_pre_comp[i][0] is the point at infinity */ 1631 /* g_pre_comp[i][0] is the point at infinity */
1587 memset(pre->g_pre_comp[i][0], 0, sizeof(pre->g_pre_comp[i][0])); 1632 memset(pre->g_pre_comp[i][0], 0, sizeof(pre->g_pre_comp[i][0]));
1588 /* the remaining multiples */ 1633 /* the remaining multiples */
1589 /* 2^56*G + 2^112*G resp. 2^84*G + 2^140*G */ 1634 /* 2^56*G + 2^112*G resp. 2^84*G + 2^140*G */
1590 point_add( 1635 point_add(
1591 pre->g_pre_comp[i][6][0], pre->g_pre_comp[i][6][1], 1636 pre->g_pre_comp[i][6][0], pre->g_pre_comp[i][6][1],
1592 pre->g_pre_comp[i][6][2], pre->g_pre_comp[i][4][0], 1637 pre->g_pre_comp[i][6][2], pre->g_pre_comp[i][4][0],
1593 pre->g_pre_comp[i][4][1], pre->g_pre_comp[i][4][2], 1638 pre->g_pre_comp[i][4][1], pre->g_pre_comp[i][4][2],
1594 0, pre->g_pre_comp[i][2][0], pre->g_pre_comp[i][2][1], 1639 0, pre->g_pre_comp[i][2][0], pre->g_pre_comp[i][2][1],
1595 pre->g_pre_comp[i][2][2]); 1640 pre->g_pre_comp[i][2][2]);
1596 /* 2^56*G + 2^168*G resp. 2^84*G + 2^196*G */ 1641 /* 2^56*G + 2^168*G resp. 2^84*G + 2^196*G */
1597 point_add( 1642 point_add(
1598 pre->g_pre_comp[i][10][0], pre->g_pre_comp[i][10][1], 1643 pre->g_pre_comp[i][10][0], pre->g_pre_comp[i][10][1],
1599 pre->g_pre_comp[i][10][2], pre->g_pre_comp[i][8][0], 1644 pre->g_pre_comp[i][10][2], pre->g_pre_comp[i][8][0],
1600 pre->g_pre_comp[i][8][1], pre->g_pre_comp[i][8][2], 1645 pre->g_pre_comp[i][8][1], pre->g_pre_comp[i][8][2],
1601 0, pre->g_pre_comp[i][2][0], pre->g_pre_comp[i][2][1], 1646 0, pre->g_pre_comp[i][2][0], pre->g_pre_comp[i][2][1],
1602 pre->g_pre_comp[i][2][2]); 1647 pre->g_pre_comp[i][2][2]);
1603 /* 2^112*G + 2^168*G resp. 2^140*G + 2^196*G */ 1648 /* 2^112*G + 2^168*G resp. 2^140*G + 2^196*G */
1604 point_add( 1649 point_add(
1605 pre->g_pre_comp[i][12][0], pre->g_pre_comp[i][12][1], 1650 pre->g_pre_comp[i][12][0], pre->g_pre_comp[i][12][1],
1606 pre->g_pre_comp[i][12][2], pre->g_pre_comp[i][8][0], 1651 pre->g_pre_comp[i][12][2], pre->g_pre_comp[i][8][0],
1607 pre->g_pre_comp[i][8][1], pre->g_pre_comp[i][8][2], 1652 pre->g_pre_comp[i][8][1], pre->g_pre_comp[i][8][2],
1608 0, pre->g_pre_comp[i][4][0], pre->g_pre_comp[i][4][1], 1653 0, pre->g_pre_comp[i][4][0], pre->g_pre_comp[i][4][1],
1609 pre->g_pre_comp[i][4][2]); 1654 pre->g_pre_comp[i][4][2]);
1610 /* 2^56*G + 2^112*G + 2^168*G resp. 2^84*G + 2^140*G + 2^196*G */ 1655 /*
1656 * 2^56*G + 2^112*G + 2^168*G resp. 2^84*G + 2^140*G +
1657 * 2^196*G
1658 */
1611 point_add( 1659 point_add(
1612 pre->g_pre_comp[i][14][0], pre->g_pre_comp[i][14][1], 1660 pre->g_pre_comp[i][14][0], pre->g_pre_comp[i][14][1],
1613 pre->g_pre_comp[i][14][2], pre->g_pre_comp[i][12][0], 1661 pre->g_pre_comp[i][14][2], pre->g_pre_comp[i][12][0],
1614 pre->g_pre_comp[i][12][1], pre->g_pre_comp[i][12][2], 1662 pre->g_pre_comp[i][12][1], pre->g_pre_comp[i][12][2],
1615 0, pre->g_pre_comp[i][2][0], pre->g_pre_comp[i][2][1], 1663 0, pre->g_pre_comp[i][2][0], pre->g_pre_comp[i][2][1],
1616 pre->g_pre_comp[i][2][2]); 1664 pre->g_pre_comp[i][2][2]);
1617 for (j = 1; j < 8; ++j) 1665 for (j = 1; j < 8; ++j) {
1618 {
1619 /* odd multiples: add G resp. 2^28*G */ 1666 /* odd multiples: add G resp. 2^28*G */
1620 point_add( 1667 point_add(
1621 pre->g_pre_comp[i][2*j+1][0], pre->g_pre_comp[i][2*j+1][1], 1668 pre->g_pre_comp[i][2 * j + 1][0], pre->g_pre_comp[i][2 * j + 1][1],
1622 pre->g_pre_comp[i][2*j+1][2], pre->g_pre_comp[i][2*j][0], 1669 pre->g_pre_comp[i][2 * j + 1][2], pre->g_pre_comp[i][2 * j][0],
1623 pre->g_pre_comp[i][2*j][1], pre->g_pre_comp[i][2*j][2], 1670 pre->g_pre_comp[i][2 * j][1], pre->g_pre_comp[i][2 * j][2],
1624 0, pre->g_pre_comp[i][1][0], pre->g_pre_comp[i][1][1], 1671 0, pre->g_pre_comp[i][1][0], pre->g_pre_comp[i][1][1],
1625 pre->g_pre_comp[i][1][2]); 1672 pre->g_pre_comp[i][1][2]);
1626 }
1627 } 1673 }
1674 }
1628 make_points_affine(31, &(pre->g_pre_comp[0][1]), tmp_felems); 1675 make_points_affine(31, &(pre->g_pre_comp[0][1]), tmp_felems);
1629 1676
1630 if (!EC_EX_DATA_set_data(&group->extra_data, pre, nistp224_pre_comp_dup, 1677 if (!EC_EX_DATA_set_data(&group->extra_data, pre, nistp224_pre_comp_dup,
1631 nistp224_pre_comp_free, nistp224_pre_comp_clear_free)) 1678 nistp224_pre_comp_free, nistp224_pre_comp_clear_free))
1632 goto err; 1679 goto err;
1633 ret = 1; 1680 ret = 1;
1634 pre = NULL; 1681 pre = NULL;
1635 err: 1682err:
1636 BN_CTX_end(ctx); 1683 BN_CTX_end(ctx);
1637 if (generator != NULL) 1684 if (generator != NULL)
1638 EC_POINT_free(generator); 1685 EC_POINT_free(generator);
@@ -1641,18 +1688,19 @@ int ec_GFp_nistp224_precompute_mult(EC_GROUP *group, BN_CTX *ctx)
1641 if (pre) 1688 if (pre)
1642 nistp224_pre_comp_free(pre); 1689 nistp224_pre_comp_free(pre);
1643 return ret; 1690 return ret;
1644 } 1691}
1645 1692
1646int ec_GFp_nistp224_have_precompute_mult(const EC_GROUP *group) 1693int
1647 { 1694ec_GFp_nistp224_have_precompute_mult(const EC_GROUP * group)
1695{
1648 if (EC_EX_DATA_get_data(group->extra_data, nistp224_pre_comp_dup, 1696 if (EC_EX_DATA_get_data(group->extra_data, nistp224_pre_comp_dup,
1649 nistp224_pre_comp_free, nistp224_pre_comp_clear_free) 1697 nistp224_pre_comp_free, nistp224_pre_comp_clear_free)
1650 != NULL) 1698 != NULL)
1651 return 1; 1699 return 1;
1652 else 1700 else
1653 return 0; 1701 return 0;
1654 } 1702}
1655 1703
1656#else 1704#else
1657static void *dummy=&dummy; 1705static void *dummy = &dummy;
1658#endif 1706#endif
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-04-25 16:17:01 +0000