21768358452

Committed 06 Feb 2026 10:35PM UTC coverage: 90.064% (-0.003%) from 90.067%

Build # 21768358452

Build Type

Pull #5289

github

Committed by

web-flow

Commit Message

Merge f589db195 into 8ea0ca252

Pull Request Pull Request #5289: Further misc header reductions, forward declarations, etc

Run Details

102238 of 113517 relevant lines covered (90.06%)

11357432.36 hits per line

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

97.66

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

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

#include <botan/internal/mod_inv.h>

#include <botan/exceptn.h>
#include <botan/mem_ops.h>
#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_ASSERT_NOMSG(n.is_positive());
   BOTAN_ASSERT_NOMSG(mod.is_positive());
   BOTAN_ASSERT_NOMSG(n < mod);
   BOTAN_ASSERT_NOMSG(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];  // NOLINT(readability-container-data-pointer)
   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);
   const word carry = bigint_add2(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
      const 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;
      const 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);
   }

   const auto a_is_0 = CT::all_zeros(a_w, mod_words);

   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, WordInfo<word>::bits) / WordInfo<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, WordInfo<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);

   CT::unpoison(X);
   return X;
}

}  // namespace

std::optional<BigInt> inverse_mod_general(const BigInt& x, const BigInt& mod) {
   BOTAN_ARG_CHECK(x > 0, "x must be greater than zero");
   BOTAN_ARG_CHECK(mod > 0, "mod must be greater than zero");
   BOTAN_ARG_CHECK(x < mod, "x must be less than m");

   // Easy case where gcd > 1 so no inverse exists
   if(x.is_even() && mod.is_even()) {
      return std::nullopt;
   }

   if(mod.is_odd()) {
      BigInt z = inverse_mod_odd_modulus(x, mod);
      if(z.is_zero()) {
         return std::nullopt;
      } else {
         return z;
      }
   }

   // If x is even and mod is even we already returned 0
   // If x is even and mod is odd we jumped directly to odd-modulus algo
   BOTAN_ASSERT_NOMSG(x.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
      auto z = inverse_mod_pow2(x, mod_lz);
      if(z.is_zero()) {
         return std::nullopt;
      } else {
         return z;
      }
   }

   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 inv_o = inverse_mod_odd_modulus(ct_modulo(x, o), o);

      // No modular inverse in this case:
      if(inv_o == 0) {
         return std::nullopt;
      }

      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 inv_o = inverse_mod_odd_modulus(ct_modulo(x, o), o);
   const BigInt inv_2k = inverse_mod_pow2(x, mod_lz);

   // No modular inverse in this case:
   if(inv_o == 0 || inv_2k == 0) {
      return std::nullopt;
   }

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

   // This should never happen; o is odd so gcd is 1 and inverse mod 2^k exists
   BOTAN_ASSERT_NOMSG(!c.is_zero());

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

BigInt inverse_mod_secret_prime(const BigInt& x, const BigInt& p) {
   BOTAN_ARG_CHECK(x.is_positive() && p.is_positive(), "Parameters must be positive");
   BOTAN_ARG_CHECK(x < p, "x must be less than p");
   BOTAN_ARG_CHECK(p.is_odd() && p > 1, "Primes are odd integers greater than 1");

   // TODO possibly use FLT, or the algorithm presented for this case in
   // Handbook of Elliptic and Hyperelliptic Curve Cryptography

   return inverse_mod_odd_modulus(x, p);
}

BigInt inverse_mod_public_prime(const BigInt& x, const BigInt& p) {
   return inverse_mod_secret_prime(x, p);
}

BigInt inverse_mod_rsa_public_modulus(const BigInt& x, const BigInt& n) {
   BOTAN_ARG_CHECK(n.is_positive() && n.is_odd(), "RSA public modulus must be odd and positive");
   BOTAN_ARG_CHECK(x.is_positive() && x < n, "Input must be positive and less than RSA modulus");
   BigInt z = inverse_mod_odd_modulus(x, n);
   BOTAN_ASSERT(!z.is_zero(), "Accidentally factored the public modulus");  // whoops
   return z;
}

namespace {

uint64_t barrett_mod_65537(uint64_t x) {
   constexpr uint64_t mod = 65537;
   constexpr size_t s = 32;
   constexpr uint64_t c = (static_cast<uint64_t>(1) << s) / mod;

   const uint64_t q = (x * c) >> s;
   const uint64_t r = x - q * mod;

   auto r_gt_mod = CT::Mask<uint64_t>::is_gte(r, mod);
   return r - r_gt_mod.if_set_return(mod);
}

word inverse_mod_65537(word x) {
   // Need 64-bit here as accum*accum exceeds 32-bit if accum=0x10000
   uint64_t accum = 1;
   // Basic square and multiply, with all bits of exponent set
   for(size_t i = 0; i != 16; ++i) {
      accum = barrett_mod_65537(accum * accum);
      accum = barrett_mod_65537(accum * x);
   }
   return static_cast<word>(accum);
}

}  // namespace

BigInt compute_rsa_secret_exponent(const BigInt& e, const BigInt& phi_n, const BigInt& p, const BigInt& q) {
   /*
   * Both p - 1 and q - 1 are chosen to be relatively prime to e. Thus
   * phi(n), the least common multiple of p - 1 and q - 1, is also
   * relatively prime to e.
   */
   BOTAN_DEBUG_ASSERT(gcd(e, phi_n) == 1);

   if(e == 65537) {
      /*
      Arazi's algorithm for inversion of prime x modulo a non-prime

      "GCD-Free Algorithms for Computing Modular Inverses"
      Marc Joye and Pascal Paillier, CHES 2003 (LNCS 2779)
      https://marcjoye.github.io/papers/JP03gcdfree.pdf

      This could be extended to cover other cases such as e=3 or e=17 but
      these days 65537 is the standard RSA public exponent
      */

      constexpr word e_w = 65537;

      const word phi_mod_e = ct_mod_word(phi_n, e_w);
      const word inv_phi_mod_e = inverse_mod_65537(phi_mod_e);
      BOTAN_DEBUG_ASSERT((inv_phi_mod_e * phi_mod_e) % e_w == 1);
      const word neg_inv_phi_mod_e = (e_w - inv_phi_mod_e);
      return ct_divide_word((phi_n * neg_inv_phi_mod_e) + 1, e_w);
   } else {
      // TODO possibly do something else taking advantage of the special structure here

      BOTAN_UNUSED(p, q);
      if(auto d = inverse_mod_general(e, phi_n)) {
         return *d;
      } else {
         throw Internal_Error("Failed to compute RSA secret exponent");
      }
   }
}

BigInt inverse_mod(const BigInt& n, const BigInt& mod) {
   BOTAN_ARG_CHECK(!mod.is_zero(), "modulus cannot be zero");
   BOTAN_ARG_CHECK(!mod.is_negative(), "modulus cannot be negative");
   BOTAN_ARG_CHECK(!n.is_negative(), "value cannot be negative");

   if(n.is_zero() || (n.is_even() && mod.is_even())) {
      return BigInt::zero();
   }

   if(n >= mod) {
      return inverse_mod(ct_modulo(n, mod), mod);
   }

   return inverse_mod_general(n, mod).value_or(BigInt::zero());
}

}  // namespace Botan

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/ct_utils.h>
13	#include <botan/internal/divide.h>
14	#include <botan/internal/mp_core.h>
15	#include <botan/internal/rounding.h>
16
17	namespace Botan {
18
19	namespace {
20
21	BigInt inverse_mod_odd_modulus(const BigInt& n, const BigInt& mod) {	37,328✔
22	// Caller should assure these preconditions:
23	BOTAN_ASSERT_NOMSG(n.is_positive());	37,328✔
24	BOTAN_ASSERT_NOMSG(mod.is_positive());	37,328✔
25	BOTAN_ASSERT_NOMSG(n < mod);	37,328✔
26	BOTAN_ASSERT_NOMSG(mod >= 3 && mod.is_odd());	74,656✔
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();	37,328✔
48	BOTAN_ASSERT(mod_words > 0, "Not empty");	37,328✔
49
50	secure_vector<word> tmp_mem(5 * mod_words);	37,328✔
51
52	word* v_w = &tmp_mem[0]; // NOLINT(readability-container-data-pointer)	37,328✔
53	word* u_w = &tmp_mem[1 * mod_words];	37,328✔
54	word* b_w = &tmp_mem[2 * mod_words];	37,328✔
55	word* a_w = &tmp_mem[3 * mod_words];	37,328✔
56	word* mp1o2 = &tmp_mem[4 * mod_words];	37,328✔
57
58	CT::poison(tmp_mem.data(), tmp_mem.size());	37,328✔
59
60	copy_mem(a_w, n._data(), std::min(n.size(), mod_words));	73,099✔
61	copy_mem(b_w, mod._data(), std::min(mod.size(), mod_words));	72,808✔
62	u_w[0] = 1;	37,328✔
63	// v_w = 0
64
65	// compute (mod + 1) / 2 which [because mod is odd] is equal to
66	// (mod / 2) + 1
67	copy_mem(mp1o2, mod._data(), std::min(mod.size(), mod_words));	72,808✔
68	bigint_shr1(mp1o2, mod_words, 1);	37,328✔
69	const word carry = bigint_add2(mp1o2, mod_words, u_w, 1);	37,328✔
70	BOTAN_ASSERT_NOMSG(carry == 0);	37,328✔
71
72	// Only n.bits() + mod.bits() iterations are required, but avoid leaking the size of n
73	const size_t execs = 2 * mod.bits();	37,328✔
74
75	for(size_t i = 0; i != execs; ++i) {	25,319,180✔
76	const word odd_a = a_w[0] & 1;	25,281,852✔
77
78	//if(odd_a) a -= b
79	const word underflow = bigint_cnd_sub(odd_a, a_w, b_w, mod_words);	25,281,852✔
80
81	//if(underflow) { b -= a; a = abs(a); swap(u, v); }
82	bigint_cnd_add(underflow, b_w, a_w, mod_words);	25,281,852✔
83	bigint_cnd_abs(underflow, a_w, mod_words);	25,281,852✔
84	bigint_cnd_swap(underflow, u_w, v_w, mod_words);	25,281,852✔
85
86	// a >>= 1
87	bigint_shr1(a_w, mod_words, 1);	25,281,852✔
88
89	//if(odd_a) u -= v;
90	const word borrow = bigint_cnd_sub(odd_a, u_w, v_w, mod_words);	25,281,852✔
91
92	// if(borrow) u += p
93	bigint_cnd_add(borrow, u_w, mod._data(), mod_words);	25,281,852✔
94
95	const word odd_u = u_w[0] & 1;	25,281,852✔
96
97	// u >>= 1
98	bigint_shr1(u_w, mod_words, 1);	25,281,852✔
99
100	//if(odd_u) u += mp1o2;
101	bigint_cnd_add(odd_u, u_w, mp1o2, mod_words);	25,281,852✔
102	}
103
104	const auto a_is_0 = CT::all_zeros(a_w, mod_words);	37,328✔
105
106	auto b_is_1 = CT::Mask<word>::is_equal(b_w[0], 1);	37,328✔
107	for(size_t i = 1; i != mod_words; ++i) {	209,382✔
108	b_is_1 &= CT::Mask<word>::is_zero(b_w[i]);	172,054✔
109	}
110
111	BOTAN_ASSERT(a_is_0.as_bool(), "A is zero");	37,328✔
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);	37,328✔
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);	37,328✔
123
124	CT::unpoison(tmp_mem.data(), tmp_mem.size());	37,328✔
125
126	BigInt r;	37,328✔
127	r.swap_reg(tmp_mem);	37,328✔
128	return r;	37,328✔
129	}	37,328✔
130
131	BigInt inverse_mod_pow2(const BigInt& a1, size_t k) {	630✔
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,260✔
138	return BigInt::zero();	×
139	}
140	if(k == 1) {	630✔
141	return BigInt::one();	2✔
142	}
143
144	BigInt a = a1;	628✔
145	a.mask_bits(k);	628✔
146
147	BigInt b = BigInt::one();	628✔
148	BigInt X = BigInt::zero();	628✔
149	BigInt newb;	628✔
150
151	const size_t a_words = a.sig_words();	628✔
152
153	X.grow_to(round_up(k, WordInfo<word>::bits) / WordInfo<word>::bits);	628✔
154	b.grow_to(a_words);	628✔
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, WordInfo<word>::bits);	628✔
162
163	for(size_t i = 0; i != iter; ++i) {	44,276✔
164	const bool b0 = b.get_bit(0);	43,648✔
165	X.conditionally_set_bit(i, b0);	43,648✔
166	newb = b - a;	43,648✔
167	b.ct_cond_assign(b0, newb);	43,648✔
168	b >>= 1;	43,648✔
169	}
170
171	X.mask_bits(k);	628✔
172
173	CT::unpoison(X);	628✔
174	return X;	628✔
175	}	628✔
176
177	} // namespace
178
179	std::optional<BigInt> inverse_mod_general(const BigInt& x, const BigInt& mod) {	590✔
180	BOTAN_ARG_CHECK(x > 0, "x must be greater than zero");	590✔
181	BOTAN_ARG_CHECK(mod > 0, "mod must be greater than zero");	590✔
182	BOTAN_ARG_CHECK(x < mod, "x must be less than m");	590✔
183
184	// Easy case where gcd > 1 so no inverse exists
185	if(x.is_even() && mod.is_even()) {	1,292✔
186	return std::nullopt;	22✔
187	}
188
189	if(mod.is_odd()) {	568✔
190	BigInt z = inverse_mod_odd_modulus(x, mod);	175✔
191	if(z.is_zero()) {	350✔
192	return std::nullopt;	28✔
193	} else {
194	return z;	147✔
195	}
196	}	175✔
197
198	// If x is even and mod is even we already returned 0
199	// If x is even and mod is odd we jumped directly to odd-modulus algo
200	BOTAN_ASSERT_NOMSG(x.is_odd());	393✔
201
202	const size_t mod_lz = low_zero_bits(mod);	393✔
203	BOTAN_ASSERT_NOMSG(mod_lz > 0);	393✔
204	const size_t mod_bits = mod.bits();	393✔
205	BOTAN_ASSERT_NOMSG(mod_bits > mod_lz);	393✔
206
207	if(mod_lz == mod_bits - 1) {	393✔
208	// In this case we are performing an inversion modulo 2^k
209	auto z = inverse_mod_pow2(x, mod_lz);	32✔
210	if(z.is_zero()) {	64✔
211	return std::nullopt;	×
212	} else {
213	return z;	32✔
214	}
215	}	32✔
216
217	if(mod_lz == 1) {	361✔
218	/*
219	Inversion modulo 2*o is an easier special case of CRT
220
221	This is exactly the main CRT flow below but taking advantage of
222	the fact that any odd number ^-1 modulo 2 is 1. As a result both
223	inv_2k and c can be taken to be 1, m2k is 2, and h is always
224	either 0 or 1, and its value depends only on the low bit of inv_o.
225
226	This is worth special casing because we generate RSA primes such
227	that phi(n) is of this form. However this only works for keys
228	that we generated in this way; pre-existing keys will typically
229	fall back to the general algorithm below.
230	*/
231
232	const BigInt o = mod >> 1;	58✔
233	const BigInt inv_o = inverse_mod_odd_modulus(ct_modulo(x, o), o);	58✔
234
235	// No modular inverse in this case:
236	if(inv_o == 0) {	58✔
237	return std::nullopt;	15✔
238	}
239
240	BigInt h = inv_o;	43✔
241	h.ct_cond_add(!inv_o.get_bit(0), o);	86✔
242	return h;	43✔
243	}	58✔
244
245	/*
246	* In this case we are performing an inversion modulo 2^k*o for
247	* some k >= 2 and some odd (not necessarily prime) integer.
248	* Compute the inversions modulo 2^k and modulo o, then combine them
249	* using CRT, which is possible because 2^k and o are relatively prime.
250	*/
251
252	const BigInt o = mod >> mod_lz;	303✔
253	const BigInt inv_o = inverse_mod_odd_modulus(ct_modulo(x, o), o);	303✔
254	const BigInt inv_2k = inverse_mod_pow2(x, mod_lz);	303✔
255
256	// No modular inverse in this case:
257	if(inv_o == 0 \|\| inv_2k == 0) {	598✔
258	return std::nullopt;	8✔
259	}
260
261	const BigInt m2k = BigInt::power_of_2(mod_lz);	295✔
262	// Compute the CRT parameter
263	const BigInt c = inverse_mod_pow2(o, mod_lz);	295✔
264
265	// This should never happen; o is odd so gcd is 1 and inverse mod 2^k exists
266	BOTAN_ASSERT_NOMSG(!c.is_zero());	590✔
267
268	// Compute h = c*(inv_2k-inv_o) mod 2^k
269	BigInt h = c * (inv_2k - inv_o);	295✔
270	const bool h_neg = h.is_negative();	295✔
271	h.set_sign(BigInt::Positive);	295✔
272	h.mask_bits(mod_lz);	295✔
273	const bool h_nonzero = h.is_nonzero();	295✔
274	h.ct_cond_assign(h_nonzero && h_neg, m2k - h);	295✔
275
276	// Return result inv_o + h * o
277	h *= o;	295✔
278	h += inv_o;	295✔
279	return h;	295✔
280	}	303✔
281
282	BigInt inverse_mod_secret_prime(const BigInt& x, const BigInt& p) {	35,276✔
283	BOTAN_ARG_CHECK(x.is_positive() && p.is_positive(), "Parameters must be positive");	35,276✔
284	BOTAN_ARG_CHECK(x < p, "x must be less than p");	35,276✔
285	BOTAN_ARG_CHECK(p.is_odd() && p > 1, "Primes are odd integers greater than 1");	105,828✔
286
287	// TODO possibly use FLT, or the algorithm presented for this case in
288	// Handbook of Elliptic and Hyperelliptic Curve Cryptography
289
290	return inverse_mod_odd_modulus(x, p);	35,276✔
291	}
292
293	BigInt inverse_mod_public_prime(const BigInt& x, const BigInt& p) {	34,602✔
294	return inverse_mod_secret_prime(x, p);	34,602✔
295	}
296
297	BigInt inverse_mod_rsa_public_modulus(const BigInt& x, const BigInt& n) {	1,516✔
298	BOTAN_ARG_CHECK(n.is_positive() && n.is_odd(), "RSA public modulus must be odd and positive");	3,032✔
299	BOTAN_ARG_CHECK(x.is_positive() && x < n, "Input must be positive and less than RSA modulus");	3,032✔
300	BigInt z = inverse_mod_odd_modulus(x, n);	1,516✔
301	BOTAN_ASSERT(!z.is_zero(), "Accidentally factored the public modulus"); // whoops	3,032✔
302	return z;	1,516✔
303	}	×
304
305	namespace {
306
307	uint64_t barrett_mod_65537(uint64_t x) {	69,136✔
308	constexpr uint64_t mod = 65537;	69,136✔
309	constexpr size_t s = 32;	69,136✔
310	constexpr uint64_t c = (static_cast<uint64_t>(1) << s) / mod;	69,136✔
311
312	const uint64_t q = (x * c) >> s;	69,136✔
313	const uint64_t r = x - q * mod;	69,136✔
314
315	auto r_gt_mod = CT::Mask<uint64_t>::is_gte(r, mod);	69,136✔
316	return r - r_gt_mod.if_set_return(mod);	69,136✔
317	}
318
319	word inverse_mod_65537(word x) {	4,321✔
320	// Need 64-bit here as accum*accum exceeds 32-bit if accum=0x10000
321	uint64_t accum = 1;	4,321✔
322	// Basic square and multiply, with all bits of exponent set
323	for(size_t i = 0; i != 16; ++i) {	73,457✔
324	accum = barrett_mod_65537(accum * accum);	69,136✔
325	accum = barrett_mod_65537(accum * x);	69,136✔
326	}
327	return static_cast<word>(accum);	4,321✔
328	}
329
330	} // namespace
331
332	BigInt compute_rsa_secret_exponent(const BigInt& e, const BigInt& phi_n, const BigInt& p, const BigInt& q) {	4,605✔
333	/*
334	* Both p - 1 and q - 1 are chosen to be relatively prime to e. Thus
335	* phi(n), the least common multiple of p - 1 and q - 1, is also
336	* relatively prime to e.
337	*/
338	BOTAN_DEBUG_ASSERT(gcd(e, phi_n) == 1);	4,605✔
339
340	if(e == 65537) {	4,605✔
341	/*
342	Arazi's algorithm for inversion of prime x modulo a non-prime
343
344	"GCD-Free Algorithms for Computing Modular Inverses"
345	Marc Joye and Pascal Paillier, CHES 2003 (LNCS 2779)
346	https://marcjoye.github.io/papers/JP03gcdfree.pdf
347
348	This could be extended to cover other cases such as e=3 or e=17 but
349	these days 65537 is the standard RSA public exponent
350	*/
351
352	constexpr word e_w = 65537;	4,321✔
353
354	const word phi_mod_e = ct_mod_word(phi_n, e_w);	4,321✔
355	const word inv_phi_mod_e = inverse_mod_65537(phi_mod_e);	4,321✔
356	BOTAN_DEBUG_ASSERT((inv_phi_mod_e * phi_mod_e) % e_w == 1);	4,321✔
357	const word neg_inv_phi_mod_e = (e_w - inv_phi_mod_e);	4,321✔
358	return ct_divide_word((phi_n * neg_inv_phi_mod_e) + 1, e_w);	8,642✔
359	} else {
360	// TODO possibly do something else taking advantage of the special structure here
361
362	BOTAN_UNUSED(p, q);	284✔
363	if(auto d = inverse_mod_general(e, phi_n)) {	284✔
364	return *d;	284✔
365	} else {
366	throw Internal_Error("Failed to compute RSA secret exponent");	×
367	}	284✔
368	}
369	}
370
371	BigInt inverse_mod(const BigInt& n, const BigInt& mod) {	256✔
372	BOTAN_ARG_CHECK(!mod.is_zero(), "modulus cannot be zero");	394✔
373	BOTAN_ARG_CHECK(!mod.is_negative(), "modulus cannot be negative");	256✔
374	BOTAN_ARG_CHECK(!n.is_negative(), "value cannot be negative");	256✔
375
376	if(n.is_zero() \|\| (n.is_even() && mod.is_even())) {	883✔
377	return BigInt::zero();	63✔
378	}
379
380	if(n >= mod) {	193✔
381	return inverse_mod(ct_modulo(n, mod), mod);	19✔
382	}
383
384	return inverse_mod_general(n, mod).value_or(BigInt::zero());	317✔
385	}
386
387	} // namespace Botan

randombit / botan / 21768358452

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