轉(zhuǎn)自http://blog./u1/50055/showart_1686985.html

基于以下原因,，俺估計(jì)RSA算法會(huì)被越來(lái)越多的共享軟件采用：

1、原理簡(jiǎn)潔易懂
2,、加密強(qiáng)度高
3、專利限制已過(guò)期
4、看雪老大三番五次呼吁共享軟件采用成熟的非對(duì)稱加密技術(shù)

所以，大家應(yīng)該對(duì)RSA算法進(jìn)行深入了解,。

RSA依賴大數(shù)運(yùn)算，目前主流RSA算法都建立在512位到1024位的
大數(shù)運(yùn)算之上,，所以我們?cè)诂F(xiàn)階段首先需要掌握1024位的大數(shù)
運(yùn)算原理,。

大多數(shù)的編譯器只能支持到64位的整數(shù)運(yùn)算，即我們?cè)谶\(yùn)算中
所使用的整數(shù)必須小于等于64位,，即：0xffffffffffffffff
也就是18446744073709551615,，這遠(yuǎn)遠(yuǎn)達(dá)不到RSA的需要，于是
需要專門(mén)建立大數(shù)運(yùn)算庫(kù)來(lái)解決這一問(wèn)題,。

最簡(jiǎn)單的辦法是將大數(shù)當(dāng)作字符串進(jìn)行處理,，也就是將大數(shù)用
10進(jìn)制字符數(shù)組進(jìn)行表示，然后模擬人們手工進(jìn)行“豎式計(jì)算”
的過(guò)程編寫(xiě)其加減乘除函數(shù),。但是這樣做效率很低,，因?yàn)?024
位的大數(shù)其10進(jìn)制數(shù)字個(gè)數(shù)就有數(shù)百個(gè)，對(duì)于任何一種運(yùn)算,，
都需要在兩個(gè)有數(shù)百個(gè)元素的數(shù)組空間上做多重循環(huán),，還需要
許多額外的空間存放計(jì)算的進(jìn)位退位標(biāo)志及中間結(jié)果。當(dāng)然其
優(yōu)點(diǎn)是算法符合人們的日常習(xí)慣,，易于理解,。

另一種思路是將大數(shù)當(dāng)作一個(gè)二進(jìn)制流進(jìn)行處理，使用各種移
位和邏輯操作來(lái)進(jìn)行加減乘除運(yùn)算,，但是這樣做代碼設(shè)計(jì)非常
復(fù)雜,，可讀性很低，難以理解也難以調(diào)試,。

于是俺琢磨了一種介于兩者之間的思路：

將大數(shù)看作一個(gè)n進(jìn)制數(shù)組,，對(duì)于目前的32位系統(tǒng)而言n可以取
值為2的32次方，即0x10000000,，假如將一個(gè)1024位的大數(shù)轉(zhuǎn)
化成0x10000000進(jìn)制,，它就變成了32位，而每一位的取值范圍
就不是0-1或0-9,，而是0-0xffffffff,。我們正好可以用一個(gè)無(wú)
符號(hào)長(zhǎng)整數(shù)來(lái)表示這一數(shù)值。所以1024位的大數(shù)就是一個(gè)有32
個(gè)元素的unsigned long數(shù)組,。而且0x100000000進(jìn)制的數(shù)組排列
與2進(jìn)制流對(duì)于計(jì)算機(jī)來(lái)說(shuō),，實(shí)際上是一回事，但是我們完全
可以針對(duì)unsigned long數(shù)組進(jìn)行“豎式計(jì)算”,，而循環(huán)規(guī)模
被降低到了32次之內(nèi),，并且算法很容易理解。

例如大數(shù)18446744073709551615,，等于“ffffffff ffffffff”,，
它就相當(dāng)于10進(jìn)制的“99”：有兩位，每位都是ffffffff,。
而大數(shù)18446744073709551616,，等于“00000001 00000000
00000000”，它就相當(dāng)于10進(jìn)制的“100”：有三位,，第一位是
1,，其它兩位是0,。如果我們要計(jì)算18446744073709551616
-18446744073709551615，就類似于100-99：
 
  00000001 00000000 00000000
-           ffffffff ffffffff
-----------------------------
=        0         0        1

所以,，可以聲明大數(shù)類如下：

//大數(shù)運(yùn)算庫(kù)頭文件：BigInt.h
//作者：[email protected]
//版本：1.0 (2003.4.26)
//說(shuō)明：適用于MFC

#define BI_MAXLEN 40
#define DEC 10
#define HEX 16

class CBigInt
{
public:
   int m_nSign;    //記錄大數(shù)的符號(hào),，支持負(fù)值運(yùn)算
   int m_nLength;  //記錄0x10000000進(jìn)制的位數(shù)，0-40之間,，相當(dāng)于2進(jìn)制的0-1280位
   unsigned long m_ulvalue[BI_MAXLEN];   //記錄每一位的“數(shù)字”

