大数运算和RSA算法

（要测试代码的发Email给[email protected]）

前几天不忙，于是想起加密算法，但是RSA加密是依赖大数运算，
而且主流RSA算法都建立在512位到1024位的。而现有的计算机
数据类型最大的也就是64（int64),于是自己编了一个大数类
CXWord来实现1024位的大数运算。
基本思想就是用DWORD[32]的数组来存储，具体实现如下。
(为加快运行速度，所有的函数都是内联的)
/****************************************************************/
file://长WORD数头文件：CXWord.h
file://作者：[email protected]
file://版本：1.0 (2004.2.17)
file://说明： 将大数看作一个n进制数组，对于目前的32位系统而言n可以取
file://值为2的32次方，即0x00000000 <> 0xffffFFFF
/****************************************************************/
file://#if !defined WWB_XWORD2004021711025632100
#ifndef WWB_XWORD2004021711025632100
#define WWB_XWORD2004021711025632100
file://#define WWB_XWORDDEBUG
file://数组位数，表示可表示的最大数是2^(32*32)=2^1024,即可表示1024位数
const DWORD XWORDLEN= 32;  
class CXWord
{
private: 
 DWORD Data[XWORDLEN];//重载 []等
public:
 inline int Getlen() const;
 inline CXWord LOffset(int value);
 inline CXWord operator+(const CXWord value) const;
 inline CXWord operator+(const DWORD value)const;
 inline CXWord operator-(const CXWord value)const;
 inline CXWord operator-(const DWORD value)const;
 inline CXWord operator*(const CXWord value)const;
 inline CXWord operator*(const DWORD value)const;
 inline CXWord operator/(const CXWord value)const;
 inline CXWord operator/(const DWORD value)const;
 inline CXWord operator%(const CXWord value)const;
 inline DWORD  operator%(const DWORD value)const;
 inline CXWord operator=(const CXWord value);
 inline CXWord operator=(const DWORD value);
 inline CXWord operator<<(const DWORD BitCount);
 inline CXWord operator>>(const DWORD BitCount);

 inline bool operator>(const DWORD value)const;
 inline bool operator>(const CXWord value)const;
 inline bool operator<(const DWORD value)const;
 inline bool operator<(const CXWord value)const;
 inline bool operator>=(const DWORD value)const;
 inline bool operator>=(const CXWord value)const;
 inline bool operator<=(const DWORD value)const;
 inline bool operator<=(const CXWord value)const;
 inline bool operator==(const CXWord value)const;
 inline bool operator==(const DWORD value)const;
 inline CXWord sqrt() const;

 inline CString Format16()const; 
 inline CString Format10()const;
 inline void operator++(); 
 inline void operator--();
 inline CXWord();
 inline CXWord(CString value);
 inline ~CXWord(){;}
};
file://DWORD CharToNum(char c);

inline DWORD CharToNum(char c)
{
 switch(c)
 {
 case '0':
 case '1':
 case '2':
 case '3':
 case '4':
 case '5':
 case '6':
 case '7':
 case '8':
 case '9':
  return 0+c-'0';
 case 'A':
 case 'B':
 case 'C':
 case 'D':
 case 'E':
 case 'F':
  return 10 + c-'A';
 }
 CString str1=c;
 MessageBox(0,"不正确的字符",str1,MB_OK|MB_ICONSTOP);
 return 0;
}
CXWord::CXWord()
{
 for(DWORD d=0;d<XWORDLEN;d++) this->Data[d]=0;
}
inline CXWord::CXWord(CString value)
{
 CXWord tmp;
 *this=0;
 file://去掉中间的空逗号
 CString str1=value;
 value="";
 for(DWORD d=0;d<str1.GetLength();d++)
 {
  char c;
  c=str1.GetAt(d);
  if((c!=' ')&&(c!=',')) value=value+c;
 }
  

 value.MakeUpper();
 if(value.Left(2) =="0X")
 {
  value.Delete(0,2);
  for(DWORD d=0;d<value.GetLength();d++)
  { 
   tmp=CharToNum(value.GetAt(d));
   for(int d2=value.GetLength()-1;d2>d;d2--)
    tmp=tmp*16;

   *this =*this+tmp;
  }
 }
 else
 {
  for(int d=value.GetLength()-1;d>=0;d--)
  {  
   tmp=CharToNum(value.GetAt(d));
   for(DWORD d2=0;d2<(value.GetLength() -1-d);d2++)
    tmp=tmp*10;

   *this =*this+tmp;
  }
 }
}
CString CXWord::Format16()const
{
 CString str1,str2;
 int dLen = this->Getlen();
 for(int d=0;d<dLen;d++)
 {
  str1.Format("%08X,",this->Data[d]);
  str2=str1+str2;
 }
 str2="0X"+str2;
 return str2;
}

