1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
|
/*
* 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) BOTAN_DEPRECATED("Just use (a*b)+c")
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) BOTAN_DEPRECATED("Just use (a-b)*c")
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) BOTAN_DEPRECATED("Just use (a*b)-c")
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. This algorithm is const time with respect to x,
* as long as x is less than modulus. It also avoids leaking
* information about the modulus, except that it does leak which of 3
* categories the modulus is in: an odd integer, a power of 2, or some
* other even number, and if the modulus is even, leaks the power of 2
* which divides the modulus.
*
* @param x a positive integer
* @param modulus a positive integer
* @return y st (x*y) % modulus == 1 or 0 if no such value
*/
BigInt BOTAN_PUBLIC_API(2,0) inverse_mod(const BigInt& x,
const BigInt& modulus);
/**
* Deprecated modular inversion function. Use inverse_mod instead.
* @param x a positive integer
* @param modulus a positive integer
* @return y st (x*y) % modulus == 1 or 0 if no such value
*/
BigInt BOTAN_DEPRECATED_API("Use inverse_mod") inverse_euclid(const BigInt& x, const BigInt& modulus);
/**
* Deprecated modular inversion function. Use inverse_mod instead.
*/
BigInt BOTAN_DEPRECATED_API("Use inverse_mod") ct_inverse_mod_odd_modulus(const BigInt& x, const BigInt& modulus);
/**
* Return a^-1 * 2^k mod b
* Returns k, between n and 2n
* Not const time
*/
size_t BOTAN_PUBLIC_API(2,0) BOTAN_DEPRECATED("Use inverse_mod")
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) BOTAN_DEPRECATED("Use inverse_mod")
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
* Tonelli-Shanks 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) BOTAN_DEPRECATED("Use inverse_mod")
monty_inverse(word input);
/**
* @param x an integer
* @return count of the low zero bits in x, or, equivalently, the
* largest value of n such that 2^n divides x evenly. Returns
* zero if x is 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 BOTAN_DEPRECATED("Use is_prime")
quick_check_prime(const BigInt& n, RandomNumberGenerator& rng)
{ return is_prime(n, rng, 32); }
inline bool BOTAN_DEPRECATED("Use is_prime")
check_prime(const BigInt& n, RandomNumberGenerator& rng)
{ return is_prime(n, rng, 56); }
inline bool BOTAN_DEPRECATED("Use is_prime")
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) BOTAN_DEPRECATED("Use DL_Group")
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) BOTAN_DEPRECATED("Use DL_Group")
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 odd primes less than 65535
*/
extern const uint16_t BOTAN_PUBLIC_API(2,0) PRIMES[];
}
#endif
|
