新建文本文档.txt

rsa 加密算法 c++ 实现

unsigned __int64 num;
unsigned long *s,*d;
       if(cmp>0)
               {
                       s=X.m_ulvalue;
                       d=A.m_ulvalue;
                       len=X.m_nLength;
               }
       if(cmp<0)
               { 
                       s=A.m_ulvalue;
                       d=X.m_ulvalue;
                       len=A.m_nLength;
                       X.m_nSign=1-X.m_nSign;
               }
       for(int i=0;i{
if((s[i]-carry)>=d[i])
{
X.m_ulvalue[i]=s[i]-carry-d[i];
carry=0;
}
else
{
num=0x100000000+s[i];
X.m_ulvalue[i]=(unsigned long)(num-carry-d[i]);
carry=1;
}
}
while(X.m_ulvalue[len-1]==0)len--;
X.m_nLength=len;
return X;
}
else{X.Mov(A);X.m_nSign=1-X.m_nSign;return Add(X);}
} 


//大数相乘
//调用形式：N.Mul(A)，返回值：N*A
/******************************************************************/
例如：
        A  B  C
*          D  E
----------------
=    S  F  G  H
+ T  I  J  K
----------------
= U  V  L  M  N 


其中，SFGH=ABC*E，TIJK=ABC*D 


而对于：
     A  B  C
*          E
-------------
= S  F  G  H     


其中，若C*E<=0xffffffff，则H=C*E，carry(进位标志)=0
     若C*E>0xffffffff，则H=(C*E)&0xffffffff
       carry=(C*E)/0xffffffff
     若B*E+carry<=0xffffffff，则G=B*E+carry，carry=0
     若B*E+carry>0xffffffff，则G=(B*E+carry)&0xffffffff
       carry=(B*E+carry)/0xffffffff
     若A*E+carry<=0xffffffff，则F=A*E+carry，carry=0
     若A*E+carry>0xffffffff，则F=(A*E+carry)&0xffffffff
       carry=(A*E+carry)/0xffffffff
     S=carry