CString CXWord::Format10()const
{
 CString str1,str2;
 CXWord Residue, Quotient,Dividend=(*this), tmp=(*this);//余数，商，被除数,临时
 int i=0;
 while (Dividend>=10)
 {
  i++;
  Quotient=Dividend / 10;
  Residue=Dividend - Quotient * 10;//<10
  str1.Format("%01d",Residue.Data[0]);
  if(i%10==0) str1=","+str1;
  str2=str1+str2;
  Dividend=Quotient;
 }
 str1.Format("%01d",Dividend);
 str2=str1+str2;
 return str2;
}

inline bool CXWord::operator==(const CXWord value) const
{
 for(DWORD d=0;d<XWORDLEN;d++)
  if (value.Data[d]!=this->Data[d]) return false;
 return true;
}
inline bool CXWord::operator==(const DWORD value) const
{
 for(DWORD d=1;d<XWORDLEN;d++)
  if (this->Data[d]!=0) return false;
 if (this->Data[0]==value) return true;
 else return false;
}
inline CXWord CXWord::operator =(const CXWord value)
{
 for(DWORD d=0;d<XWORDLEN;d++) this->Data[d]=value.Data[d];
 return *this;
}
inline CXWord CXWord::operator=(const DWORD value)
{ 
 Data[0]=value;
 for(DWORD d=1;d<XWORDLEN;d++) Data[d]=0;
 return *this;
}
/*inline CXWord CXWord::operator=(const CXWord value)
{
 for(DWORD d=0;d<XWORDLEN;d++) Data[d]=value.Data[d];
 return *this;
}*/
inline CXWord CXWord::sqrt() const
{
 CXWord result, MaxResult,MinResult, xtmp;

 int RLen=this->Getlen() ;
 MaxResult.Data[(RLen+1)/2]=1; file://可能的最大商
 if (RLen>=1) MinResult.Data[(RLen-1)/2]=1;

 while(true)
 {
  result=(MaxResult+MinResult) /2;
  if(result*result>(*this))
  {
   MaxResult=result;
  }
  else if(result*result<=(*this))
  {
   xtmp=result+1;
   if ( xtmp*xtmp<=*this)
   {
    MinResult=result;
   }
   else break;//return result;
  }

 }
 return result;
};
inline CXWord CXWord::operator/(const CXWord value) const
{
 CXWord result, MaxResult,MinResult;
 if((*this)<value) return result;
 if(value==0) throw("Error");

 int RLen=this->Getlen() - value.Getlen();
 file://for(DWORD d=0;d<XWORDLEN;d++) MaxResult.Data[d]=0xffffFFFF;
 MaxResult.Data[RLen+1]=1; file://可能的最大商
 if (RLen>=1) MinResult.Data[RLen-1]=1;
 

 while(true)
 {
  result=(MaxResult+MinResult) /2;
  if(result*value>(*this))
  {
   MaxResult=result;
  }
  else if(result*value<=(*this))
  {
   if ((*this) - result*value>=value)
   {
    MinResult=result;
   }
   else break;//return result;
  }

 }
 return result;
}
inline CXWord CXWord::operator%(const CXWord value) const
{
    CXWord result, tmp;
 tmp=(*this) / value;
 result=((*this) - tmp*value);
 return result;
}
inline CXWord CXWord::operator/(const DWORD value) const
{
 //  XYZK / w
 //
 //
 int DataLen;
 for(DataLen=XWORDLEN;DataLen>0;DataLen--)
  if (Data[DataLen-1]!=0) break;
 unsigned __int64 dividend;//被除数
 DWORD Residue, Quotient;//，余数，商，Divisor除数

 DWORD DQWS=DataLen-1;//当前位数
 CXWord  xQuotient, xTemp=*this;

 while(true)
 {
  if (xTemp.Data[DQWS]<value)
  {
   if (DQWS==0)
   {
   // xQuotient.Data[0]=0;
    break;
   }
   else
   {
    dividend =xTemp.Data[DQWS];
    dividend =dividend<<32;
    dividend =dividend +xTemp.Data[DQWS-1];
    file://dividend=(xTemp.Data[DQWS]<<32) + xTemp.Data[DQWS-1];
    Residue = dividend % value;
    Quotient= dividend / value;

    xTemp.Data[DQWS]=0;
    xTemp.Data[DQWS-1]=Residue;
    xQuotient.Data[DQWS-1]=Quotient;
    DQWS--;
   }
  }
  else//xTemp.Data[DQWS]>=value
  {
   dividend=xTemp.Data[DQWS];
   Residue=dividend % value;
   Quotient=dividend/ value;

   xQuotient.Data[DQWS]=Quotient+xQuotient.Data[DQWS];
   xTemp.Data[DQWS]=Residue;

  }
 }
 return  xQuotient;
}

