Botan
1.11.15
|
00001 /* 00002 * Number Theory Functions 00003 * (C) 1999-2007 Jack Lloyd 00004 * 00005 * Botan is released under the Simplified BSD License (see license.txt) 00006 */ 00007 00008 #ifndef BOTAN_NUMBER_THEORY_H__ 00009 #define BOTAN_NUMBER_THEORY_H__ 00010 00011 #include <botan/bigint.h> 00012 #include <botan/pow_mod.h> 00013 #include <botan/rng.h> 00014 00015 namespace Botan { 00016 00017 /** 00018 * Fused multiply-add 00019 * @param a an integer 00020 * @param b an integer 00021 * @param c an integer 00022 * @return (a*b)+c 00023 */ 00024 BigInt BOTAN_DLL mul_add(const BigInt& a, 00025 const BigInt& b, 00026 const BigInt& c); 00027 00028 /** 00029 * Fused subtract-multiply 00030 * @param a an integer 00031 * @param b an integer 00032 * @param c an integer 00033 * @return (a-b)*c 00034 */ 00035 BigInt BOTAN_DLL sub_mul(const BigInt& a, 00036 const BigInt& b, 00037 const BigInt& c); 00038 00039 /** 00040 * Return the absolute value 00041 * @param n an integer 00042 * @return absolute value of n 00043 */ 00044 inline BigInt abs(const BigInt& n) { return n.abs(); } 00045 00046 /** 00047 * Compute the greatest common divisor 00048 * @param x a positive integer 00049 * @param y a positive integer 00050 * @return gcd(x,y) 00051 */ 00052 BigInt BOTAN_DLL gcd(const BigInt& x, const BigInt& y); 00053 00054 /** 00055 * Least common multiple 00056 * @param x a positive integer 00057 * @param y a positive integer 00058 * @return z, smallest integer such that z % x == 0 and z % y == 0 00059 */ 00060 BigInt BOTAN_DLL lcm(const BigInt& x, const BigInt& y); 00061 00062 /** 00063 * @param x an integer 00064 * @return (x*x) 00065 */ 00066 BigInt BOTAN_DLL square(const BigInt& x); 00067 00068 /** 00069 * Modular inversion 00070 * @param x a positive integer 00071 * @param modulus a positive integer 00072 * @return y st (x*y) % modulus == 1 00073 */ 00074 BigInt BOTAN_DLL inverse_mod(const BigInt& x, 00075 const BigInt& modulus); 00076 00077 /** 00078 * Compute the Jacobi symbol. If n is prime, this is equivalent 00079 * to the Legendre symbol. 00080 * @see http://mathworld.wolfram.com/JacobiSymbol.html 00081 * 00082 * @param a is a non-negative integer 00083 * @param n is an odd integer > 1 00084 * @return (n / m) 00085 */ 00086 s32bit BOTAN_DLL jacobi(const BigInt& a, 00087 const BigInt& n); 00088 00089 /** 00090 * Modular exponentation 00091 * @param b an integer base 00092 * @param x a positive exponent 00093 * @param m a positive modulus 00094 * @return (b^x) % m 00095 */ 00096 BigInt BOTAN_DLL power_mod(const BigInt& b, 00097 const BigInt& x, 00098 const BigInt& m); 00099 00100 /** 00101 * Compute the square root of x modulo a prime using the 00102 * Shanks-Tonnelli algorithm 00103 * 00104 * @param x the input 00105 * @param p the prime 00106 * @return y such that (y*y)%p == x, or -1 if no such integer 00107 */ 00108 BigInt BOTAN_DLL ressol(const BigInt& x, const BigInt& p); 00109 00110 /* 00111 * Compute -input^-1 mod 2^MP_WORD_BITS. Returns zero if input 00112 * is even. If input is odd, input and 2^n are relatively prime 00113 * and an inverse exists. 00114 */ 00115 word BOTAN_DLL monty_inverse(word input); 00116 00117 /** 00118 * @param x a positive integer 00119 * @return count of the zero bits in x, or, equivalently, the largest 00120 * value of n such that 2^n divides x evenly. Returns zero if 00121 * n is less than or equal to zero. 00122 */ 00123 size_t BOTAN_DLL low_zero_bits(const BigInt& x); 00124 00125 /** 00126 * Check for primality 00127 * @param n a positive integer to test for primality 00128 * @param rng a random number generator 00129 * @param prob chance of false positive is bounded by 1/2**prob 00130 * @param is_random true if n was randomly chosen by us 00131 * @return true if all primality tests passed, otherwise false 00132 */ 00133 bool BOTAN_DLL is_prime(const BigInt& n, 00134 RandomNumberGenerator& rng, 00135 size_t prob = 56, 00136 bool is_random = false); 00137 00138 inline bool quick_check_prime(const BigInt& n, RandomNumberGenerator& rng) 00139 { return is_prime(n, rng, 32); } 00140 00141 inline bool check_prime(const BigInt& n, RandomNumberGenerator& rng) 00142 { return is_prime(n, rng, 56); } 00143 00144 inline bool verify_prime(const BigInt& n, RandomNumberGenerator& rng) 00145 { return is_prime(n, rng, 80); } 00146 00147 00148 /** 00149 * Randomly generate a prime 00150 * @param rng a random number generator 00151 * @param bits how large the resulting prime should be in bits 00152 * @param coprime a positive integer the result should be coprime to 00153 * @param equiv a non-negative number that the result should be 00154 equivalent to modulo equiv_mod 00155 * @param equiv_mod the modulus equiv should be checked against 00156 * @return random prime with the specified criteria 00157 */ 00158 BigInt BOTAN_DLL random_prime(RandomNumberGenerator& rng, 00159 size_t bits, const BigInt& coprime = 1, 00160 size_t equiv = 1, size_t equiv_mod = 2); 00161 00162 /** 00163 * Return a 'safe' prime, of the form p=2*q+1 with q prime 00164 * @param rng a random number generator 00165 * @param bits is how long the resulting prime should be 00166 * @return prime randomly chosen from safe primes of length bits 00167 */ 00168 BigInt BOTAN_DLL random_safe_prime(RandomNumberGenerator& rng, 00169 size_t bits); 00170 00171 /** 00172 * Generate DSA parameters using the FIPS 186 kosherizer 00173 * @param rng a random number generator 00174 * @param af an algorithm factory 00175 * @param p_out where the prime p will be stored 00176 * @param q_out where the prime q will be stored 00177 * @param pbits how long p will be in bits 00178 * @param qbits how long q will be in bits 00179 * @return random seed used to generate this parameter set 00180 */ 00181 std::vector<byte> BOTAN_DLL 00182 generate_dsa_primes(RandomNumberGenerator& rng, 00183 BigInt& p_out, BigInt& q_out, 00184 size_t pbits, size_t qbits); 00185 00186 /** 00187 * Generate DSA parameters using the FIPS 186 kosherizer 00188 * @param rng a random number generator 00189 * @param af an algorithm factory 00190 * @param p_out where the prime p will be stored 00191 * @param q_out where the prime q will be stored 00192 * @param pbits how long p will be in bits 00193 * @param qbits how long q will be in bits 00194 * @param seed the seed used to generate the parameters 00195 * @return true if seed generated a valid DSA parameter set, otherwise 00196 false. p_out and q_out are only valid if true was returned. 00197 */ 00198 bool BOTAN_DLL 00199 generate_dsa_primes(RandomNumberGenerator& rng, 00200 BigInt& p_out, BigInt& q_out, 00201 size_t pbits, size_t qbits, 00202 const std::vector<byte>& seed); 00203 00204 /** 00205 * The size of the PRIMES[] array 00206 */ 00207 const size_t PRIME_TABLE_SIZE = 6541; 00208 00209 /** 00210 * A const array of all primes less than 65535 00211 */ 00212 extern const u16bit BOTAN_DLL PRIMES[]; 00213 00214 } 00215 00216 #endif