Botan 3.14.1
Crypto and TLS for C&
pcurves_sm2p256v1.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
16namespace sm2p256v1 {
17
18template <typename Params>
19class Sm2p256v1Rep final {
20 public:
21 static constexpr auto P = Params::P;
22 static constexpr size_t N = Params::N;
23 typedef typename Params::W W;
24
25 constexpr static std::array<W, N> redc(const std::array<W, 2 * N>& z) {
26 const int64_t X00 = get_uint32(z.data(), 0);
27 const int64_t X01 = get_uint32(z.data(), 1);
28 const int64_t X02 = get_uint32(z.data(), 2);
29 const int64_t X03 = get_uint32(z.data(), 3);
30 const int64_t X04 = get_uint32(z.data(), 4);
31 const int64_t X05 = get_uint32(z.data(), 5);
32 const int64_t X06 = get_uint32(z.data(), 6);
33 const int64_t X07 = get_uint32(z.data(), 7);
34 const int64_t X08 = get_uint32(z.data(), 8);
35 const int64_t X09 = get_uint32(z.data(), 9);
36 const int64_t X10 = get_uint32(z.data(), 10);
37 const int64_t X11 = get_uint32(z.data(), 11);
38 const int64_t X12 = get_uint32(z.data(), 12);
39 const int64_t X13 = get_uint32(z.data(), 13);
40 const int64_t X14 = get_uint32(z.data(), 14);
41 const int64_t X15 = get_uint32(z.data(), 15);
42
43 const int64_t S0 = X00 + X08 + X09 + X10 + X11 + X12 + 2 * (X13 + X14 + X15);
44 const int64_t S1 = X01 + X09 + X10 + X11 + X12 + X13 + 2 * (X14 + X15);
45 const int64_t S2 = X02 - (X08 + X09 + X13 + X14);
46 const int64_t S3 = X03 + X08 + X11 + X12 + 2 * X13 + X14 + X15;
47 const int64_t S4 = X04 + X09 + X12 + X13 + 2 * X14 + X15;
48 const int64_t S5 = X05 + X10 + X13 + X14 + 2 * X15;
49 const int64_t S6 = X06 + X11 + X14 + X15;
50 const int64_t S7 = X07 + X08 + X09 + X10 + X11 + 2 * (X12 + X13 + X14 + X15) + X15;
51
52 std::array<W, N> r = {};
53
54 SolinasAccum sum(r);
55
56 sum.accum(S0);
57 sum.accum(S1);
58 sum.accum(S2);
59 sum.accum(S3);
60 sum.accum(S4);
61 sum.accum(S5);
62 sum.accum(S6);
63 sum.accum(S7);
64 const auto S = sum.final_carry(0);
65
66 solinas_correct_redc<N>(r, P, sm2_mul_mod_256(S));
67
68 return r;
69 }
70
71 constexpr static std::array<W, N> one() { return std::array<W, N>{1}; }
72
73 constexpr static std::array<W, N> to_rep(const std::array<W, N>& x) { return x; }
74
75 constexpr static std::array<W, N> wide_to_rep(const std::array<W, 2 * N>& x) { return redc(x); }
76
77 constexpr static std::array<W, N> from_rep(const std::array<W, N>& z) { return z; }
78
79 private:
80 // Return (i*P) % 2**256
81 //
82 // Assumes i is small
83 constexpr static std::array<W, N> sm2_mul_mod_256(W i) {
84 static_assert(WordInfo<W>::bits == 32 || WordInfo<W>::bits == 64);
85
86 // For small i, multiples of P have a simple structure so it's faster to
87 // compute the value directly vs a (constant time) table lookup
88
89 auto r = P;
90 if constexpr(WordInfo<W>::bits == 32) {
91 r[7] -= i;
92 r[3] -= i;
93 r[2] += i;
94 r[0] -= i;
95 } else {
96 const uint64_t i32 = static_cast<uint64_t>(i) << 32;
97 r[3] -= i32;
98 r[1] -= i32;
99 r[1] += i;
100 r[0] -= i;
101 }
102 return r;
103 }
104};
105
106/*
107* Montgomery arithmetic specialized for SM2
108*
109* Word-serial Montgomery reduction adds m*p to the accumulator in each step,
110* with m chosen so that the low word becomes zero. For SM2, where
111* p = 2^256 - 2^224 - 2^96 + 2^64 - 1, -p^-1 mod 2^64 is 1, so m is simply
112* the low word itself.
113*
114* Writing m*p as m*(p+1) - m: the -m is what zeros the low word, which is
115* never read again and so is not even written, while m*(p+1) is a multiple of
116* 2^64. So what is actually added is m*(p+1)/2^64, one word up, which is
117* m*(2^192 - 2^160 - 2^32 + 1) and is formed with shifts and subtractions
118* rather than a multiplication.
119*/
120template <typename Params>
121class Sm2p256v1MontgomeryRep final {
122 public:
123 static constexpr auto P = Params::P;
124 static constexpr size_t N = Params::N;
125 typedef typename Params::W W;
126
127 static_assert(WordInfo<W>::bits == 64 && N == 4);
128
129 static constexpr auto R1 = montygomery_r(P);
130 static constexpr auto R2 = mul_mod(R1, R1, P);
131 static constexpr auto R3 = mul_mod(R1, R2, P);
132
133 constexpr static std::array<W, N> one() { return R1; }
134
135 constexpr static BOTAN_FORCE_INLINE std::array<W, N> redc(const std::array<W, 2 * N>& z) {
136 // Scalar locals rather than a copy of z: GCC copies arrays using 16 byte
137 // loads, which stall on the 8 byte stores that just produced z
138 W t1 = z[1];
139 W t2 = z[2];
140 W t3 = z[3];
141 W t4 = z[4];
142 W t5 = z[5];
143 W t6 = z[6];
144 W t7 = z[7];
145
146 // The carry out at the end of each step needs to end up in the word
147 // above t3, which is exactly q3 of the next step since we shift the
148 // window 1 word at a time
149 W pending = 0;
150
151 redc_step(z[0], t1, t2, t3, t4, pending);
152 redc_step(t1, t2, t3, t4, t5, pending);
153 redc_step(t2, t3, t4, t5, t6, pending);
154 redc_step(t3, t4, t5, t6, t7, pending);
155
156 return final_sub(pending, {t4, t5, t6, t7});
157 }
158
159 constexpr static std::array<W, N> to_rep(const std::array<W, N>& x) {
160 std::array<W, 2 * N> z; // NOLINT(*-member-init)
161 comba_mul<N>(z.data(), x.data(), R2.data());
162 return redc(z);
163 }
164
165 constexpr static std::array<W, N> wide_to_rep(const std::array<W, 2 * N>& x) {
166 auto redc_x = redc(x);
167 std::array<W, 2 * N> z; // NOLINT(*-member-init)
168 comba_mul<N>(z.data(), redc_x.data(), R3.data());
169 return redc(z);
170 }
171
172 constexpr static std::array<W, N> from_rep(const std::array<W, N>& z) {
173 std::array<W, 2 * N> ze = {};
174 copy_mem(std::span{ze}.template first<N>(), z);
175 return redc(ze);
176 }
177
178 private:
179 /**
180 * Add m*(p+1)/2^64 to (t3 || t2 || t1 || t0)
181 */
182 constexpr static BOTAN_FORCE_INLINE void redc_step(W m, W& t0, W& t1, W& t2, W& t3, W& pending) {
183 auto [q0, q1, q2, q3] = sm2_m_p1_64(m);
184
185 // q3 is at most 2^64 - 2^32 so no carry out is possible here
186 q3 += pending;
187
188 // Adding m*p would zero the word holding m, which is never read
189 // again, so only the part above it is added
190 W carry = 0;
191 t0 = word_add(t0, q0, &carry);
192 t1 = word_add(t1, q1, &carry);
193 t2 = word_add(t2, q2, &carry);
194 t3 = word_add(t3, q3, &carry);
195 pending = carry;
196 }
197
198 /**
199 * Return the 4 words of m*(p+1)/2^64, which is what remains above the
200 * low word after adding m*p to an accumulator whose low word is m
201 */
202 constexpr static BOTAN_FORCE_INLINE std::array<W, N> sm2_m_p1_64(W m) {
203 const W m_lo = m << 32;
204 const W m_hi = m >> 32;
205
206 /*
207 * m*(p+1)/2^64 = m + m*2^192 - m*2^32 - m*2^160, laid out as
208 *
209 * m -> word 0 gets m
210 * m*2^192 -> word 3 gets m
211 * -m*2^32 -> word 0 loses m << 32, word 1 loses m >> 32 plus the borrow
212 * -m*2^160 -> word 2 loses m << 32, word 3 loses m >> 32 plus the borrow
213 *
214 * The total is non-negative and below 2^256, so the final borrow is zero
215 */
216 W borrow = 0;
217
218 // This variable is intentionally non-const to work around
219 // GCC 14 at -O1 inserting a undesirable conditional jump
220 W zero = CT::value_barrier<W>(0); // NOLINT(*-const-correctness)
221
222 const W q0 = word_sub(m, m_lo, &borrow);
223 const W q1 = word_sub(zero, m_hi, &borrow);
224 const W q2 = word_sub(zero, m_lo, &borrow);
225 const W q3 = word_sub(m, m_hi, &borrow);
226
227 return {q0, q1, q2, q3};
228 }
229
230 /**
231 * Given (top || t) < 2*p return it reduced modulo p
232 */
233 constexpr static BOTAN_FORCE_INLINE std::array<W, N> final_sub(W top, const std::array<W, N>& t) {
234 W borrow = 0;
235 const W r0 = word_sub(t[0], P[0], &borrow);
236 const W r1 = word_sub(t[1], P[1], &borrow);
237 const W r2 = word_sub(t[2], P[2], &borrow);
238 const W r3 = word_sub(t[3], P[3], &borrow);
239
240 // t is only < p if the subtraction underflowed and top (the 257th bit) is zero
241 const W t_lt_p = CT::value_barrier<W>(static_cast<W>(0) - (borrow & (top ^ 1)));
242
243 return {
244 Botan::choose(t_lt_p, t[0], r0),
245 Botan::choose(t_lt_p, t[1], r1),
246 Botan::choose(t_lt_p, t[2], r2),
247 Botan::choose(t_lt_p, t[3], r3),
248 };
249 }
250};
251
252// clang-format off
253
254class Params final : public EllipticCurveParameters<
255 "FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFF",
256 "FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFC",
257 "28E9FA9E9D9F5E344D5A9E4BCF6509A7F39789F515AB8F92DDBCBD414D940E93",
258 "FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFF7203DF6B21C6052B53BBF40939D54123",
259 "32C4AE2C1F1981195F9904466A39C9948FE30BBFF2660BE1715A4589334C74C7",
260 "BC3736A2F4F6779C59BDCEE36B692153D0A9877CC62A474002DF32E52139F0A0"> {
261};
262
263// clang-format on
264
265// With 32-bit words the Solinas reduction is faster than Montgomery
266using Sm2p256v1Base = std::conditional_t<WordInfo<word>::bits == 64,
269
270class Curve final : public Sm2p256v1Base {
271 public:
272 // Return the square of the inverse of x
273 static constexpr FieldElement fe_invert2(const FieldElement& x) {
274 // Generated by https://github.com/mmcloughlin/addchain
275 auto z = x.square();
276 auto t0 = x * z;
277 z = t0.square();
278 z *= x;
279 auto t1 = z;
280 t1.square_n(3);
281 t1 *= z;
282 auto t2 = t1.square();
283 z = t2 * x;
284 t2.square_n(5);
285 t1 *= t2;
286 t2 = t1;
287 t2.square_n(12);
288 t1 *= t2;
289 t1.square_n(7);
290 z *= t1;
291 t2 = z;
292 t2.square_n(2);
293 t1 = t2;
294 t1.square_n(29);
295 z *= t1;
296 t1.square_n(2);
297 t2 *= t1;
298 t0 *= t2;
299 t1.square_n(32);
300 t1 *= t0;
301 t1.square_n(64);
302 t0 *= t1;
303 t0.square_n(94);
304 z *= t0;
305 z.square_n(2);
306 return z;
307 }
308
309 static constexpr FieldElement fe_sqrt(const FieldElement& x) {
310 auto z = x.square();
311 z *= x;
312 z = z.square();
313 auto t0 = x * z;
314 z = t0.square();
315 z *= x;
316 auto t2 = z.square();
317 auto t3 = t2.square();
318 auto t1 = t3.square();
319 auto t4 = t1;
320 t4.square_n(3);
321 t3 *= t4;
322 t3.square_n(5);
323 t1 *= t3;
324 t3 = t1;
325 t3.square_n(2);
326 t2 *= t3;
327 t2.square_n(14);
328 t1 *= t2;
329 t0 *= t1;
330 t0.square_n(4);
331 t1 = t0;
332 t1.square_n(31);
333 t0 *= t1;
334 t1.square_n(32);
335 t1 *= t0;
336 t1.square_n(62);
337 t0 *= t1;
338 z *= t0;
339 z.square_n(32);
340 z *= x;
341 z.square_n(62);
342 return z;
343 }
344};
345
346} // namespace sm2p256v1
347
348} // namespace
349
350std::shared_ptr<const PrimeOrderCurve> PCurveInstance::sm2p256v1() {
352}
353
354} // namespace Botan::PCurve
static std::shared_ptr< const PrimeOrderCurve > instance()
constexpr void accum(int64_t v)
constexpr W final_carry(int64_t C)
#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)
void R2(uint32_t A, uint32_t &B, uint32_t C, uint32_t &D, uint32_t E, uint32_t &F, uint32_t G, uint32_t &H, uint32_t TJ, uint32_t Wi, uint32_t Wj)
Definition sm3_fn.h:43
void R1(uint32_t A, uint32_t &B, uint32_t C, uint32_t &D, uint32_t E, uint32_t &F, uint32_t G, uint32_t &H, uint32_t TJ, uint32_t Wi, uint32_t Wj)
Definition sm3_fn.h:21
BOTAN_FORCE_INLINE constexpr T choose(T mask, T a, T b)
Definition bit_ops.h:217
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)