Botan 2.19.1
Crypto and TLS for C&
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
13namespace Botan {
14
15class 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*/
24BigInt 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*/
36BigInt 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*/
48BigInt 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*/
58inline 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*/
66BigInt 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*/
74BigInt BOTAN_PUBLIC_API(2,0) lcm(const BigInt& x, const BigInt& y);
75
76/**
77* @param x an integer
78* @return (x*x)
79*/
80BigInt 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*/
94BigInt 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*/
103BigInt 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*/
108BigInt 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*/
115size_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*/
123BigInt 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*/
136int32_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*/
145BigInt 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*/
157BigInt 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*/
164word 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*/
173size_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*/
183bool 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*/
195BigInt BOTAN_PUBLIC_API(2,8) is_perfect_square(const BigInt& x);
196
197inline bool BOTAN_DEPRECATED("Use is_prime")
199 { return is_prime(n, rng, 32); }
200
201inline bool BOTAN_DEPRECATED("Use is_prime")
203 { return is_prime(n, rng, 56); }
204
205inline 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*/
220BigInt 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*/
236BigInt 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*/
248BigInt 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*/
260std::vector<uint8_t> BOTAN_PUBLIC_API(2,0) BOTAN_DEPRECATED("Use DL_Group")
261generate_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*/
277bool BOTAN_PUBLIC_API(2,0) BOTAN_DEPRECATED("Use DL_Group")
278generate_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*/
287const size_t PRIME_TABLE_SIZE = 6541;
288
289/**
290* A const array of all odd primes less than 65535
291*/
292extern const uint16_t BOTAN_PUBLIC_API(2,0) PRIMES[];
293
294}
295
296#endif
BigInt abs() const
Definition: bigint.cpp:392
#define BOTAN_PUBLIC_API(maj, min)
Definition: compiler.h:31
#define BOTAN_DEPRECATED_API(msg)
Definition: compiler.h:37
Definition: alg_id.cpp:13
BigInt power_mod(const BigInt &base, const BigInt &exp, const BigInt &mod)
Definition: numthry.cpp:151
BigInt inverse_euclid(const BigInt &x, const BigInt &modulus)
Definition: mod_inv.cpp:317
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
BigInt lcm(const BigInt &a, const BigInt &b)
Definition: numthry.cpp:143
BigInt square(const BigInt &x)
Definition: mp_numth.cpp:19
const uint16_t PRIMES[]
Definition: primes.cpp:12
size_t low_zero_bits(const BigInt &n)
Definition: numthry.cpp:39
BigInt abs(const BigInt &n)
Definition: numthry.h:58
const size_t PRIME_TABLE_SIZE
Definition: numthry.h:287
word monty_inverse(word a)
Definition: mod_inv.cpp:327
bool is_prime(const BigInt &n, RandomNumberGenerator &rng, size_t prob, bool is_random)
Definition: numthry.cpp:228
bool quick_check_prime(const BigInt &n, RandomNumberGenerator &rng)
Definition: numthry.h:198
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 ct_inverse_mod_odd_modulus(const BigInt &n, const BigInt &mod)
Definition: mod_inv.cpp:322
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
BigInt mul_sub(const BigInt &a, const BigInt &b, const BigInt &c)
Definition: mp_numth.cpp:73
bool verify_prime(const BigInt &n, RandomNumberGenerator &rng)
Definition: numthry.h:206
BigInt gcd(const BigInt &a, const BigInt &b)
Definition: numthry.cpp:81
BigInt ressol(const BigInt &x, const BigInt &p)
Definition: ressol.cpp:16
BigInt normalized_montgomery_inverse(const BigInt &a, const BigInt &p)
Definition: mod_inv.cpp:75
BigInt is_perfect_square(const BigInt &C)
Definition: numthry.cpp:196
BigInt sub_mul(const BigInt &a, const BigInt &b, const BigInt &c)
Definition: mp_numth.cpp:59
int32_t jacobi(const BigInt &a, const BigInt &n)
Definition: jacobi.cpp:15
BigInt random_safe_prime(RandomNumberGenerator &rng, size_t bits)
Definition: make_prm.cpp:268
BigInt inverse_mod(const BigInt &n, const BigInt &mod)
Definition: mod_inv.cpp:250
size_t almost_montgomery_inverse(BigInt &result, const BigInt &a, const BigInt &p)
Definition: mod_inv.cpp:27
BigInt mul_add(const BigInt &a, const BigInt &b, const BigInt &c)
Definition: mp_numth.cpp:30
bool check_prime(const BigInt &n, RandomNumberGenerator &rng)
Definition: numthry.h:202
Definition: bigint.h:1143