11087146043

Committed 28 Sep 2024 09:28PM UTC coverage: 92.003% (+0.7%) from 91.274%

Build # 11087146043

Build Type

push

github

Committed by

web-flow

Commit Message

Create terraform.yml

Run Details

82959 of 90170 relevant lines covered (92.0%)

9376319.11 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://inria.hal.science/hal-01506572/document

   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, 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, 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, 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.as_bool(), "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;
}

}  // namespace

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;
}

}  // namespace Botan

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) {	50,807✔
19	// Caller should assure these preconditions:
20	BOTAN_DEBUG_ASSERT(n.is_positive());	50,807✔
21	BOTAN_DEBUG_ASSERT(mod.is_positive());	50,807✔
22	BOTAN_DEBUG_ASSERT(n < mod);	50,807✔
23	BOTAN_DEBUG_ASSERT(mod >= 3 && mod.is_odd());	50,807✔
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://inria.hal.science/hal-01506572/document
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();	50,807✔
45	BOTAN_ASSERT(mod_words > 0, "Not empty");	50,807✔
46
47	secure_vector<word> tmp_mem(5 * mod_words);	50,807✔
48
49	word* v_w = &tmp_mem[0];	50,807✔
50	word* u_w = &tmp_mem[1 * mod_words];	50,807✔
51	word* b_w = &tmp_mem[2 * mod_words];	50,807✔
52	word* a_w = &tmp_mem[3 * mod_words];	50,807✔
53	word* mp1o2 = &tmp_mem[4 * mod_words];	50,807✔
54
55	CT::poison(tmp_mem.data(), tmp_mem.size());	50,807✔
56
57	copy_mem(a_w, n.data(), std::min(n.size(), mod_words));	99,428✔
58	copy_mem(b_w, mod.data(), std::min(mod.size(), mod_words));	98,441✔
59	u_w[0] = 1;	50,807✔
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));	98,441✔
65	bigint_shr1(mp1o2, mod_words, 1);	50,807✔
66	word carry = bigint_add2_nc(mp1o2, mod_words, u_w, 1);	50,807✔
67	BOTAN_ASSERT_NOMSG(carry == 0);	50,807✔
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();	50,807✔
71
72	for(size_t i = 0; i != execs; ++i) {	35,986,611✔
73	const word odd_a = a_w[0] & 1;	35,935,804✔
74
75	//if(odd_a) a -= b
76	word underflow = bigint_cnd_sub(odd_a, a_w, b_w, mod_words);	35,935,804✔
77
78	//if(underflow) { b -= a; a = abs(a); swap(u, v); }
79	bigint_cnd_add(underflow, b_w, a_w, mod_words);	35,935,804✔
80	bigint_cnd_abs(underflow, a_w, mod_words);	35,935,804✔
81	bigint_cnd_swap(underflow, u_w, v_w, mod_words);	35,935,804✔
82
83	// a >>= 1
84	bigint_shr1(a_w, mod_words, 1);	35,935,804✔
85
86	//if(odd_a) u -= v;
87	word borrow = bigint_cnd_sub(odd_a, u_w, v_w, mod_words);	35,935,804✔
88
89	// if(borrow) u += p
90	bigint_cnd_add(borrow, u_w, mod.data(), mod_words);	35,935,804✔
91
92	const word odd_u = u_w[0] & 1;	35,935,804✔
93
94	// u >>= 1
95	bigint_shr1(u_w, mod_words, 1);	35,935,804✔
96
97	//if(odd_u) u += mp1o2;
98	bigint_cnd_add(odd_u, u_w, mp1o2, mod_words);	35,935,804✔
99	}
100
101	auto a_is_0 = CT::Mask<word>::set();
102	for(size_t i = 0; i != mod_words; ++i) {	339,877✔
103	a_is_0 &= CT::Mask<word>::is_zero(a_w[i]);	289,070✔
104	}
105
106	auto b_is_1 = CT::Mask<word>::is_equal(b_w[0], 1);	50,807✔
107	for(size_t i = 1; i != mod_words; ++i) {	289,070✔
108	b_is_1 &= CT::Mask<word>::is_zero(b_w[i]);	238,263✔
109	}
110
111	BOTAN_ASSERT(a_is_0.as_bool(), "A is zero");	50,807✔
112
113	// if b != 1 then gcd(n,mod) > 1 and inverse does not exist
114	// in which case zero out the result to indicate this
115	(~b_is_1).if_set_zero_out(v_w, mod_words);	50,807✔
116
117	/*
118	* We've placed the result in the lowest words of the temp buffer.
119	* So just clear out the other values and then give that buffer to a
120	* BigInt.
121	*/
122	clear_mem(&tmp_mem[mod_words], 4 * mod_words);	50,807✔
123
124	CT::unpoison(tmp_mem.data(), tmp_mem.size());	50,807✔
125
126	BigInt r;	50,807✔
127	r.swap_reg(tmp_mem);	50,807✔
128	return r;	50,807✔
129	}	50,807✔
130
131	BigInt inverse_mod_pow2(const BigInt& a1, size_t k) {	797✔
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) {	1,594✔
138	return BigInt::zero();	×
139	}
140	if(k == 1) {	797✔
141	return BigInt::one();	1✔
142	}
143
144	BigInt a = a1;	796✔
145	a.mask_bits(k);	796✔
146
147	BigInt b = BigInt::one();	796✔
148	BigInt X = BigInt::zero();	796✔
149	BigInt newb;	796✔
150
151	const size_t a_words = a.sig_words();	796✔
152
153	X.grow_to(round_up(k, BOTAN_MP_WORD_BITS) / BOTAN_MP_WORD_BITS);	796✔
154	b.grow_to(a_words);	796✔
155
156	/*
157	Hide the exact value of k. k is anyway known to word length
158	granularity because of the length of a, so no point in doing more
159	than this.
160	*/
161	const size_t iter = round_up(k, BOTAN_MP_WORD_BITS);	796✔
162
163	for(size_t i = 0; i != iter; ++i) {	53,468✔
164	const bool b0 = b.get_bit(0);	52,672✔
165	X.conditionally_set_bit(i, b0);	52,672✔
166	newb = b - a;	52,672✔
167	b.ct_cond_assign(b0, newb);	52,672✔
168	b >>= 1;	52,672✔
169	}
170
171	X.mask_bits(k);	796✔
172	X.const_time_unpoison();	796✔
173	return X;	796✔
174	}	2,389✔
175
176	} // namespace
177
178	BigInt inverse_mod(const BigInt& n, const BigInt& mod) {	50,875✔
179	if(mod.is_zero()) {	51,517✔
180	throw Invalid_Argument("inverse_mod modulus cannot be zero");	×
181	}
182	if(mod.is_negative() \|\| n.is_negative()) {	50,875✔
183	throw Invalid_Argument("inverse_mod: arguments must be non-negative");	×
184	}
185	if(n.is_zero() \|\| (n.is_even() && mod.is_even())) {	152,064✔
186	return BigInt::zero();	52✔
187	}
188
189	if(mod.is_odd()) {	101,646✔
190	/*
191	Fastpath for common case. This leaks if n is greater than mod or
192	not, but we don't guarantee const time behavior in that case.
193	*/
194	if(n < mod) {	50,254✔
195	return inverse_mod_odd_modulus(n, mod);	50,009✔
196	} else {
197	return inverse_mod_odd_modulus(ct_modulo(n, mod), mod);	490✔
198	}
199	}
200
201	// If n is even and mod is even we already returned 0
202	// If n is even and mod is odd we jumped directly to odd-modulus algo
203	BOTAN_DEBUG_ASSERT(n.is_odd());	569✔
204
205	const size_t mod_lz = low_zero_bits(mod);	569✔
206	BOTAN_ASSERT_NOMSG(mod_lz > 0);	569✔
207	const size_t mod_bits = mod.bits();	569✔
208	BOTAN_ASSERT_NOMSG(mod_bits > mod_lz);	569✔
209
210	if(mod_lz == mod_bits - 1) {	569✔
211	// In this case we are performing an inversion modulo 2^k
212	return inverse_mod_pow2(n, mod_lz);	16✔
213	}
214
215	if(mod_lz == 1) {	553✔
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;	160✔
231	const BigInt n_redc = ct_modulo(n, o);	160✔
232	const BigInt inv_o = inverse_mod_odd_modulus(n_redc, o);	160✔
233
234	// No modular inverse in this case:
235	if(inv_o == 0) {	160✔
236	return BigInt::zero();	12✔
237	}
238
239	BigInt h = inv_o;	148✔
240	h.ct_cond_add(!inv_o.get_bit(0), o);	296✔
241	return h;	148✔
242	}	640✔
243
244	/*
245	* In this case we are performing an inversion modulo 2^k*o for
246	* some k >= 2 and some odd (not necessarily prime) integer.
247	* Compute the inversions modulo 2^k and modulo o, then combine them
248	* using CRT, which is possible because 2^k and o are relatively prime.
249	*/
250
251	const BigInt o = mod >> mod_lz;	393✔
252	const BigInt n_redc = ct_modulo(n, o);	393✔
253	const BigInt inv_o = inverse_mod_odd_modulus(n_redc, o);	393✔
254	const BigInt inv_2k = inverse_mod_pow2(n, mod_lz);	393✔
255
256	// No modular inverse in this case:
257	if(inv_o == 0 \|\| inv_2k == 0) {	781✔
258	return BigInt::zero();	5✔
259	}
260
261	const BigInt m2k = BigInt::power_of_2(mod_lz);	388✔
262	// Compute the CRT parameter
263	const BigInt c = inverse_mod_pow2(o, mod_lz);	388✔
264
265	// Compute h = c*(inv_2k-inv_o) mod 2^k
266	BigInt h = c * (inv_2k - inv_o);	388✔
267	const bool h_neg = h.is_negative();	388✔
268	h.set_sign(BigInt::Positive);	388✔
269	h.mask_bits(mod_lz);	388✔
270	const bool h_nonzero = h.is_nonzero();	388✔
271	h.ct_cond_assign(h_nonzero && h_neg, m2k - h);	388✔
272
273	// Return result inv_o + h * o
274	h *= o;	388✔
275	h += inv_o;	388✔
276	return h;	388✔
277	}	53,223✔
278
279	} // namespace Botan

randombit / botan / 11087146043

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