5079590438

Committed 25 May 2023 12:28PM UTC coverage: 92.228% (+0.5%) from 91.723%

Build # 5079590438

Build Type

Pull #3502

github

Pull Request Pull Request #3502: Apply clang-format to the codebase

Run Details

75589 of 81959 relevant lines covered (92.23%)

12139530.51 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

97.44

/src/lib/math/numbertheory/mod_inv.cpp

/*
* (C) 1999-2011,2016,2018,2019,2020 Jack Lloyd
*
* Botan is released under the Simplified BSD License (see license.txt)
*/

#include <botan/numthry.h>

#include <botan/internal/ct_utils.h>
#include <botan/internal/divide.h>
#include <botan/internal/mp_core.h>
#include <botan/internal/rounding.h>

namespace Botan {

namespace {

BigInt inverse_mod_odd_modulus(const BigInt& n, const BigInt& mod) {
   // Caller should assure these preconditions:
   BOTAN_DEBUG_ASSERT(n.is_positive());
   BOTAN_DEBUG_ASSERT(mod.is_positive());
   BOTAN_DEBUG_ASSERT(n < mod);
   BOTAN_DEBUG_ASSERT(mod >= 3 && mod.is_odd());

   /*
   This uses a modular inversion algorithm designed by Niels Möller
   and implemented in Nettle. The same algorithm was later also
   adapted to GMP in mpn_sec_invert.

   It can be easily implemented in a way that does not depend on
   secret branches or memory lookups, providing resistance against
   some forms of side channel attack.

   There is also a description of the algorithm in Appendix 5 of "Fast
   Software Polynomial Multiplication on ARM Processors using the NEON Engine"
   by Danilo Câmara, Conrado P. L. Gouvêa, Julio López, and Ricardo
   Dahab in LNCS 8182
      https://conradoplg.cryptoland.net/files/2010/12/mocrysen13.pdf

   Thanks to Niels for creating the algorithm, explaining some things
   about it, and the reference to the paper.
   */

   const size_t mod_words = mod.sig_words();
   BOTAN_ASSERT(mod_words > 0, "Not empty");

   secure_vector<word> tmp_mem(5 * mod_words);

   word* v_w = &tmp_mem[0];
   word* u_w = &tmp_mem[1 * mod_words];
   word* b_w = &tmp_mem[2 * mod_words];
   word* a_w = &tmp_mem[3 * mod_words];
   word* mp1o2 = &tmp_mem[4 * mod_words];

   CT::poison(tmp_mem.data(), tmp_mem.size());

   copy_mem(a_w, n.data(), std::min(n.size(), mod_words));
   copy_mem(b_w, mod.data(), std::min(mod.size(), mod_words));
   u_w[0] = 1;
   // v_w = 0

   // compute (mod + 1) / 2 which [because mod is odd] is equal to
   // (mod / 2) + 1
   copy_mem(mp1o2, mod.data(), std::min(mod.size(), mod_words));
   bigint_shr1(mp1o2, mod_words, 0, 1);
   word carry = bigint_add2_nc(mp1o2, mod_words, u_w, 1);
   BOTAN_ASSERT_NOMSG(carry == 0);

   // Only n.bits() + mod.bits() iterations are required, but avoid leaking the size of n
   const size_t execs = 2 * mod.bits();

   for(size_t i = 0; i != execs; ++i) {
      const word odd_a = a_w[0] & 1;

      //if(odd_a) a -= b
      word underflow = bigint_cnd_sub(odd_a, a_w, b_w, mod_words);

      //if(underflow) { b -= a; a = abs(a); swap(u, v); }
      bigint_cnd_add(underflow, b_w, a_w, mod_words);
      bigint_cnd_abs(underflow, a_w, mod_words);
      bigint_cnd_swap(underflow, u_w, v_w, mod_words);

      // a >>= 1
      bigint_shr1(a_w, mod_words, 0, 1);

      //if(odd_a) u -= v;
      word borrow = bigint_cnd_sub(odd_a, u_w, v_w, mod_words);

      // if(borrow) u += p
      bigint_cnd_add(borrow, u_w, mod.data(), mod_words);

      const word odd_u = u_w[0] & 1;

      // u >>= 1
      bigint_shr1(u_w, mod_words, 0, 1);

      //if(odd_u) u += mp1o2;
      bigint_cnd_add(odd_u, u_w, mp1o2, mod_words);
   }

   auto a_is_0 = CT::Mask<word>::set();
   for(size_t i = 0; i != mod_words; ++i)
      a_is_0 &= CT::Mask<word>::is_zero(a_w[i]);

   auto b_is_1 = CT::Mask<word>::is_equal(b_w[0], 1);
   for(size_t i = 1; i != mod_words; ++i)
      b_is_1 &= CT::Mask<word>::is_zero(b_w[i]);

   BOTAN_ASSERT(a_is_0.is_set(), "A is zero");

   // if b != 1 then gcd(n,mod) > 1 and inverse does not exist
   // in which case zero out the result to indicate this
   (~b_is_1).if_set_zero_out(v_w, mod_words);

   /*
   * We've placed the result in the lowest words of the temp buffer.
   * So just clear out the other values and then give that buffer to a
   * BigInt.
   */
   clear_mem(&tmp_mem[mod_words], 4 * mod_words);

   CT::unpoison(tmp_mem.data(), tmp_mem.size());

   BigInt r;
   r.swap_reg(tmp_mem);
   return r;
}

BigInt inverse_mod_pow2(const BigInt& a1, size_t k) {
   /*
   * From "A New Algorithm for Inversion mod p^k" by Çetin Kaya Koç
   * https://eprint.iacr.org/2017/411.pdf sections 5 and 7.
   */

   if(a1.is_even() || k == 0)
      return BigInt::zero();
   if(k == 1)
      return BigInt::one();

   BigInt a = a1;
   a.mask_bits(k);

   BigInt b = BigInt::one();
   BigInt X = BigInt::zero();
   BigInt newb;

   const size_t a_words = a.sig_words();

   X.grow_to(round_up(k, BOTAN_MP_WORD_BITS) / BOTAN_MP_WORD_BITS);
   b.grow_to(a_words);

   /*
   Hide the exact value of k. k is anyway known to word length
   granularity because of the length of a, so no point in doing more
   than this.
   */
   const size_t iter = round_up(k, BOTAN_MP_WORD_BITS);

   for(size_t i = 0; i != iter; ++i) {
      const bool b0 = b.get_bit(0);
      X.conditionally_set_bit(i, b0);
      newb = b - a;
      b.ct_cond_assign(b0, newb);
      b >>= 1;
   }

   X.mask_bits(k);
   X.const_time_unpoison();
   return X;
}

}

BigInt inverse_mod(const BigInt& n, const BigInt& mod) {
   if(mod.is_zero())
      throw Invalid_Argument("inverse_mod modulus cannot be zero");
   if(mod.is_negative() || n.is_negative())
      throw Invalid_Argument("inverse_mod: arguments must be non-negative");
   if(n.is_zero() || (n.is_even() && mod.is_even()))
      return BigInt::zero();

   if(mod.is_odd()) {
      /*
      Fastpath for common case. This leaks if n is greater than mod or
      not, but we don't guarantee const time behavior in that case.
      */
      if(n < mod)
         return inverse_mod_odd_modulus(n, mod);
      else
         return inverse_mod_odd_modulus(ct_modulo(n, mod), mod);
   }

   // If n is even and mod is even we already returned 0
   // If n is even and mod is odd we jumped directly to odd-modulus algo
   BOTAN_DEBUG_ASSERT(n.is_odd());

   const size_t mod_lz = low_zero_bits(mod);
   BOTAN_ASSERT_NOMSG(mod_lz > 0);
   const size_t mod_bits = mod.bits();
   BOTAN_ASSERT_NOMSG(mod_bits > mod_lz);

   if(mod_lz == mod_bits - 1) {
      // In this case we are performing an inversion modulo 2^k
      return inverse_mod_pow2(n, mod_lz);
   }

   if(mod_lz == 1) {
      /*
      Inversion modulo 2*o is an easier special case of CRT

      This is exactly the main CRT flow below but taking advantage of
      the fact that any odd number ^-1 modulo 2 is 1. As a result both
      inv_2k and c can be taken to be 1, m2k is 2, and h is always
      either 0 or 1, and its value depends only on the low bit of inv_o.

      This is worth special casing because we generate RSA primes such
      that phi(n) is of this form. However this only works for keys
      that we generated in this way; pre-existing keys will typically
      fall back to the general algorithm below.
      */

      const BigInt o = mod >> 1;
      const BigInt n_redc = ct_modulo(n, o);
      const BigInt inv_o = inverse_mod_odd_modulus(n_redc, o);

      // No modular inverse in this case:
      if(inv_o == 0)
         return BigInt::zero();

      BigInt h = inv_o;
      h.ct_cond_add(!inv_o.get_bit(0), o);
      return h;
   }

   /*
   * In this case we are performing an inversion modulo 2^k*o for
   * some k >= 2 and some odd (not necessarily prime) integer.
   * Compute the inversions modulo 2^k and modulo o, then combine them
   * using CRT, which is possible because 2^k and o are relatively prime.
   */

   const BigInt o = mod >> mod_lz;
   const BigInt n_redc = ct_modulo(n, o);
   const BigInt inv_o = inverse_mod_odd_modulus(n_redc, o);
   const BigInt inv_2k = inverse_mod_pow2(n, mod_lz);

   // No modular inverse in this case:
   if(inv_o == 0 || inv_2k == 0)
      return BigInt::zero();

   const BigInt m2k = BigInt::power_of_2(mod_lz);
   // Compute the CRT parameter
   const BigInt c = inverse_mod_pow2(o, mod_lz);

   // Compute h = c*(inv_2k-inv_o) mod 2^k
   BigInt h = c * (inv_2k - inv_o);
   const bool h_neg = h.is_negative();
   h.set_sign(BigInt::Positive);
   h.mask_bits(mod_lz);
   const bool h_nonzero = h.is_nonzero();
   h.ct_cond_assign(h_nonzero && h_neg, m2k - h);

   // Return result inv_o + h * o
   h *= o;
   h += inv_o;
   return h;
}

}

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
9	#include <botan/internal/ct_utils.h>
10	#include <botan/internal/divide.h>
11	#include <botan/internal/mp_core.h>
12	#include <botan/internal/rounding.h>
13
14	namespace Botan {
15
16	namespace {
17
18	BigInt inverse_mod_odd_modulus(const BigInt& n, const BigInt& mod) {	49,775✔
19	// Caller should assure these preconditions:
20	BOTAN_DEBUG_ASSERT(n.is_positive());	49,775✔
21	BOTAN_DEBUG_ASSERT(mod.is_positive());	49,775✔
22	BOTAN_DEBUG_ASSERT(n < mod);	49,775✔
23	BOTAN_DEBUG_ASSERT(mod >= 3 && mod.is_odd());	49,775✔
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();	49,775✔
45	BOTAN_ASSERT(mod_words > 0, "Not empty");	49,775✔
46
47	secure_vector<word> tmp_mem(5 * mod_words);	49,775✔
48
49	word* v_w = &tmp_mem[0];	49,775✔
50	word* u_w = &tmp_mem[1 * mod_words];	49,775✔
51	word* b_w = &tmp_mem[2 * mod_words];	49,775✔
52	word* a_w = &tmp_mem[3 * mod_words];	49,775✔
53	word* mp1o2 = &tmp_mem[4 * mod_words];	49,775✔
54
55	CT::poison(tmp_mem.data(), tmp_mem.size());	49,775✔
56
57	copy_mem(a_w, n.data(), std::min(n.size(), mod_words));	97,391✔
58	copy_mem(b_w, mod.data(), std::min(mod.size(), mod_words));	96,398✔
59	u_w[0] = 1;	49,775✔
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));	96,398✔
65	bigint_shr1(mp1o2, mod_words, 0, 1);	49,775✔
66	word carry = bigint_add2_nc(mp1o2, mod_words, u_w, 1);	49,775✔
67	BOTAN_ASSERT_NOMSG(carry == 0);	49,775✔
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();	49,775✔
71
72	for(size_t i = 0; i != execs; ++i) {	35,175,669✔
73	const word odd_a = a_w[0] & 1;	35,125,894✔
74
75	//if(odd_a) a -= b
76	word underflow = bigint_cnd_sub(odd_a, a_w, b_w, mod_words);	35,125,894✔
77
78	//if(underflow) { b -= a; a = abs(a); swap(u, v); }
79	bigint_cnd_add(underflow, b_w, a_w, mod_words);	35,125,894✔
80	bigint_cnd_abs(underflow, a_w, mod_words);	35,125,894✔
81	bigint_cnd_swap(underflow, u_w, v_w, mod_words);	35,125,894✔
82
83	// a >>= 1
84	bigint_shr1(a_w, mod_words, 0, 1);	35,125,894✔
85
86	//if(odd_a) u -= v;
87	word borrow = bigint_cnd_sub(odd_a, u_w, v_w, mod_words);	35,125,894✔
88
89	// if(borrow) u += p
90	bigint_cnd_add(borrow, u_w, mod.data(), mod_words);	35,125,894✔
91
92	const word odd_u = u_w[0] & 1;	35,125,894✔
93
94	// u >>= 1
95	bigint_shr1(u_w, mod_words, 0, 1);	35,125,894✔
96
97	//if(odd_u) u += mp1o2;
98	bigint_cnd_add(odd_u, u_w, mp1o2, mod_words);	35,125,894✔
99	}
100
101	auto a_is_0 = CT::Mask<word>::set();
102	for(size_t i = 0; i != mod_words; ++i)	332,429✔
103	a_is_0 &= CT::Mask<word>::is_zero(a_w[i]);	282,654✔
104
105	auto b_is_1 = CT::Mask<word>::is_equal(b_w[0], 1);	49,775✔
106	for(size_t i = 1; i != mod_words; ++i)	282,654✔
107	b_is_1 &= CT::Mask<word>::is_zero(b_w[i]);	232,879✔
108
109	BOTAN_ASSERT(a_is_0.is_set(), "A is zero");	49,775✔
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);	49,775✔
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);	49,775✔
121
122	CT::unpoison(tmp_mem.data(), tmp_mem.size());	49,775✔
123
124	BigInt r;	49,775✔
125	r.swap_reg(tmp_mem);	49,775✔
126	return r;	49,775✔
127	}	49,775✔
128
129	BigInt inverse_mod_pow2(const BigInt& a1, size_t k) {	794✔
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)	1,588✔
136	return BigInt::zero();	×
137	if(k == 1)	794✔
138	return BigInt::one();	1✔
139
140	BigInt a = a1;	793✔
141	a.mask_bits(k);	793✔
142
143	BigInt b = BigInt::one();	793✔
144	BigInt X = BigInt::zero();	793✔
145	BigInt newb;	793✔
146
147	const size_t a_words = a.sig_words();	793✔
148
149	X.grow_to(round_up(k, BOTAN_MP_WORD_BITS) / BOTAN_MP_WORD_BITS);	1,586✔
150	b.grow_to(a_words);	793✔
151
152	/*
153	Hide the exact value of k. k is anyway known to word length
154	granularity because of the length of a, so no point in doing more
155	than this.
156	*/
157	const size_t iter = round_up(k, BOTAN_MP_WORD_BITS);	793✔
158
159	for(size_t i = 0; i != iter; ++i) {	53,273✔
160	const bool b0 = b.get_bit(0);	52,480✔
161	X.conditionally_set_bit(i, b0);	52,480✔
162	newb = b - a;	52,480✔
163	b.ct_cond_assign(b0, newb);	52,480✔
164	b >>= 1;	52,480✔
165	}
166
167	X.mask_bits(k);	793✔
168	X.const_time_unpoison();	793✔
169	return X;	793✔
170	}	2,380✔
171
172	}
173
174	BigInt inverse_mod(const BigInt& n, const BigInt& mod) {	49,848✔
175	if(mod.is_zero())	50,477✔
176	throw Invalid_Argument("inverse_mod modulus cannot be zero");	×
177	if(mod.is_negative() \|\| n.is_negative())	49,848✔
178	throw Invalid_Argument("inverse_mod: arguments must be non-negative");	×
179	if(n.is_zero() \|\| (n.is_even() && mod.is_even()))	149,303✔
180	return BigInt::zero();	57✔
181
182	if(mod.is_odd()) {	99,582✔
183	/*
184	Fastpath for common case. This leaks if n is greater than mod or
185	not, but we don't guarantee const time behavior in that case.
186	*/
187	if(n < mod)	49,238✔
188	return inverse_mod_odd_modulus(n, mod);	48,990✔
189	else
190	return inverse_mod_odd_modulus(ct_modulo(n, mod), mod);	496✔
191	}
192
193	// If n is even and mod is even we already returned 0
194	// If n is even and mod is odd we jumped directly to odd-modulus algo
195	BOTAN_DEBUG_ASSERT(n.is_odd());	553✔
196
197	const size_t mod_lz = low_zero_bits(mod);	553✔
198	BOTAN_ASSERT_NOMSG(mod_lz > 0);	553✔
199	const size_t mod_bits = mod.bits();	553✔
200	BOTAN_ASSERT_NOMSG(mod_bits > mod_lz);	553✔
201
202	if(mod_lz == mod_bits - 1) {	553✔
203	// In this case we are performing an inversion modulo 2^k
204	return inverse_mod_pow2(n, mod_lz);	16✔
205	}
206
207	if(mod_lz == 1) {	537✔
208	/*
209	Inversion modulo 2*o is an easier special case of CRT
210
211	This is exactly the main CRT flow below but taking advantage of
212	the fact that any odd number ^-1 modulo 2 is 1. As a result both
213	inv_2k and c can be taken to be 1, m2k is 2, and h is always
214	either 0 or 1, and its value depends only on the low bit of inv_o.
215
216	This is worth special casing because we generate RSA primes such
217	that phi(n) is of this form. However this only works for keys
218	that we generated in this way; pre-existing keys will typically
219	fall back to the general algorithm below.
220	*/
221
222	const BigInt o = mod >> 1;	146✔
223	const BigInt n_redc = ct_modulo(n, o);	146✔
224	const BigInt inv_o = inverse_mod_odd_modulus(n_redc, o);	146✔
225
226	// No modular inverse in this case:
227	if(inv_o == 0)	146✔
228	return BigInt::zero();	8✔
229
230	BigInt h = inv_o;	138✔
231	h.ct_cond_add(!inv_o.get_bit(0), o);	276✔
232	return h;	138✔
233	}	584✔
234
235	/*
236	* In this case we are performing an inversion modulo 2^k*o for
237	* some k >= 2 and some odd (not necessarily prime) integer.
238	* Compute the inversions modulo 2^k and modulo o, then combine them
239	* using CRT, which is possible because 2^k and o are relatively prime.
240	*/
241
242	const BigInt o = mod >> mod_lz;	391✔
243	const BigInt n_redc = ct_modulo(n, o);	391✔
244	const BigInt inv_o = inverse_mod_odd_modulus(n_redc, o);	391✔
245	const BigInt inv_2k = inverse_mod_pow2(n, mod_lz);	391✔
246
247	// No modular inverse in this case:
248	if(inv_o == 0 \|\| inv_2k == 0)	778✔
249	return BigInt::zero();	4✔
250
251	const BigInt m2k = BigInt::power_of_2(mod_lz);	387✔
252	// Compute the CRT parameter
253	const BigInt c = inverse_mod_pow2(o, mod_lz);	387✔
254
255	// Compute h = c*(inv_2k-inv_o) mod 2^k
256	BigInt h = c * (inv_2k - inv_o);	387✔
257	const bool h_neg = h.is_negative();	387✔
258	h.set_sign(BigInt::Positive);	387✔
259	h.mask_bits(mod_lz);	387✔
260	const bool h_nonzero = h.is_nonzero();	387✔
261	h.ct_cond_assign(h_nonzero && h_neg, m2k - h);	387✔
262
263	// Return result inv_o + h * o
264	h *= o;	387✔
265	h += inv_o;	387✔
266	return h;	387✔
267	}	52,186✔
268
269	}

randombit / botan / 5079590438

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous