Botan 3.14.1
Crypto and TLS for C&
bls12_381_scalar.cpp
Go to the documentation of this file.
1/*
2* (C) 2024,2025,2026 Jack Lloyd
3*
4* Botan is released under the Simplified BSD License (see license.txt)
5*/
6
7#include <botan/bls12_381.h>
8
9#include <botan/mem_ops.h>
10#include <botan/internal/ct_utils.h>
11#include <botan/internal/mp_core.h>
12#include <algorithm>
13
14namespace Botan::BLS12_381 {
15
16namespace {
17
18constexpr auto SCALAR_P = hex_to_words<word>("73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001");
19
20// R1 = 2**256 % p
21constexpr auto SCALAR_R1 = hex_to_words<word>("1824b159acc5056f998c4fefecbc4ff55884b7fa0003480200000001fffffffe");
22
23// R2 = (R1**2) % p
24constexpr auto SCALAR_R2 = hex_to_words<word>("748d9d99f59ff1105d314967254398f2b6cedcb87925c23c999e990f3f29c6d");
25
26// R3 = (R1*R2) % p
27constexpr auto SCALAR_R3 = hex_to_words<word>("6e2a5bb9c8db33e973d13c71c7b5f4181b3e0d188cf06990c62c1807439b73af");
28
29constexpr word SCALAR_P_DASH = monty_inverse(SCALAR_P[0]);
30
31std::array<word, Scalar::N> scalar_redc(const std::array<word, 2 * Scalar::N>& v) {
32 std::array<word, Scalar::N> r{};
33 std::array<word, Scalar::N> ws{};
34 bigint_monty_redc(r.data(), v.data(), SCALAR_P.data(), SCALAR_P.size(), SCALAR_P_DASH, ws.data(), ws.size());
35 return r;
36}
37
38std::array<word, Scalar::N> scalar_to_rep(std::array<word, Scalar::N> v) {
39 std::array<word, 2 * Scalar::N> z{};
40 comba_mul<Scalar::N>(z.data(), v.data(), SCALAR_R2.data());
41 return scalar_redc(z);
42}
43
44std::array<word, Scalar::N> scalar_wide_to_rep(const std::array<word, 2 * Scalar::N>& v) {
45 auto redc_v = scalar_redc(v);
46 std::array<word, 2 * Scalar::N> z{};
47 comba_mul<Scalar::N>(z.data(), redc_v.data(), SCALAR_R3.data());
48 return scalar_redc(z);
49}
50
51std::array<word, Scalar::N> scalar_from_rep(const std::array<word, Scalar::N>& v) {
52 std::array<word, 2 * Scalar::N> z{};
53 copy_mem(z.data(), v.data(), v.size());
54 return scalar_redc(z);
55}
56
57} // namespace
58
59void Scalar::wipe() {
61}
62
63//static
64Scalar Scalar::from_words(std::array<word, Scalar::N> v) {
65 return Scalar(scalar_to_rep(v));
66}
67
68//static
70 std::array<word, Scalar::N> w{};
71 w[0] = v;
72 return Scalar::from_words(w);
73}
74
75//static
77 return Scalar(SCALAR_R1);
78}
79
80std::optional<Scalar> Scalar::deserialize(std::span<const uint8_t> bytes) {
81 if(bytes.size() != Scalar::BYTES) {
82 return {};
83 }
84
85 const auto words = bytes_to_words<word, N, BYTES>(bytes.first<Scalar::BYTES>());
86
87 if(!bigint_ct_is_lt(words.data(), N, SCALAR_P.data(), N).as_bool()) {
88 return {};
89 }
90
91 // Reject the zero scalar; a zero secret key, challenge, or nonce is
92 // essentially always a mistake. This matches EC_Scalar::deserialize.
93 if(CT::all_zeros(words.data(), N).as_bool()) {
94 return {};
95 }
96
97 return Scalar::from_words(words);
98}
99
100Scalar Scalar::from_bytes_wide(std::span<const uint8_t, 64> bytes) {
101 return Scalar(scalar_wide_to_rep(bytes_to_words<word, 2 * N, 2 * BYTES>(bytes)));
102}
103
104void Scalar::serialize_to(std::span<uint8_t, Scalar::BYTES> bytes) const {
105 auto v = scalar_from_rep(m_val);
106 std::reverse(v.begin(), v.end());
107 store_be(bytes, v);
108 // The scalar may be a secret; don't leave an extra copy on the stack
110}
111
112Scalar Scalar::add(const Scalar& other) const {
113 std::array<word, Scalar::N> t{};
114 word carry = 0;
115 for(size_t i = 0; i != Scalar::N; ++i) {
116 t[i] = word_add(m_val[i], other.m_val[i], &carry);
117 }
118
119 std::array<word, Scalar::N> r{};
120 bigint_monty_maybe_sub<Scalar::N>(r.data(), carry, t.data(), SCALAR_P.data());
121 return Scalar(r);
122}
123
124Scalar Scalar::sub(const Scalar& other) const {
125 std::array<word, Scalar::N> r; // NOLINT(*-member-init)
126 word borrow = 0;
127 for(size_t i = 0; i != Scalar::N; ++i) {
128 r[i] = word_sub(m_val[i], other.m_val[i], &borrow);
129 }
130
131 const word mask = CT::Mask<word>::expand(borrow).value();
132 word carry = 0;
133 for(size_t i = 0; i != Scalar::N; ++i) {
134 r[i] = word_add(r[i], SCALAR_P[i] & mask, &carry);
135 }
136
137 return Scalar(r);
138}
139
140Scalar Scalar::mul(const Scalar& other) const {
141 std::array<word, 2 * Scalar::N> z{};
142 comba_mul<Scalar::N>(z.data(), data(), other.data());
143 return Scalar(scalar_redc(z));
144}
145
147 std::array<word, 2 * Scalar::N> z{};
148 comba_sqr<Scalar::N>(z.data(), data());
149 return Scalar(scalar_redc(z));
150}
151
152void Scalar::square_n(size_t n) {
153 std::array<word, 2 * N> z{};
154 for(size_t i = 0; i != n; ++i) {
155 comba_sqr<N>(z.data(), this->data());
156 m_val = scalar_redc(z);
157 }
158}
159
161 auto v_is_zero = CT::all_zeros(this->data(), N);
162
163 std::array<word, N> r{};
164 bigint_sub3(r.data(), SCALAR_P.data(), N, this->data(), N);
165 v_is_zero.if_set_zero_out(r.data(), N);
166 return Scalar(r);
167}
168
170 // Addition chain for exponentiation to p - 2
171 // Found using https://github.com/mmcloughlin/addchain
172 auto t3 = this->square();
173 auto z = t3 * (*this);
174 auto t14 = (*this) * z;
175 auto t2 = t14 * t3;
176 auto t4 = t2.square();
177 auto t8 = t2 * t4;
178 auto t5 = t8 * (*this);
179 auto t11 = t5 * z;
180 auto t0 = t11 * t3;
181 auto t9 = t0 * t3;
182 auto t1 = t11 * t4;
183 auto t10 = t1 * t5;
184 auto t6 = t10 * t2;
185 t2 = t10 * t11;
186 auto t7 = t2 * t3;
187 t5 = t6 * t9;
188 t8 *= t5;
189 t3 *= t8;
190 t9 *= t3;
191 auto t12 = t11 * t9;
192 auto t13 = t12 * t14;
193 t1 *= t13;
194 t11 = t0 * t1;
195 t14 *= t11;
196 auto t15 = t14 * t4;
197 t4 = t0 * t11;
198 t0 *= t15;
199 t15.square_n(8);
200 t14 *= t15;
201 t14.square_n(9);
202 t13 *= t14;
203 t13.square_n(9);
204 t13 *= t12;
205 t13.square_n(9);
206 t12 *= t13;
207 t12.square_n(8);
208 t11 *= t12;
209 t11.square_n(6);
210 t10 *= t11;
211 t10.square_n(10);
212 t9 *= t10;
213 t9.square_n(9);
214 t8 *= t9;
215 t8.square_n(8);
216 t8 *= t6;
217 t8.square_n(8);
218 t8 *= (*this);
219 t8.square_n(14);
220 t7 *= t8;
221 t7.square_n(10);
222 t6 *= t7;
223 t6.square_n(15);
224 t5 *= t6;
225 t5.square_n(10);
226 t4 *= t5;
227 t4.square_n(8);
228 t3 *= t4;
229 t3.square_n(16);
230 t3 *= t1;
231 t3.square_n(8);
232 t3 *= t0;
233 t3.square_n(7);
234 t2 *= t3;
235 t2.square_n(9);
236 t2 *= t0;
237 t2.square_n(8);
238 t2 *= t1;
239 t2.square_n(8);
240 t2 *= t0;
241 t2.square_n(8);
242 t2 *= t0;
243 t2.square_n(8);
244 t2 *= t0;
245 t2.square_n(8);
246 t1 *= t2;
247 t1.square_n(8);
248 t1 *= t0;
249 t1.square_n(8);
250 t1 *= t0;
251 t1.square_n(8);
252 t0 *= t1;
253 t0.square_n(2);
254 z *= t0;
255 return z;
256}
257
258} // namespace Botan::BLS12_381
static Scalar from_u32(uint32_t v)
static std::optional< Scalar > deserialize(std::span< const uint8_t > bytes)
static constexpr size_t N
Definition bls12_381.h:38
Scalar mul(const Scalar &x) const
void serialize_to(std::span< uint8_t, Scalar::BYTES > bytes) const
static constexpr size_t BYTES
Definition bls12_381.h:35
static Scalar from_bytes_wide(std::span< const uint8_t, 64 > bytes)
Scalar sub(const Scalar &x) const
Scalar add(const Scalar &x) const
static constexpr Mask< T > expand(T v)
Definition ct_utils.h:397
constexpr CT::Mask< T > all_zeros(const T elem[], size_t len)
Definition ct_utils.h:790
constexpr auto bytes_to_words(std::span< const uint8_t, L > bytes)
Definition mp_core.h:1255
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_sqr(W z[2 *N], const W x[N])
Definition mp_core.h:1017
constexpr void comba_mul(W z[2 *N], const W x[N], const W y[N])
Definition mp_core.h:981
constexpr auto bigint_sub3(W z[], const W x[], size_t x_size, const W y[], size_t y_size) -> W
Definition mp_core.h:196
constexpr auto monty_inverse(W a) -> W
Definition mp_core.h:866
constexpr void copy_mem(T *out, const T *in, size_t n)
Definition mem_ops.h:144
void secure_scrub_memory(void *ptr, size_t n)
Definition mem_utils.cpp:24
void bigint_monty_redc(word r[], const word z[], const word p[], size_t p_size, word p_dash, word ws[], size_t ws_size)
Definition mp_core.h:1086
constexpr void bigint_monty_maybe_sub(size_t N, W z[], W x0, const W x[], const W p[])
Definition mp_core.h:229
constexpr auto bigint_ct_is_lt(const W x[], size_t x_size, const W y[], size_t y_size, bool lt_or_equal=false) -> CT::Mask< W >
Definition mp_core.h:510
constexpr auto hex_to_words(const char(&s)[N])
Definition mp_core.h:921
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
constexpr auto store_be(ParamTs &&... params)
Definition loadstor.h:745