numthry.cpp

含有多种公开密钥算法、多种块加密、多种数据流加密、多种HASH函数、多种CheckSum校验、多种MAC校验等几十种加密算法的程序

/*************************************************
* Number Theory Source File                      *
* (C) 1999-2002 The Botan Project                *
*************************************************/

#include <botan/primes.h>
#include <botan/numthry.h>
#include <botan/mil_rab.h>
#include <botan/barrett.h>

namespace Botan {

namespace {

/*************************************************
* Miller-Rabin Iterations                        *
*************************************************/
u32bit miller_rabin_test_iterations(u32bit bits, bool verify)
   {
   struct mapping { u32bit bits; u32bit verify_iter; u32bit check_iter; };

   static const mapping tests[] = {
      {   50, 60, 25 },
      {  100, 40, 22 },
      {  160, 34, 18 },
      {  163, 33, 17 },
      {  166, 32, 16 },
      {  169, 31, 16 },
      {  173, 30, 16 },
      {  177, 29, 16 },
      {  181, 28, 15 },
      {  185, 27, 15 },
      {  190, 26, 15 },
      {  195, 25, 14 },
      {  201, 24, 14 },
      {  208, 23, 14 },
      {  215, 22, 13 },
      {  222, 21, 13 },
      {  231, 20, 13 },
      {  241, 19, 12 },
      {  252, 18, 12 },
      {  264, 17, 12 },
      {  278, 16, 11 },
      {  294, 15, 10 },
      {  313, 14,  9 },
      {  334, 13,  8 },
      {  360, 12,  8 },
      {  392, 11,  7 },
      {  430, 10,  7 },
      {  479,  9,  6 },
      {  542,  8,  6 },
      {  626,  7,  5 },
      {  746,  6,  4 },
      {  926,  5,  3 },
      { 1232,  4,  2 },
      { 1853,  3,  2 },
      {    0,  0,  0 }
   };

   for(u32bit j = 0; tests[j].bits; j++)
      {
      if(bits <= tests[j].bits)
         if(verify)
            return tests[j].verify_iter;
         else
            return tests[j].check_iter;
      }
   return 2;
   }

}

/*************************************************
* Return the number of 0 bits at the end of n    *
*************************************************/
u32bit low_zero_bits(const BigInt& n)
   {
   if(n.is_zero()) return 0;

   u32bit bits = 0, max_bits = n.bits();
   while((n.get_bit(bits) == 0) && bits < max_bits) bits++;
   return bits;
   }

/*************************************************
* Calculate the GCD                              *
*************************************************/
BigInt gcd(const BigInt& a, const BigInt& b)
   {
   if(a.is_zero() || b.is_zero())
      return BigInt::zero();
   if(a == BigInt::one() || b == BigInt::one())
      return BigInt::one();

   BigInt x = a, y = b;
   x.set_sign(Positive);
   y.set_sign(Positive);
   u32bit shift = std::min(low_zero_bits(x), low_zero_bits(y));

   x >>= shift;
   y >>= shift;

   while(x.is_nonzero())
      {
      x >>= low_zero_bits(x);
      y >>= low_zero_bits(y);
      if(x >= y) { x -= y; x >>= 1; }
      else       { y -= x; y >>= 1; }
      }

   return (y << shift);
   }

/*************************************************
* Calculate the LCM                              *
*************************************************/
BigInt lcm(const BigInt& a, const BigInt& b)
   {
   return ((a * b) / gcd(a, b));
   }

/*************************************************
* Square a BigInt                                *
*************************************************/
BigInt square(const BigInt& a)
   {
   return (a * a);
   }

/*************************************************
* Find the Modular Inverse                       *
*************************************************/
BigInt inverse_mod(const BigInt& n, const BigInt& mod)
   {
   if(mod.is_zero()) throw BigInt::DivideByZero();
   if(mod.is_negative() || n.is_negative())
      throw Invalid_Argument("inverse_mod: arguments must be non-negative");
   if(n.is_even() && mod.is_even())
      return BigInt::zero();

   BigInt x = mod, y = n, u = mod, v = n;
   BigInt A = BigInt::one(),  B = BigInt::zero(),
          C = BigInt::zero(), D = BigInt::one();

   while(u.is_nonzero())
      {
      u32bit zero_bits = low_zero_bits(u);
      u >>= zero_bits;
      for(u32bit j = 0; j != zero_bits; j++)
         {
         if(A.is_odd() || B.is_odd())
            { A += y; B -= x; }
         A >>= 1; B >>= 1;
         }

      zero_bits = low_zero_bits(v);
      v >>= zero_bits;
      for(u32bit j = 0; j != zero_bits; j++)
         {
         if(C.is_odd() || D.is_odd())
            { C += y; D -= x; }
         C >>= 1; D >>= 1;
         }

      if(u >= v) { u -= v; A -= C; B -= D; }
      else       { v -= u; C -= A; D -= B; }
      }

   if(v != BigInt::one())
      return BigInt::zero();

   while(D.is_negative()) D += mod;
   while(D >= mod) D -= mod;

   return D;
   }

/*************************************************
* Calculate the Jacobi symbol                    *
*************************************************/
s32bit jacobi(const BigInt& a, const BigInt& n)
   {
   if(a.is_negative())
      throw Invalid_Argument("jacobi: first argument must be non-negative");
   if(n.is_even() || n < 2)
      throw Invalid_Argument("jacobi: second argument must be odd and > 1");

   BigInt x = a, y = n;
   s32bit J = 1;

   while(y > BigInt::one())
      {
      x %= y;
      if(x > y >> 1)
         {
         x = y - x;
         if(y % 4 == 3)
            J = -J;
         }
      if(x.is_zero())
         return 0;
      while(x % 4 == 0)
         x >>= 2;
      if(x.is_even())
         {
         x >>= 1;
         if(y % 8 == 3 || y % 8 == 5)
            J = -J;
         }
      if(x % 4 == 3 && y % 4 == 3)
         J = -J;
      std::swap(x, y);
      }
   return J;
   }

/*************************************************
* Exponentiation                                 *
*************************************************/
BigInt power(const BigInt& base, u32bit exp)
   {
   BigInt x = BigInt::one(), a = base;
   while(exp)
      {
      if(exp % 2)
         x *= a;
      exp >>= 1;
      if(exp)
         a = square(a);
      }
   return x;
   }

/*************************************************
* Modular Exponentiation                         *
*************************************************/
BigInt power_mod(const BigInt& base, const BigInt& exp, const BigInt& mod)
   {
   ModularReducer* reducer = new BarrettReducer(mod);
   BigInt x = power_mod(base, exp, reducer);
   delete reducer;
   return x;
   }

/*************************************************
* Left-to-Right Binary Modular Exponentiation    *
*************************************************/
BigInt power_mod(const BigInt& base, const BigInt& exp,
                 ModularReducer* reducer)
   {
   if(exp.is_negative())
      throw Invalid_Argument("power_mod: exponent must be positive");
   if(exp.is_zero())
      return BigInt::one();

   BigInt x = BigInt::one();
   const u32bit exp_bits = exp.bits();

   for(u32bit j = exp_bits; j > 0; j--)
      {
      x = reducer->square(x);
      if(exp.get_bit(j-1))
         x = reducer->multiply(x, base);
      }
   return x;
   }

/*************************************************
* Do simple tests of primality                   *
*************************************************/
s32bit simple_primality_tests(const BigInt& n)
   {
   static const s32bit NOT_PRIME = -1, UNKNOWN = 0, PRIME = 1;

   if(n == 2)
      return PRIME;
   if(n <= 1 || n.is_even())
      return NOT_PRIME;

   if(n <= PRIMES[PRIME_TABLE_SIZE-1])
      {
      const u32bit num = n.word_at(0);
      for(u32bit j = 0; PRIMES[j]; j++)
         {
         if(num == PRIMES[j]) return PRIME;
         if(num <  PRIMES[j]) return NOT_PRIME;
         }
      return NOT_PRIME;
      }

   for(u32bit j = 0; j != n.bits() / 16; j++)
      if(gcd(n, PRIME_PRODUCTS[j]) != BigInt::one())
         return NOT_PRIME;

   return UNKNOWN;
   }

/*************************************************
* Check for primality                            *
*************************************************/
bool is_prime(const BigInt& n)
   {
   s32bit simple_tests = simple_primality_tests(n);
   if(simple_tests) return (simple_tests == 1) ? true : false;
   return passes_mr_tests(n, false);
   }

/*************************************************
* Verify primality                               *
*************************************************/
bool verify_prime(const BigInt& n)
   {
   s32bit simple_tests = simple_primality_tests(n);
   if(simple_tests) return (simple_tests == 1) ? true : false;
   return passes_mr_tests(n, true);
   }

/*************************************************
* Verify primality                               *
*************************************************/
bool passes_mr_tests(const BigInt& n, bool verify)
   {
   MillerRabin_Test mr(n);

   if(!mr.passes_test(2))
      return false;

   u32bit tests = miller_rabin_test_iterations(n.bits(), verify);

   for(u32bit j = 0; j != tests; j++)
      {
      if(verify && !mr.passes_test(random_integer(48)))
         return false;
      else if(!mr.passes_test(PRIMES[j]))
         return false;
      }
   return true;
   }

}