Botan 3.7.1
Crypto and TLS for C&
pcurves_secp384r1.cpp
Go to the documentation of this file.
1/*
2* (C) 2024 Jack Lloyd
3*
4* Botan is released under the Simplified BSD License (see license.txt)
5*/
6
7#include <botan/internal/pcurves_instance.h>
8
9#include <botan/internal/pcurves_solinas.h>
10#include <botan/internal/pcurves_wrap.h>
11
12namespace Botan::PCurve {
13
14namespace {
15
16template <typename Params>
17class Secp384r1Rep final {
18 public:
19 static constexpr auto P = Params::P;
20 static constexpr size_t N = Params::N;
21 typedef typename Params::W W;
22
23 constexpr static std::array<W, N> redc(const std::array<W, 2 * N>& z) {
24 const int64_t X00 = get_uint32(z.data(), 0);
25 const int64_t X01 = get_uint32(z.data(), 1);
26 const int64_t X02 = get_uint32(z.data(), 2);
27 const int64_t X03 = get_uint32(z.data(), 3);
28 const int64_t X04 = get_uint32(z.data(), 4);
29 const int64_t X05 = get_uint32(z.data(), 5);
30 const int64_t X06 = get_uint32(z.data(), 6);
31 const int64_t X07 = get_uint32(z.data(), 7);
32 const int64_t X08 = get_uint32(z.data(), 8);
33 const int64_t X09 = get_uint32(z.data(), 9);
34 const int64_t X10 = get_uint32(z.data(), 10);
35 const int64_t X11 = get_uint32(z.data(), 11);
36 const int64_t X12 = get_uint32(z.data(), 12);
37 const int64_t X13 = get_uint32(z.data(), 13);
38 const int64_t X14 = get_uint32(z.data(), 14);
39 const int64_t X15 = get_uint32(z.data(), 15);
40 const int64_t X16 = get_uint32(z.data(), 16);
41 const int64_t X17 = get_uint32(z.data(), 17);
42 const int64_t X18 = get_uint32(z.data(), 18);
43 const int64_t X19 = get_uint32(z.data(), 19);
44 const int64_t X20 = get_uint32(z.data(), 20);
45 const int64_t X21 = get_uint32(z.data(), 21);
46 const int64_t X22 = get_uint32(z.data(), 22);
47 const int64_t X23 = get_uint32(z.data(), 23);
48
49 // One copy of P-384 is added to prevent underflow
50 const int64_t S0 = 0xFFFFFFFF + X00 + X12 + X20 + X21 - X23;
51 const int64_t S1 = 0x00000000 + X01 + X13 + X22 + X23 - X12 - X20;
52 const int64_t S2 = 0x00000000 + X02 + X14 + X23 - X13 - X21;
53 const int64_t S3 = 0xFFFFFFFF + X03 + X12 + X15 + X20 + X21 - X14 - X22 - X23;
54 const int64_t S4 = 0xFFFFFFFE + X04 + X12 + X13 + X16 + X20 + X21 * 2 + X22 - X15 - X23 * 2;
55 const int64_t S5 = 0xFFFFFFFF + X05 + X13 + X14 + X17 + X21 + X22 * 2 + X23 - X16;
56 const int64_t S6 = 0xFFFFFFFF + X06 + X14 + X15 + X18 + X22 + X23 * 2 - X17;
57 const int64_t S7 = 0xFFFFFFFF + X07 + X15 + X16 + X19 + X23 - X18;
58 const int64_t S8 = 0xFFFFFFFF + X08 + X16 + X17 + X20 - X19;
59 const int64_t S9 = 0xFFFFFFFF + X09 + X17 + X18 + X21 - X20;
60 const int64_t SA = 0xFFFFFFFF + X10 + X18 + X19 + X22 - X21;
61 const int64_t SB = 0xFFFFFFFF + X11 + X19 + X20 + X23 - X22;
62
63 std::array<W, N> r = {};
64
65 SolinasAccum sum(r);
66
67 sum.accum(S0);
68 sum.accum(S1);
69 sum.accum(S2);
70 sum.accum(S3);
71 sum.accum(S4);
72 sum.accum(S5);
73 sum.accum(S6);
74 sum.accum(S7);
75 sum.accum(S8);
76 sum.accum(S9);
77 sum.accum(SA);
78 sum.accum(SB);
79 const auto S = sum.final_carry(0);
80
81 BOTAN_DEBUG_ASSERT(S <= 4);
82
83 bigint_correct_redc<N>(r, P, p384_mul_mod_384(S));
84
85 return r;
86 }
87
88 constexpr static std::array<W, N> one() { return std::array<W, N>{1}; }
89
90 constexpr static std::array<W, N> to_rep(const std::array<W, N>& x) { return x; }
91
92 constexpr static std::array<W, N> wide_to_rep(const std::array<W, 2 * N>& x) { return redc(x); }
93
94 constexpr static std::array<W, N> from_rep(const std::array<W, N>& z) { return z; }
95
96 private:
97 // Return (i*P-384) % 2**384
98 //
99 // Assumes i is small
100 constexpr static std::array<W, N> p384_mul_mod_384(W i) {
101 static_assert(WordInfo<W>::bits == 32 || WordInfo<W>::bits == 64);
102
103 // For small i, multiples of P-384 have a simple structure so it's faster to
104 // compute the value directly vs a (constant time) table lookup
105
106 auto r = P;
107 if constexpr(WordInfo<W>::bits == 32) {
108 r[4] -= i;
109 r[3] -= i;
110 r[1] += i;
111 r[0] -= i;
112 } else {
113 const uint64_t i32 = static_cast<uint64_t>(i) << 32;
114 r[2] -= i;
115 r[1] -= i32;
116 r[0] += i32;
117 r[0] -= i;
118 }
119 return r;
120 }
121};
122
123// clang-format off
124namespace secp384r1 {
125
126class Params final : public EllipticCurveParameters<
127 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFF0000000000000000FFFFFFFF",
128 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFF0000000000000000FFFFFFFC",
129 "B3312FA7E23EE7E4988E056BE3F82D19181D9C6EFE8141120314088F5013875AC656398D8A2ED19D2A85C8EDD3EC2AEF",
130 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFC7634D81F4372DDF581A0DB248B0A77AECEC196ACCC52973",
131 "AA87CA22BE8B05378EB1C71EF320AD746E1D3B628BA79B9859F741E082542A385502F25DBF55296C3A545E3872760AB7",
132 "3617DE4A96262C6F5D9E98BF9292DC29F8F41DBD289A147CE9DA3113B5F0B8C00A60B1CE1D7E819D7A431D7C90EA0E5F",
133 -12> {
134};
135
136// clang-format on
137
138class Curve final : public EllipticCurve<Params, Secp384r1Rep> {
139 public:
140 // Return the square of the inverse of x
141 static constexpr FieldElement fe_invert2(const FieldElement& x) {
142 // From https://briansmith.org/ecc-inversion-addition-chains-01
143
144 FieldElement r = x.square();
145 r *= x;
146 const auto x2 = r;
147 r = r.square();
148 r *= x;
149 const auto x3 = r;
150 r.square_n(3);
151 r *= x3;
152 auto rl = r;
153 r.square_n(6);
154 r *= rl;
155 r.square_n(3);
156 r *= x3;
157 const auto x15 = r;
158 r.square_n(15);
159 r *= x15;
160 const auto x30 = r;
161 r.square_n(30);
162 r *= x30;
163 rl = r;
164 r.square_n(60);
165 r *= rl;
166 rl = r;
167 r.square_n(120);
168 r *= rl;
169 r.square_n(15);
170 r *= x15;
171 r.square_n(31);
172 r *= x30;
173 r.square_n(2);
174 r *= x2;
175 r.square_n(94);
176 r *= x30;
177 r.square_n(2);
178
179 return r;
180 }
181
182 static constexpr Scalar scalar_invert(const Scalar& x) {
183 // Generated using https://github.com/mmcloughlin/addchain
184
185 auto t3 = x.square();
186 auto t1 = x * t3;
187 auto t0 = t3 * t1;
188 auto t2 = t3 * t0;
189 auto t4 = t3 * t2;
190 auto z = t3 * t4;
191 auto t5 = t3 * z;
192 t3 *= t5;
193 auto t6 = t3.square();
194 t6 *= x;
195 auto t8 = t6;
196 t8.square_n(2);
197 auto t9 = t8.square();
198 auto t7 = t9.square();
199 auto t10 = t7;
200 t10.square_n(5);
201 t7 *= t10;
202 t10 = t7;
203 t10.square_n(10);
204 t7 *= t10;
205 t10 = t7;
206 t10.square_n(4);
207 t9 *= t10;
208 t9.square_n(21);
209 t7 *= t9;
210 t9 = t7;
211 t9.square_n(3);
212 t8 *= t9;
213 t8.square_n(47);
214 t7 *= t8;
215 t8 = t7;
216 t8.square_n(95);
217 t7 *= t8;
218 t7 *= t3;
219 t7.square_n(6);
220 t7 *= t2;
221 t7.square_n(3);
222 t7 *= t1;
223 t7.square_n(7);
224 t7 *= t5;
225 t7.square_n(6);
226 t7 *= t5;
227 t7 = t7.square();
228 t7 *= x;
229 t7.square_n(11);
230 t7 *= t6;
231 t7.square_n(2);
232 t7 *= x;
233 t7.square_n(8);
234 t7 *= t5;
235 t7.square_n(2);
236 t7 *= t1;
237 t7.square_n(6);
238 t7 *= z;
239 t7.square_n(4);
240 t7 *= t2;
241 t7.square_n(6);
242 t6 *= t7;
243 t6.square_n(5);
244 t6 *= z;
245 t6.square_n(10);
246 t6 *= t5;
247 t6.square_n(9);
248 t5 *= t6;
249 t5.square_n(4);
250 t5 *= z;
251 t5.square_n(6);
252 t4 *= t5;
253 t4.square_n(3);
254 t4 *= x;
255 t4.square_n(7);
256 t4 *= z;
257 t4.square_n(7);
258 t4 *= t0;
259 t4.square_n(5);
260 t4 *= t2;
261 t4.square_n(5);
262 t3 *= t4;
263 t3.square_n(5);
264 t3 *= z;
265 t3.square_n(4);
266 t3 *= z;
267 t3.square_n(5);
268 t2 *= t3;
269 t2.square_n(3);
270 t2 *= t1;
271 t2.square_n(7);
272 t2 *= t1;
273 t2.square_n(6);
274 t2 *= z;
275 t2.square_n(4);
276 t2 *= t0;
277 t2.square_n(3);
278 t2 *= t1;
279 t2.square_n(4);
280 t2 *= t1;
281 t2.square_n(4);
282 t1 *= t2;
283 t1.square_n(6);
284 t1 *= t0;
285 t1.square_n(5);
286 t0 *= t1;
287 t0.square_n(6);
288 z *= t0;
289 z = z.square();
290 z *= x;
291 z.square_n(4);
292 z *= x;
293
294 return z;
295 }
296};
297
298} // namespace secp384r1
299
300} // namespace
301
302std::shared_ptr<const PrimeOrderCurve> PCurveInstance::secp384r1() {
304}
305
306} // namespace Botan::PCurve
#define BOTAN_DEBUG_ASSERT(expr)
Definition assert.h:98
static std::shared_ptr< const PrimeOrderCurve > secp384r1()
Definition pcurves.cpp:40
static std::shared_ptr< const PrimeOrderCurve > instance()
int(* final)(unsigned char *, CTX *)
constexpr uint32_t get_uint32(const W xw[], size_t i)
constexpr void bigint_correct_redc(std::array< W, N > &r, const std::array< W, N > &P, const std::array< W, N > &C)
Definition mp_core.h:1108