   CBigInt();
   ~CBigInt();

//將大數(shù)賦值為另一個(gè)大數(shù)    
   CBigInt& Mov(CBigInt& A);

//將大數(shù)賦值為編譯器能夠理解的任何整形常數(shù)或變量  
   CBigInt& Mov(unsigned __int64 A);

//比較兩個(gè)大數(shù)大小
   int Cmp(CBigInt& A);

//計(jì)算兩個(gè)大數(shù)的和
   CBigInt Add(CBigInt& A);

//重載函數(shù)以支持大數(shù)與普通整數(shù)相加
   CBigInt Add(long A);

//計(jì)算兩個(gè)大數(shù)的差
   CBigInt Sub(CBigInt& A);

//重載函數(shù)以支持大數(shù)與普通整數(shù)相減
   CBigInt Sub(long A);

//計(jì)算兩個(gè)大數(shù)的積
   CBigInt Mul(CBigInt& A);

//重載函數(shù)以支持大數(shù)與普通整數(shù)相乘
   CBigInt Mul(long A);

//計(jì)算兩個(gè)大數(shù)的商
   CBigInt Div(CBigInt& A);

//重載函數(shù)以支持大數(shù)與普通整數(shù)相除
   CBigInt Div(long A);

//計(jì)算兩個(gè)大數(shù)相除的余數(shù)
   CBigInt Mod(CBigInt& A);

//重載函數(shù)以支持大數(shù)與普通整數(shù)相除求模
   long Mod(long A);

//將輸入的10進(jìn)制或16進(jìn)制字符串轉(zhuǎn)換成大數(shù)
   int InPutFromStr(CString& str, const unsigned int system);

//將大數(shù)按10進(jìn)制或16進(jìn)制格式輸出到字符串
   int OutPutToStr(CString& str, const unsigned int system);

//歐幾里德算法求：Y=X.Euc(A),，使?jié)M足：YX mod A = 1
   CBigInt Euc(CBigInt& A);

//蒙哥馬利算法求：Y=X.Mon(A,B)，使?jié)M足：X^A mod B = Y
   CBigInt Mon(CBigInt& A, CBigInt& B);
};

