Botan 3.14.1
Crypto and TLS for C&
mod_inv.cpp
Go to the documentation of this file.
1/*
2* (C) 1999-2011,2016,2018,2019,2020,2025 Jack Lloyd
3*
4* Botan is released under the Simplified BSD License (see license.txt)
5*/
6
7#include <botan/internal/mod_inv.h>
8
9#include <botan/exceptn.h>
10#include <botan/mem_ops.h>
11#include <botan/numthry.h>
12#include <botan/internal/bit_ops.h>
13#include <botan/internal/ct_utils.h>
14#include <botan/internal/divide.h>
15#include <botan/internal/mp_core.h>
16
17namespace Botan {
18
19namespace {
20
21BigInt inverse_mod_odd_modulus(const BigInt& n, const BigInt& mod) {
22 // Caller should assure these preconditions:
23 BOTAN_ASSERT_NOMSG(n.signum() >= 0);
24 BOTAN_ASSERT_NOMSG(mod.signum() > 0);
25 BOTAN_ASSERT_NOMSG(n < mod);
26 BOTAN_ASSERT_NOMSG(mod >= 3 && CT::driveby_unpoison(mod.is_odd()));
27
28 /*
29 This uses a modular inversion algorithm designed by Niels Möller
30 and implemented in Nettle. The same algorithm was later also
31 adapted to GMP in mpn_sec_invert.
32
33 It can be easily implemented in a way that does not depend on
34 secret branches or memory lookups, providing resistance against
35 some forms of side channel attack.
36
37 There is also a description of the algorithm in Appendix 5 of "Fast
38 Software Polynomial Multiplication on ARM Processors using the NEON Engine"
39 by Danilo Câmara, Conrado P. L. Gouvêa, Julio López, and Ricardo
40 Dahab in LNCS 8182
41 https://inria.hal.science/hal-01506572/document
42
43 Thanks to Niels for creating the algorithm, explaining some things
44 about it, and the reference to the paper.
45 */
46
47 const size_t mod_words = mod.sig_words();
48 BOTAN_ASSERT(mod_words > 0, "Not empty");
49
50 secure_vector<word> tmp_mem(5 * mod_words);
51
52 word* v_w = &tmp_mem[0]; // NOLINT(readability-container-data-pointer)
53 word* u_w = &tmp_mem[1 * mod_words];
54 word* b_w = &tmp_mem[2 * mod_words];
55 word* a_w = &tmp_mem[3 * mod_words];
56 word* mp1o2 = &tmp_mem[4 * mod_words];
57
58 copy_mem(a_w, n._data(), std::min(n.size(), mod_words));
59 copy_mem(b_w, mod._data(), std::min(mod.size(), mod_words));
60 u_w[0] = 1;
61 // v_w = 0
62
63 // compute (mod + 1) / 2 which [because mod is odd] is equal to
64 // (mod / 2) + 1
65 copy_mem(mp1o2, mod._data(), std::min(mod.size(), mod_words));
66 bigint_shr1(mp1o2, mod_words, 1);
67 const word carry = bigint_add2(mp1o2, mod_words, u_w, 1);
69
70 // Only n.bits() + mod.bits() iterations are required, but avoid leaking the size of n
71 const size_t execs = 2 * mod.bits();
72
73 for(size_t i = 0; i != execs; ++i) {
74 const word odd_a = a_w[0] & 1;
75
76 //if(odd_a) a -= b
77 const word underflow = bigint_cnd_sub(odd_a, a_w, b_w, mod_words);
78
79 //if(underflow) { b -= a; a = abs(a); swap(u, v); }
80 bigint_cnd_add(underflow, b_w, a_w, mod_words);
81 bigint_cnd_abs(underflow, a_w, mod_words);
82 bigint_cnd_swap(underflow, u_w, v_w, mod_words);
83
84 // a >>= 1
85 bigint_shr1(a_w, mod_words, 1);
86
87 //if(odd_a) u -= v;
88 const word borrow = bigint_cnd_sub(odd_a, u_w, v_w, mod_words);
89
90 // if(borrow) u += p
91 bigint_cnd_add(borrow, u_w, mod._data(), mod_words);
92
93 const word odd_u = u_w[0] & 1;
94
95 // u >>= 1
96 bigint_shr1(u_w, mod_words, 1);
97
98 //if(odd_u) u += mp1o2;
99 bigint_cnd_add(odd_u, u_w, mp1o2, mod_words);
100 }
101
102 const auto a_is_0 = CT::all_zeros(a_w, mod_words);
103
104 auto b_is_1 = CT::Mask<word>::is_equal(b_w[0], 1);
105 for(size_t i = 1; i != mod_words; ++i) {
106 b_is_1 &= CT::Mask<word>::is_zero(b_w[i]);
107 }
108
109 BOTAN_ASSERT(a_is_0.as_bool(), "A is zero");
110
111 // if b != 1 then gcd(n,mod) > 1 and inverse does not exist
112 // in which case zero out the result to indicate this
113 (~b_is_1).if_set_zero_out(v_w, mod_words);
114
115 /*
116 * We've placed the result in the lowest words of the temp buffer.
117 * So just clear out the other values and then give that buffer to a
118 * BigInt.
119 */
120 clear_mem(&tmp_mem[mod_words], 4 * mod_words);
121
122 BigInt r;
123 r.swap_reg(tmp_mem);
124 return r;
125}
126
127BigInt inverse_mod_pow2(const BigInt& a1, size_t k) {
128 /*
129 * From "A New Algorithm for Inversion mod p^k" by Çetin Kaya Koç
130 * https://eprint.iacr.org/2017/411.pdf sections 5 and 7.
131 */
132
133 if(a1.is_even() || k == 0) {
134 return BigInt::zero();
135 }
136 if(k == 1) {
137 return BigInt::one();
138 }
139
140 BigInt a = a1;
141 a.mask_bits(k);
142
143 BigInt b = BigInt::one();
144 BigInt X = BigInt::zero();
145 BigInt newb;
146
147 const size_t a_words = a.sig_words();
148
149 /*
150 Hide the exact value of k. k is anyway known to word length
151 granularity because of the length of a, so no point in doing more
152 than this.
153 */
154 const size_t k_words = ceil_division(k, WordInfo<word>::bits);
155 const size_t iter = k_words * WordInfo<word>::bits;
156
157 X.grow_to(k_words);
158 b.grow_to(a_words);
159
160 for(size_t i = 0; i != iter; ++i) {
161 const bool b0 = b.get_bit(0);
162 X.conditionally_set_bit(i, b0);
163 newb = b - a;
164 b.ct_cond_assign(b0, newb);
165 b >>= 1;
166 }
167
168 X.mask_bits(k);
169
170 return X;
171}
172
173} // namespace
174
175std::optional<BigInt> inverse_mod_general(const BigInt& x, const BigInt& mod) {
176 BOTAN_ARG_CHECK(x > 0, "x must be greater than zero");
177 BOTAN_ARG_CHECK(mod > 0, "mod must be greater than zero");
178 BOTAN_ARG_CHECK(x < mod, "x must be less than m");
179
180 // Easy case where gcd > 1 so no inverse exists
181 if(x.is_even() && mod.is_even()) {
182 return std::nullopt;
183 }
184
185 if(mod.is_odd()) {
186 BigInt z = inverse_mod_odd_modulus(x, mod);
187 if(z.is_zero()) {
188 return std::nullopt;
189 } else {
190 return z;
191 }
192 }
193
194 // If x is even and mod is even we already returned 0
195 // If x is even and mod is odd we jumped directly to odd-modulus algo
197
198 const size_t mod_lz = low_zero_bits(mod);
199 BOTAN_ASSERT_NOMSG(mod_lz > 0);
200 const size_t mod_bits = mod.bits();
201 BOTAN_ASSERT_NOMSG(mod_bits > mod_lz);
202
203 if(mod_lz == mod_bits - 1) {
204 // In this case we are performing an inversion modulo 2^k
205 auto z = inverse_mod_pow2(x, mod_lz);
206 if(z.is_zero()) {
207 return std::nullopt;
208 } else {
209 return z;
210 }
211 }
212
213 if(mod_lz == 1) {
214 /*
215 Inversion modulo 2*o is an easier special case of CRT
216
217 This is exactly the main CRT flow below but taking advantage of
218 the fact that any odd number ^-1 modulo 2 is 1. As a result both
219 inv_2k and c can be taken to be 1, m2k is 2, and h is always
220 either 0 or 1, and its value depends only on the low bit of inv_o.
221
222 This is worth special casing because we generate RSA primes such
223 that phi(n) is of this form. However this only works for keys
224 that we generated in this way; pre-existing keys will typically
225 fall back to the general algorithm below.
226 */
227
228 const BigInt o = mod >> 1;
229 const BigInt inv_o = inverse_mod_odd_modulus(ct_modulo(x, o), o);
230
231 // No modular inverse in this case:
232 if(inv_o == 0) {
233 return std::nullopt;
234 }
235
236 BigInt h = inv_o;
237 h.ct_cond_add(!inv_o.get_bit(0), o);
238 return h;
239 }
240
241 /*
242 * In this case we are performing an inversion modulo 2^k*o for
243 * some k >= 2 and some odd (not necessarily prime) integer.
244 * Compute the inversions modulo 2^k and modulo o, then combine them
245 * using CRT, which is possible because 2^k and o are relatively prime.
246 */
247
248 const BigInt o = mod >> mod_lz;
249 const BigInt inv_o = inverse_mod_odd_modulus(ct_modulo(x, o), o);
250 const BigInt inv_2k = inverse_mod_pow2(x, mod_lz);
251
252 // No modular inverse in this case:
253 if(inv_o == 0 || inv_2k == 0) {
254 return std::nullopt;
255 }
256
257 const BigInt m2k = BigInt::power_of_2(mod_lz);
258 // Compute the CRT parameter
259 const BigInt c = inverse_mod_pow2(o, mod_lz);
260
261 // This should never happen; o is odd so gcd is 1 and inverse mod 2^k exists
262 BOTAN_ASSERT_NOMSG(c.signum() != 0);
263
264 // Compute h = c*(inv_2k-inv_o) mod 2^k
265 BigInt h = c * (inv_2k - inv_o);
266 const bool h_neg = h.signum() < 0;
268 h.mask_bits(mod_lz);
269 const bool h_nonzero = h.signum() != 0;
270 h.ct_cond_assign(h_nonzero && h_neg, m2k - h);
271
272 // Return result inv_o + h * o
273 h *= o;
274 h += inv_o;
275 return h;
276}
277
279 BOTAN_ARG_CHECK(p.signum() > 0, "Modulus must be positive");
280 BOTAN_ARG_CHECK(x.signum() > 0, "Input must be positive");
281 BOTAN_ARG_CHECK(x < p, "Input must be less than modulus");
282 BOTAN_ARG_CHECK(CT::driveby_unpoison(p.is_odd()) && p > 1, "Primes are odd integers greater than 1");
283
284 // TODO possibly use FLT, or the algorithm presented for this case in
285 // Handbook of Elliptic and Hyperelliptic Curve Cryptography
286
287 return inverse_mod_odd_modulus(x, p);
288}
289
291 BOTAN_ARG_CHECK(p.signum() > 0, "Modulus must be positive");
292 BOTAN_ARG_CHECK(x.signum() > 0, "Input must be positive");
293 BOTAN_ARG_CHECK(x < p, "Input must be less than modulus");
294 BOTAN_ARG_CHECK(p.is_odd() && p > 1, "Primes are odd integers greater than 1");
295
296 // TODO possibly use FLT, or the algorithm presented for this case in
297 // Handbook of Elliptic and Hyperelliptic Curve Cryptography
298
299 return inverse_mod_odd_modulus(x, p);
300}
301
303 BOTAN_ARG_CHECK(n.signum() > 0 && n.is_odd(), "RSA public modulus must be odd and positive");
304 BOTAN_ARG_CHECK(x.signum() > 0 && x < n, "Input must be positive and less than RSA modulus");
305 BigInt z = inverse_mod_odd_modulus(x, n);
306 BOTAN_ASSERT(z.signum() != 0, "Accidentally factored the public modulus"); // whoops
307 return z;
308}
309
310namespace {
311
312uint64_t barrett_mod_65537(uint64_t x) {
313 constexpr uint64_t mod = 65537;
314 constexpr size_t s = 32;
315 constexpr uint64_t c = (static_cast<uint64_t>(1) << s) / mod;
316
317 const uint64_t q = (x * c) >> s;
318 const uint64_t r = x - q * mod;
319
320 const auto r_gt_mod = CT::Mask<uint64_t>::is_gte(r, mod);
321 return r - r_gt_mod.if_set_return(mod);
322}
323
324word inverse_mod_65537(word x) {
325 // Need 64-bit here as accum*accum exceeds 32-bit if accum=0x10000
326 uint64_t accum = 1;
327 // Basic square and multiply, with all bits of exponent set
328 for(size_t i = 0; i != 16; ++i) {
329 accum = barrett_mod_65537(accum * accum);
330 accum = barrett_mod_65537(accum * x);
331 }
332 return static_cast<word>(accum);
333}
334
335} // namespace
336
337std::optional<BigInt> compute_rsa_secret_exponent(const BigInt& e,
338 const BigInt& phi_n,
339 const BigInt& p,
340 const BigInt& q) {
341 BOTAN_ARG_CHECK(e > 0 && phi_n > 0, "RSA exponent and lcm(p-1, q-1) must be positive");
342
343 // TODO possibly do something else taking advantage of the special structure here
344 BOTAN_UNUSED(p, q);
345
346 if(e == 65537) {
347 /*
348 Arazi's algorithm for inversion of prime x modulo a non-prime
349
350 "GCD-Free Algorithms for Computing Modular Inverses"
351 Marc Joye and Pascal Paillier, CHES 2003 (LNCS 2779)
352 https://marcjoye.github.io/papers/JP03gcdfree.pdf
353
354 This could be extended to cover other cases such as e=3 or e=17 but
355 these days 65537 is the standard RSA public exponent
356 */
357
358 constexpr word e_w = 65537;
359
360 const word phi_mod_e = ct_mod_word(phi_n, e_w);
361
362 // If e divides phi_n there is no inverse, which the general path below reports
363 if(CT::driveby_unpoison(phi_mod_e != 0)) {
364 const word inv_phi_mod_e = inverse_mod_65537(phi_mod_e);
365 BOTAN_DEBUG_ASSERT((inv_phi_mod_e * phi_mod_e) % e_w == 1);
366 const word neg_inv_phi_mod_e = (e_w - inv_phi_mod_e);
367 return ct_divide_word((phi_n * neg_inv_phi_mod_e) + 1, e_w);
368 }
369 }
370
371 // inverse_mod_general requires its argument to be reduced
372 const BigInt e_mod_phi = ct_modulo(e, phi_n);
373
374 if(e_mod_phi.is_zero()) {
375 return std::nullopt;
376 }
377
378 CT::unpoison_all(e_mod_phi, phi_n);
379 return inverse_mod_general(e_mod_phi, phi_n);
380}
381
382BigInt inverse_mod(const BigInt& n, const BigInt& mod) {
383 BOTAN_ARG_CHECK(mod.signum() > 0, "Modulus must be positive");
384 BOTAN_ARG_CHECK(n.signum() >= 0, "Value cannot be negative");
385
386 if(n.is_zero() || (n.is_even() && mod.is_even())) {
387 return BigInt::zero();
388 }
389
390 if(n >= mod) {
391 return inverse_mod(ct_modulo(n, mod), mod);
392 }
393
394 return inverse_mod_general(n, mod).value_or(BigInt::zero());
395}
396
397} // namespace Botan
#define BOTAN_UNUSED
Definition assert.h:151
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:82
#define BOTAN_DEBUG_ASSERT(expr)
Definition assert.h:136
#define BOTAN_ARG_CHECK(expr, msg)
Definition assert.h:33
#define BOTAN_ASSERT(expr, assertion_made)
Definition assert.h:69
void ct_cond_add(bool predicate, const BigInt &value)
Definition bigint.cpp:452
static BigInt zero()
Definition bigint.h:50
size_t sig_words() const
Definition bigint.h:687
bool is_odd() const
Definition bigint.h:487
void ct_cond_assign(bool predicate, const BigInt &other)
Definition bigint.cpp:536
int signum() const
Definition bigint.h:493
static BigInt one()
Definition bigint.h:55
void mask_bits(size_t n)
Definition bigint.h:542
size_t bits() const
Definition bigint.cpp:308
bool is_even() const
Definition bigint.h:481
static BigInt power_of_2(size_t n)
Definition bigint.h:906
bool is_zero() const
Definition bigint.h:510
bool get_bit(size_t n) const
Definition bigint.h:549
void swap_reg(secure_vector< word > &reg)
Definition bigint.h:218
void set_sign(Sign sign)
Definition bigint.h:663
static constexpr Mask< T > is_gte(T x, T y)
Definition ct_utils.h:473
static constexpr Mask< T > is_equal(T x, T y)
Definition ct_utils.h:447
static constexpr Mask< T > is_zero(T x)
Definition ct_utils.h:442
constexpr decltype(auto) driveby_unpoison(T &&v)
Definition ct_utils.h:243
constexpr void unpoison_all(const Ts &... ts)
Definition ct_utils.h:207
constexpr CT::Mask< T > all_zeros(const T elem[], size_t len)
Definition ct_utils.h:790
constexpr void bigint_cnd_abs(W cnd, W x[], size_t size)
Definition mp_core.h:84
BigInt inverse_mod_secret_prime(const BigInt &x, const BigInt &p)
Definition mod_inv.cpp:278
constexpr auto bigint_add2(W x[], size_t x_size, const W y[], size_t y_size) -> W
Definition mp_core.h:98
constexpr auto bigint_cnd_sub(W cnd, W x[], const W y[], size_t size) -> W
Definition mp_core.h:66
constexpr void bigint_cnd_swap(W cnd, W x[], W y[], size_t size)
Definition mp_core.h:33
word ct_mod_word(const BigInt &x, word y)
Definition divide.cpp:247
std::optional< BigInt > compute_rsa_secret_exponent(const BigInt &e, const BigInt &phi_n, const BigInt &p, const BigInt &q)
Definition mod_inv.cpp:337
BOTAN_FORCE_INLINE constexpr T ceil_division(T a, T b)
Definition bit_ops.h:167
constexpr void bigint_shr1(W x[], size_t x_size, size_t shift)
Definition mp_core.h:335
size_t low_zero_bits(const BigInt &n)
Definition numthry.cpp:194
constexpr void copy_mem(T *out, const T *in, size_t n)
Definition mem_ops.h:144
BigInt inverse_mod_public_prime(const BigInt &x, const BigInt &p)
Definition mod_inv.cpp:290
BigInt ct_modulo(const BigInt &x, const BigInt &y)
Definition divide.cpp:262
constexpr W bigint_cnd_add(W cnd, W x[], const W y[], size_t size)
Definition mp_core.h:49
void ct_divide_word(const BigInt &x, word y, BigInt &q_out, word &r_out)
Definition divide.cpp:205
std::optional< BigInt > inverse_mod_general(const BigInt &x, const BigInt &mod)
Definition mod_inv.cpp:175
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:128
BigInt inverse_mod_rsa_public_modulus(const BigInt &x, const BigInt &n)
Definition mod_inv.cpp:302
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
BigInt inverse_mod(const BigInt &n, const BigInt &mod)
Definition mod_inv.cpp:382
constexpr void clear_mem(T *ptr, size_t n)
Definition mem_ops.h:118