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