大数运算和RSA算法

（要测试代码的发Email给wwb206@163.com）

前几天不忙，于是想起加密算法，但是RSA加密是依赖大数运算，

而且主流RSA算法都建立在512位到1024位的。而现有的计算机

数据类型最大的也就是64（int64),于是自己编了一个大数类

CXWord来实现1024位的大数运算。

基本思想就是用DWORD[32]的数组来存储，具体实现如下。

(为加快运行速度，所有的函数都是内联的)

/****************************************************************/

file://长WORD数头文件：CXWord.h

file://作者：wwb206@163.com

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

• ·JDO Query介绍
• ·用 Javascript 实现的“Dual l
• ·最短的无组件上传代码（仅9行）
• ·开发工具浅谈
• ·DOS下的保留
• ·动态设置系统日期格式
• ·泛型(Generics Types)学习笔记&
• ·Asp:base64编码、解码函数
• ·软件产品的可用性的测试
• ·设计优秀的用户界面