/*****************************************************************/
CBigInt CBigInt::Mul(CBigInt& A)
{
CBigInt X,Y;
unsigned __int64 mul;
       unsigned long carry;
       for(int i=0;i{
Y.m_nLength=m_nLength;
carry=0;
for(int j=0;j{
mul=m_ulvalue[j];
mul=mul*A.m_ulvalue[i]+carry;
Y.m_ulvalue[j]=(unsigned long)mul;
carry=(unsigned long)(mul>>32);
}
if(carry&&(Y.m_nLength               {
                       Y.m_nLength++;
                       Y.m_ulvalue[Y.m_nLength-1]=carry;
               }
if(Y.m_nLength{
Y.m_nLength+=i;
       for(int k=Y.m_nLength-1;k>=i;k--)Y.m_ulvalue[k]=Y.m_ulvalue[k-i];
       for(k=0;k}
X.Mov(X.Add(Y));
}
if(m_nSign+A.m_nSign==1)X.m_nSign=0;
else X.m_nSign=1;
return X;
} 


//大数相除
//调用形式：N.Div(A)，返回值：N/A
//除法的关键在于“试商”，然后就变成了乘法和减法
//这里将被除数与除数的试商转化成了被除数最高位与除数最高位的试商
CBigInt CBigInt::Div(CBigInt& A)
{
CBigInt X,Y,Z;
int len;
unsigned __int64 num,div;
unsigned long carry=0;
Y.Mov(*this);
while(Y.Cmp(A)>0)
{       
if(Y.m_ulvalue[Y.m_nLength-1]>A.m_ulvalue[A.m_nLength-1])
{
len=Y.m_nLength-A.m_nLength;
div=Y.m_ulvalue[Y.m_nLength-1]/(A.m_ulvalue[A.m_nLength-1]+1);
}
else if(Y.m_nLength>A.m_nLength)
{
len=Y.m_nLength-A.m_nLength-1;
num=Y.m_ulvalue[Y.m_nLength-1];
num=(num<<32)+Y.m_ulvalue[Y.m_nLength-2];
if(A.m_ulvalue[A.m_nLength-1]==0xffffffff)div=(num>>32);
else div=num/(A.m_ulvalue[A.m_nLength-1]+1);
}
else
{
                       X.Mov(X.Add(1));
break;
}
               Z.Mov(div);
Z.m_nLength+=len;
for(int i=Z.m_nLength-1;i>=len;i--)Z.m_ulvalue[i]=Z.m_ulvalue[i-len];
for(i=0;iX.Mov(X.Add(Z));
Z.Mov(Z.Mul(A));
Y.Mov(Y.Sub(Z));
}
if(Y.Cmp(A)==0)X.Mov(X.Add(1));
if(m_nSign+A.m_nSign==1)X.m_nSign=0;
else X.m_nSign=1;
return X;
} 


//大数求模
//调用形式：N.Mod(A)，返回值：N%A
//求模与求商原理相同
CBigInt CBigInt::Mod(CBigInt& A)
{
CBigInt X,Y;
int len;
unsigned __int64 num,div;
unsigned long carry=0;
X.Mov(*this);
while(X.Cmp(A)>0)
{       
if(X.m_ulvalue[X.m_nLength-1]>A.m_ulvalue[A.m_nLength-1])
{
len=X.m_nLength-A.m_nLength;
div=X.m_ulvalue[X.m_nLength-1]/(A.m_ulvalue[A.m_nLength-1]+1);
}
else if(X.m_nLength>A.m_nLength)
{
len=X.m_nLength-A.m_nLength-1;
num=X.m_ulvalue[X.m_nLength-1];
num=(num<<32)+X.m_ulvalue[X.m_nLength-2];
if(A.m_ulvalue[A.m_nLength-1]==0xffffffff)div=(num>>32);
else div=num/(A.m_ulvalue[A.m_nLength-1]+1);
}
else
{
X.Mov(X.Sub(A));
break;
}
               Y.Mov(div);
Y.Mov(Y.Mul(A));
Y.m_nLength+=len;
for(int i=Y.m_nLength-1;i>=len;i--)Y.m_ulvalue[i]=Y.m_ulvalue[i-len];
for(i=0;iX.Mov(X.Sub(Y));
}
if(X.Cmp(A)==0)X.Mov(0);
return X;
} 



//暂时只给出了十进制字符串的转化
int CBigInt::InPutFromStr(CString& str, const unsigned int system=DEC)
{
       int len=str.GetLength();
Mov(0);
for(int i=0;i       {
             Mov(Mul(system));
int k=str[i]-48;
Mov(Add(k));
 }
 return 0;
} 


//暂时只给出了十进制字符串的转化
int CBigInt::OutPutToStr(CString& str, const unsigned int system=DEC)
{
str="";
char ch;
CBigInt X;
X.Mov(*this);
while(X.m_ulvalue[X.m_nLength-1]>0)
{
ch=X.Mod(system)+48;
str.Insert(0,ch);
       X.Mov(X.Div(system));
}
return 0;
} 


//欧几里德算法求：Y=X.Euc(A)，使满足：YX mod A=1
//相当于对不定方程ax-by=1求最小整数解
//实际上就是初中学过的辗转相除法
/********************************************************************/
例如：11x-49y=1，求x 


           11 x  -  49 y  =   1      a)
49%11=5 ->  11 x  -   5 y  =   1      b)
11%5 =1 ->     x  -   5 y  =   1      c) 


令y=1  代入c)式  得x=6
令x=6  代入b)式  得y=13
令y=13 代入a)式  得x=58  
/********************************************************************/
CBigInt CBigInt::Euc(CBigInt& A)
{
CBigInt X,Y;
X.Mov(*this);
Y.Mov(A);
if((X.m_nLength==1)&&(X.m_ulvalue[0]==1))return X;
if((Y.m_nLength==1)&&(Y.m_ulvalue[0]==1)){X.Mov(X.Sub(1));return X;}
if(X.Cmp(Y)==1)X.Mov(X.Mod(Y));
else Y.Mov(Y.Mod(X));
X.Mov(X.Euc(Y));
       Y.Mov(*this);
if(Y.Cmp(A)==1)
{
X.Mov(X.Mul(Y));
X.Mov(X.Sub(1));
X.Mov(X.Div(A));
}
else
{
X.Mov(X.Mul(A));
X.Mov(X.Add(1));
X.Mov(X.Div(Y));
}
return X;
} 


//蒙哥马利算法求：Y=X.Mon(A,B)，使满足：X^A mod B=Y
//俺估计就是高中学过的反复平方法
CBigInt CBigInt::Mon(CBigInt& A, CBigInt& B)
{
CBigInt X,Y,Z;
X.Mov(1);
Y.Mov(*this);
       Z.Mov(A);
while((Z.m_nLength!=1)||Z.m_ulvalue[0])
{
if(Z.m_ulvalue[0]&1)
{
Z.Mov(Z.Sub(1));
X.Mov(X.Mul(Y));
X.Mov(X.Mod(B));
}
else
{
Z.Mov(Z.Div(2));
Y.Mov(Y.Mul(Y));
Y.Mov(Y.Mod(B));
}
}
       return X;
} 



最后需要说明的是因为在VC里面存在一个__int64类型可以
用来计算进位与借位值，所以将大数当作0x100000000进制
进行运算是可能的，而在其他编译系统中如果不存在64位
整形，则可以采用0x40000000进制，由于在0x40000000
进制中，对任何两个“数字”进行四则运算，结果都在
0x3fffffff*03fffffff之间，小于0xffffffff，都可以用
一个32位无符号整数来表示。事实上《楚汉棋缘》采用的
freelip大数库正是运用了0x40000000进制来表示大数的，
所以其反汇编后大数的值在内存中表现出来有些“奇怪”。