注意以上函數(shù)的聲明格式,，完全遵循普通整數(shù)運(yùn)算的習(xí)慣,，例如大數(shù)
Y=X+Z 相當(dāng)于 Y.Mov(X.(Add(Z))，這樣似乎沒(méi)有Mov(Y,Add(X,Z))
看起來(lái)舒服,，但是一旦我們重載運(yùn)算符“=”為“Mov”,，“+”為“Add”，
則Y.Mov(X.(Add(Z))的形式就等價(jià)于 Y=X+Z,。

俺不知道其他編程語(yǔ)言里是否支持運(yùn)算浮重載,，至少這樣定義函數(shù)格式
在C++里可以帶來(lái)很大的方便。

下面讓我們來(lái)實(shí)現(xiàn)大數(shù)類的主要成員函數(shù)：

//大數(shù)運(yùn)算庫(kù)源文件：BigInt.cpp
//作者：[email protected]
//版本：1.0 (2003.4.26)
//說(shuō)明：適用于MFC

#include "stdafx.h"
#include "BigInt.h"

//初始化大數(shù)為0
CBigInt::CBigInt()
{
m_nSign=1;
m_nLength=1;
for(int i=0;i<BI_MAXLEN;i++)m_ulvalue[i]=0;
}

//采用缺省的解構(gòu)函數(shù)
CBigInt::~CBigInt()
{
}

//大數(shù)比較,，如果大數(shù)A位數(shù)比大數(shù)B多,，當(dāng)然A>B
//如果位數(shù)相同，則從高位開(kāi)始比較,，直到分出大小
int CBigInt::Cmp(CBigInt& A)
{
if(m_nLength>A.m_nLength)return 1;
if(m_nLength<A.m_nLength)return -1;
for(int i=m_nLength-1;i>=0;i--)
{
if(m_ulvalue[i]>A.m_ulvalue[i])return 1;
if(m_ulvalue[i]<A.m_ulvalue[i])return -1;
}
return 0;
}

//照搬參數(shù)的各屬性
CBigInt& CBigInt::Mov(CBigInt& A)
{
m_nLength=A.m_nLength;
for(int i=0;i<BI_MAXLEN;i++)m_ulvalue[i]=A.m_ulvalue[i];
return *this;
}

//大數(shù)相加
//調(diào)用形式：N.Add(A),，返回值：N+A
//若兩大數(shù)符號(hào)相同，其值相加,，否則改變參數(shù)符號(hào)再調(diào)用大數(shù)相減函數(shù)

例如：
     A  B  C
+       D  E
--------------
= S  F  G  H

其中,，若C+E<=0xffffffff，則H=C+E,，carry(進(jìn)位標(biāo)志)=0
     若C+E>0xffffffff,，則H=C+E-0x100000000，carry=1

     若B+D+carry<=0xfffffff,，則G=B+D,，carry=0      
     若B+D+carry>0xfffffff，則G=B+D+carry-0x10000000,，carry=1

     若carry=0,，則F=A，S=0
     若carry=1,，A<0xfffffff,，則F=A+1，S=0
     若carry=1，A=0xfffffff,，則F=0,，S=1

CBigInt CBigInt::Add(CBigInt& A)
{
CBigInt X;
if(X.m_nSign==A.m_nSign)
{
X.Mov(*this);
int carry=0;
       unsigned __int64 sum=0;
       if(X.m_nLength<A.m_nLength)X.m_nLength=A.m_nLength;
for(int i=0;i<X.m_nLength;i++)
{
sum=A.m_ulvalue[i];
sum=sum+X.m_ulvalue[i]+carry;
X.m_ulvalue[i]=(unsigned long)sum;
if(sum>0xffffffff)carry=1;
else carry=0;
}
if(X.m_nLength<BI_MAXLEN)
{
X.m_ulvalue[X.m_nLength]=carry;
   X.m_nLength+=carry;
}
return X;
}
else{X.Mov(A);X.m_nSign=1-X.m_nSign;return Sub(X);}
}

//大數(shù)相減
//調(diào)用形式：N.Sub(A)，返回值：N-A
//若兩大數(shù)符號(hào)相同,，其值相減,，否則改變參數(shù)符號(hào)再調(diào)用大數(shù)相加函數(shù)

例如：
     A  B  C
-       D  E
--------------
=    F  G  H

其中，若C>=E,，則H=C-E，carry(借位標(biāo)志)=0
     若C<E,，則H=C-E+0x100000000,，carry=1

     若B-carry>=D，則G=B-carry-D,，carry=0      
     若B-carry<D,，則G=B-carry-D+0x10000000，carry=1

     若carry=0,，則F=A
     若carry=1,，A>1，則F=A-1
     若carry=1,，A=1,，則F=0

CBigInt CBigInt::Sub(CBigInt& A)
{
CBigInt X;
if(m_nSign==A.m_nSign)
{
X.Mov(*this);
int cmp=X.Cmp(A);
if(cmp==0){X.Mov(0);return X;}
int len,carry=0;
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<len;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);}
}

//大數(shù)相乘
//調(diào)用形式：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

而對(duì)于：
     A  B  C
*          E
-------------
= S  F  G  H    

其中，若C*E<=0xffffffff,，則H=C*E,，carry(進(jìn)位標(biāo)志)=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<A.m_nLength;i++)
{
Y.m_nLength=m_nLength;
carry=0;
for(int j=0;j<m_nLength;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<BI_MAXLEN))
               {
                       Y.m_nLength++;
                       Y.m_ulvalue[Y.m_nLength-1]=carry;
               }
if(Y.m_nLength<BI_MAXLEN-i)
{
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<i;k++)Y.m_ulvalue[k]=0;
}
X.Mov(X.Add(Y));
}
if(m_nSign+A.m_nSign==1)X.m_nSign=0;
else X.m_nSign=1;
return X;
}

//大數(shù)相除
//調(diào)用形式：N.Div(A),，返回值：N/A
//除法的關(guān)鍵在于“試商”,，然后就變成了乘法和減法
//這里將被除數(shù)與除數(shù)的試商轉(zhuǎn)化成了被除數(shù)最高位與除數(shù)最高位的試商
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;i<len;i++)Z.m_ulvalue[i]=0;
X.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;
}

//大數(shù)求模
//調(diào)用形式：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;i<len;i++)Y.m_ulvalue[i]=0;
X.Mov(X.Sub(Y));
}
if(X.Cmp(A)==0)X.Mov(0);
return X;
}

//暫時(shí)只給出了十進(jìn)制字符串的轉(zhuǎn)化
int CBigInt::InPutFromStr(CString& str, const unsigned int system=DEC)
{
       int len=str.GetLength();
Mov(0);
for(int i=0;i<len;i++)
       {
             Mov(Mul(system));
int k=str[i]-48;
Mov(Add(k));
 }
 return 0;
}

//暫時(shí)只給出了十進(jìn)制字符串的轉(zhuǎn)化
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),，使?jié)M足：YX mod A=1
//相當(dāng)于對(duì)不定方程ax-by=1求最小整數(shù)解
//實(shí)際上就是初中學(xué)過(guò)的輾轉(zhuǎn)相除法

例如：11x-49y=1,，求x

           11 x  -  49 y  =   1      a)
49=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)，使?jié)M足：X^A mod B=Y
//俺估計(jì)就是高中學(xué)過(guò)的反復(fù)平方法
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;
}