inline DWORD CXWord::operator %(const DWORD value) const
{
 CXWord w1;
 w1=*this / value;
 w1=*this - (w1 * value);
    return w1.Data[0];

}
//    a b
// +b c d
//  

inline CXWord CXWord::operator +(const CXWord value) const
{
 CXWord result;
 unsigned __int64 x,Carry=0;//进位标志
 for(DWORD d=0;d<XWORDLEN;d++)
 {
  x=(unsigned  __int64)value.Data[d]+this->Data[d]+Carry;
  Carry=x>>32;
  result.Data[d]=(x<<32)>>32;
 }
 if (Carry!=0)
 {
  #ifdef WWB_XWORDDEBUG 
  throw("超出XWORD范围");
  #endif
  for(DWORD d=0;d<XWORDLEN;d++) result.Data[d]=0xFFFFffff;
 }
 return result;
}
inline CXWord CXWord::operator+(const DWORD value) const
{
 DWORD Carry=0;//进位标志
 CXWord result;
 unsigned __int64 x;

 x=(unsigned __int64)value+this->Data[0];
 Carry=x>>32;
 result.Data[0]=(x<<32)>>32;
 for(DWORD d=1;d<XWORDLEN;d++)
 {
  x=(unsigned __int64)this->Data[d]+Carry;
  Carry=x>>32;
  result.Data[d]=(x<<32)>>32;
 }
 if (Carry!=0)
 {
  #ifdef WWB_XWORDDEBUG 
  throw("超出XWORD范围");
  #endif
  for(DWORD d=0;d<XWORDLEN;d++) result.Data[d]=0xFFFFffff;
 }
 return result; 
}
inline void CXWord::operator ++()
{
 file://为了加快运速度这里用到了移位
 file://把从右到左的最后一个零变为1，该位后面的位都变成0    
 bool bFind1=false;//
 for(DWORD Digit=0;Digit<XWORDLEN;Digit++)
 {
  for(DWORD d2=0;d2<32;d2++)
  {
   DWORD dx=(Data[Digit]<<(31-d2));
   dx=(dx>>31); 
   
   if(((Data[Digit]<<(31-d2))>>31)==0)//该位是否是0
   {
    Data[Digit]=(Data[Digit] | (1l<<d2));//把该为变为1
    Data[Digit]=(Data[Digit] & (0xffffFFFF<<(d2)));//把前一位变为0
    for(DWORD d3=0;d3<Digit;d3++)
     Data[d3]=0;
    bFind1=true;
    break;
   }
  }
  if(bFind1) break;
 }
}

