Botan 3.7.1
Crypto and TLS for C&
pcurves_secp256r1.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 Secp256r1Rep 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 bigint_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
112namespace secp256r1 {
113
114// clang-format off
115class Params final : public EllipticCurveParameters<
116 "FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF",
117 "FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC",
118 "5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B",
119 "FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551",
120 "6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296",
121 "4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5",
122 -10> {
123};
124
125// clang-format on
126
127class Curve final : public EllipticCurve<Params, Secp256r1Rep> {
128 public:
129 // Return the square of the inverse of x
130 static constexpr FieldElement fe_invert2(const FieldElement& x) {
131 // Generated using https://github.com/mmcloughlin/addchain
132
133 auto z = x.square();
134 z *= x;
135 z = z.square();
136 z *= x;
137 auto t0 = z;
138 t0.square_n(3);
139 t0 *= z;
140 auto t1 = t0;
141 t1.square_n(6);
142 t0 *= t1;
143 t0.square_n(3);
144 z *= t0;
145 t0 = z.square();
146 t0 *= x;
147 t1 = t0;
148 t1.square_n(16);
149 t0 *= t1;
150 t0.square_n(15);
151 z *= t0;
152 t0.square_n(17);
153 t0 *= x;
154 t0.square_n(143);
155 t0 *= z;
156 t0.square_n(47);
157 z *= t0;
158 z.square_n(2);
159
160 return z;
161 }
162
163 static constexpr Scalar scalar_invert(const Scalar& x) {
164 auto t1 = x.square();
165 auto t5 = t1.square();
166 auto t2 = t5 * x;
167 auto t10 = t2 * x;
168 auto t3 = t2 * t5;
169 auto z = t10 * t3;
170 auto t9 = t3.square();
171 auto t4 = t10 * z;
172 auto t0 = t10 * t9;
173 auto t13 = t0 * t1;
174 auto t8 = t13 * t4;
175 t4 = t3 * t8;
176 auto t7 = t2 * t4;
177 t2 = t1 * t7;
178 auto t6 = t7 * t9;
179 t3 = t6 * t9;
180 t1 *= t3;
181 auto t12 = t3 * t9;
182 t5 *= t12;
183 auto t11 = t10 * t5;
184 t0 *= t11;
185 t9 *= t0;
186 t10 *= t9;
187 t4 *= t10;
188 t13 *= t4;
189 auto t14 = t13;
190 t14.square_n(8);
191 t13 *= t14;
192 t14 = t13;
193 t14.square_n(16);
194 t14 *= t13;
195 t14.square_n(48);
196 t14 *= t13;
197 t14.square_n(16);
198 t14 *= t13;
199 t14.square_n(16);
200 t14 *= t13;
201 t14.square_n(16);
202 t13 *= t14;
203 t13.square_n(6);
204 t13 *= t8;
205 t13.square_n(9);
206 t12 *= t13;
207 t12.square_n(8);
208 t11 *= t12;
209 t11.square_n(9);
210 t10 *= t11;
211 t10.square_n(8);
212 t9 *= t10;
213 t9.square_n(9);
214 t8 *= t9;
215 t8.square_n(8);
216 t7 *= t8;
217 t7.square_n(11);
218 t6 *= t7;
219 t6.square_n(9);
220 t5 *= t6;
221 t5.square_n(10);
222 t4 *= t5;
223 t4.square_n(8);
224 t3 *= t4;
225 t3.square_n(7);
226 t2 *= t3;
227 t2.square_n(10);
228 t1 *= t2;
229 t1.square_n(10);
230 t0 *= t1;
231 t0.square_n(6);
232 z *= t0;
233
234 return z;
235 }
236};
237
238} // namespace secp256r1
239
240} // namespace
241
242std::shared_ptr<const PrimeOrderCurve> PCurveInstance::secp256r1() {
244}
245
246} // namespace Botan::PCurve
#define BOTAN_DEBUG_ASSERT(expr)
Definition assert.h:98
static std::shared_ptr< const PrimeOrderCurve > secp256r1()
Definition pcurves.cpp:33
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
constexpr auto hex_to_words(const char(&s)[N])
Definition mp_core.h:846