/src/botan/src/lib/math/numbertheory/numthry.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | /* |
2 | | * Number Theory Functions |
3 | | * (C) 1999-2011,2016,2018,2019 Jack Lloyd |
4 | | * |
5 | | * Botan is released under the Simplified BSD License (see license.txt) |
6 | | */ |
7 | | |
8 | | #include <botan/numthry.h> |
9 | | #include <botan/reducer.h> |
10 | | #include <botan/monty.h> |
11 | | #include <botan/divide.h> |
12 | | #include <botan/rng.h> |
13 | | #include <botan/internal/ct_utils.h> |
14 | | #include <botan/internal/mp_core.h> |
15 | | #include <botan/internal/monty_exp.h> |
16 | | #include <botan/internal/primality.h> |
17 | | #include <algorithm> |
18 | | |
19 | | namespace Botan { |
20 | | |
21 | | namespace { |
22 | | |
23 | | void sub_abs(BigInt& z, const BigInt& x, const BigInt& y) |
24 | 0 | { |
25 | 0 | const size_t x_sw = x.sig_words(); |
26 | 0 | const size_t y_sw = y.sig_words(); |
27 | 0 | z.resize(std::max(x_sw, y_sw)); |
28 | 0 |
|
29 | 0 | bigint_sub_abs(z.mutable_data(), |
30 | 0 | x.data(), x_sw, |
31 | 0 | y.data(), y_sw); |
32 | 0 | } |
33 | | |
34 | | } |
35 | | |
36 | | /* |
37 | | * Return the number of 0 bits at the end of n |
38 | | */ |
39 | | size_t low_zero_bits(const BigInt& n) |
40 | 3.03M | { |
41 | 3.03M | size_t low_zero = 0; |
42 | 3.03M | |
43 | 3.03M | auto seen_nonempty_word = CT::Mask<word>::cleared(); |
44 | 3.03M | |
45 | 55.2M | for(size_t i = 0; i != n.size(); ++i) |
46 | 52.1M | { |
47 | 52.1M | const word x = n.word_at(i); |
48 | 52.1M | |
49 | 52.1M | // ctz(0) will return sizeof(word) |
50 | 52.1M | const size_t tz_x = ctz(x); |
51 | 52.1M | |
52 | 52.1M | // if x > 0 we want to count tz_x in total but not any |
53 | 52.1M | // further words, so set the mask after the addition |
54 | 52.1M | low_zero += seen_nonempty_word.if_not_set_return(tz_x); |
55 | 52.1M | |
56 | 52.1M | seen_nonempty_word |= CT::Mask<word>::expand(x); |
57 | 52.1M | } |
58 | 3.03M | |
59 | 3.03M | // if we saw no words with x > 0 then n == 0 and the value we have |
60 | 3.03M | // computed is meaningless. Instead return 0 in that case. |
61 | 3.03M | return seen_nonempty_word.if_set_return(low_zero); |
62 | 3.03M | } |
63 | | |
64 | | /* |
65 | | * Calculate the GCD |
66 | | */ |
67 | | BigInt gcd(const BigInt& a, const BigInt& b) |
68 | 0 | { |
69 | 0 | if(a.is_zero() || b.is_zero()) |
70 | 0 | return 0; |
71 | 0 | if(a == 1 || b == 1) |
72 | 0 | return 1; |
73 | 0 | |
74 | 0 | // See https://gcd.cr.yp.to/safegcd-20190413.pdf fig 1.2 |
75 | 0 | |
76 | 0 | BigInt f = a; |
77 | 0 | BigInt g = b; |
78 | 0 | f.const_time_poison(); |
79 | 0 | g.const_time_poison(); |
80 | 0 |
|
81 | 0 | f.set_sign(BigInt::Positive); |
82 | 0 | g.set_sign(BigInt::Positive); |
83 | 0 |
|
84 | 0 | const size_t common2s = std::min(low_zero_bits(f), low_zero_bits(g)); |
85 | 0 | CT::unpoison(common2s); |
86 | 0 |
|
87 | 0 | f >>= common2s; |
88 | 0 | g >>= common2s; |
89 | 0 |
|
90 | 0 | f.ct_cond_swap(f.is_even(), g); |
91 | 0 |
|
92 | 0 | int32_t delta = 1; |
93 | 0 |
|
94 | 0 | const size_t loop_cnt = 4 + 3*std::max(f.bits(), g.bits()); |
95 | 0 |
|
96 | 0 | BigInt newg, t; |
97 | 0 | for(size_t i = 0; i != loop_cnt; ++i) |
98 | 0 | { |
99 | 0 | sub_abs(newg, f, g); |
100 | 0 |
|
101 | 0 | const bool need_swap = (g.is_odd() && delta > 0); |
102 | 0 |
|
103 | 0 | // if(need_swap) delta *= -1 |
104 | 0 | delta *= CT::Mask<uint8_t>::expand(need_swap).select(0, 2) - 1; |
105 | 0 | f.ct_cond_swap(need_swap, g); |
106 | 0 | g.ct_cond_swap(need_swap, newg); |
107 | 0 |
|
108 | 0 | delta += 1; |
109 | 0 |
|
110 | 0 | g.ct_cond_add(g.is_odd(), f); |
111 | 0 | g >>= 1; |
112 | 0 | } |
113 | 0 |
|
114 | 0 | f <<= common2s; |
115 | 0 |
|
116 | 0 | f.const_time_unpoison(); |
117 | 0 | g.const_time_unpoison(); |
118 | 0 |
|
119 | 0 | return f; |
120 | 0 | } |
121 | | |
122 | | /* |
123 | | * Calculate the LCM |
124 | | */ |
125 | | BigInt lcm(const BigInt& a, const BigInt& b) |
126 | 0 | { |
127 | 0 | return ct_divide(a * b, gcd(a, b)); |
128 | 0 | } |
129 | | |
130 | | /* |
131 | | * Modular Exponentiation |
132 | | */ |
133 | | BigInt power_mod(const BigInt& base, const BigInt& exp, const BigInt& mod) |
134 | 63.9k | { |
135 | 63.9k | if(mod.is_negative() || mod == 1) |
136 | 18 | { |
137 | 18 | return 0; |
138 | 18 | } |
139 | 63.9k | |
140 | 63.9k | if(base.is_zero() || mod.is_zero()) |
141 | 13 | { |
142 | 13 | if(exp.is_zero()) |
143 | 1 | return 1; |
144 | 12 | return 0; |
145 | 12 | } |
146 | 63.9k | |
147 | 63.9k | Modular_Reducer reduce_mod(mod); |
148 | 63.9k | |
149 | 63.9k | const size_t exp_bits = exp.bits(); |
150 | 63.9k | |
151 | 63.9k | if(mod.is_odd()) |
152 | 63.3k | { |
153 | 63.3k | const size_t powm_window = 4; |
154 | 63.3k | |
155 | 63.3k | auto monty_mod = std::make_shared<Montgomery_Params>(mod, reduce_mod); |
156 | 63.3k | auto powm_base_mod = monty_precompute(monty_mod, reduce_mod.reduce(base), powm_window); |
157 | 63.3k | return monty_execute(*powm_base_mod, exp, exp_bits); |
158 | 63.3k | } |
159 | 556 | |
160 | 556 | /* |
161 | 556 | Support for even modulus is just a convenience and not considered |
162 | 556 | cryptographically important, so this implementation is slow ... |
163 | 556 | */ |
164 | 556 | BigInt accum = 1; |
165 | 556 | BigInt g = reduce_mod.reduce(base); |
166 | 556 | BigInt t; |
167 | 556 | |
168 | 253k | for(size_t i = 0; i != exp_bits; ++i) |
169 | 252k | { |
170 | 252k | t = reduce_mod.multiply(g, accum); |
171 | 252k | g = reduce_mod.square(g); |
172 | 252k | accum.ct_cond_assign(exp.get_bit(i), t); |
173 | 252k | } |
174 | 556 | return accum; |
175 | 556 | } |
176 | | |
177 | | |
178 | | BigInt is_perfect_square(const BigInt& C) |
179 | 94 | { |
180 | 94 | if(C < 1) |
181 | 0 | throw Invalid_Argument("is_perfect_square requires C >= 1"); |
182 | 94 | if(C == 1) |
183 | 0 | return 1; |
184 | 94 | |
185 | 94 | const size_t n = C.bits(); |
186 | 94 | const size_t m = (n + 1) / 2; |
187 | 94 | const BigInt B = C + BigInt::power_of_2(m); |
188 | 94 | |
189 | 94 | BigInt X = BigInt::power_of_2(m) - 1; |
190 | 94 | BigInt X2 = (X*X); |
191 | 94 | |
192 | 94 | for(;;) |
193 | 453 | { |
194 | 453 | X = (X2 + C) / (2*X); |
195 | 453 | X2 = (X*X); |
196 | 453 | |
197 | 453 | if(X2 < B) |
198 | 94 | break; |
199 | 453 | } |
200 | 94 | |
201 | 94 | if(X2 == C) |
202 | 0 | return X; |
203 | 94 | else |
204 | 94 | return 0; |
205 | 94 | } |
206 | | |
207 | | /* |
208 | | * Test for primality using Miller-Rabin |
209 | | */ |
210 | | bool is_prime(const BigInt& n, |
211 | | RandomNumberGenerator& rng, |
212 | | size_t prob, |
213 | | bool is_random) |
214 | 149 | { |
215 | 149 | if(n == 2) |
216 | 0 | return true; |
217 | 149 | if(n <= 1 || n.is_even()) |
218 | 0 | return false; |
219 | 149 | |
220 | 149 | const size_t n_bits = n.bits(); |
221 | 149 | |
222 | 149 | // Fast path testing for small numbers (<= 65521) |
223 | 149 | if(n_bits <= 16) |
224 | 0 | { |
225 | 0 | const uint16_t num = static_cast<uint16_t>(n.word_at(0)); |
226 | 0 |
|
227 | 0 | return std::binary_search(PRIMES, PRIMES + PRIME_TABLE_SIZE, num); |
228 | 0 | } |
229 | 149 | |
230 | 149 | Modular_Reducer mod_n(n); |
231 | 149 | |
232 | 149 | if(rng.is_seeded()) |
233 | 149 | { |
234 | 149 | const size_t t = miller_rabin_test_iterations(n_bits, prob, is_random); |
235 | 149 | |
236 | 149 | if(is_miller_rabin_probable_prime(n, mod_n, rng, t) == false) |
237 | 69 | return false; |
238 | 80 | |
239 | 80 | return is_lucas_probable_prime(n, mod_n); |
240 | 80 | } |
241 | 0 | else |
242 | 0 | { |
243 | 0 | return is_bailie_psw_probable_prime(n, mod_n); |
244 | 0 | } |
245 | 149 | } |
246 | | |
247 | | } |