Botan 3.7.1
Crypto and TLS for C&
pcurves_secp224r1.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 secp224r1 {
17
18template <typename Params>
19class Secp224r1Rep 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
41 const int64_t S0 = 0x00000001 + X00 - X07 - X11;
42 const int64_t S1 = 0x00000000 + X01 - X08 - X12;
43 const int64_t S2 = 0x00000000 + X02 - X09 - X13;
44 const int64_t S3 = 0xFFFFFFFF + X03 + X07 + X11 - X10;
45 const int64_t S4 = 0xFFFFFFFF + X04 + X08 + X12 - X11;
46 const int64_t S5 = 0xFFFFFFFF + X05 + X09 + X13 - X12;
47 const int64_t S6 = 0xFFFFFFFF + X06 + X10 - X13;
48
49 std::array<W, N> r = {};
50
51 SolinasAccum sum(r);
52
53 sum.accum(S0);
54 sum.accum(S1);
55 sum.accum(S2);
56 sum.accum(S3);
57 sum.accum(S4);
58 sum.accum(S5);
59 sum.accum(S6);
60 const auto S = sum.final_carry(0);
61
62 BOTAN_DEBUG_ASSERT(S <= 2);
63
64 bigint_correct_redc<N>(r, P, p224_mul_mod_224(S));
65
66 return r;
67 }
68
69 constexpr static std::array<W, N> one() { return std::array<W, N>{1}; }
70
71 constexpr static std::array<W, N> to_rep(const std::array<W, N>& x) { return x; }
72
73 constexpr static std::array<W, N> wide_to_rep(const std::array<W, 2 * N>& x) { return redc(x); }
74
75 constexpr static std::array<W, N> from_rep(const std::array<W, N>& z) { return z; }
76
77 private:
78 // Return (i*P-224) % 2**224
79 //
80 // Assumes i is small
81 constexpr static std::array<W, N> p224_mul_mod_224(W i) {
82 static_assert(WordInfo<W>::bits == 32 || WordInfo<W>::bits == 64);
83
84 // For small i, multiples of P-224 have a simple structure so it's faster to
85 // compute the value directly vs a (constant time) table lookup
86
87 auto r = P;
88
89 if constexpr(WordInfo<W>::bits == 32) {
90 r[3] -= i;
91 r[0] += i;
92 } else {
93 const W i32 = i << 32;
94 r[1] -= i32;
95 r[0] += i;
96 }
97 return r;
98 }
99};
100
101// clang-format off
102class Params final : public EllipticCurveParameters<
103 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF000000000000000000000001",
104 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFE",
105 "B4050A850C04B3ABF54132565044B0B7D7BFD8BA270B39432355FFB4",
106 "FFFFFFFFFFFFFFFFFFFFFFFFFFFF16A2E0B8F03E13DD29455C5C2A3D",
107 "B70E0CBD6BB4BF7F321390B94A03C1D356C21122343280D6115C1D21",
108 "BD376388B5F723FB4C22DFE6CD4375A05A07476444D5819985007E34"> {
109};
110
111// clang-format on
112
113class Curve final : public EllipticCurve<Params, Secp224r1Rep> {
114 public:
115 // Return the square of the inverse of x
116 static constexpr FieldElement fe_invert2(const FieldElement& x) {
117 auto z = x.square();
118 z *= x;
119 z = z.square();
120 z *= x;
121 auto t0 = z;
122 t0.square_n(3);
123 t0 *= z;
124 auto t1 = t0;
125 t1.square_n(6);
126 t0 *= t1;
127 t0.square_n(3);
128 z *= t0;
129 t0 = z.square();
130 t0 *= x;
131 t1 = t0;
132 t1.square_n(16);
133 t0 *= t1;
134 t1 = t0;
135 t1.square_n(15);
136 z *= t1;
137 t1 = z;
138 t1.square_n(47);
139 z *= t1;
140 z = z.square();
141 z *= x;
142 t1 = z;
143 t1.square_n(32);
144 t0 *= t1;
145 t0.square_n(96);
146 z *= t0;
147 return z.square();
148 }
149
150 static constexpr Scalar scalar_invert(const Scalar& x) {
151 // Generated using https://github.com/mmcloughlin/addchain
152 auto t6 = x.square();
153 auto z = t6.square();
154 auto t3 = x * z;
155 auto t2 = t3 * t6;
156 auto t8 = t2 * z;
157 auto t7 = t8 * z;
158 auto t5 = t7 * z;
159 auto t0 = t5 * t6;
160 auto t1 = t0 * t6;
161 auto t4 = t1 * z;
162 z = t4 * t6;
163 t6 *= z;
164 auto t10 = t6.square();
165 auto t9 = t10 * x;
166 t10.square_n(5);
167 t9 *= t10;
168 t10.square_n(5);
169 t9 *= t10;
170 t10 = t9;
171 t10.square_n(16);
172 t10 *= t9;
173 auto t11 = t10;
174 t11.square_n(32);
175 t11 *= t10;
176 t11.square_n(32);
177 t10 *= t11;
178 t10.square_n(16);
179 t9 *= t10;
180 t9.square_n(7);
181 t8 *= t9;
182 t8.square_n(4);
183 t8 *= t3;
184 t8.square_n(8);
185 t8 *= t1;
186 t8.square_n(10);
187 t8 *= t1;
188 t8.square_n(7);
189 t7 *= t8;
190 t7.square_n(11);
191 t6 *= t7;
192 t6.square_n(9);
193 t5 *= t6;
194 t5.square_n(5);
195 t4 *= t5;
196 t4.square_n(3);
197 t4 *= t3;
198 t4.square_n(5);
199 t4 *= t3;
200 t4.square_n(5);
201 t3 *= t4;
202 t3.square_n(8);
203 t3 *= t0;
204 t3.square_n(4);
205 t2 *= t3;
206 t2.square_n(8);
207 t1 *= t2;
208 t1.square_n(9);
209 t0 *= t1;
210 t0.square_n(8);
211 z *= t0;
212 z = z.square();
213 z *= x;
214 return z;
215 }
216};
217
218} // namespace secp224r1
219
220} // namespace
221
222std::shared_ptr<const PrimeOrderCurve> PCurveInstance::secp224r1() {
224}
225
226} // namespace Botan::PCurve
#define BOTAN_DEBUG_ASSERT(expr)
Definition assert.h:98
static std::shared_ptr< const PrimeOrderCurve > secp224r1()
Definition pcurves.cpp:26
static std::shared_ptr< const PrimeOrderCurve > instance()
constexpr void accum(int64_t v)
constexpr W final_carry(int64_t C)
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