inline bool CXWord::operator>(const DWORD value) const
{
 for(DWORD d=1; d<XWORDLEN; d++)
  if (this->Data[d]>0) return true;
 
 return (Data[0]>value) ;
}
inline bool CXWord::operator>(const CXWord value) const
{
 for(int d=XWORDLEN-1;d>=0;d--)
 {
  if (Data[d]>value.Data[d]) return true;
  else if(Data[d]<value.Data[d]) return false;
 }
 return false;
}
inline bool CXWord::operator<(const DWORD value) const
{
 for(DWORD d=1; d<XWORDLEN; d++)
  if (this->Data[d]>0) return false;
 
 return(Data[0]<value);
}
inline bool CXWord::operator<(const CXWord value) const
{
 for(int d=XWORDLEN-1;d>=0;d--)
 {
  if (Data[d]<value.Data[d]) return true;
  else if(Data[d]>value.Data[d]) return false;
 }
 return false;
}
inline bool CXWord::operator>=(const DWORD value) const
{
 for(DWORD d=1; d<XWORDLEN; d++)
  if (this->Data[d]>0) return true; 
 return(Data[0]>=value);
}
inline bool CXWord::operator>=(const CXWord value) const
{
 for(int d=XWORDLEN-1;d>=0;d--)
 {
  if (Data[d]>value.Data[d]) return true;
  else if(Data[d]<value.Data[d]) return false;
 }
 return true;
}
inline bool CXWord::operator<=(const DWORD value) const
{
  for(DWORD d=1; d<XWORDLEN; d++)
  if (this->Data[d]>0) return false; 
 return(Data[0]<=value);
}
inline bool CXWord::operator<=(const CXWord value) const
{
 for(int d=XWORDLEN-1;d>=0;d--)
 {
  if (Data[d]>value.Data[d]) return false;
  else if(Data[d]<value.Data[d]) return true;
 }
 return true;
}
inline CXWord CXWord::operator*(const CXWord value)const
{
 CXWord result,tmp;
 for(DWORD d=0;d<XWORDLEN;d++)
 {
  if (Data[d]==0) continue;
  tmp=value*Data[d] ; 
  
 // for(DWORD d2=0;d2<d;d2++) tmp=tmp * (0xFFFFffff+1);
  #ifdef WWB_XWORDDEBUG 
   for(int i=XWORDLEN-1;i>XWORDLEN-1-i;i--) 
    if(tmp.Data[i]>0) throw("超出XWORD范围");
  #endif

  for(DWORD d2=0;(d2<XWORDLEN - d) && (d!=0) ;d2++)
  {

   tmp.Data[XWORDLEN-1-d2]=tmp.Data[XWORDLEN-1-d-d2];
   
  }
  for(DWORD d3=0;d3<d;d3++) tmp.Data[d3]=0; 

  result= result+tmp;

 }
 return result;
}
inline CXWord CXWord::operator*(const DWORD value)const
{
 CXWord result;
 unsigned __int64 x, Carry=0;//进位标志
 for(DWORD d=0;d<XWORDLEN;d++)
 {
  x=(unsigned __int64)Data[d]*value+Carry;
  result.Data[d]=((x<<32)>>32);
  Carry=(x>>32);  
 }
 if (Carry!=0)
 {
  #ifdef WWB_XWORDDEBUG 
  throw("超出XWORD范围");
  #endif
  for(DWORD d=0;d<XWORDLEN;d++) result.Data[d]=0xFFFFffff;
 } 
 return result;
}
inline CXWord CXWord::operator-(const CXWord value)const
{
 CXWord result, tmp;
 if(*this<value)
 {
  #ifdef WWB_XWORDDEBUG 
  throw("超出XWORD范围");
  #endif
  return result;
 }
 unsigned __int64 Minuend, Subtrahend;//被减数，减数 结果
 tmp=(*this);
 for(DWORD d=0;d<XWORDLEN;d++)
 {
  if(tmp.Data[d]>=value.Data[d]) result.Data[d]=tmp.Data[d]-value.Data[d];
  else
  {
   file://借位
   Minuend=1;
   Minuend=(Minuend<<32) + tmp.Data[d];//not Minuend<<31
   result.Data[d]=Minuend - value.Data[d];
   for(DWORD d2=d+1; d2<XWORDLEN;d2++)
   {
    if(tmp.Data[d2]!=0)
    {
     tmp.Data[d2]--;
     for(DWORD d3= d+1; d3<d2;d3++) tmp.Data[d3]=0xFFFFffff;
    }
   }

  }
 }
 return result;
}
inline CXWord CXWord::operator-(const DWORD value)const
{

 CXWord result;
 if(*this<value)
 {
  #ifdef WWB_XWORDDEBUG 
  throw("超出XWORD范围");
  #endif
  return result;
 }
 result=(*this);
 if(Data[0]>=value)  result.Data[0]=Data[0]-value;
 else
 {
  unsigned __int64 tmp;
  tmp=1;
  tmp=(tmp<<32);//32 not 31
  tmp=tmp + Data[0] - value;
  result.Data[0]=tmp;
  for(DWORD d=1;d<XWORDLEN;d++)
  {
   if (result.Data[d]>0)
   {
    for(DWORD d2=1;d2<d;d2++) result.Data[d2]=0xFFFFffff;
    result.Data[d]=result.Data[d]-1;
    break;
   }
  }
 }
 return result;
}
inline int CXWord::Getlen()const
{
 int i;
 for (i=XWORDLEN;i>0;i--)
 {
  if(Data[i-1]!=0)
   break;
 }
 return i;
}
inline CXWord CXWord::LOffset(int value)
{
 if(abs(value)>=XWORDLEN-1)
 {
  for(int i=0;i<XWORDLEN;i++)
   Data[i]=0;
 }
 else if(value >0)
 {
  for(int i=XWORDLEN -1; i>=value;i--)
   Data[i]=Data[i-value];
  
  for( i=0;i<value;i++)
   Data[i]=0;
 }
 else if (value<0)
 {
  for(int i=0; i<=XWORDLEN + value;i++)
   Data[i]=Data[i-value];  
  for( i=value;i<0;i++)
   Data[XWORDLEN -1 +i]=0;
 }
 return *this;
}

#endif

本文地址：http://com.8s8s.com/it/it1241.htm