| 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 |