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