Botan 2.1.0 Crypto and TLS for C++11

- Main Page
- Namespaces
- Classes
- Files

- File List
- File Members

numthry.h
Go to the documentation of this file.
1 /*
2 * Number Theory Functions
3 * (C) 1999-2007 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 #include <botan/pow_mod.h>
13 #include <botan/rng.h>
14
15 namespace Botan {
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_DLL 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_DLL 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_DLL 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_DLL 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_DLL lcm(const BigInt& x, const BigInt& y);
72
73 /**
74 * @param x an integer
75 * @return (x*x)
76 */
77 BigInt BOTAN_DLL 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_DLL inverse_mod(const BigInt& x,
87 const BigInt& modulus);
88
89 /**
90 * Const time modular inversion
91 * Requires the modulus be odd
92 */
93 BigInt BOTAN_DLL ct_inverse_mod_odd_modulus(const BigInt& n, const BigInt& mod);
94
95 /**
96 * Return a^-1 * 2^k mod b
97 * Returns k, between n and 2n
98 * Not const time
99 */
100 size_t BOTAN_DLL almost_montgomery_inverse(BigInt& result,
101 const BigInt& a,
102 const BigInt& b);
103
104 /**
105 * Call almost_montgomery_inverse and correct the result to a^-1 mod b
106 */
107 BigInt BOTAN_DLL normalized_montgomery_inverse(const BigInt& a, const BigInt& b);
108
109
110 /**
111 * Compute the Jacobi symbol. If n is prime, this is equivalent
112 * to the Legendre symbol.
113 * @see http://mathworld.wolfram.com/JacobiSymbol.html
114 *
115 * @param a is a non-negative integer
116 * @param n is an odd integer > 1
117 * @return (n / m)
118 */
119 int32_t BOTAN_DLL jacobi(const BigInt& a,
120 const BigInt& n);
121
122 /**
123 * Modular exponentation
124 * @param b an integer base
125 * @param x a positive exponent
126 * @param m a positive modulus
127 * @return (b^x) % m
128 */
129 BigInt BOTAN_DLL power_mod(const BigInt& b,
130 const BigInt& x,
131 const BigInt& m);
132
133 /**
134 * Compute the square root of x modulo a prime using the
135 * Shanks-Tonnelli algorithm
136 *
137 * @param x the input
138 * @param p the prime
139 * @return y such that (y*y)%p == x, or -1 if no such integer
140 */
141 BigInt BOTAN_DLL ressol(const BigInt& x, const BigInt& p);
142
143 /*
144 * Compute -input^-1 mod 2^MP_WORD_BITS. Returns zero if input
145 * is even. If input is odd, input and 2^n are relatively prime
146 * and an inverse exists.
147 */
148 word BOTAN_DLL monty_inverse(word input);
149
150 /**
151 * @param x a positive integer
152 * @return count of the zero bits in x, or, equivalently, the largest
153 * value of n such that 2^n divides x evenly. Returns zero if
154 * n is less than or equal to zero.
155 */
156 size_t BOTAN_DLL low_zero_bits(const BigInt& x);
157
158 /**
159 * Check for primality
160 * @param n a positive integer to test for primality
161 * @param rng a random number generator
162 * @param prob chance of false positive is bounded by 1/2**prob
163 * @param is_random true if n was randomly chosen by us
164 * @return true if all primality tests passed, otherwise false
165 */
166 bool BOTAN_DLL is_prime(const BigInt& n,
167 RandomNumberGenerator& rng,
168 size_t prob = 56,
169 bool is_random = false);
170
171 inline bool quick_check_prime(const BigInt& n, RandomNumberGenerator& rng)
172 { return is_prime(n, rng, 32); }
173
174 inline bool check_prime(const BigInt& n, RandomNumberGenerator& rng)
175 { return is_prime(n, rng, 56); }
176
177 inline bool verify_prime(const BigInt& n, RandomNumberGenerator& rng)
178 { return is_prime(n, rng, 80); }
179
180
181 /**
182 * Randomly generate a prime
183 * @param rng a random number generator
184 * @param bits how large the resulting prime should be in bits
185 * @param coprime a positive integer the result should be coprime to
186 * @param equiv a non-negative number that the result should be
187 equivalent to modulo equiv_mod
188 * @param equiv_mod the modulus equiv should be checked against
189 * @return random prime with the specified criteria
190 */
191 BigInt BOTAN_DLL random_prime(RandomNumberGenerator& rng,
192 size_t bits, const BigInt& coprime = 1,
193 size_t equiv = 1, size_t equiv_mod = 2);
194
195 /**
196 * Return a 'safe' prime, of the form p=2*q+1 with q prime
197 * @param rng a random number generator
198 * @param bits is how long the resulting prime should be
199 * @return prime randomly chosen from safe primes of length bits
200 */
201 BigInt BOTAN_DLL random_safe_prime(RandomNumberGenerator& rng,
202 size_t bits);
203
204 /**
205 * Generate DSA parameters using the FIPS 186 kosherizer
206 * @param rng a random number generator
207 * @param p_out where the prime p will be stored
208 * @param q_out where the prime q will be stored
209 * @param pbits how long p will be in bits
210 * @param qbits how long q will be in bits
211 * @return random seed used to generate this parameter set
212 */
213 std::vector<uint8_t> BOTAN_DLL
214 generate_dsa_primes(RandomNumberGenerator& rng,
215 BigInt& p_out, BigInt& q_out,
216 size_t pbits, size_t qbits);
217
218 /**
219 * Generate DSA parameters using the FIPS 186 kosherizer
220 * @param rng a random number generator
221 * @param p_out where the prime p will be stored
222 * @param q_out where the prime q will be stored
223 * @param pbits how long p will be in bits
224 * @param qbits how long q will be in bits
225 * @param seed the seed used to generate the parameters
226 * @param offset optional offset from seed to start searching at
227 * @return true if seed generated a valid DSA parameter set, otherwise
228 false. p_out and q_out are only valid if true was returned.
229 */
230 bool BOTAN_DLL
231 generate_dsa_primes(RandomNumberGenerator& rng,
232 BigInt& p_out, BigInt& q_out,
233 size_t pbits, size_t qbits,
234 const std::vector<uint8_t>& seed,
235 size_t offset = 0);
236
237 /**
238 * The size of the PRIMES[] array
239 */
240 const size_t PRIME_TABLE_SIZE = 6541;
241
242 /**
243 * A const array of all primes less than 65535
244 */
245 extern const uint16_t BOTAN_DLL PRIMES[];
246
247 }
248
249 #endif
Botan::PRIME_TABLE_SIZE
const size_t PRIME_TABLE_SIZE
Definition: numthry.h:240
Botan::normalized_montgomery_inverse
BigInt normalized_montgomery_inverse(const BigInt &a, const BigInt &p)
Definition: numthry.cpp:138
Botan::PRIMES
const uint16_t BOTAN_DLL PRIMES[]
Definition: primes.cpp:12
Botan::BigInt
Definition: bigint.h:23
Botan::RandomNumberGenerator
Definition: rng.h:25
Botan::is_prime
bool is_prime(const BigInt &n, RandomNumberGenerator &rng, size_t prob, bool is_random)
Definition: numthry.cpp:441
Botan::gcd
BigInt gcd(const BigInt &a, const BigInt &b)
Definition: numthry.cpp:46
Botan::quick_check_prime
bool quick_check_prime(const BigInt &n, RandomNumberGenerator &rng)
Definition: numthry.h:171
Botan::BigInt::abs
BigInt abs() const
Definition: bigint.cpp:254
Botan::ressol
BigInt BOTAN_DLL ressol(const BigInt &x, const BigInt &p)
Definition: ressol.cpp:17
Botan::generate_dsa_primes
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
Botan::abs
BigInt abs(const BigInt &n)
Definition: numthry.h:55
Botan::almost_montgomery_inverse
size_t almost_montgomery_inverse(BigInt &result, const BigInt &a, const BigInt &p)
Definition: numthry.cpp:90
Botan::verify_prime
bool verify_prime(const BigInt &n, RandomNumberGenerator &rng)
Definition: numthry.h:177
Botan::ct_inverse_mod_odd_modulus
BigInt ct_inverse_mod_odd_modulus(const BigInt &n, const BigInt &mod)
Definition: numthry.cpp:153
Botan
Definition: alg_id.cpp:13
Botan::random_safe_prime
BigInt random_safe_prime(RandomNumberGenerator &rng, size_t bits)
Definition: make_prm.cpp:114
Botan::low_zero_bits
size_t low_zero_bits(const BigInt &n)
Definition: numthry.cpp:20
Botan::inverse_mod
BigInt inverse_mod(const BigInt &n, const BigInt &mod)
Definition: numthry.cpp:276
Botan::sub_mul
BigInt sub_mul(const BigInt &a, const BigInt &b, const BigInt &c)
Definition: mp_numth.cpp:57
Botan::square
BigInt square(const BigInt &x)
Definition: mp_numth.cpp:19
Botan::power_mod
BigInt power_mod(const BigInt &base, const BigInt &exp, const BigInt &mod)
Definition: numthry.cpp:373
Botan::monty_inverse
word monty_inverse(word input)
Definition: numthry.cpp:325
Botan::jacobi
int32_t jacobi(const BigInt &a, const BigInt &n)
Definition: jacobi.cpp:15
Botan::lcm
BigInt lcm(const BigInt &a, const BigInt &b)
Definition: numthry.cpp:73
Botan::mul_add
BigInt mul_add(const BigInt &a, const BigInt &b, const BigInt &c)
Definition: mp_numth.cpp:35
Botan::mul_sub
BigInt mul_sub(const BigInt &a, const BigInt &b, const BigInt &c)
Definition: mp_numth.cpp:71
Botan::random_prime
BigInt random_prime(RandomNumberGenerator &rng, size_t bits, const BigInt &coprime, size_t equiv, size_t modulo)
Definition: make_prm.cpp:17
Botan::check_prime
bool check_prime(const BigInt &n, RandomNumberGenerator &rng)
Definition: numthry.h:174