/src/botan/build/include/botan/numthry.h

Source (jump to first uncovered line)
/*
* Number Theory Functions
* (C) 1999-2007,2018 Jack Lloyd
*
* Botan is released under the Simplified BSD License (see license.txt)
*/

#ifndef BOTAN_NUMBER_THEORY_H_
#define BOTAN_NUMBER_THEORY_H_

#include <botan/bigint.h>

namespace Botan {

class RandomNumberGenerator;

/**
* Fused multiply-add
* @param a an integer
* @param b an integer
* @param c an integer
* @return (a*b)+c
*/
BigInt BOTAN_PUBLIC_API(2,0) mul_add(const BigInt& a,
                                     const BigInt& b,
                                     const BigInt& c);

/**
* Fused subtract-multiply
* @param a an integer
* @param b an integer
* @param c an integer
* @return (a-b)*c
*/
BigInt BOTAN_PUBLIC_API(2,0) sub_mul(const BigInt& a,
                                     const BigInt& b,
                                     const BigInt& c);

/**
* Fused multiply-subtract
* @param a an integer
* @param b an integer
* @param c an integer
* @return (a*b)-c
*/
BigInt BOTAN_PUBLIC_API(2,0) mul_sub(const BigInt& a,
                                     const BigInt& b,
                                     const BigInt& c);

/**
* Return the absolute value
* @param n an integer
* @return absolute value of n
*/
inline BigInt abs(const BigInt& n) { return n.abs(); }

/**
* Compute the greatest common divisor
* @param x a positive integer
* @param y a positive integer
* @return gcd(x,y)
*/
BigInt BOTAN_PUBLIC_API(2,0) gcd(const BigInt& x, const BigInt& y);

/**
* Least common multiple
* @param x a positive integer
* @param y a positive integer
* @return z, smallest integer such that z % x == 0 and z % y == 0
*/
BigInt BOTAN_PUBLIC_API(2,0) lcm(const BigInt& x, const BigInt& y);

/**
* @param x an integer
* @return (x*x)
*/
BigInt BOTAN_PUBLIC_API(2,0) square(const BigInt& x);

/**
* Modular inversion
* @param x a positive integer
* @param modulus a positive integer
* @return y st (x*y) % modulus == 1 or 0 if no such value
* Not const time
*/
BigInt BOTAN_PUBLIC_API(2,0) inverse_mod(const BigInt& x,
                                         const BigInt& modulus);

/**
* Modular inversion using extended binary Euclidian algorithm
* @param x a positive integer
* @param modulus a positive integer
* @return y st (x*y) % modulus == 1 or 0 if no such value
* Not const time
*/
BigInt BOTAN_PUBLIC_API(2,5) inverse_euclid(const BigInt& x,
                                            const BigInt& modulus);

/**
* Const time modular inversion
* Requires the modulus be odd
*/
BigInt BOTAN_PUBLIC_API(2,0) ct_inverse_mod_odd_modulus(const BigInt& n, const BigInt& mod);

/**
* Return a^-1 * 2^k mod b
* Returns k, between n and 2n
* Not const time
*/
size_t BOTAN_PUBLIC_API(2,0) almost_montgomery_inverse(BigInt& result,
                                                       const BigInt& a,
                                                       const BigInt& b);

/**
* Call almost_montgomery_inverse and correct the result to a^-1 mod b
*/
BigInt BOTAN_PUBLIC_API(2,0) normalized_montgomery_inverse(const BigInt& a, const BigInt& b);


/**
* Compute the Jacobi symbol. If n is prime, this is equivalent
* to the Legendre symbol.
* @see http://mathworld.wolfram.com/JacobiSymbol.html
*
* @param a is a non-negative integer
* @param n is an odd integer > 1
* @return (n / m)
*/
int32_t BOTAN_PUBLIC_API(2,0) jacobi(const BigInt& a, const BigInt& n);

/**
* Modular exponentation
* @param b an integer base
* @param x a positive exponent
* @param m a positive modulus
* @return (b^x) % m
*/
BigInt BOTAN_PUBLIC_API(2,0) power_mod(const BigInt& b,
                                       const BigInt& x,
                                       const BigInt& m);

/**
* Compute the square root of x modulo a prime using the
* Shanks-Tonnelli algorithm
*
* @param x the input
* @param p the prime
* @return y such that (y*y)%p == x, or -1 if no such integer
*/
BigInt BOTAN_PUBLIC_API(2,0) ressol(const BigInt& x, const BigInt& p);

/*
* Compute -input^-1 mod 2^MP_WORD_BITS. Throws an exception if input
* is even. If input is odd, then input and 2^n are relatively prime
* and an inverse exists.
*/
word BOTAN_PUBLIC_API(2,0) monty_inverse(word input);

/**
* @param x a positive integer
* @return count of the zero bits in x, or, equivalently, the largest
*         value of n such that 2^n divides x evenly. Returns zero if
*         n is less than or equal to zero.
*/
size_t BOTAN_PUBLIC_API(2,0) low_zero_bits(const BigInt& x);

/**
* Check for primality
* @param n a positive integer to test for primality
* @param rng a random number generator
* @param prob chance of false positive is bounded by 1/2**prob
* @param is_random true if n was randomly chosen by us
* @return true if all primality tests passed, otherwise false
*/
bool BOTAN_PUBLIC_API(2,0) is_prime(const BigInt& n,
                                    RandomNumberGenerator& rng,
                                    size_t prob = 64,
                                    bool is_random = false);

/**
* Test if the positive integer x is a perfect square ie if there
* exists some positive integer y st y*y == x
* See FIPS 186-4 sec C.4
* @return 0 if the integer is not a perfect square, otherwise
*         returns the positive y st y*y == x
*/
BigInt BOTAN_PUBLIC_API(2,8) is_perfect_square(const BigInt& x);

inline bool quick_check_prime(const BigInt& n, RandomNumberGenerator& rng)
   { return is_prime(n, rng, 32); }

inline bool check_prime(const BigInt& n, RandomNumberGenerator& rng)
   { return is_prime(n, rng, 56); }

inline bool verify_prime(const BigInt& n, RandomNumberGenerator& rng)
   { return is_prime(n, rng, 80); }

/**
* Randomly generate a prime suitable for discrete logarithm parameters
* @param rng a random number generator
* @param bits how large the resulting prime should be in bits
* @param coprime a positive integer that (prime - 1) should be coprime to
* @param equiv a non-negative number that the result should be
               equivalent to modulo equiv_mod
* @param equiv_mod the modulus equiv should be checked against
* @param prob use test so false positive is bounded by 1/2**prob
* @return random prime with the specified criteria
*/
BigInt BOTAN_PUBLIC_API(2,0) random_prime(RandomNumberGenerator& rng,
                                          size_t bits,
                                          const BigInt& coprime = 0,
                                          size_t equiv = 1,
                                          size_t equiv_mod = 2,
                                          size_t prob = 128);

/**
* Generate a prime suitable for RSA p/q
* @param keygen_rng a random number generator
* @param prime_test_rng a random number generator
* @param bits how large the resulting prime should be in bits (must be >= 512)
* @param coprime a positive integer that (prime - 1) should be coprime to
* @param prob use test so false positive is bounded by 1/2**prob
* @return random prime with the specified criteria
*/
BigInt BOTAN_PUBLIC_API(2,7) generate_rsa_prime(RandomNumberGenerator& keygen_rng,
                                                RandomNumberGenerator& prime_test_rng,
                                                size_t bits,
                                                const BigInt& coprime,
                                                size_t prob = 128);

/**
* Return a 'safe' prime, of the form p=2*q+1 with q prime
* @param rng a random number generator
* @param bits is how long the resulting prime should be
* @return prime randomly chosen from safe primes of length bits
*/
BigInt BOTAN_PUBLIC_API(2,0) random_safe_prime(RandomNumberGenerator& rng,
                                               size_t bits);

/**
* Generate DSA parameters using the FIPS 186 kosherizer
* @param rng a random number generator
* @param p_out where the prime p will be stored
* @param q_out where the prime q will be stored
* @param pbits how long p will be in bits
* @param qbits how long q will be in bits
* @return random seed used to generate this parameter set
*/
std::vector<uint8_t> BOTAN_PUBLIC_API(2,0)
generate_dsa_primes(RandomNumberGenerator& rng,
                    BigInt& p_out, BigInt& q_out,
                    size_t pbits, size_t qbits);

/**
* Generate DSA parameters using the FIPS 186 kosherizer
* @param rng a random number generator
* @param p_out where the prime p will be stored
* @param q_out where the prime q will be stored
* @param pbits how long p will be in bits
* @param qbits how long q will be in bits
* @param seed the seed used to generate the parameters
* @param offset optional offset from seed to start searching at
* @return true if seed generated a valid DSA parameter set, otherwise
          false. p_out and q_out are only valid if true was returned.
*/
bool BOTAN_PUBLIC_API(2,0)
generate_dsa_primes(RandomNumberGenerator& rng,
                    BigInt& p_out, BigInt& q_out,
                    size_t pbits, size_t qbits,
                    const std::vector<uint8_t>& seed,
                    size_t offset = 0);

/**
* The size of the PRIMES[] array
*/
const size_t PRIME_TABLE_SIZE = 6541;

/**
* A const array of all primes less than 65535
*/
extern const uint16_t BOTAN_PUBLIC_API(2,0) PRIMES[];

}

