OLD | NEW |
1 // Copyright (c) 2012 The Chromium Authors. All rights reserved. | 1 // Copyright (c) 2012 The Chromium Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 // This is an implementation of the P224 elliptic curve group. It's written to | 5 // This is an implementation of the P224 elliptic curve group. It's written to |
6 // be short and simple rather than fast, although it's still constant-time. | 6 // be short and simple rather than fast, although it's still constant-time. |
7 // | 7 // |
8 // See http://www.imperialviolet.org/2010/12/04/ecc.html ([1]) for background. | 8 // See http://www.imperialviolet.org/2010/12/04/ecc.html ([1]) for background. |
9 | 9 |
10 #include "crypto/p224.h" | 10 #include "crypto/p224.h" |
(...skipping 457 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
468 // S2 = Y2*Z1*Z1Z1 | 468 // S2 = Y2*Z1*Z1Z1 |
469 Mul(&s2, a.z, z1z1); | 469 Mul(&s2, a.z, z1z1); |
470 Mul(&s2, b.y, s2); | 470 Mul(&s2, b.y, s2); |
471 | 471 |
472 // H = U2-U1 | 472 // H = U2-U1 |
473 Subtract(&h, u2, u1); | 473 Subtract(&h, u2, u1); |
474 Reduce(&h); | 474 Reduce(&h); |
475 uint32 x_equal = IsZero(h); | 475 uint32 x_equal = IsZero(h); |
476 | 476 |
477 // I = (2*H)² | 477 // I = (2*H)² |
478 for (int j = 0; j < 8; j++) { | 478 for (int k = 0; k < 8; k++) { |
479 i[j] = h[j] << 1; | 479 i[k] = h[k] << 1; |
480 } | 480 } |
481 Reduce(&i); | 481 Reduce(&i); |
482 Square(&i, i); | 482 Square(&i, i); |
483 | 483 |
484 // J = H*I | 484 // J = H*I |
485 Mul(&j, h, i); | 485 Mul(&j, h, i); |
486 // r = 2*(S2-S1) | 486 // r = 2*(S2-S1) |
487 Subtract(&r, s2, s1); | 487 Subtract(&r, s2, s1); |
488 Reduce(&r); | 488 Reduce(&r); |
489 uint32 y_equal = IsZero(r); | 489 uint32 y_equal = IsZero(r); |
490 | 490 |
491 if (x_equal && y_equal && !z1_is_zero && !z2_is_zero) { | 491 if (x_equal && y_equal && !z1_is_zero && !z2_is_zero) { |
492 // The two input points are the same therefore we must use the dedicated | 492 // The two input points are the same therefore we must use the dedicated |
493 // doubling function as the slope of the line is undefined. | 493 // doubling function as the slope of the line is undefined. |
494 DoubleJacobian(out, a); | 494 DoubleJacobian(out, a); |
495 return; | 495 return; |
496 } | 496 } |
497 | 497 |
498 for (int i = 0; i < 8; i++) { | 498 for (int k = 0; k < 8; k++) { |
499 r[i] <<= 1; | 499 r[k] <<= 1; |
500 } | 500 } |
501 Reduce(&r); | 501 Reduce(&r); |
502 | 502 |
503 // V = U1*I | 503 // V = U1*I |
504 Mul(&v, u1, i); | 504 Mul(&v, u1, i); |
505 | 505 |
506 // Z3 = ((Z1+Z2)²-Z1Z1-Z2Z2)*H | 506 // Z3 = ((Z1+Z2)²-Z1Z1-Z2Z2)*H |
507 Add(&z1z1, z1z1, z2z2); | 507 Add(&z1z1, z1z1, z2z2); |
508 Add(&z2z2, a.z, b.z); | 508 Add(&z2z2, a.z, b.z); |
509 Reduce(&z2z2); | 509 Reduce(&z2z2); |
510 Square(&z2z2, z2z2); | 510 Square(&z2z2, z2z2); |
511 Subtract(&out->z, z2z2, z1z1); | 511 Subtract(&out->z, z2z2, z1z1); |
512 Reduce(&out->z); | 512 Reduce(&out->z); |
513 Mul(&out->z, out->z, h); | 513 Mul(&out->z, out->z, h); |
514 | 514 |
515 // X3 = r²-J-2*V | 515 // X3 = r²-J-2*V |
516 for (int i = 0; i < 8; i++) { | 516 for (int k = 0; k < 8; k++) { |
517 z1z1[i] = v[i] << 1; | 517 z1z1[k] = v[k] << 1; |
518 } | 518 } |
519 Add(&z1z1, j, z1z1); | 519 Add(&z1z1, j, z1z1); |
520 Reduce(&z1z1); | 520 Reduce(&z1z1); |
521 Square(&out->x, r); | 521 Square(&out->x, r); |
522 Subtract(&out->x, out->x, z1z1); | 522 Subtract(&out->x, out->x, z1z1); |
523 Reduce(&out->x); | 523 Reduce(&out->x); |
524 | 524 |
525 // Y3 = r*(V-X3)-2*S1*J | 525 // Y3 = r*(V-X3)-2*S1*J |
526 for (int i = 0; i < 8; i++) { | 526 for (int k = 0; k < 8; k++) { |
527 s1[i] <<= 1; | 527 s1[k] <<= 1; |
528 } | 528 } |
529 Mul(&s1, s1, j); | 529 Mul(&s1, s1, j); |
530 Subtract(&z1z1, v, out->x); | 530 Subtract(&z1z1, v, out->x); |
531 Reduce(&z1z1); | 531 Reduce(&z1z1); |
532 Mul(&z1z1, z1z1, r); | 532 Mul(&z1z1, z1z1, r); |
533 Subtract(&out->y, z1z1, s1); | 533 Subtract(&out->y, z1z1, s1); |
534 Reduce(&out->y); | 534 Reduce(&out->y); |
535 | 535 |
536 CopyConditional(out, a, z2_is_zero); | 536 CopyConditional(out, a, z2_is_zero); |
537 CopyConditional(out, b, z1_is_zero); | 537 CopyConditional(out, b, z1_is_zero); |
(...skipping 146 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
684 Reduce(&three_x); | 684 Reduce(&three_x); |
685 Subtract(&rhs, rhs, three_x); | 685 Subtract(&rhs, rhs, three_x); |
686 Reduce(&rhs); | 686 Reduce(&rhs); |
687 | 687 |
688 ::Add(&rhs, rhs, kB); | 688 ::Add(&rhs, rhs, kB); |
689 Contract(&rhs); | 689 Contract(&rhs); |
690 return memcmp(&lhs, &rhs, sizeof(lhs)) == 0; | 690 return memcmp(&lhs, &rhs, sizeof(lhs)) == 0; |
691 } | 691 } |
692 | 692 |
693 std::string Point::ToString() const { | 693 std::string Point::ToString() const { |
694 FieldElement zinv, zinv_sq, x, y; | 694 FieldElement zinv, zinv_sq, xx, yy; |
695 | 695 |
696 // If this is the point at infinity we return a string of all zeros. | 696 // If this is the point at infinity we return a string of all zeros. |
697 if (IsZero(this->z)) { | 697 if (IsZero(this->z)) { |
698 static const char zeros[56] = {0}; | 698 static const char zeros[56] = {0}; |
699 return std::string(zeros, sizeof(zeros)); | 699 return std::string(zeros, sizeof(zeros)); |
700 } | 700 } |
701 | 701 |
702 Invert(&zinv, this->z); | 702 Invert(&zinv, this->z); |
703 Square(&zinv_sq, zinv); | 703 Square(&zinv_sq, zinv); |
704 Mul(&x, this->x, zinv_sq); | 704 Mul(&xx, x, zinv_sq); |
705 Mul(&zinv_sq, zinv_sq, zinv); | 705 Mul(&zinv_sq, zinv_sq, zinv); |
706 Mul(&y, this->y, zinv_sq); | 706 Mul(&yy, y, zinv_sq); |
707 | 707 |
708 Contract(&x); | 708 Contract(&xx); |
709 Contract(&y); | 709 Contract(&yy); |
710 | 710 |
711 uint32 outwords[14]; | 711 uint32 outwords[14]; |
712 Put224Bits(outwords, x); | 712 Put224Bits(outwords, xx); |
713 Put224Bits(outwords + 7, y); | 713 Put224Bits(outwords + 7, yy); |
714 return std::string(reinterpret_cast<const char*>(outwords), sizeof(outwords)); | 714 return std::string(reinterpret_cast<const char*>(outwords), sizeof(outwords)); |
715 } | 715 } |
716 | 716 |
717 void ScalarMult(const Point& in, const uint8* scalar, Point* out) { | 717 void ScalarMult(const Point& in, const uint8* scalar, Point* out) { |
718 ::ScalarMult(out, in, scalar, 28); | 718 ::ScalarMult(out, in, scalar, 28); |
719 } | 719 } |
720 | 720 |
721 // kBasePoint is the base point (generator) of the elliptic curve group. | 721 // kBasePoint is the base point (generator) of the elliptic curve group. |
722 static const Point kBasePoint = { | 722 static const Point kBasePoint = { |
723 {22813985, 52956513, 34677300, 203240812, | 723 {22813985, 52956513, 34677300, 203240812, |
(...skipping 25 matching lines...) Expand all Loading... |
749 Subtract(&out->y, kP, y); | 749 Subtract(&out->y, kP, y); |
750 Reduce(&out->y); | 750 Reduce(&out->y); |
751 | 751 |
752 memset(&out->z, 0, sizeof(out->z)); | 752 memset(&out->z, 0, sizeof(out->z)); |
753 out->z[0] = 1; | 753 out->z[0] = 1; |
754 } | 754 } |
755 | 755 |
756 } // namespace p224 | 756 } // namespace p224 |
757 | 757 |
758 } // namespace crypto | 758 } // namespace crypto |
OLD | NEW |