bignum.cpp

“网络安全技术实践与代码详解”实例代码

// BigNum.cpp: implementation of the CBigNum class.
//
//////////////////////////////////////////////////////////////////////

#include <string.h>
#include <stdio.h>
#include <time.h>
#include "bignum.h"

const char CBigNum::szBase64[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CBigNum::CBigNum() : m_arVal(0), m_nSize(0)
{
}

CBigNum::CBigNum(unsigned int nValue) : m_arVal(0), m_nSize(0)
{
   if (m_arVal != NULL)
      delete[] m_arVal;

   m_nSize=2;
   m_arVal = new unsigned int[m_nSize];
   m_arVal[0] = nValue & 0xFFFF;
   m_arVal[1] = nValue >> 16;
}

CBigNum::~CBigNum()
{
   if (m_arVal != NULL)
   {
      delete[] m_arVal;
      m_arVal = NULL;
      m_nSize = 0;
   }

}

CBigNum::CBigNum(const char *szSourceVal) : m_arVal(0), m_nSize(0)
{
   *this=szSourceVal;
}

CBigNum & CBigNum::operator=(const char *szSourceVal)
{
   unsigned int nLen = strlen(szSourceVal);
   unsigned int nIdx;
   const char *pChar;
   CBigNum Pow10;

   operator=(0U);

   if (m_arVal != NULL)
   {
      Pow10 = 1;
      for (pChar = szSourceVal + nLen - 1, nIdx=0; pChar >= szSourceVal; pChar--, nIdx++)
      {
         operator+=(Pow10 * (unsigned int)(*pChar - '0'));
         Pow10*=10;
      }
   }
   return *this;
}


CBigNum &CBigNum::operator+=(const CBigNum &rhs)
{
   unsigned int nIdx;

   if (rhs.m_nSize > m_nSize)
      Resize(rhs.m_nSize);

   for (nIdx = 0; nIdx < rhs.m_nSize; nIdx++)
   {
      m_arVal[nIdx] += rhs.m_arVal[nIdx];
   }
   
   HandleCarry();
   return *this;
}

CBigNum &CBigNum::operator=(unsigned int intVal)
{
   unsigned int nIdx;

   for (nIdx = 0; nIdx < m_nSize; nIdx++)
   {
      m_arVal[nIdx] = 0;
   }

   if (m_nSize <= 0)
      Resize(1);

   m_arVal[0] = intVal;
   
   HandleCarry();
   return *this;
}

void CBigNum::HandleCarry()
{
   unsigned int nIdx;

   for (nIdx=0; nIdx < m_nSize; nIdx++)
   {
      if ((m_arVal[nIdx] & 0xFFFF0000) != 0)
      {
         if (nIdx >= m_nSize - 1)
         {
            Resize(nIdx + 2);
         }
         m_arVal[nIdx+1] += (m_arVal[nIdx] >> 16);
         m_arVal[nIdx] &= 0xFFFF;
      }
   }
}

void CBigNum::Resize(unsigned int nNewSize)
{
   unsigned int *pNewVal;
   unsigned int nIdx;

   if (nNewSize > 0)
      pNewVal = new unsigned int[nNewSize];
   else
      pNewVal = NULL;

   if (nNewSize < m_nSize)
      m_nSize = nNewSize;

   for (nIdx=0; nIdx < m_nSize; nIdx++)
   {
      pNewVal[nIdx] = m_arVal[nIdx];
   }

   for (;nIdx<nNewSize; nIdx++)
   {
      pNewVal[nIdx] = 0;
   }

   if (m_arVal)
      delete[] m_arVal;

   m_arVal = pNewVal;
   m_nSize = nNewSize;
}

CBigNum &CBigNum::operator>>=(unsigned int rhs)
{
   unsigned int nIdx;

   if (m_nSize)
   {
      while(rhs>=16)
      {
         for (nIdx=0; nIdx < m_nSize-1; nIdx++)
         {
            m_arVal[nIdx] = m_arVal[nIdx+1];
         }
         rhs-=16;
         m_arVal[nIdx] = 0;
      }
   }

   for (nIdx=0; nIdx < m_nSize-1; nIdx++)
   {
      m_arVal[nIdx] = (m_arVal[nIdx] >> rhs) | ((m_arVal[nIdx+1] << (16 - rhs)) & 0xFFFF);
   }
   
   if (nIdx < m_nSize)
      m_arVal[nIdx] >>= rhs;

   return *this;
}

CBigNum &CBigNum::operator<<=(unsigned int rhs)
{
   unsigned int nIdx;

   if (m_nSize)
   {
      while(rhs>=16)
      {
         if (m_arVal[m_nSize-1])
            Resize(m_nSize+1);
         for (nIdx = m_nSize-1; nIdx > 0; nIdx--)
         {
            m_arVal[nIdx] = m_arVal[nIdx-1];
         }
         rhs -=16;
         m_arVal[0] = 0;
      }

      if ((m_arVal[m_nSize - 1] << rhs) & 0xFFFF0000)
         Resize(m_nSize + 1);
   }

   if (m_nSize)
   {
      for (nIdx = m_nSize-1; nIdx > 0; nIdx--)
      {
         m_arVal[nIdx] = (m_arVal[nIdx] << rhs) | (m_arVal[nIdx-1] >> (16-rhs));
         m_arVal[nIdx] &= 0xFFFF;
      }
      m_arVal[0] <<= rhs;
      m_arVal[0] &= 0xFFFF;
   }

   return *this;
}

CBigNum CBigNum::operator<<(unsigned int rhs) const
{
   CBigNum result(*this);
   result <<= rhs;
   return result;
}

CBigNum CBigNum::operator>>(unsigned int rhs) const
{
   CBigNum result(*this);
   result >>= rhs;
   return result;
}

CBigNum::operator bool(void) const
{
   unsigned int nIdx;

   for (nIdx=0; nIdx < m_nSize; nIdx++)
      if (m_arVal[nIdx]) return true;
   
   return false;
}


CBigNum & CBigNum::operator&=(CBigNum rhs)
{
   unsigned int nIdx;
   unsigned int nMin;

   if (rhs.m_nSize < m_nSize)
      nMin = rhs.m_nSize;

   for (nIdx=0; nIdx < nMin; nIdx++)
      m_arVal[nIdx] &= rhs.m_arVal[nIdx];

   for (;nIdx < m_nSize; nIdx++)
      m_arVal[nIdx] = 0;
   
   return *this;
}

unsigned int CBigNum::operator&(unsigned int rhs)
{
   if (m_nSize)
      return m_arVal[0] & rhs;
   else
      return 0;
}

CBigNum &CBigNum::operator=(CBigNum rhs)
{
   if (rhs.m_arVal != m_arVal)
   {
      delete m_arVal;
      m_arVal = NULL;
      m_nSize=0;

      unsigned int nIdx;
      Resize(rhs.m_nSize);
      for (nIdx = 0; nIdx < m_nSize; nIdx++)
         m_arVal[nIdx] = rhs.m_arVal[nIdx];
   }
   return *this;
}

CBigNum CBigNum::Pow(unsigned int rhs) const
{
   CBigNum Result(1);
   CBigNum CurrentVal = *this;

   while (rhs)
   {
      if (rhs & 1U)
         Result *=(CurrentVal);
      rhs >>= 1;
      CurrentVal *= CurrentVal;
   }
   
   return Result;
}

CBigNum CBigNum::PowMod(CBigNum rhs, const CBigNum &mod, const clock_t ctShowSteps) const
{
   CBigNum Result(1);
   CBigNum CurrentVal = *this;
   int nSteps = rhs.log2();
   clock_t ctStart, ctCurrent;

   ctStart = ctCurrent = clock();

   while (rhs > 0U)
   {

      if (rhs.m_arVal[0] & 1U)
      {
         Result = (Result * CurrentVal) % mod;
         Result.Reduce();
      }
      rhs>>=1U;
      CurrentVal = (CurrentVal * CurrentVal) % mod;
      CurrentVal.Reduce();
      nSteps--;
      if (ctShowSteps)
      {
         if (clock() > ctCurrent + ctShowSteps)
         {
          
            ctCurrent = clock();
         }
      }
   }
   
   return Result;
}

bool CBigNum::operator==(unsigned int rhs) const
{
   if (m_nSize>=2)
      return ((m_arVal[0] == (rhs & 0xFFFF)) && ((m_arVal[1]<<16) == (rhs & 0xFFFF0000)));
   else if (m_nSize==1)
      return (m_arVal[0] == rhs);
   else
      return (rhs == 0);
}

bool CBigNum::operator!=(unsigned int rhs) const
{
   return !(operator==(rhs));
}

CBigNum CBigNum::operator *(const CBigNum &rhs) const
{
   CBigNum Result=0U;
   unsigned int i, j;

   if (Result.m_nSize != rhs.m_nSize + m_nSize)
      Result.Resize(rhs.m_nSize + m_nSize);
   for (i=0; i < m_nSize; i++)
   {
      for (j=0; j<rhs.m_nSize; j++)
         Result.m_arVal[i+j] += m_arVal[i] * rhs.m_arVal[j];
      Result.HandleCarry();
   }
   return Result;
}

CBigNum &CBigNum::operator *=(const CBigNum &rhs)
{
   return *this = *this * rhs;
}

CBigNum CBigNum::operator *(unsigned int rhs) const
{
   unsigned int nIdx;

   CBigNum result(*this);

   if (result.m_nSize==0)
   {
      return result;
   }

   for (nIdx = 0; nIdx < result.m_nSize; nIdx++)
   {
      result.m_arVal[nIdx] *= rhs;
   }
   result.HandleCarry();
   return result;
}

CBigNum::CBigNum(const CBigNum &copy) : m_nSize(0), m_arVal(0)
{
   unsigned int nIdx;

   Resize(copy.m_nSize);

   for (nIdx = 0; nIdx < m_nSize; nIdx++)
      m_arVal[nIdx] = copy.m_arVal[nIdx];
}

CBigNum &CBigNum::operator*=(unsigned int rhs)
{
   unsigned int nIdx;

   if (m_nSize <= 0)
   {
      operator=(0U);
   }
   else
   {
      for (nIdx = 0; nIdx < m_nSize; nIdx++)
      {
         m_arVal[nIdx] *= rhs;
      }
      HandleCarry();
   }
   return *this;
}

CBigNumString::CBigNumString() : m_szBuffer(NULL), m_nSize(0)
{
}

CBigNumString::~CBigNumString()
{
   if (m_szBuffer)
   {
      delete[] m_szBuffer;
      m_szBuffer = NULL;
      m_nSize = 0;
   }
}

void CBigNumString::Realloc(unsigned int nByteCount)
{
   if (m_szBuffer)
   {
      delete[] m_szBuffer;
      m_szBuffer = NULL;
   }
   m_szBuffer = new char[nByteCount];
   memset(m_szBuffer, 0, nByteCount);
   m_nSize = nByteCount;
}

CBigNumString::CBigNumString(const CBigNumString &rhs) : m_szBuffer(NULL), m_nSize(0)
{
   if ((rhs.m_szBuffer) && (rhs.m_nSize > 0))
   {
      m_szBuffer = new char[rhs.m_nSize];
      strcpy(m_szBuffer, rhs.m_szBuffer);
      m_nSize = rhs.m_nSize;
   }
}

CBigNumString::operator const char *() const
{
   return m_szBuffer;
}

CBigNum CBigNum::FromByteString(const char *szIn, const unsigned int nLength)
{
   CBigNum Result;
   unsigned int i, r;
   unsigned int nUseLength;

   if (!nLength)
      nUseLength = strlen(szIn);
   else
      nUseLength = nLength;

   Result.m_nSize = (nUseLength+1) >> 1;
   Result.m_arVal = new unsigned int[Result.m_nSize];

   for (i=0; i<nUseLength; i+=1)
   {
      r = nUseLength - 1 - i;
      if (i % 2)
         Result.m_arVal[i >> 1] |= ((unsigned int)szIn[r]) << 8;
      else
         Result.m_arVal[i >> 1] = szIn[r];
   }

   return Result;
}

CBigNum CBigNum::FromHexString(const char *szIn)
{
   CBigNum Result;
   unsigned int i, r;
   unsigned int nUseLength;
   unsigned int nPlaceVal;

   nUseLength = strlen(szIn);
   
   Result.m_nSize = (nUseLength+3) >> 2;
   Result.m_arVal = new unsigned int[Result.m_nSize];

   for (i=0; i<nUseLength; i+=1)
   {
      r = nUseLength - 1 - i;
      if ((szIn[r] >= '0') && (szIn[r] <= '9'))
         nPlaceVal = szIn[r] - '0';
      else if ((szIn[r] >= 'A') && (szIn[r] <= 'F'))
         nPlaceVal = szIn[r] - 'A' + 10;
      else if ((szIn[r] >= 'a') && (szIn[r] <= 'f'))
         nPlaceVal = szIn[r] - 'a' + 10;
      else
         nPlaceVal = 0;

      if (!(i % 4))
         Result.m_arVal[i >> 2] = nPlaceVal;
      else
         Result.m_arVal[i >> 2] |= nPlaceVal << ((i % 4) << 2);
   }
   return Result;
}

CBigNum CBigNum::FromBase64String(const char *szIn)
{
   CBigNum Result;
   int i, r;
   const char *pc;
   unsigned int nUseLength;
   unsigned int nByteCount;
   unsigned char szCharMap[255];
   unsigned char bin[4], bout;
   
   memset(szCharMap, 255, 255);
   for (i=0; i<sizeof(szBase64)-1; i++)
   {
      szCharMap[szBase64[i]] = i;
   }
   szCharMap['='] = 0;

   nUseLength = strlen(szIn);
   nByteCount = (nUseLength / 4) * 3;

   Result.Resize((nByteCount+1)/2);

   for (pc=szIn+nUseLength-1;((pc > szIn) && (255 == szCharMap[*pc]));pc--)
      ;
   for (r=0; r<4; r++)
   {
      bin[r] = *pc;
      while ((pc > szIn) && (255 == szCharMap[*(--pc)]))
         ;
   }

   i=0;
   if (bin[0] == '=')
      i=-1;
   if (bin[1] == '=')
      i=-2;

   while (true)
   {
      if ((i>=0) && ((unsigned)i>>1 < Result.m_nSize))
      {
         bout = szCharMap[bin[0]] | ((szCharMap[bin[1]] & 0x03) << 6);
         Result.m_arVal[i>>1] |= bout << ((i % 2) << 3);
      }   
      i++;

      if ((i>=0) && ((unsigned)i>>1 < Result.m_nSize))
      {
         bout = ((szCharMap[bin[1]] & 0x3C) >> 2) | ((szCharMap[bin[2]] & 0x0F) << 4);
         Result.m_arVal[i>>1] |= bout << ((i % 2) << 3);
      }
      i++;

      if ((unsigned)i>>1 < Result.m_nSize)
      {
         bout = ((szCharMap[bin[2]] & 0x30) >> 4) | (szCharMap[bin[3]] << 2);
         Result.m_arVal[i>>1] |= bout << ((i % 2) << 3);
      }
      i++;

      if (pc <= szIn)
         break;

      for (r=0; r<4; r++)
      {
         bin[r] = *pc;
         while ((pc > szIn) && (255 == szCharMap[*(--pc)]))
            ;
      }      
   }

   Result.Reduce();
   return Result;
}

CBigNumString CBigNum::ToByteString(bool bMakePrintable) const
{
   CBigNumString Result;
   unsigned int nOutSize = m_nSize * 2;
   unsigned int i, r;

   while ((nOutSize > 0) && !(m_arVal[(nOutSize-1) >> 1] & (0xFF << (((nOutSize-1) % 2) << 3))))
      nOutSize--;

   Result.Realloc(nOutSize+1);
   for (i=0; i<nOutSize; i++)
   {
      r = nOutSize - 1 - i;
      if (i % 2)
         Result[r] = (m_arVal[i >> 1] >> 8) & 0xFF;
      else
         Result[r] = m_arVal[i >> 1] & 0xFF;
      if (bMakePrintable)
      {
         switch (Result[r] & 0xE0)
         {
         case 0:
            switch(Result[r])
            {
            case 10: // lf
            case 13: // cr
               break;
            default:
               Result[r] = '.';
               break;
            }
            break;
         case 0x80:
         case 0xA0:
         case 0xC0:
         case 0xE0:
            Result[r] = '.';
            break;
         default:
            break;
         }
      }
   }

   Result[nOutSize] = '\0';
   return Result;
}

CBigNumString CBigNum::ToHexString() const
{
   CBigNumString Result;
   unsigned int nOutSize = m_nSize * 4;
   unsigned int i, r;

   while ((nOutSize > 0) && !(m_arVal[(nOutSize-1) >> 2] & (0xF << (((nOutSize-1) % 4) << 2))))
      nOutSize--;

   Result.Realloc(nOutSize+1);
   for (i=0; i<nOutSize; i++)
   {
      r = nOutSize - 1 - i;
      switch((m_arVal[i >> 2] >> ((i % 4) << 2)) & 0xF)
      {
      case 0:
         Result[r] = '0';
         break;
      case 1:
         Result[r] = '1';
         break;
      case 2:
         Result[r] = '2';
         break;
      case 3:
         Result[r] = '3';
         break;
      case 4:
         Result[r] = '4';
         break;
      case 5:
         Result[r] = '5';
         break;
      case 6:
         Result[r] = '6';