#endif

Coverage Report

Created: 2020-02-14 15:38

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
81		* @param x a positive integer
82		* @param modulus a positive integer
83		* @return y st (x*y) % modulus == 1 or 0 if no such value
84		* Not const time
85		*/
86		BigInt BOTAN_PUBLIC_API(2,0) inverse_mod(const BigInt& x,
87		const BigInt& modulus);
88
89		/**
90		* Modular inversion using extended binary Euclidian algorithm
91		* @param x a positive integer
92		* @param modulus a positive integer
93		* @return y st (x*y) % modulus == 1 or 0 if no such value
94		* Not const time
95		*/
96		BigInt BOTAN_PUBLIC_API(2,5) inverse_euclid(const BigInt& x,
97		const BigInt& modulus);
98
99		/**
100		* Const time modular inversion
101		* Requires the modulus be odd
102		*/
103		BigInt BOTAN_PUBLIC_API(2,0) ct_inverse_mod_odd_modulus(const BigInt& n, const BigInt& mod);
104
105		/**
106		* Return a^-1 * 2^k mod b
107		* Returns k, between n and 2n
108		* Not const time
109		*/
110		size_t BOTAN_PUBLIC_API(2,0) almost_montgomery_inverse(BigInt& result,
111		const BigInt& a,
112		const BigInt& b);
113
114		/**
115		* Call almost_montgomery_inverse and correct the result to a^-1 mod b
116		*/
117		BigInt BOTAN_PUBLIC_API(2,0) normalized_montgomery_inverse(const BigInt& a, const BigInt& b);
118
119
120		/**
121		* Compute the Jacobi symbol. If n is prime, this is equivalent
122		* to the Legendre symbol.
123		* @see http://mathworld.wolfram.com/JacobiSymbol.html
124		*
125		* @param a is a non-negative integer
126		* @param n is an odd integer > 1
127		* @return (n / m)
128		*/
129		int32_t BOTAN_PUBLIC_API(2,0) jacobi(const BigInt& a, const BigInt& n);
130
131		/**
132		* Modular exponentation
133		* @param b an integer base
134		* @param x a positive exponent
135		* @param m a positive modulus
136		* @return (b^x) % m
137		*/
138		BigInt BOTAN_PUBLIC_API(2,0) power_mod(const BigInt& b,
139		const BigInt& x,
140		const BigInt& m);
141
142		/**
143		* Compute the square root of x modulo a prime using the
144		* Shanks-Tonnelli algorithm
145		*
146		* @param x the input
147		* @param p the prime
148		* @return y such that (y*y)%p == x, or -1 if no such integer
149		*/
150		BigInt BOTAN_PUBLIC_API(2,0) ressol(const BigInt& x, const BigInt& p);
151
152		/*
153		* Compute -input^-1 mod 2^MP_WORD_BITS. Throws an exception if input
154		* is even. If input is odd, then input and 2^n are relatively prime
155		* and an inverse exists.
156		*/
157		word BOTAN_PUBLIC_API(2,0) monty_inverse(word input);
158
159		/**
160		* @param x a positive integer
161		* @return count of the zero bits in x, or, equivalently, the largest
162		* value of n such that 2^n divides x evenly. Returns zero if
163		* n is less than or equal to zero.
164		*/
165		size_t BOTAN_PUBLIC_API(2,0) low_zero_bits(const BigInt& x);
166
167		/**
168		* Check for primality
169		* @param n a positive integer to test for primality
170		* @param rng a random number generator
171		* @param prob chance of false positive is bounded by 1/2**prob
172		* @param is_random true if n was randomly chosen by us
173		* @return true if all primality tests passed, otherwise false
174		*/
175		bool BOTAN_PUBLIC_API(2,0) is_prime(const BigInt& n,
176		RandomNumberGenerator& rng,
177		size_t prob = 64,
178		bool is_random = false);
179
180		/**
181		* Test if the positive integer x is a perfect square ie if there
182		* exists some positive integer y st y*y == x
183		* See FIPS 186-4 sec C.4
184		* @return 0 if the integer is not a perfect square, otherwise
185		* returns the positive y st y*y == x
186		*/
187		BigInt BOTAN_PUBLIC_API(2,8) is_perfect_square(const BigInt& x);
188
189		inline bool quick_check_prime(const BigInt& n, RandomNumberGenerator& rng)
190	0	{ return is_prime(n, rng, 32); }
191
192		inline bool check_prime(const BigInt& n, RandomNumberGenerator& rng)
193	0	{ return is_prime(n, rng, 56); }
194
195		inline bool verify_prime(const BigInt& n, RandomNumberGenerator& rng)
196	0	{ return is_prime(n, rng, 80); }
197
198		/**
199		* Randomly generate a prime suitable for discrete logarithm parameters
200		* @param rng a random number generator
201		* @param bits how large the resulting prime should be in bits
202		* @param coprime a positive integer that (prime - 1) should be coprime to
203		* @param equiv a non-negative number that the result should be
204		equivalent to modulo equiv_mod
205		* @param equiv_mod the modulus equiv should be checked against
206		* @param prob use test so false positive is bounded by 1/2**prob
207		* @return random prime with the specified criteria
208		*/
209		BigInt BOTAN_PUBLIC_API(2,0) random_prime(RandomNumberGenerator& rng,
210		size_t bits,
211		const BigInt& coprime = 0,
212		size_t equiv = 1,
213		size_t equiv_mod = 2,
214		size_t prob = 128);
215
216		/**
217		* Generate a prime suitable for RSA p/q
218		* @param keygen_rng a random number generator
219		* @param prime_test_rng a random number generator
220		* @param bits how large the resulting prime should be in bits (must be >= 512)
221		* @param coprime a positive integer that (prime - 1) should be coprime to
222		* @param prob use test so false positive is bounded by 1/2**prob
223		* @return random prime with the specified criteria
224		*/
225		BigInt BOTAN_PUBLIC_API(2,7) generate_rsa_prime(RandomNumberGenerator& keygen_rng,
226		RandomNumberGenerator& prime_test_rng,
227		size_t bits,
228		const BigInt& coprime,
229		size_t prob = 128);
230
231		/**
232		* Return a 'safe' prime, of the form p=2*q+1 with q prime
233		* @param rng a random number generator
234		* @param bits is how long the resulting prime should be
235		* @return prime randomly chosen from safe primes of length bits
236		*/
237		BigInt BOTAN_PUBLIC_API(2,0) random_safe_prime(RandomNumberGenerator& rng,
238		size_t bits);
239
240		/**
241		* Generate DSA parameters using the FIPS 186 kosherizer
242		* @param rng a random number generator
243		* @param p_out where the prime p will be stored
244		* @param q_out where the prime q will be stored
245		* @param pbits how long p will be in bits
246		* @param qbits how long q will be in bits
247		* @return random seed used to generate this parameter set
248		*/
249		std::vector<uint8_t> BOTAN_PUBLIC_API(2,0)
250		generate_dsa_primes(RandomNumberGenerator& rng,
251		BigInt& p_out, BigInt& q_out,
252		size_t pbits, size_t qbits);
253
254		/**
255		* Generate DSA parameters using the FIPS 186 kosherizer
256		* @param rng a random number generator
257		* @param p_out where the prime p will be stored
258		* @param q_out where the prime q will be stored
259		* @param pbits how long p will be in bits
260		* @param qbits how long q will be in bits
261		* @param seed the seed used to generate the parameters
262		* @param offset optional offset from seed to start searching at
263		* @return true if seed generated a valid DSA parameter set, otherwise
264		false. p_out and q_out are only valid if true was returned.
265		*/
266		bool BOTAN_PUBLIC_API(2,0)
267		generate_dsa_primes(RandomNumberGenerator& rng,
268		BigInt& p_out, BigInt& q_out,
269		size_t pbits, size_t qbits,
270		const std::vector<uint8_t>& seed,
271		size_t offset = 0);
272
273		/**
274		* The size of the PRIMES[] array
275		*/
276		const size_t PRIME_TABLE_SIZE = 6541;
277
278		/**
279		* A const array of all primes less than 65535
280		*/
281		extern const uint16_t BOTAN_PUBLIC_API(2,0) PRIMES[];
282
283		}
284
285		#endif