Botan 3.7.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/numthry.h>
10#include <botan/internal/ct_utils.h>
11#include <botan/internal/divide.h>
12#include <botan/internal/mp_core.h>
13#include <botan/internal/rounding.h>
14
15namespace Botan {
16
17namespace {
18
19BigInt inverse_mod_odd_modulus(const BigInt& n, const BigInt& mod) {
20 // Caller should assure these preconditions:
21 BOTAN_ASSERT_NOMSG(n.is_positive());
22 BOTAN_ASSERT_NOMSG(mod.is_positive());
23 BOTAN_ASSERT_NOMSG(n < mod);
24 BOTAN_ASSERT_NOMSG(mod >= 3 && mod.is_odd());
25
26 /*
27 This uses a modular inversion algorithm designed by Niels Möller
28 and implemented in Nettle. The same algorithm was later also
29 adapted to GMP in mpn_sec_invert.
30
31 It can be easily implemented in a way that does not depend on
32 secret branches or memory lookups, providing resistance against
33 some forms of side channel attack.
34
35 There is also a description of the algorithm in Appendix 5 of "Fast
36 Software Polynomial Multiplication on ARM Processors using the NEON Engine"
37 by Danilo Câmara, Conrado P. L. Gouvêa, Julio López, and Ricardo
38 Dahab in LNCS 8182
39 https://inria.hal.science/hal-01506572/document
40
41 Thanks to Niels for creating the algorithm, explaining some things
42 about it, and the reference to the paper.
43 */
44
45 const size_t mod_words = mod.sig_words();
46 BOTAN_ASSERT(mod_words > 0, "Not empty");
47
48 secure_vector<word> tmp_mem(5 * mod_words);
49
50 word* v_w = &tmp_mem[0];
51 word* u_w = &tmp_mem[1 * mod_words];
52 word* b_w = &tmp_mem[2 * mod_words];
53 word* a_w = &tmp_mem[3 * mod_words];
54 word* mp1o2 = &tmp_mem[4 * mod_words];
55
56 CT::poison(tmp_mem.data(), tmp_mem.size());
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 word carry = bigint_add2_nc(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 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 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 CT::unpoison(tmp_mem.data(), tmp_mem.size());
123
124 BigInt r;
125 r.swap_reg(tmp_mem);
126 return r;
127}
128
129BigInt inverse_mod_pow2(const BigInt& a1, size_t k) {
130 /*
131 * From "A New Algorithm for Inversion mod p^k" by Çetin Kaya Koç
132 * https://eprint.iacr.org/2017/411.pdf sections 5 and 7.
133 */
134
135 if(a1.is_even() || k == 0) {
136 return BigInt::zero();
137 }
138 if(k == 1) {
139 return BigInt::one();
140 }
141
142 BigInt a = a1;
143 a.mask_bits(k);
144
145 BigInt b = BigInt::one();
146 BigInt X = BigInt::zero();
147 BigInt newb;
148
149 const size_t a_words = a.sig_words();
150
152 b.grow_to(a_words);
153
154 /*
155 Hide the exact value of k. k is anyway known to word length
156 granularity because of the length of a, so no point in doing more
157 than this.
158 */
159 const size_t iter = round_up(k, BOTAN_MP_WORD_BITS);
160
161 for(size_t i = 0; i != iter; ++i) {
162 const bool b0 = b.get_bit(0);
163 X.conditionally_set_bit(i, b0);
164 newb = b - a;
165 b.ct_cond_assign(b0, newb);
166 b >>= 1;
167 }
168
169 X.mask_bits(k);
170
172 return X;
173}
174
175} // namespace
176
177std::optional<BigInt> inverse_mod_general(const BigInt& x, const BigInt& mod) {
178 BOTAN_ARG_CHECK(x > 0, "x must be greater than zero");
179 BOTAN_ARG_CHECK(mod > 0, "mod must be greater than zero");
180 BOTAN_ARG_CHECK(x < mod, "x must be less than m");
181
182 // Easy case where gcd > 1 so no inverse exists
183 if(x.is_even() && mod.is_even()) {
184 return std::nullopt;
185 }
186
187 if(mod.is_odd()) {
188 BigInt z = inverse_mod_odd_modulus(x, mod);
189 if(z.is_zero()) {
190 return std::nullopt;
191 } else {
192 return z;
193 }
194 }
195
196 // If x is even and mod is even we already returned 0
197 // If x is even and mod is odd we jumped directly to odd-modulus algo
199
200 const size_t mod_lz = low_zero_bits(mod);
201 BOTAN_ASSERT_NOMSG(mod_lz > 0);
202 const size_t mod_bits = mod.bits();
203 BOTAN_ASSERT_NOMSG(mod_bits > mod_lz);
204
205 if(mod_lz == mod_bits - 1) {
206 // In this case we are performing an inversion modulo 2^k
207 auto z = inverse_mod_pow2(x, mod_lz);
208 if(z.is_zero()) {
209 return std::nullopt;
210 } else {
211 return z;
212 }
213 }
214
215 if(mod_lz == 1) {
216 /*
217 Inversion modulo 2*o is an easier special case of CRT
218
219 This is exactly the main CRT flow below but taking advantage of
220 the fact that any odd number ^-1 modulo 2 is 1. As a result both
221 inv_2k and c can be taken to be 1, m2k is 2, and h is always
222 either 0 or 1, and its value depends only on the low bit of inv_o.
223
224 This is worth special casing because we generate RSA primes such
225 that phi(n) is of this form. However this only works for keys
226 that we generated in this way; pre-existing keys will typically
227 fall back to the general algorithm below.
228 */
229
230 const BigInt o = mod >> 1;
231 const BigInt inv_o = inverse_mod_odd_modulus(ct_modulo(x, o), o);
232
233 // No modular inverse in this case:
234 if(inv_o == 0) {
235 return std::nullopt;
236 }
237
238 BigInt h = inv_o;
239 h.ct_cond_add(!inv_o.get_bit(0), o);
240 return h;
241 }
242
243 /*
244 * In this case we are performing an inversion modulo 2^k*o for
245 * some k >= 2 and some odd (not necessarily prime) integer.
246 * Compute the inversions modulo 2^k and modulo o, then combine them
247 * using CRT, which is possible because 2^k and o are relatively prime.
248 */
249
250 const BigInt o = mod >> mod_lz;
251 const BigInt inv_o = inverse_mod_odd_modulus(ct_modulo(x, o), o);
252 const BigInt inv_2k = inverse_mod_pow2(x, mod_lz);
253
254 // No modular inverse in this case:
255 if(inv_o == 0 || inv_2k == 0) {
256 return std::nullopt;
257 }
258
259 const BigInt m2k = BigInt::power_of_2(mod_lz);
260 // Compute the CRT parameter
261 const BigInt c = inverse_mod_pow2(o, mod_lz);
262
263 // This should never happen; o is odd so gcd is 1 and inverse mod 2^k exists
265
266 // Compute h = c*(inv_2k-inv_o) mod 2^k
267 BigInt h = c * (inv_2k - inv_o);
268 const bool h_neg = h.is_negative();
270 h.mask_bits(mod_lz);
271 const bool h_nonzero = h.is_nonzero();
272 h.ct_cond_assign(h_nonzero && h_neg, m2k - h);
273
274 // Return result inv_o + h * o
275 h *= o;
276 h += inv_o;
277 return h;
278}
279
281 BOTAN_ARG_CHECK(x.is_positive() && p.is_positive(), "Parameters must be positive");
282 BOTAN_ARG_CHECK(x < p, "x must be less than p");
283 BOTAN_ARG_CHECK(p.is_odd() and p > 1, "Primes are odd integers greater than 1");
284
285 // TODO possibly use FLT, or the algorithm presented for this case in
286 // Handbook of Elliptic and Hyperelliptic Curve Cryptography
287
288 return inverse_mod_odd_modulus(x, p);
289}
290
292 return inverse_mod_secret_prime(x, p);
293}
294
296 BOTAN_ARG_CHECK(n.is_positive() && n.is_odd(), "RSA public modulus must be odd and positive");
297 BOTAN_ARG_CHECK(x.is_positive() && x < n, "Input must be positive and less than RSA modulus");
298 BigInt z = inverse_mod_odd_modulus(x, n);
299 BOTAN_ASSERT(!z.is_zero(), "Accidentally factored the public modulus"); // whoops
300 return z;
301}
302
303namespace {
304
305uint64_t barrett_mod_65537(uint64_t x) {
306 constexpr uint64_t mod = 65537;
307 constexpr size_t s = 32;
308 constexpr uint64_t c = (static_cast<uint64_t>(1) << s) / mod;
309
310 uint64_t q = (x * c) >> s;
311 uint64_t r = x - q * mod;
312
313 auto r_gt_mod = CT::Mask<uint64_t>::is_gte(r, mod);
314 return r - r_gt_mod.if_set_return(mod);
315}
316
317word inverse_mod_65537(word x) {
318 // Need 64-bit here as accum*accum exceeds 32-bit if accum=0x10000
319 uint64_t accum = 1;
320 // Basic square and multiply, with all bits of exponent set
321 for(size_t i = 0; i != 16; ++i) {
322 accum = barrett_mod_65537(accum * accum);
323 accum = barrett_mod_65537(accum * x);
324 }
325 return static_cast<word>(accum);
326}
327
328} // namespace
329
330BigInt compute_rsa_secret_exponent(const BigInt& e, const BigInt& phi_n, const BigInt& p, const BigInt& q) {
331 /*
332 * Both p - 1 and q - 1 are chosen to be relatively prime to e. Thus
333 * phi(n), the least common multiple of p - 1 and q - 1, is also
334 * relatively prime to e.
335 */
336 BOTAN_DEBUG_ASSERT(gcd(e, phi_n) == 1);
337
338 if(e == 65537) {
339 /*
340 Arazi's algorithm for inversion of prime x modulo a non-prime
341
342 "GCD-Free Algorithms for Computing Modular Inverses"
343 Marc Joye and Pascal Paillier, CHES 2003 (LNCS 2779)
344 https://marcjoye.github.io/papers/JP03gcdfree.pdf
345
346 This could be extended to cover other cases such as e=3 or e=17 but
347 these days 65537 is the standard RSA public exponent
348 */
349
350 constexpr word e_w = 65537;
351
352 const word phi_mod_e = ct_mod_word(phi_n, e_w);
353 const word inv_phi_mod_e = inverse_mod_65537(phi_mod_e);
354 BOTAN_DEBUG_ASSERT((inv_phi_mod_e * phi_mod_e) % e_w == 1);
355 const word neg_inv_phi_mod_e = (e_w - inv_phi_mod_e);
356 return ct_divide_word((phi_n * neg_inv_phi_mod_e) + 1, e_w);
357 } else {
358 // TODO possibly do something else taking advantage of the special structure here
359
360 BOTAN_UNUSED(p, q);
361 if(auto d = inverse_mod_general(e, phi_n)) {
362 return *d;
363 } else {
364 throw Internal_Error("Failed to compute RSA secret exponent");
365 }
366 }
367}
368
369BigInt inverse_mod(const BigInt& n, const BigInt& mod) {
370 BOTAN_ARG_CHECK(!mod.is_zero(), "modulus cannot be zero");
371 BOTAN_ARG_CHECK(!mod.is_negative(), "modulus cannot be negative");
372 BOTAN_ARG_CHECK(!n.is_negative(), "value cannot be negative");
373
374 if(n.is_zero() || (n.is_even() && mod.is_even())) {
375 return BigInt::zero();
376 }
377
378 if(n >= mod) {
379 return inverse_mod(ct_modulo(n, mod), mod);
380 }
381
382 return inverse_mod_general(n, mod).value_or(BigInt::zero());
383}
384
385} // namespace Botan
#define BOTAN_UNUSED
Definition assert.h:118
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:59
#define BOTAN_DEBUG_ASSERT(expr)
Definition assert.h:98
#define BOTAN_ARG_CHECK(expr, msg)
Definition assert.h:29
#define BOTAN_ASSERT(expr, assertion_made)
Definition assert.h:50
void ct_cond_add(bool predicate, const BigInt &value)
Definition bigint.cpp:437
static BigInt zero()
Definition bigint.h:50
bool is_odd() const
Definition bigint.h:446
void ct_cond_assign(bool predicate, const BigInt &other)
Definition bigint.cpp:500
static BigInt one()
Definition bigint.h:55
void mask_bits(size_t n)
Definition bigint.h:490
size_t bits() const
Definition bigint.cpp:295
bool is_even() const
Definition bigint.h:440
static BigInt power_of_2(size_t n)
Definition bigint.h:830
bool is_zero() const
Definition bigint.h:458
bool is_negative() const
Definition bigint.h:560
bool is_nonzero() const
Definition bigint.h:452
bool is_positive() const
Definition bigint.h:566
bool get_bit(size_t n) const
Definition bigint.h:497
void set_sign(Sign sign)
Definition bigint.h:593
static constexpr Mask< T > is_gte(T x, T y)
Definition ct_utils.h:479
static constexpr Mask< T > is_equal(T x, T y)
Definition ct_utils.h:453
static constexpr Mask< T > is_zero(T x)
Definition ct_utils.h:448
FE_25519 X
Definition ge.cpp:25
#define BOTAN_MP_WORD_BITS
Definition build.h:71
constexpr void unpoison(const T *p, size_t n)
Definition ct_utils.h:64
constexpr CT::Mask< T > all_zeros(const T elem[], size_t len)
Definition ct_utils.h:775
constexpr void poison(const T *p, size_t n)
Definition ct_utils.h:53
constexpr void bigint_cnd_abs(W cnd, W x[], size_t size)
Definition mp_core.h:173
BigInt inverse_mod_secret_prime(const BigInt &x, const BigInt &p)
Definition mod_inv.cpp:280
constexpr void bigint_cnd_swap(W cnd, W x[], W y[], size_t size)
Definition mp_core.h:31
word ct_mod_word(const BigInt &x, word y)
Definition divide.cpp:157
constexpr void bigint_shr1(W x[], size_t x_size, size_t shift)
Definition mp_core.h:467
size_t low_zero_bits(const BigInt &n)
Definition numthry.cpp:167
constexpr size_t round_up(size_t n, size_t align_to)
Definition rounding.h:25
BigInt inverse_mod_public_prime(const BigInt &x, const BigInt &p)
Definition mod_inv.cpp:291
BigInt ct_modulo(const BigInt &x, const BigInt &y)
Definition divide.cpp:181
BigInt compute_rsa_secret_exponent(const BigInt &e, const BigInt &phi_n, const BigInt &p, const BigInt &q)
Definition mod_inv.cpp:330
constexpr auto bigint_cnd_sub(W cnd, W x[], size_t x_size, const W y[], size_t y_size) -> W
Definition mp_core.h:75
void ct_divide_word(const BigInt &x, word y, BigInt &q_out, word &r_out)
Definition divide.cpp:120
constexpr W bigint_cnd_add(W cnd, W x[], size_t x_size, const W y[], size_t y_size)
Definition mp_core.h:43
void carry(int64_t &h0, int64_t &h1)
std::optional< BigInt > inverse_mod_general(const BigInt &x, const BigInt &mod)
Definition mod_inv.cpp:177
BigInt gcd(const BigInt &a, const BigInt &b)
Definition numthry.cpp:193
const SIMD_8x32 & b
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:61
BigInt inverse_mod_rsa_public_modulus(const BigInt &x, const BigInt &n)
Definition mod_inv.cpp:295
constexpr auto bigint_add2_nc(W x[], size_t x_size, const W y[], size_t y_size) -> W
Definition mp_core.h:187
constexpr void copy_mem(T *out, const T *in, size_t n)
Definition mem_ops.h:147
BigInt inverse_mod(const BigInt &n, const BigInt &mod)
Definition mod_inv.cpp:369
constexpr void clear_mem(T *ptr, size_t n)
Definition mem_ops.h:121