| 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 105 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 116 static const uint32 kBottom28Bits = 0xfffffff; | 116 static const uint32 kBottom28Bits = 0xfffffff; |
| 117 | 117 |
| 118 // LargeFieldElement also represents an element of the field. The limbs are | 118 // LargeFieldElement also represents an element of the field. The limbs are |
| 119 // still spaced 28-bits apart and in little-endian order. So the limbs are at | 119 // still spaced 28-bits apart and in little-endian order. So the limbs are at |
| 120 // 0, 28, 56, ..., 392 bits, each 64-bits wide. | 120 // 0, 28, 56, ..., 392 bits, each 64-bits wide. |
| 121 typedef uint64 LargeFieldElement[15]; | 121 typedef uint64 LargeFieldElement[15]; |
| 122 | 122 |
| 123 // ReduceLarge converts a LargeFieldElement to a FieldElement. | 123 // ReduceLarge converts a LargeFieldElement to a FieldElement. |
| 124 // | 124 // |
| 125 // in[i] < 2**62 | 125 // in[i] < 2**62 |
| 126 |
| 127 // GCC 4.9 incorrectly vectorizes the first coefficient elimination loop, so |
| 128 // disable that optimization via pragma. Don't use the pragma under Clang, since |
| 129 // clang doesn't understand it. |
| 130 // TODO(wez): Remove this when crbug.com/439566 is fixed. |
| 131 #if defined(__GNUC__) && !defined(__clang__) |
| 132 #pragma GCC optimize("no-tree-vectorize") |
| 133 #endif |
| 134 |
| 126 void ReduceLarge(FieldElement* out, LargeFieldElement* inptr) { | 135 void ReduceLarge(FieldElement* out, LargeFieldElement* inptr) { |
| 127 LargeFieldElement& in(*inptr); | 136 LargeFieldElement& in(*inptr); |
| 128 | 137 |
| 129 for (int i = 0; i < 8; i++) { | 138 for (int i = 0; i < 8; i++) { |
| 130 in[i] += kZero63ModP[i]; | 139 in[i] += kZero63ModP[i]; |
| 131 } | 140 } |
| 132 | 141 |
| 133 // Eliminate the coefficients at 2**224 and greater while maintaining the | 142 // Eliminate the coefficients at 2**224 and greater while maintaining the |
| 134 // same value mod p. | 143 // same value mod p. |
| 135 for (int i = 14; i >= 8; i--) { | 144 for (int i = 14; i >= 8; i--) { |
| (...skipping 21 matching lines...) Expand all Loading... |
| 157 // out[1,2,5..7] < 2**28 | 166 // out[1,2,5..7] < 2**28 |
| 158 | 167 |
| 159 (*out)[0] = static_cast<uint32>(in[0] & kBottom28Bits); | 168 (*out)[0] = static_cast<uint32>(in[0] & kBottom28Bits); |
| 160 (*out)[1] += static_cast<uint32>((in[0] >> 28) & kBottom28Bits); | 169 (*out)[1] += static_cast<uint32>((in[0] >> 28) & kBottom28Bits); |
| 161 (*out)[2] += static_cast<uint32>(in[0] >> 56); | 170 (*out)[2] += static_cast<uint32>(in[0] >> 56); |
| 162 // out[0] < 2**28 | 171 // out[0] < 2**28 |
| 163 // out[1..4] < 2**29 | 172 // out[1..4] < 2**29 |
| 164 // out[5..7] < 2**28 | 173 // out[5..7] < 2**28 |
| 165 } | 174 } |
| 166 | 175 |
| 176 // TODO(wez): Remove this when crbug.com/439566 is fixed. |
| 177 #if defined(__GNUC__) && !defined(__clang__) |
| 178 #pragma GCC optimize("tree-vectorize") |
| 179 #endif |
| 180 |
| 167 // Mul computes *out = a*b | 181 // Mul computes *out = a*b |
| 168 // | 182 // |
| 169 // a[i] < 2**29, b[i] < 2**30 (or vice versa) | 183 // a[i] < 2**29, b[i] < 2**30 (or vice versa) |
| 170 // out[i] < 2**29 | 184 // out[i] < 2**29 |
| 171 void Mul(FieldElement* out, const FieldElement& a, const FieldElement& b) { | 185 void Mul(FieldElement* out, const FieldElement& a, const FieldElement& b) { |
| 172 LargeFieldElement tmp; | 186 LargeFieldElement tmp; |
| 173 memset(&tmp, 0, sizeof(tmp)); | 187 memset(&tmp, 0, sizeof(tmp)); |
| 174 | 188 |
| 175 for (int i = 0; i < 8; i++) { | 189 for (int i = 0; i < 8; i++) { |
| 176 for (int j = 0; j < 8; j++) { | 190 for (int j = 0; j < 8; j++) { |
| (...skipping 557 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 734 Subtract(&out->y, kP, y); | 748 Subtract(&out->y, kP, y); |
| 735 Reduce(&out->y); | 749 Reduce(&out->y); |
| 736 | 750 |
| 737 memset(&out->z, 0, sizeof(out->z)); | 751 memset(&out->z, 0, sizeof(out->z)); |
| 738 out->z[0] = 1; | 752 out->z[0] = 1; |
| 739 } | 753 } |
| 740 | 754 |
| 741 } // namespace p224 | 755 } // namespace p224 |
| 742 | 756 |
| 743 } // namespace crypto | 757 } // namespace crypto |
| OLD | NEW |