00001 00002 00003 00004 00005 00006 00007 #if !defined(_XBOX) && !defined(X360) 00008 00009 /* 00010 * BigInts are stored as 32-bit integer arrays. 00011 * Each integer in the array is referred to as a limb ala GMP. 00012 * Lower numbered limbs are less significant to the number represented. 00013 * eg, limb 0 is the least significant limb. 00014 * Also known as little-endian digit order 00015 */ 00016 00017 #ifndef BIG_INT_HPP 00018 #define BIG_INT_HPP 00019 00020 #include "Platform.h" 00021 #include "NativeTypes.h" 00022 //#include <string> 00023 00024 namespace big 00025 { 00026 // returns the degree of the base 2 monic polynomial 00027 // (the number of bits used to represent the number) 00028 // eg, 0 0 0 0 1 0 1 1 ... => 28 out of 32 used 00029 uint32_t Degree(uint32_t v); 00030 00031 // returns the number of limbs that are actually used 00032 int LimbDegree(const uint32_t *n, int limbs); 00033 00034 // return bits used 00035 uint32_t Degree(const uint32_t *n, int limbs); 00036 00037 // lhs = rhs (unequal limbs) 00038 void Set(uint32_t *lhs, int lhs_limbs, const uint32_t *rhs, int rhs_limbs); 00039 00040 // lhs = rhs (equal limbs) 00041 void Set(uint32_t *lhs, int limbs, const uint32_t *rhs); 00042 00043 // lhs = rhs (32-bit extension) 00044 void Set32(uint32_t *lhs, int lhs_limbs, const uint32_t rhs); 00045 00046 #if defined(__BIG_ENDIAN__) 00047 // Flip the byte order as needed to make 'n' big-endian for sharing over a network 00048 void ToLittleEndian(uint32_t *n, int limbs); 00049 00050 // Flip the byte order as needed to make big-endian 'n' use the local byte order 00051 void FromLittleEndian(uint32_t *n, int limbs); 00052 #else 00053 inline void ToLittleEndian(uint32_t *, int) {} 00054 inline void FromLittleEndian(uint32_t *, int) {} 00055 #endif 00056 00057 // Comparisons where both operands have the same number of limbs 00058 bool Less(int limbs, const uint32_t *lhs, const uint32_t *rhs); 00059 bool Greater(int limbs, const uint32_t *lhs, const uint32_t *rhs); 00060 bool Equal(int limbs, const uint32_t *lhs, const uint32_t *rhs); 00061 00062 // lhs < rhs 00063 bool Less(const uint32_t *lhs, int lhs_limbs, const uint32_t *rhs, int rhs_limbs); 00064 00065 // lhs >= rhs 00066 inline bool GreaterOrEqual(const uint32_t *lhs, int lhs_limbs, const uint32_t *rhs, int rhs_limbs) 00067 { 00068 return !Less(lhs, lhs_limbs, rhs, rhs_limbs); 00069 } 00070 00071 // lhs > rhs 00072 bool Greater(const uint32_t *lhs, int lhs_limbs, const uint32_t *rhs, int rhs_limbs); 00073 00074 // lhs <= rhs 00075 inline bool LessOrEqual(const uint32_t *lhs, int lhs_limbs, const uint32_t *rhs, int rhs_limbs) 00076 { 00077 return !Greater(lhs, lhs_limbs, rhs, rhs_limbs); 00078 } 00079 00080 // lhs > rhs 00081 bool Greater32(const uint32_t *lhs, int lhs_limbs, uint32_t rhs); 00082 00083 // lhs <= rhs 00084 inline bool LessOrEqual32(const uint32_t *lhs, int lhs_limbs, uint32_t rhs) 00085 { 00086 return !Greater32(lhs, lhs_limbs, rhs); 00087 } 00088 00089 // lhs == rhs 00090 bool Equal(const uint32_t *lhs, int lhs_limbs, const uint32_t *rhs, int rhs_limbs); 00091 00092 // lhs == rhs 00093 bool Equal32(const uint32_t *lhs, int lhs_limbs, uint32_t rhs); 00094 00095 // out = in >>> shift 00096 // Precondition: 0 <= shift < 31 00097 void ShiftRight(int limbs, uint32_t *out, const uint32_t *in, int shift); 00098 00099 // {out, carry} = in <<< shift 00100 // Precondition: 0 <= shift < 31 00101 uint32_t ShiftLeft(int limbs, uint32_t *out, const uint32_t *in, int shift); 00102 00103 // lhs += rhs, return carry out 00104 // precondition: lhs_limbs >= rhs_limbs 00105 uint32_t Add(uint32_t *lhs, int lhs_limbs, const uint32_t *rhs, int rhs_limbs); 00106 00107 // out = lhs + rhs, return carry out 00108 // precondition: lhs_limbs >= rhs_limbs 00109 uint32_t Add(uint32_t *out, const uint32_t *lhs, int lhs_limbs, const uint32_t *rhs, int rhs_limbs); 00110 00111 // lhs += rhs, return carry out 00112 // precondition: lhs_limbs > 0 00113 uint32_t Add32(uint32_t *lhs, int lhs_limbs, uint32_t rhs); 00114 00115 // lhs -= rhs, return borrow out 00116 // precondition: lhs_limbs >= rhs_limbs 00117 int32_t Subtract(uint32_t *lhs, int lhs_limbs, const uint32_t *rhs, int rhs_limbs); 00118 00119 // out = lhs - rhs, return borrow out 00120 // precondition: lhs_limbs >= rhs_limbs 00121 int32_t Subtract(uint32_t *out, const uint32_t *lhs, int lhs_limbs, const uint32_t *rhs, int rhs_limbs); 00122 00123 // lhs -= rhs, return borrow out 00124 // precondition: lhs_limbs > 0, result limbs = lhs_limbs 00125 int32_t Subtract32(uint32_t *lhs, int lhs_limbs, uint32_t rhs); 00126 00127 // lhs = -rhs 00128 void Negate(int limbs, uint32_t *lhs, const uint32_t *rhs); 00129 00130 // n = ~n, only invert bits up to the MSB, but none above that 00131 void BitNot(uint32_t *n, int limbs); 00132 00133 // n = ~n, invert all bits, even ones above MSB 00134 void LimbNot(uint32_t *n, int limbs); 00135 00136 // lhs ^= rhs 00137 void Xor(int limbs, uint32_t *lhs, const uint32_t *rhs); 00138 00139 // Return the carry out from A += B << S 00140 uint32_t AddLeftShift32( 00141 int limbs, // Number of limbs in parameter A and B 00142 uint32_t *A, // Large number 00143 const uint32_t *B, // Large number 00144 uint32_t S); // 32-bit number 00145 00146 // Return the carry out from result = A * B 00147 uint32_t Multiply32( 00148 int limbs, // Number of limbs in parameter A, result 00149 uint32_t *result, // Large number 00150 const uint32_t *A, // Large number 00151 uint32_t B); // 32-bit number 00152 00153 // Return the carry out from X = X * M + A 00154 uint32_t MultiplyAdd32( 00155 int limbs, // Number of limbs in parameter A and B 00156 uint32_t *X, // Large number 00157 uint32_t M, // Large number 00158 uint32_t A); // 32-bit number 00159 00160 // Return the carry out from A += B * M 00161 uint32_t AddMultiply32( 00162 int limbs, // Number of limbs in parameter A and B 00163 uint32_t *A, // Large number 00164 const uint32_t *B, // Large number 00165 uint32_t M); // 32-bit number 00166 00167 // product = x * y 00168 void SimpleMultiply( 00169 int limbs, // Number of limbs in parameters x, y 00170 uint32_t *product, // Large number; buffer size = limbs*2 00171 const uint32_t *x, // Large number 00172 const uint32_t *y); // Large number 00173 00174 // product = x ^ 2 00175 void SimpleSquare( 00176 int limbs, // Number of limbs in parameter x 00177 uint32_t *product, // Large number; buffer size = limbs*2 00178 const uint32_t *x); // Large number 00179 00180 // product = xy 00181 // memory space for product may not overlap with x,y 00182 void Multiply( 00183 int limbs, // Number of limbs in x,y 00184 uint32_t *product, // Product; buffer size = limbs*2 00185 const uint32_t *x, // Large number; buffer size = limbs 00186 const uint32_t *y); // Large number; buffer size = limbs 00187 00188 // product = low half of x * y product 00189 void SimpleMultiplyLowHalf( 00190 int limbs, // Number of limbs in parameters x, y 00191 uint32_t *product, // Large number; buffer size = limbs 00192 const uint32_t *x, // Large number 00193 const uint32_t *y); // Large number 00194 00195 // product = x^2 00196 // memory space for product may not overlap with x 00197 void Square( 00198 int limbs, // Number of limbs in x 00199 uint32_t *product, // Product; buffer size = limbs*2 00200 const uint32_t *x); // Large number; buffer size = limbs 00201 00202 // Returns the remainder of N / divisor for a 32-bit divisor 00203 uint32_t Modulus32( 00204 int limbs, // Number of limbs in parameter N 00205 const uint32_t *N, // Large number, buffer size = limbs 00206 uint32_t divisor); // 32-bit number 00207 00208 /* 00209 * 'A' is overwritten with the quotient of the operation 00210 * Returns the remainder of 'A' / divisor for a 32-bit divisor 00211 * 00212 * Does not check for divide-by-zero 00213 */ 00214 uint32_t Divide32( 00215 int limbs, // Number of limbs in parameter A 00216 uint32_t *A, // Large number, buffer size = limbs 00217 uint32_t divisor); // 32-bit number 00218 00219 // returns (n ^ -1) Mod 2^32 00220 uint32_t MulInverse32(uint32_t n); 00221 00222 /* 00223 * Computes multiplicative inverse of given number 00224 * Such that: result * u = 1 00225 * Using Extended Euclid's Algorithm (GCDe) 00226 * 00227 * This is not always possible, so it will return false iff not possible. 00228 */ 00229 bool MulInverse( 00230 int limbs, // Limbs in u and result 00231 const uint32_t *u, // Large number, buffer size = limbs 00232 uint32_t *result); // Large number, buffer size = limbs 00233 00234 // {q, r} = u / v 00235 // Return false on divide by zero 00236 bool Divide( 00237 const uint32_t *u, // numerator, size = u_limbs 00238 int u_limbs, 00239 const uint32_t *v, // denominator, size = v_limbs 00240 int v_limbs, 00241 uint32_t *q, // quotient, size = u_limbs 00242 uint32_t *r); // remainder, size = v_limbs 00243 00244 // r = u % v 00245 // Return false on divide by zero 00246 bool Modulus( 00247 const uint32_t *u, // numerator, size = u_limbs 00248 int u_limbs, 00249 const uint32_t *v, // denominator, size = v_limbs 00250 int v_limbs, 00251 uint32_t *r); // remainder, size = v_limbs 00252 00253 // m_inv ~= 2^(2k)/m 00254 // Generates m_inv parameter of BarrettModulus() 00255 // It is limbs in size, chopping off the 2^k bit 00256 // Only works for m with the high bit set 00257 void BarrettModulusPrecomp( 00258 int limbs, // Number of limbs in m and m_inv 00259 const uint32_t *m, // Modulus, size = limbs 00260 uint32_t *m_inv); // Large number result, size = limbs 00261 00262 // r = x mod m 00263 // Using Barrett's method with precomputed m_inv 00264 void BarrettModulus( 00265 int limbs, // Number of limbs in m and m_inv 00266 const uint32_t *x, // Number to reduce, size = limbs*2 00267 const uint32_t *m, // Modulus, size = limbs 00268 const uint32_t *m_inv, // R/Modulus, precomputed, size = limbs 00269 uint32_t *result); // Large number result 00270 00271 // result = (x * y) (Mod modulus) 00272 bool MulMod( 00273 int limbs, // Number of limbs in x,y,modulus 00274 const uint32_t *x, // Large number x 00275 const uint32_t *y, // Large number y 00276 const uint32_t *modulus, // Large number modulus 00277 uint32_t *result); // Large number result 00278 00279 // Convert string to bigint 00280 // Return 0 if string contains non-digit characters, else number of limbs used 00281 int ToInt(uint32_t *lhs, int max_limbs, const char *rhs, uint32_t base = 10); 00282 00283 /* 00284 * Computes: result = (1/u) (Mod v) 00285 * Such that: result * u (Mod v) = 1 00286 * Using Extended Euclid's Algorithm (GCDe) 00287 * 00288 * This is not always possible, so it will return false iff not possible. 00289 */ 00290 bool InvMod( 00291 const uint32_t *u, // Large number, buffer size = u_limbs 00292 int u_limbs, // Limbs in u 00293 const uint32_t *v, // Large number, buffer size = limbs 00294 int limbs, // Limbs in modulus and result 00295 uint32_t *result); // Large number, buffer size = limbs 00296 00297 /* 00298 * Computes: result = GCD(a, b) (greatest common divisor) 00299 * 00300 * Length of result is the length of the smallest argument 00301 */ 00302 void GCD( 00303 const uint32_t *a, // Large number, buffer size = a_limbs 00304 int a_limbs, // Size of a 00305 const uint32_t *b, // Large number, buffer size = b_limbs 00306 int b_limbs, // Size of b 00307 uint32_t *result); // Large number, buffer size = min(a, b) 00308 00309 // root = sqrt(square) 00310 // Based on Newton-Raphson iteration: root_n+1 = (root_n + square/root_n) / 2 00311 // Doubles number of correct bits each iteration 00312 // Precondition: The high limb of square is non-zero 00313 // Returns false if it was unable to determine the root 00314 bool SquareRoot( 00315 int limbs, // Number of limbs in root 00316 const uint32_t *square, // Square to root, size = limbs * 2 00317 uint32_t *root); // Output root, size = limbs 00318 00319 // Calculates mod_inv from low limb of modulus for Mon*() 00320 uint32_t MonReducePrecomp(uint32_t modulus0); 00321 00322 // Compute n_residue for Montgomery reduction 00323 void MonInputResidue( 00324 const uint32_t *n, // Large number, buffer size = n_limbs 00325 int n_limbs, // Number of limbs in n 00326 const uint32_t *modulus, // Large number, buffer size = m_limbs 00327 int m_limbs, // Number of limbs in modulus 00328 uint32_t *n_residue); // Result, buffer size = m_limbs 00329 00330 // result = a * b * r^-1 (Mod modulus) in Montgomery domain 00331 void MonPro( 00332 int limbs, // Number of limbs in each parameter 00333 const uint32_t *a_residue, // Large number, buffer size = limbs 00334 const uint32_t *b_residue, // Large number, buffer size = limbs 00335 const uint32_t *modulus, // Large number, buffer size = limbs 00336 uint32_t mod_inv, // MonReducePrecomp() return 00337 uint32_t *result); // Large number, buffer size = limbs 00338 00339 // result = a^-1 (Mod modulus) in Montgomery domain 00340 void MonInverse( 00341 int limbs, // Number of limbs in each parameter 00342 const uint32_t *a_residue, // Large number, buffer size = limbs 00343 const uint32_t *modulus, // Large number, buffer size = limbs 00344 uint32_t mod_inv, // MonReducePrecomp() return 00345 uint32_t *result); // Large number, buffer size = limbs 00346 00347 // result = a * r^-1 (Mod modulus) in Montgomery domain 00348 // The result may be greater than the modulus, but this is okay since 00349 // the result is still in the RNS. MonFinish() corrects this at the end. 00350 void MonReduce( 00351 int limbs, // Number of limbs in each parameter 00352 uint32_t *s, // Large number, buffer size = limbs*2, gets clobbered 00353 const uint32_t *modulus, // Large number, buffer size = limbs 00354 uint32_t mod_inv, // MonReducePrecomp() return 00355 uint32_t *result); // Large number, buffer size = limbs 00356 00357 // result = a * r^-1 (Mod modulus) in Montgomery domain 00358 void MonFinish( 00359 int limbs, // Number of limbs in each parameter 00360 uint32_t *n, // Large number, buffer size = limbs 00361 const uint32_t *modulus, // Large number, buffer size = limbs 00362 uint32_t mod_inv); // MonReducePrecomp() return 00363 00364 // Computes: result = base ^ exponent (Mod modulus) 00365 // Using Montgomery multiplication with simple squaring method 00366 // Base parameter must be a Montgomery Residue created with MonInputResidue() 00367 void MonExpMod( 00368 const uint32_t *base, // Base for exponentiation, buffer size = mod_limbs 00369 const uint32_t *exponent,// Exponent, buffer size = exponent_limbs 00370 int exponent_limbs, // Number of limbs in exponent 00371 const uint32_t *modulus, // Modulus, buffer size = mod_limbs 00372 int mod_limbs, // Number of limbs in modulus 00373 uint32_t mod_inv, // MonReducePrecomp() return 00374 uint32_t *result); // Result, buffer size = mod_limbs 00375 00376 // Computes: result = base ^ exponent (Mod modulus) 00377 // Using Montgomery multiplication with simple squaring method 00378 void ExpMod( 00379 const uint32_t *base, // Base for exponentiation, buffer size = base_limbs 00380 int base_limbs, // Number of limbs in base 00381 const uint32_t *exponent,// Exponent, buffer size = exponent_limbs 00382 int exponent_limbs, // Number of limbs in exponent 00383 const uint32_t *modulus, // Modulus, buffer size = mod_limbs 00384 int mod_limbs, // Number of limbs in modulus 00385 uint32_t mod_inv, // MonReducePrecomp() return 00386 uint32_t *result); // Result, buffer size = mod_limbs 00387 00388 // Computes: result = base ^ exponent (Mod modulus=mod_p*mod_q) 00389 // Using Montgomery multiplication with Chinese Remainder Theorem 00390 void ExpCRT( 00391 const uint32_t *base, // Base for exponentiation, buffer size = base_limbs 00392 int base_limbs, // Number of limbs in base 00393 const uint32_t *exponent,// Exponent, buffer size = exponent_limbs 00394 int exponent_limbs, // Number of limbs in exponent 00395 const uint32_t *mod_p, // Large number, factorization of modulus, buffer size = p_limbs 00396 uint32_t p_inv, // MonModInv() return 00397 const uint32_t *mod_q, // Large number, factorization of modulus, buffer size = q_limbs 00398 uint32_t q_inv, // MonModInv() return 00399 const uint32_t *pinvq, // Large number, InvMod(p, q) precalculated, buffer size = phi_limbs 00400 int mod_limbs, // Number of limbs in p, q and phi 00401 uint32_t *result); // Result, buffer size = mod_limbs*2 00402 00403 // Rabin-Miller method for finding a strong pseudo-prime 00404 // Preconditions: High bit and low bit of n = 1 00405 bool RabinMillerPrimeTest( 00406 const uint32_t *n, // Number to check for primality 00407 int limbs, // Number of limbs in n 00408 uint32_t k); // Confidence level (40 is pretty good) 00409 00410 // Generate a strong pseudo-prime using the Rabin-Miller primality test 00411 void GenerateStrongPseudoPrime( 00412 uint32_t *n, // Output prime 00413 int limbs); // Number of limbs in n 00414 } 00415 00416 #endif // include guard 00417 00418 #endif
1.7.1