Botan  2.10.0
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) 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 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  { return is_prime(n, rng, 32); }
191 
192 inline bool check_prime(const BigInt& n, RandomNumberGenerator& rng)
193  { return is_prime(n, rng, 56); }
194 
195 inline bool verify_prime(const BigInt& n, RandomNumberGenerator& rng)
196  { 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
const size_t PRIME_TABLE_SIZE
Definition: numthry.h:276
bool RandomNumberGenerator size_t bool is_random
Definition: numthry.h:178
BigInt const BigInt & x
Definition: numthry.h:139
BigInt mul_add(const BigInt &a, const BigInt &b, const BigInt &c)
Definition: mp_numth.cpp:30
bool RandomNumberGenerator & rng
Definition: numthry.h:176
size_t low_zero_bits(const BigInt &n)
Definition: numthry.cpp:26
BigInt size_t n
Definition: bigint.h:1096
BigInt gcd(const BigInt &a, const BigInt &b)
Definition: numthry.cpp:52
bool BigInt BigInt size_t size_t const std::vector< uint8_t > size_t offset
Definition: numthry.h:271
bool const OID & b
Definition: asn1_oid.h:109
BigInt power_mod(const BigInt &base, const BigInt &exp, const BigInt &mod)
Definition: numthry.cpp:416
BigInt inverse_euclid(const BigInt &n, const BigInt &mod)
Definition: numthry.cpp:305
BigInt mul_sub(const BigInt &a, const BigInt &b, const BigInt &c)
Definition: mp_numth.cpp:73
BigInt size_t bits
Definition: numthry.h:210
bool quick_check_prime(const BigInt &n, RandomNumberGenerator &rng)
Definition: numthry.h:189
Definition: bigint.h:1136
BigInt ct_inverse_mod_odd_modulus(const BigInt &n, const BigInt &mod)
Definition: numthry.cpp:165
BigInt normalized_montgomery_inverse(const BigInt &a, const BigInt &p)
Definition: numthry.cpp:150
bool is_prime(const BigInt &n, RandomNumberGenerator &rng, size_t prob, bool is_random)
Definition: numthry.cpp:488
std::vector< uint8_t > BigInt BigInt size_t pbits
Definition: numthry.h:251
BigInt ressol(const BigInt &a, const BigInt &p)
Definition: ressol.cpp:17
BigInt sub_mul(const BigInt &a, const BigInt &b, const BigInt &c)
Definition: mp_numth.cpp:59
bool BigInt BigInt size_t size_t const std::vector< uint8_t > & seed
Definition: numthry.h:268
BigInt const BigInt & mod
Definition: numthry.h:103
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 const BigInt & m
Definition: bigint.h:1094
BigInt abs(const BigInt &n)
Definition: numthry.h:55
const uint16_t PRIMES[PRIME_TABLE_SIZE+1]
Definition: primes.cpp:12
bool RandomNumberGenerator size_t prob
Definition: numthry.h:177
size_t const BigInt & a
Definition: numthry.h:111
BigInt const BigInt & p
Definition: numthry.h:150
BigInt lcm(const BigInt &a, const BigInt &b)
Definition: numthry.cpp:85
bool verify_prime(const BigInt &n, RandomNumberGenerator &rng)
Definition: numthry.h:195
BigInt random_safe_prime(RandomNumberGenerator &rng, size_t bits)
Definition: make_prm.cpp:263
BigInt is_perfect_square(const BigInt &C)
Definition: numthry.cpp:456
BigInt size_t const BigInt & coprime
Definition: numthry.h:211
BigInt inverse_mod(const BigInt &n, const BigInt &mod)
Definition: numthry.cpp:290
BigInt square(const BigInt &x)
Definition: mp_numth.cpp:19
std::vector< uint8_t > BigInt & p_out
Definition: numthry.h:251
Definition: alg_id.cpp:13
std::vector< uint8_t > BigInt BigInt size_t size_t qbits
Definition: numthry.h:251
BigInt random_prime(RandomNumberGenerator &rng, size_t bits, const BigInt &coprime, size_t equiv, size_t modulo, size_t prob)
Definition: make_prm.cpp:74
class BOTAN_PUBLIC_API(2, 0) AlgorithmIdentifier final bool BOTAN_PUBLIC_API(2, 0) operator
Name Constraints.
Definition: asn1_obj.h:65
size_t const uint8_t input[]
Definition: base32.h:30
word monty_inverse(word a)
Definition: numthry.cpp:384
BigInt RandomNumberGenerator & prime_test_rng
Definition: numthry.h:226
BigInt const BigInt const BigInt & c
Definition: numthry.h:25
size_t almost_montgomery_inverse(BigInt &result, const BigInt &a, const BigInt &p)
Definition: numthry.cpp:102
const OctetString & y
Definition: symkey.h:126
std::vector< uint8_t > BigInt BigInt & q_out
Definition: numthry.h:251
BigInt const BigInt & modulus
Definition: numthry.h:87
BigInt generate_rsa_prime(RandomNumberGenerator &keygen_rng, RandomNumberGenerator &prime_test_rng, size_t bits, const BigInt &coprime, size_t prob)
Definition: make_prm.cpp:180
int32_t jacobi(const BigInt &a, const BigInt &n)
Definition: jacobi.cpp:15
BigInt size_t const BigInt size_t equiv
Definition: numthry.h:212
bool check_prime(const BigInt &n, RandomNumberGenerator &rng)
Definition: numthry.h:192
BigInt size_t const BigInt size_t size_t equiv_mod
Definition: numthry.h:213