Botan 3.14.1
Crypto and TLS for C&
barrett.cpp
Go to the documentation of this file.
1/*
2* (C) 2025 Jack Lloyd
3*
4* Botan is released under the Simplified BSD License (see license.txt)
5*/
6
7#include <botan/internal/barrett.h>
8
9#include <botan/mem_ops.h>
10#include <botan/internal/ct_utils.h>
11#include <botan/internal/divide.h>
12#include <botan/internal/mp_core.h>
13
14namespace Botan {
15
16Barrett_Reduction::Barrett_Reduction(const BigInt& m, BigInt mu, size_t mw) :
17 m_modulus(m), m_mu(std::move(mu)), m_mod_words(mw), m_modulus_bits(m.bits()) {
18 // Give some extra space for Karatsuba
19 m_modulus.grow_to(m_mod_words + 8);
20 m_mu.grow_to(m_mod_words + 8);
21}
22
23Barrett_Reduction Barrett_Reduction::for_secret_modulus(const BigInt& mod) {
24 BOTAN_ARG_CHECK(mod.signum() > 0, "Modulus must be positive");
25
26 const size_t mod_words = mod.sig_words();
27
28 // Compute mu = floor(2^{2k} / m)
29 const size_t mu_bits = 2 * WordInfo<word>::bits * mod_words;
30 return Barrett_Reduction(mod, ct_divide_pow2k(mu_bits, mod), mod_words);
31}
32
36
37namespace {
38
39/*
40* Barrett Reduction
41*
42* This function assumes that the significant size of x_words (ie the number of
43* words with a value other than zero) is at most 2 * mod_words. In any case, any
44* larger value cannot be reduced using Barrett reduction; callers should have
45* already checked for this.
46*/
47BigInt barrett_reduce(
48 size_t mod_words, const BigInt& modulus, const BigInt& mu, std::span<const word> x_words, secure_vector<word>& ws) {
49 BOTAN_ASSERT_NOMSG(modulus.sig_words() == mod_words);
50
51 // Caller must expand input to be at least this size
52 BOTAN_ASSERT_NOMSG(x_words.size() >= 2 * mod_words);
53
54 // Normally mod_words + 1 but can be + 2 if the modulus is a power of 2
55 const size_t mu_words = mu.sig_words();
56 BOTAN_ASSERT_NOMSG(mu_words <= mod_words + 2);
57
58 if(ws.size() < 2 * (mod_words + 2)) {
59 ws.resize(2 * (mod_words + 2));
60 }
61
62 /*
63 * Following the notation of Handbook of Applied Cryptography
64 * Algorithm 14.42 "Barrett modular reduction", page 604
65 * <https://cacr.uwaterloo.ca/hac/about/chap14.pdf>
66 *
67 * Using `mu` for µ in the code
68 */
69
70 // Compute q1 = floor(x / 2^(k - 1)) which is equivalent to ignoring the low (k-1) words
71
72 // 2 * mod_words + 1 is sufficient, extra is to enable Karatsuba
73 secure_vector<word> r(2 * mu_words + 2);
74
75 copy_mem(r.data(), x_words.data() + (mod_words - 1), mod_words + 1);
76
77 // Now compute q2 = q1 * µ
78
79 // We allocate more size than required since this allows Karatsuba more often;
80 // just `mu_words + (mod_words + 1)` is sufficient
81 const size_t q2_size = 2 * mu_words + 2;
82
83 secure_vector<word> q2(q2_size);
84
85 bigint_mul(
86 q2.data(), q2.size(), r.data(), r.size(), mod_words + 1, mu._data(), mu.size(), mu_words, ws.data(), ws.size());
87
88 // Compute r2 = (floor(q2 / b^(k+1)) * m) mod 2^(k+1)
89 // The division/floor is again effected by just ignoring the low k + 1 words
90 bigint_mul(r.data(),
91 r.size(),
92 &q2[mod_words + 1], // ignoring the low mod_words + 1 words of the first product
93 q2.size() - (mod_words + 1),
94 mod_words + 1,
95 modulus._data(),
96 modulus.size(),
97 mod_words,
98 ws.data(),
99 ws.size());
100
101 // Clear the high words of the product, equivalent to computing mod 2^(k+1)
102 // TODO add masked mul to avoid computing high bits at all
103 clear_mem(std::span{r}.subspan(mod_words + 1));
104
105 // Compute r = r1 - r2
106
107 // The return value of bigint_sub_abs isn't quite right for what we need here so first compare
108 const int32_t relative_size = bigint_cmp(r.data(), mod_words + 1, x_words.data(), mod_words + 1);
109
110 bigint_sub_abs(r.data(), r.data(), x_words.data(), mod_words + 1, ws.data());
111
112 /*
113 If r is negative then we have to set r to r + 2^(k+1)
114
115 However for r negative computing this sum is equivalent to computing 2^(k+1) - abs(r)
116 */
117 clear_mem(ws.data(), mod_words + 2);
118 ws[mod_words + 1] = 1;
119 bigint_sub2(ws.data(), mod_words + 2, r.data(), mod_words + 2);
120
121 // If relative_size > 0 then assign r to 2^(k+1) - r
122 CT::Mask<word>::is_equal(static_cast<word>(relative_size), 1).select_n(r.data(), ws.data(), r.data(), mod_words + 2);
123
124 /*
125 * Per HAC Note 14.44 (ii) "step 4 is repeated at most twice since 0 <= r < 3m"
126 */
127 const size_t bound = 2;
128
129 BOTAN_ASSERT_NOMSG(r.size() >= mod_words + 1);
130 for(size_t i = 0; i != bound; ++i) {
131 const word borrow = bigint_sub3(ws.data(), r.data(), mod_words + 1, modulus._data(), mod_words);
132 CT::Mask<word>::is_zero(borrow).select_n(r.data(), ws.data(), r.data(), mod_words + 1);
133 }
134
135 return BigInt::_from_words(r);
136}
137
138CT::Choice acceptable_barrett_input(const BigInt& x, const BigInt& modulus) {
139 const auto x_is_positive = CT::Choice::from_int(static_cast<uint32_t>(x.signum() >= 0));
140 const auto x_lt_mod = bigint_ct_is_lt(x._data(), x.size(), modulus._data(), modulus.sig_words()).as_choice();
141 return x_is_positive && x_lt_mod;
142}
143
144} // namespace
145
147 BOTAN_ARG_CHECK(acceptable_barrett_input(x, m_modulus).as_bool(), "Invalid x param for Barrett multiply");
148 BOTAN_ARG_CHECK(acceptable_barrett_input(y, m_modulus).as_bool(), "Invalid y param for Barrett multiply");
149
150 secure_vector<word> ws(2 * (m_mod_words + 2));
151 secure_vector<word> xy(2 * m_mod_words);
152
153 bigint_mul(xy.data(),
154 xy.size(),
155 x._data(),
156 x.size(),
157 std::min(x.size(), m_mod_words),
158 y._data(),
159 y.size(),
160 std::min(y.size(), m_mod_words),
161 ws.data(),
162 ws.size());
163
164 return barrett_reduce(m_mod_words, m_modulus, m_mu, xy, ws);
165}
166
168 BOTAN_ARG_CHECK(acceptable_barrett_input(x, m_modulus).as_bool(), "Invalid x param for Barrett square");
169
170 secure_vector<word> ws(2 * (m_mod_words + 2));
171 secure_vector<word> x2(2 * m_mod_words);
172
173 bigint_sqr(x2.data(), x2.size(), x._data(), x.size(), std::min(x.size(), m_mod_words), ws.data(), ws.size());
174
175 return barrett_reduce(m_mod_words, m_modulus, m_mu, x2, ws);
176}
177
179 BOTAN_ARG_CHECK(x.signum() >= 0, "Argument must be non-negative");
180
181 const size_t x_sw = x.sig_words();
182 BOTAN_ARG_CHECK(x_sw <= 2 * m_mod_words, "Argument is too large for Barrett reduction");
183
184 x.grow_to(2 * m_mod_words);
185
187 return barrett_reduce(m_mod_words, m_modulus, m_mu, x._as_span(), ws);
188}
189
190} // namespace Botan
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:82
#define BOTAN_ARG_CHECK(expr, msg)
Definition assert.h:33
static Barrett_Reduction for_public_modulus(const BigInt &m)
Definition barrett.cpp:33
static Barrett_Reduction for_secret_modulus(const BigInt &m)
Definition barrett.cpp:23
BigInt reduce(const BigInt &x) const
Definition barrett.cpp:178
BigInt multiply(const BigInt &x, const BigInt &y) const
Definition barrett.cpp:146
BigInt square(const BigInt &x) const
Definition barrett.cpp:167
size_t sig_words() const
Definition bigint.h:687
size_t size() const
Definition bigint.h:681
void grow_to(size_t n) const
Definition bigint.h:738
int signum() const
Definition bigint.h:493
const word * _data() const
Definition bigint.h:1033
std::span< const word > _as_span() const
Definition bigint.h:1023
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
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 int32_t bigint_cmp(const W x[], size_t x_size, const W y[], size_t y_size)
Definition mp_core.h:463
BigInt ct_divide_pow2k(size_t k, const BigInt &y)
Definition divide.cpp:194
constexpr auto bigint_sub_abs(W z[], const W x[], const W y[], size_t N, W ws[]) -> CT::Mask< W >
Definition mp_core.h:283
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
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
constexpr void clear_mem(T *ptr, size_t n)
Definition mem_ops.h:118