/src/botan/build/include/botan/numthry.h
Line | Count | Source (jump to first uncovered line) |
1 | | /* |
2 | | * Number Theory Functions |
3 | | * (C) 1999-2007,2018 Jack Lloyd |
4 | | * |
5 | | * Botan is released under the Simplified BSD License (see license.txt) |
6 | | */ |
7 | | |
8 | | #ifndef BOTAN_NUMBER_THEORY_H_ |
9 | | #define BOTAN_NUMBER_THEORY_H_ |
10 | | |
11 | | #include <botan/bigint.h> |
12 | | |
13 | | namespace Botan { |
14 | | |
15 | | class RandomNumberGenerator; |
16 | | |
17 | | /** |
18 | | * Fused multiply-add |
19 | | * @param a an integer |
20 | | * @param b an integer |
21 | | * @param c an integer |
22 | | * @return (a*b)+c |
23 | | */ |
24 | | BigInt BOTAN_PUBLIC_API(2,0) mul_add(const BigInt& a, |
25 | | const BigInt& b, |
26 | | const BigInt& c); |
27 | | |
28 | | /** |
29 | | * Fused subtract-multiply |
30 | | * @param a an integer |
31 | | * @param b an integer |
32 | | * @param c an integer |
33 | | * @return (a-b)*c |
34 | | */ |
35 | | BigInt BOTAN_PUBLIC_API(2,0) sub_mul(const BigInt& a, |
36 | | const BigInt& b, |
37 | | const BigInt& c); |
38 | | |
39 | | /** |
40 | | * Fused multiply-subtract |
41 | | * @param a an integer |
42 | | * @param b an integer |
43 | | * @param c an integer |
44 | | * @return (a*b)-c |
45 | | */ |
46 | | BigInt BOTAN_PUBLIC_API(2,0) mul_sub(const BigInt& a, |
47 | | const BigInt& b, |
48 | | const BigInt& c); |
49 | | |
50 | | /** |
51 | | * Return the absolute value |
52 | | * @param n an integer |
53 | | * @return absolute value of n |
54 | | */ |
55 | 0 | inline BigInt abs(const BigInt& n) { return n.abs(); } |
56 | | |
57 | | /** |
58 | | * Compute the greatest common divisor |
59 | | * @param x a positive integer |
60 | | * @param y a positive integer |
61 | | * @return gcd(x,y) |
62 | | */ |
63 | | BigInt BOTAN_PUBLIC_API(2,0) gcd(const BigInt& x, const BigInt& y); |
64 | | |
65 | | /** |
66 | | * Least common multiple |
67 | | * @param x a positive integer |
68 | | * @param y a positive integer |
69 | | * @return z, smallest integer such that z % x == 0 and z % y == 0 |
70 | | */ |
71 | | BigInt BOTAN_PUBLIC_API(2,0) lcm(const BigInt& x, const BigInt& y); |
72 | | |
73 | | /** |
74 | | * @param x an integer |
75 | | * @return (x*x) |
76 | | */ |
77 | | BigInt BOTAN_PUBLIC_API(2,0) square(const BigInt& x); |
78 | | |
79 | | /** |
80 | | * Modular inversion. This algorithm is const time with respect to x, |
81 | | * as long as x is less than modulus. It also avoids leaking |
82 | | * information about the modulus, except that it does leak which of 3 |
83 | | * categories the modulus is in: an odd integer, a power of 2, or some |
84 | | * other even number, and if the modulus is even, leaks the power of 2 |
85 | | * which divides the modulus. |
86 | | * |
87 | | * @param x a positive integer |
88 | | * @param modulus a positive integer |
89 | | * @return y st (x*y) % modulus == 1 or 0 if no such value |
90 | | */ |
91 | | BigInt BOTAN_PUBLIC_API(2,0) inverse_mod(const BigInt& x, |
92 | | const BigInt& modulus); |
93 | | |
94 | | /** |
95 | | * Deprecated modular inversion function. Use inverse_mod instead. |
96 | | * @param x a positive integer |
97 | | * @param modulus a positive integer |
98 | | * @return y st (x*y) % modulus == 1 or 0 if no such value |
99 | | */ |
100 | | BigInt BOTAN_DEPRECATED_API("Use inverse_mod") inverse_euclid(const BigInt& x, const BigInt& modulus); |
101 | | |
102 | | /** |
103 | | * Deprecated modular inversion function. Use inverse_mod instead. |
104 | | */ |
105 | | BigInt BOTAN_DEPRECATED_API("Use inverse_mod") ct_inverse_mod_odd_modulus(const BigInt& n, const BigInt& mod); |
106 | | |
107 | | /** |
108 | | * Return a^-1 * 2^k mod b |
109 | | * Returns k, between n and 2n |
110 | | * Not const time |
111 | | */ |
112 | | size_t BOTAN_PUBLIC_API(2,0) almost_montgomery_inverse(BigInt& result, |
113 | | const BigInt& a, |
114 | | const BigInt& b); |
115 | | |
116 | | /** |
117 | | * Call almost_montgomery_inverse and correct the result to a^-1 mod b |
118 | | */ |
119 | | BigInt BOTAN_PUBLIC_API(2,0) normalized_montgomery_inverse(const BigInt& a, const BigInt& b); |
120 | | |
121 | | |
122 | | /** |
123 | | * Compute the Jacobi symbol. If n is prime, this is equivalent |
124 | | * to the Legendre symbol. |
125 | | * @see http://mathworld.wolfram.com/JacobiSymbol.html |
126 | | * |
127 | | * @param a is a non-negative integer |
128 | | * @param n is an odd integer > 1 |
129 | | * @return (n / m) |
130 | | */ |
131 | | int32_t BOTAN_PUBLIC_API(2,0) jacobi(const BigInt& a, const BigInt& n); |
132 | | |
133 | | /** |
134 | | * Modular exponentation |
135 | | * @param b an integer base |
136 | | * @param x a positive exponent |
137 | | * @param m a positive modulus |
138 | | * @return (b^x) % m |
139 | | */ |
140 | | BigInt BOTAN_PUBLIC_API(2,0) power_mod(const BigInt& b, |
141 | | const BigInt& x, |
142 | | const BigInt& m); |
143 | | |
144 | | /** |
145 | | * Compute the square root of x modulo a prime using the |
146 | | * Shanks-Tonnelli algorithm |
147 | | * |
148 | | * @param x the input |
149 | | * @param p the prime |
150 | | * @return y such that (y*y)%p == x, or -1 if no such integer |
151 | | */ |
152 | | BigInt BOTAN_PUBLIC_API(2,0) ressol(const BigInt& x, const BigInt& p); |
153 | | |
154 | | /* |
155 | | * Compute -input^-1 mod 2^MP_WORD_BITS. Throws an exception if input |
156 | | * is even. If input is odd, then input and 2^n are relatively prime |
157 | | * and an inverse exists. |
158 | | */ |
159 | | word BOTAN_PUBLIC_API(2,0) monty_inverse(word input); |
160 | | |
161 | | /** |
162 | | * @param x a positive integer |
163 | | * @return count of the zero bits in x, or, equivalently, the largest |
164 | | * value of n such that 2^n divides x evenly. Returns zero if |
165 | | * n is less than or equal to zero. |
166 | | */ |
167 | | size_t BOTAN_PUBLIC_API(2,0) low_zero_bits(const BigInt& x); |
168 | | |
169 | | /** |
170 | | * Check for primality |
171 | | * @param n a positive integer to test for primality |
172 | | * @param rng a random number generator |
173 | | * @param prob chance of false positive is bounded by 1/2**prob |
174 | | * @param is_random true if n was randomly chosen by us |
175 | | * @return true if all primality tests passed, otherwise false |
176 | | */ |
177 | | bool BOTAN_PUBLIC_API(2,0) is_prime(const BigInt& n, |
178 | | RandomNumberGenerator& rng, |
179 | | size_t prob = 64, |
180 | | bool is_random = false); |
181 | | |
182 | | /** |
183 | | * Test if the positive integer x is a perfect square ie if there |
184 | | * exists some positive integer y st y*y == x |
185 | | * See FIPS 186-4 sec C.4 |
186 | | * @return 0 if the integer is not a perfect square, otherwise |
187 | | * returns the positive y st y*y == x |
188 | | */ |
189 | | BigInt BOTAN_PUBLIC_API(2,8) is_perfect_square(const BigInt& x); |
190 | | |
191 | | inline bool quick_check_prime(const BigInt& n, RandomNumberGenerator& rng) |
192 | 0 | { return is_prime(n, rng, 32); } |
193 | | |
194 | | inline bool check_prime(const BigInt& n, RandomNumberGenerator& rng) |
195 | 0 | { return is_prime(n, rng, 56); } |
196 | | |
197 | | inline bool verify_prime(const BigInt& n, RandomNumberGenerator& rng) |
198 | 0 | { return is_prime(n, rng, 80); } |
199 | | |
200 | | /** |
201 | | * Randomly generate a prime suitable for discrete logarithm parameters |
202 | | * @param rng a random number generator |
203 | | * @param bits how large the resulting prime should be in bits |
204 | | * @param coprime a positive integer that (prime - 1) should be coprime to |
205 | | * @param equiv a non-negative number that the result should be |
206 | | equivalent to modulo equiv_mod |
207 | | * @param equiv_mod the modulus equiv should be checked against |
208 | | * @param prob use test so false positive is bounded by 1/2**prob |
209 | | * @return random prime with the specified criteria |
210 | | */ |
211 | | BigInt BOTAN_PUBLIC_API(2,0) random_prime(RandomNumberGenerator& rng, |
212 | | size_t bits, |
213 | | const BigInt& coprime = 0, |
214 | | size_t equiv = 1, |
215 | | size_t equiv_mod = 2, |
216 | | size_t prob = 128); |
217 | | |
218 | | /** |
219 | | * Generate a prime suitable for RSA p/q |
220 | | * @param keygen_rng a random number generator |
221 | | * @param prime_test_rng a random number generator |
222 | | * @param bits how large the resulting prime should be in bits (must be >= 512) |
223 | | * @param coprime a positive integer that (prime - 1) should be coprime to |
224 | | * @param prob use test so false positive is bounded by 1/2**prob |
225 | | * @return random prime with the specified criteria |
226 | | */ |
227 | | BigInt BOTAN_PUBLIC_API(2,7) generate_rsa_prime(RandomNumberGenerator& keygen_rng, |
228 | | RandomNumberGenerator& prime_test_rng, |
229 | | size_t bits, |
230 | | const BigInt& coprime, |
231 | | size_t prob = 128); |
232 | | |
233 | | /** |
234 | | * Return a 'safe' prime, of the form p=2*q+1 with q prime |
235 | | * @param rng a random number generator |
236 | | * @param bits is how long the resulting prime should be |
237 | | * @return prime randomly chosen from safe primes of length bits |
238 | | */ |
239 | | BigInt BOTAN_PUBLIC_API(2,0) random_safe_prime(RandomNumberGenerator& rng, |
240 | | size_t bits); |
241 | | |
242 | | /** |
243 | | * Generate DSA parameters using the FIPS 186 kosherizer |
244 | | * @param rng a random number generator |
245 | | * @param p_out where the prime p will be stored |
246 | | * @param q_out where the prime q will be stored |
247 | | * @param pbits how long p will be in bits |
248 | | * @param qbits how long q will be in bits |
249 | | * @return random seed used to generate this parameter set |
250 | | */ |
251 | | std::vector<uint8_t> BOTAN_PUBLIC_API(2,0) |
252 | | generate_dsa_primes(RandomNumberGenerator& rng, |
253 | | BigInt& p_out, BigInt& q_out, |
254 | | size_t pbits, size_t qbits); |
255 | | |
256 | | /** |
257 | | * Generate DSA parameters using the FIPS 186 kosherizer |
258 | | * @param rng a random number generator |
259 | | * @param p_out where the prime p will be stored |
260 | | * @param q_out where the prime q will be stored |
261 | | * @param pbits how long p will be in bits |
262 | | * @param qbits how long q will be in bits |
263 | | * @param seed the seed used to generate the parameters |
264 | | * @param offset optional offset from seed to start searching at |
265 | | * @return true if seed generated a valid DSA parameter set, otherwise |
266 | | false. p_out and q_out are only valid if true was returned. |
267 | | */ |
268 | | bool BOTAN_PUBLIC_API(2,0) |
269 | | generate_dsa_primes(RandomNumberGenerator& rng, |
270 | | BigInt& p_out, BigInt& q_out, |
271 | | size_t pbits, size_t qbits, |
272 | | const std::vector<uint8_t>& seed, |
273 | | size_t offset = 0); |
274 | | |
275 | | /** |
276 | | * The size of the PRIMES[] array |
277 | | */ |
278 | | const size_t PRIME_TABLE_SIZE = 6541; |
279 | | |
280 | | /** |
281 | | * A const array of all primes less than 65535 |
282 | | */ |
283 | | extern const uint16_t BOTAN_PUBLIC_API(2,0) PRIMES[]; |
284 | | |
285 | | } |
286 | | |
287 | | #endif |