Botan 3.14.1
Crypto and TLS for C&
pcurves_secp256r1.cpp
Go to the documentation of this file.
1/*
2* (C) 2024,2026 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 Secp256r1SolinasRep 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 // Adds 4 * P-256 to prevent underflow
24 static constexpr auto P256_4 =
25 hex_to_words<uint32_t>("0x3fffffffc00000004000000000000000000000003fffffffffffffffffffffffc");
26
27 constexpr static std::array<W, N> redc(const std::array<W, 2 * N>& z) {
28 const int64_t X00 = get_uint32(z.data(), 0);
29 const int64_t X01 = get_uint32(z.data(), 1);
30 const int64_t X02 = get_uint32(z.data(), 2);
31 const int64_t X03 = get_uint32(z.data(), 3);
32 const int64_t X04 = get_uint32(z.data(), 4);
33 const int64_t X05 = get_uint32(z.data(), 5);
34 const int64_t X06 = get_uint32(z.data(), 6);
35 const int64_t X07 = get_uint32(z.data(), 7);
36 const int64_t X08 = get_uint32(z.data(), 8);
37 const int64_t X09 = get_uint32(z.data(), 9);
38 const int64_t X10 = get_uint32(z.data(), 10);
39 const int64_t X11 = get_uint32(z.data(), 11);
40 const int64_t X12 = get_uint32(z.data(), 12);
41 const int64_t X13 = get_uint32(z.data(), 13);
42 const int64_t X14 = get_uint32(z.data(), 14);
43 const int64_t X15 = get_uint32(z.data(), 15);
44
45 // See SP 800-186 section G.1.2
46 const int64_t S0 = P256_4[0] + X00 + X08 + X09 - (X11 + X12 + X13 + X14);
47 const int64_t S1 = P256_4[1] + X01 + X09 + X10 - (X12 + X13 + X14 + X15);
48 const int64_t S2 = P256_4[2] + X02 + X10 + X11 - (X13 + X14 + X15);
49 const int64_t S3 = P256_4[3] + X03 + 2 * (X11 + X12) + X13 - (X15 + X08 + X09);
50 const int64_t S4 = P256_4[4] + X04 + 2 * (X12 + X13) + X14 - (X09 + X10);
51 const int64_t S5 = P256_4[5] + X05 + 2 * (X13 + X14) + X15 - (X10 + X11);
52 const int64_t S6 = P256_4[6] + X06 + X13 + X14 * 3 + X15 * 2 - (X08 + X09);
53 const int64_t S7 = P256_4[7] + X07 + X15 * 3 + X08 - (X10 + X11 + X12 + X13);
54 const int64_t S8 = P256_4[8];
55
56 std::array<W, N> r = {};
57
58 SolinasAccum sum(r);
59
60 sum.accum(S0);
61 sum.accum(S1);
62 sum.accum(S2);
63 sum.accum(S3);
64 sum.accum(S4);
65 sum.accum(S5);
66 sum.accum(S6);
67 sum.accum(S7);
68 const auto S = sum.final_carry(S8);
69
70 BOTAN_DEBUG_ASSERT(S <= 8);
71
72 solinas_correct_redc<N>(r, P, p256_mul_mod_256(S));
73
74 return r;
75 }
76
77 constexpr static std::array<W, N> one() { return std::array<W, N>{1}; }
78
79 constexpr static std::array<W, N> to_rep(const std::array<W, N>& x) { return x; }
80
81 constexpr static std::array<W, N> wide_to_rep(const std::array<W, 2 * N>& x) { return redc(x); }
82
83 constexpr static std::array<W, N> from_rep(const std::array<W, N>& z) { return z; }
84
85 private:
86 // Return (i*P-256) % 2**256
87 //
88 // Assumes i is small
89 constexpr static std::array<W, N> p256_mul_mod_256(W i) {
90 static_assert(WordInfo<W>::bits == 32 || WordInfo<W>::bits == 64);
91
92 // For small i, multiples of P-256 have a simple structure so it's faster to
93 // compute the value directly vs a (constant time) table lookup
94
95 auto r = P;
96 if constexpr(WordInfo<W>::bits == 32) {
97 r[7] -= i;
98 r[6] += i;
99 r[3] += i;
100 r[0] -= i;
101 } else {
102 const uint64_t i32 = static_cast<uint64_t>(i) << 32;
103 r[3] -= i32;
104 r[3] += i;
105 r[1] += i32;
106 r[0] -= i;
107 }
108 return r;
109 }
110};
111
112/*
113* Montgomery arithmetic specialized for P-256
114*
115* Word-serial Montgomery reduction adds m*p to the accumulator in each step,
116* with m chosen so that the low word becomes zero. For P-256 the Montgomery
117* p' value is 1, so m is always exactly equal to the low word.
118*
119* Writing m*p as m*(p+1)-m: the -m is what zeros the low word, which is never
120* read again and so is not even written, while m*(p+1) is a multiple of 2^64.
121* We can ignore the implicit low zero word and (shifting the index one word up)
122* add m*(p+1)/2^64, which for P-256 is m*(2^192 - 2^160 + 2^128 + 2^32). That
123* value can be formed with shifts and subtractions rather than a multiplication.
124*/
125template <typename Params>
126class Secp256r1MontgomeryRep final {
127 public:
128 static constexpr auto P = Params::P;
129 static constexpr size_t N = Params::N;
130 typedef typename Params::W W;
131
132 static_assert(WordInfo<W>::bits == 64 && N == 4);
133
134 static constexpr auto R1 = montygomery_r(P);
135 static constexpr auto R2 = mul_mod(R1, R1, P);
136 static constexpr auto R3 = mul_mod(R1, R2, P);
137
138 constexpr static std::array<W, N> one() { return R1; }
139
140 constexpr static BOTAN_FORCE_INLINE std::array<W, N> redc(const std::array<W, 2 * N>& z) {
141 // Scalar locals rather than a copy of z: GCC copies arrays using 16 byte
142 // loads, which stall on the 8 byte stores that just produced z
143 W t1 = z[1];
144 W t2 = z[2];
145 W t3 = z[3];
146 W t4 = z[4];
147 W t5 = z[5];
148 W t6 = z[6];
149 W t7 = z[7];
150
151 // The carry out from the previous step
152 W pending = 0;
153
154 redc_step(z[0], t1, t2, t3, t4, pending);
155 redc_step(t1, t2, t3, t4, t5, pending);
156 redc_step(t2, t3, t4, t5, t6, pending);
157 redc_step(t3, t4, t5, t6, t7, pending);
158
159 return final_sub(pending, {t4, t5, t6, t7});
160 }
161
162 constexpr static std::array<W, N> to_rep(const std::array<W, N>& x) {
163 std::array<W, 2 * N> z; // NOLINT(*-member-init)
164 comba_mul<N>(z.data(), x.data(), R2.data());
165 return redc(z);
166 }
167
168 constexpr static std::array<W, N> wide_to_rep(const std::array<W, 2 * N>& x) {
169 auto redc_x = redc(x);
170 std::array<W, 2 * N> z; // NOLINT(*-member-init)
171 comba_mul<N>(z.data(), redc_x.data(), R3.data());
172 return redc(z);
173 }
174
175 constexpr static std::array<W, N> from_rep(const std::array<W, N>& z) {
176 std::array<W, 2 * N> ze = {};
177 copy_mem(std::span{ze}.template first<N>(), z);
178 return redc(ze);
179 }
180
181 private:
182 /**
183 * Add m*(p+1)/2^64 to (t3 || t2 || t1 || t0)
184 */
185 constexpr static BOTAN_FORCE_INLINE void redc_step(W m, W& t0, W& t1, W& t2, W& t3, W& pending) {
186 auto [q0, q1, q2, q3] = p256_m_p1_64(m);
187
188 // q3 is at most 2^64 - 2^32, leaving room to add the carry from the
189 // previous step without worrying about creating a new carry
190 q3 += pending;
191
192 W carry = 0;
193 t0 = word_add(t0, q0, &carry);
194 t1 = word_add(t1, q1, &carry);
195 t2 = word_add(t2, q2, &carry);
196 t3 = word_add(t3, q3, &carry);
197 pending = carry;
198 }
199
200 /**
201 * Return the 4 words of m*(p+1)/2^64, which is what remains above the
202 * low word after adding m*p to an accumulator whose low word is m
203 */
204 constexpr static BOTAN_FORCE_INLINE std::array<W, N> p256_m_p1_64(W m) {
205 const W m_lo = m << 32;
206 const W m_hi = m >> 32;
207
208 /*
209 * m*(p+1)/2^64 = m*2^32 + m*2^128 + m*2^192 - m*2^160, laid out as
210 *
211 * m*2^32 -> word 0 gets m << 32, word 1 gets m >> 32
212 * m*2^128 -> word 2 gets m
213 * m*2^192 -> word 3 gets m
214 * -m*2^160 -> word 2 loses m << 32, word 3 loses m >> 32 plus the borrow
215 *
216 * The total is non-negative and below 2^256, so the final borrow is zero
217 */
218 W borrow = 0;
219 const W q2 = word_sub(m, m_lo, &borrow);
220 const W q3 = word_sub(m, m_hi, &borrow);
221
222 return {m_lo, m_hi, q2, q3};
223 }
224
225 /**
226 * Given (top || t) < 2*p return it reduced modulo p
227 */
228 constexpr static BOTAN_FORCE_INLINE std::array<W, N> final_sub(W top, const std::array<W, N>& t) {
229 W borrow = 0;
230 const W r0 = word_sub(t[0], P[0], &borrow);
231 const W r1 = word_sub(t[1], P[1], &borrow);
232 const W r2 = word_sub(t[2], P[2], &borrow);
233 const W r3 = word_sub(t[3], P[3], &borrow);
234
235 // t is only < p if the subtraction underflowed and top (the 257th bit) is zero
236 const W t_lt_p = CT::value_barrier<W>(static_cast<W>(0) - (borrow & (top ^ 1)));
237
238 return {
239 choose(t_lt_p, t[0], r0),
240 choose(t_lt_p, t[1], r1),
241 choose(t_lt_p, t[2], r2),
242 choose(t_lt_p, t[3], r3),
243 };
244 }
245};
246
247namespace secp256r1 {
248
249// clang-format off
250
251class Params final : public EllipticCurveParameters<
252 "FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF",
253 "FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC",
254 "5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B",
255 "FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551",
256 "6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296",
257 "4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5",
258 -10> {
259};
260
261// clang-format on
262
263using Secp256r1Base = std::conditional_t<WordInfo<word>::bits == 64,
266
267class Curve final : public Secp256r1Base {
268 public:
269 // Return the square of the inverse of x
270 static constexpr FieldElement fe_invert2(const FieldElement& x) {
271 // Generated using https://github.com/mmcloughlin/addchain
272
273 auto z = x.square();
274 z *= x;
275 z = z.square();
276 z *= x;
277 auto t0 = z;
278 t0.square_n(3);
279 t0 *= z;
280 auto t1 = t0;
281 t1.square_n(6);
282 t0 *= t1;
283 t0.square_n(3);
284 z *= t0;
285 t0 = z.square();
286 t0 *= x;
287 t1 = t0;
288 t1.square_n(16);
289 t0 *= t1;
290 t0.square_n(15);
291 z *= t0;
292 t0.square_n(17);
293 t0 *= x;
294 t0.square_n(143);
295 t0 *= z;
296 t0.square_n(47);
297 z *= t0;
298 z.square_n(2);
299
300 return z;
301 }
302
303 // Return the square root of x
304 static constexpr FieldElement fe_sqrt(const FieldElement& x) {
305 // Generated using addchain
306 auto z = x.square();
307 z *= x;
308 auto t0 = z;
309 t0.square_n(2);
310 z *= t0;
311 t0 = z;
312 t0.square_n(4);
313 z *= t0;
314 t0 = z;
315 t0.square_n(8);
316 z *= t0;
317 t0 = z;
318 t0.square_n(16);
319 z *= t0;
320 z.square_n(32);
321 z *= x;
322 z.square_n(96);
323 z *= x;
324 z.square_n(94);
325 return z;
326 }
327
328 static constexpr Scalar scalar_invert(const Scalar& x) {
329 auto t1 = x.square();
330 auto t5 = t1.square();
331 auto t2 = t5 * x;
332 auto t10 = t2 * x;
333 auto t3 = t2 * t5;
334 auto z = t10 * t3;
335 auto t9 = t3.square();
336 auto t4 = t10 * z;
337 auto t0 = t10 * t9;
338 auto t13 = t0 * t1;
339 auto t8 = t13 * t4;
340 t4 = t3 * t8;
341 auto t7 = t2 * t4;
342 t2 = t1 * t7;
343 auto t6 = t7 * t9;
344 t3 = t6 * t9;
345 t1 *= t3;
346 auto t12 = t3 * t9;
347 t5 *= t12;
348 auto t11 = t10 * t5;
349 t0 *= t11;
350 t9 *= t0;
351 t10 *= t9;
352 t4 *= t10;
353 t13 *= t4;
354 auto t14 = t13;
355 t14.square_n(8);
356 t13 *= t14;
357 t14 = t13;
358 t14.square_n(16);
359 t14 *= t13;
360 t14.square_n(48);
361 t14 *= t13;
362 t14.square_n(16);
363 t14 *= t13;
364 t14.square_n(16);
365 t14 *= t13;
366 t14.square_n(16);
367 t13 *= t14;
368 t13.square_n(6);
369 t13 *= t8;
370 t13.square_n(9);
371 t12 *= t13;
372 t12.square_n(8);
373 t11 *= t12;
374 t11.square_n(9);
375 t10 *= t11;
376 t10.square_n(8);
377 t9 *= t10;
378 t9.square_n(9);
379 t8 *= t9;
380 t8.square_n(8);
381 t7 *= t8;
382 t7.square_n(11);
383 t6 *= t7;
384 t6.square_n(9);
385 t5 *= t6;
386 t5.square_n(10);
387 t4 *= t5;
388 t4.square_n(8);
389 t3 *= t4;
390 t3.square_n(7);
391 t2 *= t3;
392 t2.square_n(10);
393 t1 *= t2;
394 t1.square_n(10);
395 t0 *= t1;
396 t0.square_n(6);
397 z *= t0;
398
399 return z;
400 }
401};
402
403} // namespace secp256r1
404
405} // namespace
406
407std::shared_ptr<const PrimeOrderCurve> PCurveInstance::secp256r1() {
409}
410
411} // namespace Botan::PCurve
#define BOTAN_DEBUG_ASSERT(expr)
Definition assert.h:136
static std::shared_ptr< const PrimeOrderCurve > instance()
#define BOTAN_FORCE_INLINE
Definition compiler.h:86
constexpr T value_barrier(T x)
constexpr auto word_sub(W x, W y, W *carry) -> W
Definition mp_asmi.h:355
constexpr auto word_add(W x, W y, W *carry) -> W
Definition mp_asmi.h:260
constexpr void comba_mul(W z[2 *N], const W x[N], const W y[N])
Definition mp_core.h:981
constexpr void copy_mem(T *out, const T *in, size_t n)
Definition mem_ops.h:144
constexpr uint32_t get_uint32(const W xw[], size_t i)
consteval std::array< W, N > mul_mod(const std::array< W, N > &x, const std::array< W, N > &y, const std::array< W, N > &p)
BOTAN_FORCE_INLINE constexpr T choose(T mask, T a, T b)
Definition bit_ops.h:217
constexpr auto hex_to_words(const char(&s)[N])
Definition mp_core.h:921
consteval std::array< W, N > montygomery_r(const std::array< W, N > &p)
constexpr void solinas_correct_redc(std::array< W, N > &r, const std::array< W, N > &P, const std::array< W, N > &C)