Botan 3.14.1
Crypto and TLS for C&
bls12_381_fields.h
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#ifndef BOTAN_BLS12_381_FIELDS_H_
8#define BOTAN_BLS12_381_FIELDS_H_
9
10#include <botan/types.h>
11#include <botan/internal/ct_utils.h>
12#include <botan/internal/mp_core.h>
13#include <array>
14#include <optional>
15#include <span>
16
17namespace Botan::BLS12_381 {
18
19/**
20* A BLS12-381 field element
21*
22* Integer modulo 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
23*/
25 public:
26 static constexpr size_t BITS = 381;
27 static constexpr size_t BYTES = (BITS + 7) / 8;
28 static constexpr size_t N = (BYTES + sizeof(word) - 1) / sizeof(word);
29
30 static_assert(BYTES == N * sizeof(word));
31
32 /** Default constructed as zero */
33 constexpr FieldElement() : m_val({}) {}
34
35 static FieldElement from_u32(uint32_t v);
36
37 static FieldElement zero() { return FieldElement(); }
38
39 static FieldElement one();
40
41 static std::optional<FieldElement> deserialize(std::span<const uint8_t> bytes);
42
43 static FieldElement from_bytes_wide(std::span<const uint8_t, 96> bytes);
44
45 CT::Choice is_zero() const;
46
47 void serialize_to(std::span<uint8_t, FieldElement::BYTES> bytes) const;
48
49 std::array<uint8_t, FieldElement::BYTES> serialize() const {
50 std::array<uint8_t, FieldElement::BYTES> buf{};
51 this->serialize_to(buf);
52 return buf;
53 }
54
55 FieldElement add(const FieldElement& x) const;
56
57 FieldElement sub(const FieldElement& x) const;
58
59 FieldElement mul(const FieldElement& x) const;
60
62 (*this) = this->add(x);
63 return (*this);
64 }
65
67 (*this) = this->sub(x);
68 return (*this);
69 }
70
72 (*this) = this->mul(x);
73 return (*this);
74 }
75
76 FieldElement negate() const;
77
78 /**
79 * Return the multiplicative inverse of this element, or zero for zero
80 */
81 FieldElement invert() const;
82
83 FieldElement square() const;
84
85 /**
86 * Return the square root of this element, if one exists
87 *
88 * If x and -x are both square roots, which of the two is returned
89 * is unspecified.
90 */
91 CT::Option<FieldElement> sqrt() const;
92
93 /**
94 * Constant time equality
95 */
96 CT::Choice operator==(const FieldElement& other) const;
97
98 CT::Choice operator!=(const FieldElement& other) const { return !(*this == other); }
99
100 /**
101 * Set iff this is larger than its negation
102 *
103 * Ie set if this is > (p-1)/2
104 */
105 CT::Choice _is_lexicographically_largest() const;
106
107 /**
108 * The input is assumed to be valid and already in Montgomery representation
109 */
110 static constexpr FieldElement _unchecked_from_words(std::array<word, FieldElement::N> v) {
111 return FieldElement(v);
112 }
113
114 /**
115 * The Montgomery representation words
116 */
117 constexpr const std::array<word, N>& _words() const { return m_val; }
118
119 /**
120 * If cnd is set assign other to this, in constant time
121 */
122 void conditional_assign(CT::Choice cnd, const FieldElement& other);
123
124 private:
125 // Squaring in place
126 void square_n(size_t n);
127
128 constexpr const std::array<word, N>& value() const { return m_val; }
129
130 constexpr const word* data() const { return m_val.data(); }
131
132 static FieldElement from_words(std::array<word, FieldElement::N> v);
133
134 explicit constexpr FieldElement(std::array<word, FieldElement::N> v) : m_val(v) {}
135
136 std::array<word, FieldElement::N> m_val;
137};
138
140 return a.add(b);
141}
142
144 return a.sub(b);
145}
146
148 return a.mul(b);
149}
150
151/**
152* An element of the extension field Fp2 = Fp[u]/(u^2 + 1)
153*
154* Represented as c0 + c1*u
155*/
157 public:
158 static constexpr size_t BYTES = 2 * FieldElement::BYTES;
159
160 /** Default constructed as zero */
161 constexpr FieldElement2() = default;
162
163 constexpr FieldElement2(const FieldElement& c0, const FieldElement& c1) : m_c0(c0), m_c1(c1) {}
164
165 static FieldElement2 zero() { return FieldElement2(); }
166
168
169 /**
170 * Deserialization; the c1 coefficient is encoded first, following
171 * the ZCash convention for G2 point encoding
172 */
173 static std::optional<FieldElement2> deserialize(std::span<const uint8_t> bytes);
174
175 void serialize_to(std::span<uint8_t, FieldElement2::BYTES> bytes) const;
176
177 std::array<uint8_t, FieldElement2::BYTES> serialize() const {
178 std::array<uint8_t, FieldElement2::BYTES> buf{};
179 this->serialize_to(buf);
180 return buf;
181 }
182
183 const FieldElement& c0() const { return m_c0; }
184
185 const FieldElement& c1() const { return m_c1; }
186
187 CT::Choice is_zero() const;
188
189 FieldElement2 add(const FieldElement2& x) const;
190
191 FieldElement2 sub(const FieldElement2& x) const;
192
193 FieldElement2 mul(const FieldElement2& x) const;
194
196 (*this) = this->add(x);
197 return (*this);
198 }
199
201 (*this) = this->sub(x);
202 return (*this);
203 }
204
206 (*this) = this->mul(x);
207 return (*this);
208 }
209
210 FieldElement2 negate() const;
211
212 /**
213 * Return the multiplicative inverse of this element, or zero for zero
214 */
215 FieldElement2 invert() const;
216
217 FieldElement2 square() const;
218
219 // Squaring in place for fixed addition chains
220 void square_n(size_t n);
221
222 /**
223 * Return the conjugate c0 - c1*u, which is also the image of this
224 * element under the Frobenius endomorphism x -> x^p
225 */
226 FieldElement2 conjugate() const;
227
228 /**
229 * Multiplication by the sextic nonresidue u + 1
230 */
231 FieldElement2 mul_by_nonresidue() const;
232
233 /**
234 * Return the square root of this element, if one exists
235 *
236 * If x and -x are both square roots, which of the two is returned
237 * is unspecified.
238 */
239 CT::Option<FieldElement2> sqrt() const;
240
241 /**
242 * Constant time equality
243 */
244 CT::Choice operator==(const FieldElement2& other) const;
245
246 CT::Choice operator!=(const FieldElement2& other) const { return !(*this == other); }
247
248 /**
249 * Set iff this is larger than its negation
250 *
251 * The comparison is lexicographic on (c1, c0), matching the ZCash
252 * convention: c1 > (p-1)/2, or c1 == 0 and c0 > (p-1)/2.
253 */
254 CT::Choice _is_lexicographically_largest() const;
255
256 /**
257 * The inputs are assumed to be valid and already in Montgomery representation
258 */
259 static constexpr FieldElement2 _unchecked_from_words(std::array<word, FieldElement::N> c0,
260 std::array<word, FieldElement::N> c1) {
262 }
263
264 /**
265 * If cnd is set assign other to this, in constant time
266 */
267 void conditional_assign(CT::Choice cnd, const FieldElement2& other);
268
269 private:
270 FieldElement m_c0;
271 FieldElement m_c1;
272};
273
275 return a.add(b);
276}
277
279 return a.sub(b);
280}
281
283 return a.mul(b);
284}
285
286FieldElement2 pow_p2_minus_9_over_16(const FieldElement2& x);
287
288/**
289* Generic MSB-first exponentiation with a fixed public exponent
290*
291* Since every exponent used is a fixed constant, each user could
292* instead use an addchain generated chain (as invert does), reducing
293* the multiplication count roughly 3x; the sqrts during G1 and
294* especially G2 deserialization would benefit the most.
295*/
296template <typename FE, size_t N>
297FE pow_msb(const FE& x, const std::array<word, N>& exp) {
298 auto r = FE::one();
299 for(size_t i = 0; i != N; ++i) {
300 const word w = exp[N - 1 - i];
301 for(size_t b = 0; b != WordInfo<word>::bits; ++b) {
302 r = r.square();
303 // The exponent is a public constant so this branch leaks nothing
304 if(((w >> (WordInfo<word>::bits - 1 - b)) & 1) == 1) {
305 r = r * x;
306 }
307 }
308 }
309 return r;
310}
311
312} // namespace Botan::BLS12_381
313
314#endif
#define BOTAN_TEST_API
Definition api.h:41
FieldElement2 add(const FieldElement2 &x) const
CT::Choice operator!=(const FieldElement2 &other) const
constexpr FieldElement2()=default
std::array< uint8_t, FieldElement2::BYTES > serialize() const
FieldElement2 mul(const FieldElement2 &x) const
FieldElement2 & operator+=(const FieldElement2 &x)
static constexpr FieldElement2 _unchecked_from_words(std::array< word, FieldElement::N > c0, std::array< word, FieldElement::N > c1)
FieldElement2 sub(const FieldElement2 &x) const
static constexpr size_t BYTES
const FieldElement & c0() const
const FieldElement & c1() const
void serialize_to(std::span< uint8_t, FieldElement2::BYTES > bytes) const
constexpr FieldElement2(const FieldElement &c0, const FieldElement &c1)
FieldElement2 & operator-=(const FieldElement2 &x)
FieldElement2 & operator*=(const FieldElement2 &x)
static constexpr size_t BITS
static constexpr FieldElement _unchecked_from_words(std::array< word, FieldElement::N > v)
FieldElement add(const FieldElement &x) const
std::array< uint8_t, FieldElement::BYTES > serialize() const
static FieldElement one()
FieldElement & operator-=(const FieldElement &x)
static constexpr size_t BYTES
constexpr const std::array< word, N > & _words() const
FieldElement & operator*=(const FieldElement &x)
FieldElement & operator+=(const FieldElement &x)
void serialize_to(std::span< uint8_t, FieldElement::BYTES > bytes) const
FieldElement mul(const FieldElement &x) const
CT::Choice operator!=(const FieldElement &other) const
FieldElement sub(const FieldElement &x) const
static constexpr size_t N
Scalar operator-(const Scalar &a, const Scalar &b)
Definition bls12_381.h:177
FieldElement2 pow_p2_minus_9_over_16(const FieldElement2 &x)
FE pow_msb(const FE &x, const std::array< word, N > &exp)
Scalar operator+(const Scalar &a, const Scalar &b)
Definition bls12_381.h:172
Scalar operator*(const Scalar &a, const Scalar &b)
Definition bls12_381.h:182
BigInt square(const BigInt &x)
Definition numthry.cpp:184
bool operator==(const AlgorithmIdentifier &x, const AlgorithmIdentifier &y)
Definition alg_id.cpp:54
std::conditional_t< HasNative64BitRegisters, std::uint64_t, uint32_t > word
The native machine word, used as the limb type for multiprecision integers.
Definition types.h:131