Botan 3.0.0-alpha0
Crypto and TLS for C&
mod_inv.cpp
Go to the documentation of this file.
1/*
2* (C) 1999-2011,2016,2018,2019,2020 Jack Lloyd
3*
4* Botan is released under the Simplified BSD License (see license.txt)
5*/
6
7#include <botan/numthry.h>
8#include <botan/internal/divide.h>
9#include <botan/internal/ct_utils.h>
10#include <botan/internal/mp_core.h>
11#include <botan/internal/rounding.h>
12
13namespace Botan {
14
15namespace {
16
17BigInt inverse_mod_odd_modulus(const BigInt& n, const BigInt& mod)
18 {
19 // Caller should assure these preconditions:
20 BOTAN_DEBUG_ASSERT(n.is_positive());
21 BOTAN_DEBUG_ASSERT(mod.is_positive());
22 BOTAN_DEBUG_ASSERT(n < mod);
23 BOTAN_DEBUG_ASSERT(mod >= 3 && mod.is_odd());
24
25 /*
26 This uses a modular inversion algorithm designed by Niels Möller
27 and implemented in Nettle. The same algorithm was later also
28 adapted to GMP in mpn_sec_invert.
29
30 It can be easily implemented in a way that does not depend on
31 secret branches or memory lookups, providing resistance against
32 some forms of side channel attack.
33
34 There is also a description of the algorithm in Appendix 5 of "Fast
35 Software Polynomial Multiplication on ARM Processors using the NEON Engine"
36 by Danilo Câmara, Conrado P. L. Gouvêa, Julio López, and Ricardo
37 Dahab in LNCS 8182
38 https://conradoplg.cryptoland.net/files/2010/12/mocrysen13.pdf
39
40 Thanks to Niels for creating the algorithm, explaining some things
41 about it, and the reference to the paper.
42 */
43
44 const size_t mod_words = mod.sig_words();
45 BOTAN_ASSERT(mod_words > 0, "Not empty");
46
47 secure_vector<word> tmp_mem(5*mod_words);
48
49 word* v_w = &tmp_mem[0];
50 word* u_w = &tmp_mem[1*mod_words];
51 word* b_w = &tmp_mem[2*mod_words];
52 word* a_w = &tmp_mem[3*mod_words];
53 word* mp1o2 = &tmp_mem[4*mod_words];
54
55 CT::poison(tmp_mem.data(), tmp_mem.size());
56
57 copy_mem(a_w, n.data(), std::min(n.size(), mod_words));
58 copy_mem(b_w, mod.data(), std::min(mod.size(), mod_words));
59 u_w[0] = 1;
60 // v_w = 0
61
62 // compute (mod + 1) / 2 which [because mod is odd] is equal to
63 // (mod / 2) + 1
64 copy_mem(mp1o2, mod.data(), std::min(mod.size(), mod_words));
65 bigint_shr1(mp1o2, mod_words, 0, 1);
66 word carry = bigint_add2_nc(mp1o2, mod_words, u_w, 1);
68
69 // Only n.bits() + mod.bits() iterations are required, but avoid leaking the size of n
70 const size_t execs = 2 * mod.bits();
71
72 for(size_t i = 0; i != execs; ++i)
73 {
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, 0, 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, 0, 1);
97
98 //if(odd_u) u += mp1o2;
99 bigint_cnd_add(odd_u, u_w, mp1o2, mod_words);
100 }
101
102 auto a_is_0 = CT::Mask<word>::set();
103 for(size_t i = 0; i != mod_words; ++i)
104 a_is_0 &= CT::Mask<word>::is_zero(a_w[i]);
105
106 auto b_is_1 = CT::Mask<word>::is_equal(b_w[0], 1);
107 for(size_t i = 1; i != mod_words; ++i)
108 b_is_1 &= CT::Mask<word>::is_zero(b_w[i]);
109
110 BOTAN_ASSERT(a_is_0.is_set(), "A is zero");
111
112 // if b != 1 then gcd(n,mod) > 1 and inverse does not exist
113 // in which case zero out the result to indicate this
114 (~b_is_1).if_set_zero_out(v_w, mod_words);
115
116 /*
117 * We've placed the result in the lowest words of the temp buffer.
118 * So just clear out the other values and then give that buffer to a
119 * BigInt.
120 */
121 clear_mem(&tmp_mem[mod_words], 4*mod_words);
122
123 CT::unpoison(tmp_mem.data(), tmp_mem.size());
124
125 BigInt r;
126 r.swap_reg(tmp_mem);
127 return r;
128 }
129
130BigInt inverse_mod_pow2(const BigInt& a1, size_t k)
131 {
132 /*
133 * From "A New Algorithm for Inversion mod p^k" by Çetin Kaya Koç
134 * https://eprint.iacr.org/2017/411.pdf sections 5 and 7.
135 */
136
137 if(a1.is_even() || k == 0)
138 return BigInt::zero();
139 if(k == 1)
140 return BigInt::one();
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 {
163 const bool b0 = b.get_bit(0);
164 X.conditionally_set_bit(i, b0);
165 newb = b - a;
166 b.ct_cond_assign(b0, newb);
167 b >>= 1;
168 }
169
170 X.mask_bits(k);
171 X.const_time_unpoison();
172 return X;
173 }
174
175}
176
177BigInt inverse_mod(const BigInt& n, const BigInt& mod)
178 {
179 if(mod.is_zero())
180 throw Invalid_Argument("inverse_mod modulus cannot be zero");
181 if(mod.is_negative() || n.is_negative())
182 throw Invalid_Argument("inverse_mod: arguments must be non-negative");
183 if(n.is_zero() || (n.is_even() && mod.is_even()))
184 return BigInt::zero();
185
186 if(mod.is_odd())
187 {
188 /*
189 Fastpath for common case. This leaks if n is greater than mod or
190 not, but we don't guarantee const time behavior in that case.
191 */
192 if(n < mod)
193 return inverse_mod_odd_modulus(n, mod);
194 else
195 return inverse_mod_odd_modulus(ct_modulo(n, mod), mod);
196 }
197
198 // If n is even and mod is even we already returned 0
199 // If n is even and mod is odd we jumped directly to odd-modulus algo
201
202 const size_t mod_lz = low_zero_bits(mod);
203 BOTAN_ASSERT_NOMSG(mod_lz > 0);
204 const size_t mod_bits = mod.bits();
205 BOTAN_ASSERT_NOMSG(mod_bits > mod_lz);
206
207 if(mod_lz == mod_bits - 1)
208 {
209 // In this case we are performing an inversion modulo 2^k
210 return inverse_mod_pow2(n, mod_lz);
211 }
212
213 if(mod_lz == 1)
214 {
215 /*
216 Inversion modulo 2*o is an easier special case of CRT
217
218 This is exactly the main CRT flow below but taking advantage of
219 the fact that any odd number ^-1 modulo 2 is 1. As a result both
220 inv_2k and c can be taken to be 1, m2k is 2, and h is always
221 either 0 or 1, and its value depends only on the low bit of inv_o.
222
223 This is worth special casing because we generate RSA primes such
224 that phi(n) is of this form. However this only works for keys
225 that we generated in this way; pre-existing keys will typically
226 fall back to the general algorithm below.
227 */
228
229 const BigInt o = mod >> 1;
230 const BigInt n_redc = ct_modulo(n, o);
231 const BigInt inv_o = inverse_mod_odd_modulus(n_redc, o);
232
233 // No modular inverse in this case:
234 if(inv_o == 0)
235 return BigInt::zero();
236
237 BigInt h = inv_o;
238 h.ct_cond_add(!inv_o.get_bit(0), o);
239 return h;
240 }
241
242 /*
243 * In this case we are performing an inversion modulo 2^k*o for
244 * some k >= 2 and some odd (not necessarily prime) integer.
245 * Compute the inversions modulo 2^k and modulo o, then combine them
246 * using CRT, which is possible because 2^k and o are relatively prime.
247 */
248
249 const BigInt o = mod >> mod_lz;
250 const BigInt n_redc = ct_modulo(n, o);
251 const BigInt inv_o = inverse_mod_odd_modulus(n_redc, o);
252 const BigInt inv_2k = inverse_mod_pow2(n, mod_lz);
253
254 // No modular inverse in this case:
255 if(inv_o == 0 || inv_2k == 0)
256 return BigInt::zero();
257
258 const BigInt m2k = BigInt::power_of_2(mod_lz);
259 // Compute the CRT parameter
260 const BigInt c = inverse_mod_pow2(o, mod_lz);
261
262 // Compute h = c*(inv_2k-inv_o) mod 2^k
263 BigInt h = c * (inv_2k - inv_o);
264 const bool h_neg = h.is_negative();
266 h.mask_bits(mod_lz);
267 const bool h_nonzero = h.is_nonzero();
268 h.ct_cond_assign(h_nonzero && h_neg, m2k - h);
269
270 // Return result inv_o + h * o
271 h *= o;
272 h += inv_o;
273 return h;
274 }
275
276}
#define BOTAN_ASSERT_NOMSG(expr)
Definition: assert.h:67
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:122
#define BOTAN_ASSERT(expr, assertion_made)
Definition: assert.h:54
void ct_cond_add(bool predicate, const BigInt &value)
Definition: bigint.cpp:451
static BigInt zero()
Definition: bigint.h:45
bool is_odd() const
Definition: bigint.h:418
void ct_cond_assign(bool predicate, const BigInt &other)
Definition: bigint.cpp:484
static BigInt one()
Definition: bigint.h:50
void mask_bits(size_t n)
Definition: bigint.h:469
size_t bits() const
Definition: bigint.cpp:309
bool is_even() const
Definition: bigint.h:412
static BigInt power_of_2(size_t n)
Definition: bigint.h:753
bool is_zero() const
Definition: bigint.h:430
bool is_negative() const
Definition: bigint.h:541
bool is_nonzero() const
Definition: bigint.h:424
bool get_bit(size_t n) const
Definition: bigint.h:479
void set_sign(Sign sign)
Definition: bigint.h:577
static Mask< T > is_equal(T x, T y)
Definition: ct_utils.h:147
static Mask< T > is_zero(T x)
Definition: ct_utils.h:139
static Mask< T > set()
Definition: ct_utils.h:105
fe X
Definition: ge.cpp:26
#define BOTAN_MP_WORD_BITS
Definition: build.h:52
PolynomialVector b
Definition: kyber.cpp:821
void poison(const T *p, size_t n)
Definition: ct_utils.h:48
void unpoison(const T *p, size_t n)
Definition: ct_utils.h:58
Definition: alg_id.cpp:13
void bigint_shr1(word x[], size_t x_size, size_t word_shift, size_t bit_shift)
Definition: mp_core.h:427
word bigint_cnd_add(word cnd, word x[], word x_size, const word y[], size_t y_size)
Definition: mp_core.h:42
size_t low_zero_bits(const BigInt &n)
Definition: numthry.cpp:181
word bigint_cnd_sub(word cnd, word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:88
void bigint_cnd_swap(word cnd, word x[], word y[], size_t size)
Definition: mp_core.h:29
constexpr void copy_mem(T *out, const T *in, size_t n)
Definition: mem_ops.h:126
void carry(int64_t &h0, int64_t &h1)
BigInt ct_modulo(const BigInt &x, const BigInt &y)
Definition: divide.cpp:124
word bigint_add2_nc(word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:227
void bigint_cnd_abs(word cnd, word x[], size_t size)
Definition: mp_core.h:212
BigInt inverse_mod(const BigInt &n, const BigInt &mod)
Definition: mod_inv.cpp:177
constexpr void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:115
size_t round_up(size_t n, size_t align_to)
Definition: rounding.h:21