Botan 3.14.1
Crypto and TLS for C&
monty.cpp
Go to the documentation of this file.
1/*
2* (C) 2018,2024,2025 Jack Lloyd
3*
4* Botan is released under the Simplified BSD License (see license.txt)
5*/
6
7#include <botan/internal/monty.h>
8
9#include <botan/exceptn.h>
10#include <botan/mem_ops.h>
11#include <botan/internal/barrett.h>
12#include <botan/internal/bit_ops.h>
13#include <botan/internal/ct_utils.h>
14#include <botan/internal/mp_core.h>
15#include <functional>
16
17namespace Botan {
18
19namespace {
20
21// If the modulus is at most this many words, then use the stack instead
22// of a heap variable for some temporary values
23constexpr size_t MontgomeryUseStackLimit = 32;
24
25/*
26* The typed std::less<T*> specialization gives a strict total order on pointers
27* of the same type even when they belong to different allocations (while direct
28* < and > on raw pointers are only specified within a single array object).
29* The transparent std::less<> forwards to <, so it is unsuitable here.
30*/
31bool ranges_overlap(const word* a, size_t na, const word* b, size_t nb) {
32 if(na == 0 || nb == 0) {
33 return false;
34 }
35 const std::less<const word*> lt; // NOLINT(modernize-use-transparent-functors)
36 return lt(a, b + nb) && lt(b, a + na);
37}
38
39} // namespace
40
41Montgomery_Params::Data::Data(const BigInt& p, const Barrett_Reduction& mod_p) {
42 if(CT::driveby_unpoison(p.is_even()) || p < 3) {
43 throw Invalid_Argument("Montgomery_Params invalid modulus");
44 }
45
46 m_p = p;
47 m_p_bits = m_p.bits();
48 m_p_words = m_p.sig_words();
49 m_p_dash = monty_inverse(m_p.word_at(0));
50
51 // floor(2^(bits(p) - 1 + WB) / p), derived from Barrett's floor(2^(2*WB*p_words) / p)
52 m_p_top_mu =
53 (mod_p.mu() >> (2 * WordInfo<word>::bits * m_p_words - (m_p_bits - 1 + WordInfo<word>::bits))).word_at(0);
54
55 const BigInt r = BigInt::power_of_2(m_p_words * WordInfo<word>::bits);
56
57 m_r1 = mod_p.reduce(r);
58 m_r2 = mod_p.square(m_r1);
59 m_r3 = mod_p.multiply(m_r1, m_r2);
60
61 // Barrett should be at least zero prefixing up to modulus size
62 BOTAN_ASSERT_NOMSG(m_r1.size() >= m_p_words);
63 BOTAN_ASSERT_NOMSG(m_r2.size() >= m_p_words);
64 BOTAN_ASSERT_NOMSG(m_r3.size() >= m_p_words);
65}
66
68 m_data(std::make_shared<Data>(p, mod_p)) {}
69
72
74 if(this->m_data == other.m_data) {
75 return true;
76 }
77
78 return (this->m_data->p() == other.m_data->p());
79}
80
82 const size_t p_size = this->p_words();
83
84 if(ws.size() < p_size) {
85 ws.resize(p_size);
86 }
87
88 BigInt z = x;
89 z.grow_to(2 * p_size);
90
91 bigint_monty_redc_inplace(z.mutable_data(), this->p()._data(), p_size, this->p_dash(), ws.data(), ws.size());
92
93 return z;
94}
95
97 const size_t p_size = this->p_words();
98 BigInt z = BigInt::with_capacity(2 * p_size);
99 this->mul(z, x, y, ws);
100 return z;
101}
102
103void Montgomery_Params::mul(BigInt& z, const BigInt& x, const BigInt& y, secure_vector<word>& ws) const {
104 BOTAN_ARG_CHECK(&z != &x && &z != &y, "Montgomery_Params::mul output must not alias inputs");
105
106 const size_t p_size = this->p_words();
107
108 if(ws.size() < 2 * p_size) {
109 ws.resize(2 * p_size);
110 }
111
112 BOTAN_DEBUG_ASSERT(x.sig_words() <= p_size);
113 BOTAN_DEBUG_ASSERT(y.sig_words() <= p_size);
114
115 if(z.size() < 2 * p_size) {
116 z.grow_to(2 * p_size);
117 }
118
120 z.size(),
121 x._data(),
122 x.size(),
123 std::min(p_size, x.size()),
124 y._data(),
125 y.size(),
126 std::min(p_size, y.size()),
127 ws.data(),
128 ws.size());
129
130 bigint_monty_redc_inplace(z.mutable_data(), this->p()._data(), p_size, this->p_dash(), ws.data(), ws.size());
131}
132
133void Montgomery_Params::mul(BigInt& z, const BigInt& x, std::span<const word> y, secure_vector<word>& ws) const {
134 BOTAN_ARG_CHECK(&z != &x, "Montgomery_Params::mul output must not alias x");
135 BOTAN_ARG_CHECK(!ranges_overlap(z._data(), z.size(), y.data(), y.size()),
136 "Montgomery_Params::mul output must not overlap y");
137
138 const size_t p_size = this->p_words();
139
140 if(ws.size() < 2 * p_size) {
141 ws.resize(2 * p_size);
142 }
143 if(z.size() < 2 * p_size) {
144 z.grow_to(2 * p_size);
145 }
146
147 BOTAN_DEBUG_ASSERT(x.sig_words() <= p_size);
148
150 z.size(),
151 x._data(),
152 x.size(),
153 std::min(p_size, x.size()),
154 y.data(),
155 y.size(),
156 std::min(p_size, y.size()),
157 ws.data(),
158 ws.size());
159
160 bigint_monty_redc_inplace(z.mutable_data(), this->p()._data(), p_size, this->p_dash(), ws.data(), ws.size());
161}
162
164 const size_t p_size = this->p_words();
165
166 if(ws.size() < 4 * p_size) {
167 ws.resize(4 * p_size);
168 }
169
170 word* z_data = ws.data();
171 word* ws_data = &ws[2 * p_size];
172
173 BOTAN_DEBUG_ASSERT(x.sig_words() <= p_size);
174
175 bigint_mul(z_data,
176 2 * p_size,
177 x._data(),
178 x.size(),
179 std::min(p_size, x.size()),
180 y._data(),
181 y.size(),
182 std::min(p_size, y.size()),
183 ws_data,
184 2 * p_size);
185
186 bigint_monty_redc_inplace(z_data, this->p()._data(), p_size, this->p_dash(), ws_data, 2 * p_size);
187
188 if(x.size() < 2 * p_size) {
189 x.grow_to(2 * p_size);
190 }
191 copy_mem(x.mutable_data(), z_data, 2 * p_size);
192}
193
195 BOTAN_DEBUG_ASSERT(x.sig_words() <= this->p_words());
196 return this->sqr(std::span{x._data(), x.size()}, ws);
197}
198
199BigInt Montgomery_Params::sqr(std::span<const word> x, secure_vector<word>& ws) const {
200 const size_t p_size = this->p_words();
201 BigInt z = BigInt::with_capacity(2 * p_size);
202 this->sqr(z, x, ws);
203 return z;
204}
205
207 BOTAN_ARG_CHECK(&z != &x, "Montgomery_Params::sqr output must not alias input");
208 this->sqr(z, std::span{x._data(), x.size()}, ws);
209}
210
211void Montgomery_Params::sqr(BigInt& z, std::span<const word> x, secure_vector<word>& ws) const {
212 BOTAN_ARG_CHECK(!ranges_overlap(z._data(), z.size(), x.data(), x.size()),
213 "Montgomery_Params::sqr output must not overlap input");
214
215 const size_t p_size = this->p_words();
216
217 if(ws.size() < 2 * p_size) {
218 ws.resize(2 * p_size);
219 }
220
221 if(z.size() < 2 * p_size) {
222 z.grow_to(2 * p_size);
223 }
224
225 bigint_sqr(z.mutable_data(), z.size(), x.data(), x.size(), std::min(p_size, x.size()), ws.data(), ws.size());
226
227 bigint_monty_redc_inplace(z.mutable_data(), this->p()._data(), p_size, this->p_dash(), ws.data(), ws.size());
228}
229
230Montgomery_Int::Montgomery_Int(const Montgomery_Params& params) : m_params(params), m_v(m_params.p_words()) {}
231
233 m_params(params), m_v(std::move(words)) {
234 BOTAN_ASSERT_NOMSG(m_v.size() == m_params.p_words());
235}
236
238 return Montgomery_Int(params, params.R1(), false);
239}
240
243 const auto redc_x = params.mul(params.redc(x, ws), params.R3(), ws);
244 return Montgomery_Int(params, redc_x, false);
245}
246
247Montgomery_Int::Montgomery_Int(const Montgomery_Params& params, const BigInt& v, bool redc_needed) :
248 m_params(params), m_v(m_params.p_words()) {
249 BOTAN_ARG_CHECK(v.signum() >= 0 && v < m_params.p(), "Input out of range");
250
251 const size_t p_size = m_params.p_words();
252
253 auto v_span = v._as_span();
254
255 if(v_span.size() > p_size) {
256 // Safe to truncate the span since we already checked v < p
257 v_span = v_span.first(p_size);
258 }
259
260 BOTAN_ASSERT_NOMSG(m_v.size() >= v_span.size());
261
262 copy_mem(std::span{m_v}.first(v_span.size()), v_span);
263
264 if(redc_needed) {
266 this->mul_by(m_params.R2()._as_span().first(p_size), ws);
267 }
268}
269
270Montgomery_Int::Montgomery_Int(const Montgomery_Params& params, std::span<const word> words) :
271 m_params(params), m_v(words.begin(), words.end()) {
272 BOTAN_ARG_CHECK(m_v.size() == m_params.p_words(), "Invalid input span");
273}
274
275std::vector<uint8_t> Montgomery_Int::serialize() const {
276 return value().serialize();
277}
278
280 secure_vector<word> ws(m_params.p_words());
281
282 secure_vector<word> z = m_v;
283 z.resize(2 * m_params.p_words()); // zero extend
284
286 z.data(), m_params.p()._data(), m_params.p_words(), m_params.p_dash(), ws.data(), ws.size());
287
288 return BigInt::_from_words(z);
289}
290
292 BOTAN_STATE_CHECK(other.m_params == m_params);
293
294 const size_t p_size = m_params.p_words();
295 BOTAN_ASSERT_NOMSG(m_v.size() == p_size && other.m_v.size() == p_size);
296
297 secure_vector<word> z(2 * p_size);
298
299 word* r = std::span{z}.first(p_size).data();
300 word* t = std::span{z}.last(p_size).data();
301
302 // t = this + other
303 const word carry = bigint_add3(t, m_v.data(), p_size, other.m_v.data(), p_size);
304
305 // Conditionally subtract r = t - p
306 bigint_monty_maybe_sub(p_size, r, carry, t, m_params.p()._data());
307
308 z.resize(p_size); // truncate leaving only r
309 return Montgomery_Int(m_params, std::move(z));
310}
311
313 BOTAN_STATE_CHECK(other.m_params == m_params);
314
315 const size_t p_size = m_params.p_words();
316 BOTAN_ASSERT_NOMSG(m_v.size() == p_size && other.m_v.size() == p_size);
317
318 secure_vector<word> t(p_size);
319 const word borrow = bigint_sub3(t.data(), m_v.data(), p_size, other.m_v.data(), p_size);
320
321 bigint_cnd_add(borrow, t.data(), m_params.p()._data(), p_size);
322
323 return Montgomery_Int(m_params, std::move(t));
324}
325
327 BOTAN_STATE_CHECK(other.m_params == m_params);
328
329 const size_t p_size = m_params.p_words();
330 BOTAN_ASSERT_NOMSG(m_v.size() == p_size && other.m_v.size() == p_size);
331
332 if(ws.size() < 4 * p_size) {
333 ws.resize(4 * p_size);
334 }
335
336 secure_vector<word> z(p_size);
337
339 z.data(), m_v.data(), other.m_v.data(), m_params.p()._data(), p_size, m_params.p_dash(), ws.data(), ws.size());
340
341 return Montgomery_Int(m_params, std::move(z));
342}
343
345 BOTAN_STATE_CHECK(other.m_params == m_params);
346 return this->mul_by(std::span{other.m_v}, ws);
347}
348
350 const size_t p_size = m_params.p_words();
351 BOTAN_ASSERT_NOMSG(m_v.size() == p_size && other.size() == p_size);
352
353 if(ws.size() < 4 * p_size) {
354 ws.resize(4 * p_size);
355 }
356
358 m_v.data(), m_v.data(), other.data(), m_params.p()._data(), p_size, m_params.p_dash(), ws.data(), ws.size());
359
360 return (*this);
361}
362
364 const size_t p_size = m_params.p_words();
365 BOTAN_ASSERT_NOMSG(m_v.size() == p_size);
366
367 if(ws.size() < 4 * p_size) {
368 ws.resize(4 * p_size);
369 }
370
371 for(size_t i = 0; i != n; ++i) {
372 bigint_monty_sqr(m_v.data(), m_v.data(), m_params.p()._data(), p_size, m_params.p_dash(), ws.data(), ws.size());
373 }
374
375 return (*this);
376}
377
378void Montgomery_Int::add_mod_p(std::span<const word> other) {
379 const size_t p_size = m_params.p_words();
380 BOTAN_ASSERT_NOMSG(m_v.size() == p_size && other.size() == p_size);
381
382 const auto do_add = [&](std::span<word> t) {
383 const word carry = bigint_add3(t.data(), m_v.data(), p_size, other.data(), p_size);
384 bigint_monty_maybe_sub(p_size, m_v.data(), carry, t.data(), m_params.p()._data());
385 };
386
387 if(p_size <= MontgomeryUseStackLimit) {
388 std::array<word, MontgomeryUseStackLimit> t{};
389 do_add(std::span{t}.first(p_size));
390 } else {
391 secure_vector<word> t(p_size);
392 do_add(t);
393 }
394}
395
397 BOTAN_STATE_CHECK(other.m_params == m_params);
398 this->add_mod_p(other.m_v);
399 return (*this);
400}
401
403 BOTAN_STATE_CHECK(other.m_params == m_params);
404
405 const size_t p_size = m_params.p_words();
406 BOTAN_ASSERT_NOMSG(m_v.size() == p_size && other.m_v.size() == p_size);
407
408 const word borrow = bigint_sub2(m_v.data(), p_size, other.m_v.data(), p_size);
409 bigint_cnd_add(borrow, m_v.data(), m_params.p()._data(), p_size);
410
411 return (*this);
412}
413
415 constexpr size_t WB = WordInfo<word>::bits;
416
417 BOTAN_ARG_CHECK(!CT::Mask<word>::expand(d >> (WB - 2)).as_bool(), "Multiplier too large");
418
419 const size_t p_size = m_params.p_words();
420 BOTAN_ASSERT_NOMSG(m_v.size() == p_size);
421
422 const word* p = m_params.p()._data();
423
424 const auto do_mul = [&](std::span<word> t) {
425 // t = x*d, which is less than d*p < 2^(bits(p) - 2 + WB)
426 bigint_linmul3(t.data(), m_v.data(), p_size, d);
427
428 /*
429 * Estimate q = floor(t/p) as floor(T*mu / 2^(WB+1)), where T is the WB bits
430 * of t starting at bit bits(p) - 2 and mu = floor(2^(bits(p) - 1 + WB) / p).
431 * The estimate is never too high, and is low by at most one.
432 */
433 const size_t pos = m_params.p_bits() - 2;
434 const size_t pos_word = pos / WB;
435 const size_t pos_bit = pos % WB;
436 const word T = (t[pos_word] >> pos_bit) | ((t[pos_word + 1] << 1) << (WB - 1 - pos_bit));
437
438 word q = 0;
439 word_madd2(T, m_params.p_top_mu(), &q);
440 q >>= 1;
441
442 // Now t - q*p < 2*p
443 const word t_hi = t[p_size] - bigint_submul(t.data(), p, p_size, q);
444 bigint_monty_maybe_sub(p_size, m_v.data(), t_hi, t.data(), p);
445 };
446
447 if(p_size <= MontgomeryUseStackLimit) {
448 std::array<word, MontgomeryUseStackLimit + 1> t{};
449 do_mul(std::span{t}.first(p_size + 1));
450 } else {
451 secure_vector<word> t(p_size + 1);
452 do_mul(t);
453 }
454
455 return (*this);
456}
457
459 const size_t p_size = m_params.p_words();
460 BOTAN_ASSERT_NOMSG(m_v.size() == p_size);
461 constexpr size_t WB = WordInfo<word>::bits;
462
463 // If odd, add p (also odd) to make the value even; the sum is below 2p
464 const word carry = bigint_cnd_add(m_v[0] & 1, m_v.data(), m_params.p()._data(), p_size);
465
466 for(size_t i = 0; i != p_size - 1; ++i) {
467 m_v[i] = (m_v[i] >> 1) | (m_v[i + 1] << (WB - 1));
468 }
469 m_v[p_size - 1] = (m_v[p_size - 1] >> 1) | (carry << (WB - 1));
470
471 return (*this);
472}
473
474void Montgomery_Int::ct_cond_negate(bool predicate) {
475 const size_t p_size = m_params.p_words();
476 BOTAN_ASSERT_NOMSG(m_v.size() == p_size);
477
478 // The negation of zero is zero, not p
479 const auto negate = CT::Mask<word>::expand_bool(predicate) & ~CT::all_zeros(m_v.data(), p_size);
480
481 const auto do_negate = [&](std::span<word> t) {
482 bigint_sub3(t.data(), m_params.p()._data(), p_size, m_v.data(), p_size);
483 negate.select_n(m_v.data(), t.data(), m_v.data(), p_size);
484 };
485
486 if(p_size <= MontgomeryUseStackLimit) {
487 std::array<word, MontgomeryUseStackLimit> t{};
488 do_negate(std::span{t}.first(p_size));
489 } else {
490 secure_vector<word> t(p_size);
491 do_negate(t);
492 }
493}
494
495void Montgomery_Int::ct_cond_assign(bool predicate, const Montgomery_Int& other) {
496 BOTAN_STATE_CHECK(other.m_params == m_params);
497 BOTAN_ASSERT_NOMSG(m_v.size() == other.m_v.size());
498 CT::conditional_assign_mem(static_cast<word>(predicate), m_v.data(), other.m_v.data(), m_v.size());
499}
500
502 return CT::all_zeros(m_v.data(), m_v.size()).as_bool();
503}
504
506 auto z = (*this);
507 z.square_this_n_times(ws, 1);
508 return z;
509}
510
511} // namespace Botan
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:82
#define BOTAN_DEBUG_ASSERT(expr)
Definition assert.h:136
#define BOTAN_STATE_CHECK(expr)
Definition assert.h:49
#define BOTAN_ARG_CHECK(expr, msg)
Definition assert.h:33
size_t sig_words() const
Definition bigint.h:687
word * mutable_data()
Definition bigint.h:712
size_t size() const
Definition bigint.h:681
void grow_to(size_t n) const
Definition bigint.h:738
static BigInt _from_words(secure_vector< word > &words)
Definition bigint.h:1052
int signum() const
Definition bigint.h:493
static BigInt power_of_2(size_t n)
Definition bigint.h:906
const word * _data() const
Definition bigint.h:1033
T serialize(size_t len) const
Definition bigint.h:790
static BigInt with_capacity(size_t n)
Definition bigint.cpp:52
std::span< const word > _as_span() const
Definition bigint.h:1023
static constexpr Mask< T > expand(T v)
Definition ct_utils.h:397
static constexpr Mask< T > expand_bool(bool v)
Definition ct_utils.h:402
Montgomery_Int & div2()
Definition monty.cpp:458
static Montgomery_Int from_wide_int(const Montgomery_Params &params, const BigInt &x)
Definition monty.cpp:241
Montgomery_Int & operator+=(const Montgomery_Int &other)
Definition monty.cpp:396
Montgomery_Int & operator-=(const Montgomery_Int &other)
Definition monty.cpp:402
Montgomery_Int square(secure_vector< word > &ws) const
Definition monty.cpp:505
void ct_cond_assign(bool predicate, const Montgomery_Int &other)
Definition monty.cpp:495
static Montgomery_Int one(const Montgomery_Params &params)
Definition monty.cpp:237
Montgomery_Int operator-(const Montgomery_Int &other) const
Definition monty.cpp:312
Montgomery_Int(const Montgomery_Params &params)
Definition monty.cpp:230
Montgomery_Int operator+(const Montgomery_Int &other) const
Definition monty.cpp:291
bool is_zero() const
Definition monty.cpp:501
BigInt value() const
Definition monty.cpp:279
void ct_cond_negate(bool predicate)
Definition monty.cpp:474
Montgomery_Int & square_this_n_times(secure_vector< word > &ws, size_t n)
Definition monty.cpp:363
Montgomery_Int & mul_by_word(word d)
Definition monty.cpp:414
Montgomery_Int mul(const Montgomery_Int &other, secure_vector< word > &ws) const
Definition monty.cpp:326
Montgomery_Int & mul_by(const Montgomery_Int &other, secure_vector< word > &ws)
Definition monty.cpp:344
std::vector< uint8_t > serialize() const
Definition monty.cpp:275
BigInt redc(const BigInt &x, secure_vector< word > &ws) const
Definition monty.cpp:81
BigInt sqr(const BigInt &x, secure_vector< word > &ws) const
Definition monty.cpp:194
void mul(BigInt &z, const BigInt &x, const BigInt &y, secure_vector< word > &ws) const
Definition monty.cpp:103
size_t p_words() const
Definition monty.h:58
bool operator==(const Montgomery_Params &other) const
Definition monty.cpp:73
void mul_by(BigInt &x, const BigInt &y, secure_vector< word > &ws) const
Definition monty.cpp:163
Montgomery_Params(const BigInt &p, const Barrett_Reduction &mod_p)
Definition monty.cpp:67
const BigInt & R3() const
Definition monty.h:47
const BigInt & R1() const
Definition monty.h:43
word p_dash() const
Definition monty.h:49
const BigInt & p() const
Definition monty.h:41
constexpr decltype(auto) driveby_unpoison(T &&v)
Definition ct_utils.h:243
constexpr CT::Mask< T > all_zeros(const T elem[], size_t len)
Definition ct_utils.h:790
constexpr Mask< T > conditional_assign_mem(T cnd, T *dest, const T *src, size_t elems)
Definition ct_utils.h:754
constexpr void bigint_linmul3(W z[], const W x[], size_t x_size, W y)
Definition mp_core.h:420
BOTAN_TEST_API void bigint_monty_mul(word z[], const word x[], const word y[], const word p[], size_t p_size, word p_dash, word ws[], size_t ws_size)
Definition mp_monty.cpp:143
constexpr auto bigint_add3(W z[], const W x[], size_t x_size, const W y[], size_t y_size) -> W
Definition mp_core.h:124
constexpr auto bigint_submul(W z[], const W y[], size_t N, W q) -> W
Definition mp_core.h:443
constexpr auto word_madd2(W a, W b, W *c) -> W
Definition mp_asmi.h:111
void bigint_sqr(word z[], size_t z_size, const word x[], size_t x_size, size_t x_sw, word workspace[], size_t ws_size)
Definition mp_karat.cpp:327
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
void bigint_mul(word z[], size_t z_size, const word x[], size_t x_size, size_t x_sw, const word y[], size_t y_size, size_t y_sw, word workspace[], size_t ws_size)
Definition mp_karat.cpp:283
constexpr void copy_mem(T *out, const T *in, size_t n)
Definition mem_ops.h:144
void bigint_monty_redc_inplace(word z[], const word p[], size_t p_size, word p_dash, word ws[], size_t ws_size)
Definition mp_core.h:1111
constexpr W bigint_cnd_add(W cnd, W x[], const W y[], size_t size)
Definition mp_core.h:49
constexpr void bigint_monty_maybe_sub(size_t N, W z[], W x0, const W x[], const W p[])
Definition mp_core.h:229
BOTAN_TEST_API void bigint_monty_sqr(word z[], const word x[], const word p[], size_t p_size, word p_dash, word ws[], size_t ws_size)
Definition mp_monty.cpp:159
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:128
constexpr auto bigint_sub2(W x[], size_t x_size, const W y[], size_t y_size) -> W
Definition mp_core.h:152
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