【文章內(nèi)容簡(jiǎn)介】 是一個(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 0000000000000000”，它就相當(dāng)于 10進(jìn)制的“100”：有三位，第一位是 1，其它兩位是 0。如果要計(jì)算1844674407370955161618446744073709551615，就類似于 10099： 00000001 00000000 00000000 ffffffff ffffffff= 0 0 1 ⑵. 大數(shù)冪模與乘模運(yùn)算 Montgomery 冪模算法在實(shí)現(xiàn)了 CBigInt 類型后，大數(shù)的存儲(chǔ)和四則運(yùn)算的功能都完成了?？紤]到 RSA 算法需要進(jìn)行冪模運(yùn)算，需要準(zhǔn)備實(shí)現(xiàn)這些運(yùn)算的方法。所以寫(xiě)一個(gè)RsaTrans 函數(shù)，完成冪模運(yùn)算功能。冪模運(yùn)算是 RSA 算法中比重最大的計(jì)算，最直接地決定了 RSA 算法的性能，針對(duì)快速冪模運(yùn)算這一課題，西方現(xiàn)代數(shù)學(xué)家提出了很多的解決方案。經(jīng)查閱相關(guān)數(shù)學(xué)著作，發(fā)現(xiàn)通常都是依據(jù)乘模的性質(zhì) nbnabamod)()od(m)(???，先將冪模運(yùn)算化簡(jiǎn)為乘模運(yùn)算。蒙哥馬利算法用到了因子 r。r 是一個(gè) 2 的冪。若設(shè) R39。為 r 在模 m 下的逆元，那么運(yùn)算 mm（a,b,m）=a*b*R39。 mod m。另外，a*a mod n=(a mod n)*(a mod n)mod n。實(shí)際上，連 mod n 這樣的運(yùn)算最后也被轉(zhuǎn)化到 mod r，這樣模運(yùn)算就方便多了。蒙哥馬利算法求乘方的模調(diào)用方式：(A,B)返回值：X=N^A MOD B（1）X=1。（2）若 A 為奇數(shù)，則 A=A1,X=(X*N) MOD B。（3）若 A 為偶數(shù)，則 A=A/2,N=(N*N) MOD B。（4）重復(fù)（2） 、 （3）對(duì) A 進(jìn)行降階，直至 A=0。（5）此時(shí)的 X 即為所求結(jié)果。CBigInt CBigInt::RsaTrans(CBigIntamp。 A, CBigIntamp。 B){ CBigInt X,Y,Z。 (1)。 (*this)。 (A)。 if((2)==1) { ((1))。 //A=A1,X=(X*N) MOD B ((Y))。 ((B))。 } else if((2)==0) { ((2))。 //A=A/2,N=(N*N) MOD B ((Y))。 ((B))。 } return X。}⑶. 尋找素?cái)?shù)與素?cái)?shù)測(cè)試首先要說(shuō)明的是，事實(shí)上，當(dāng)今的計(jì)算機(jī)還不足以聰明到立刻計(jì)算生成一個(gè)很大的隨機(jī)素?cái)?shù)。一般來(lái)說(shuō)，要得到 100%準(zhǔn)確的大素?cái)?shù)，都是通過(guò)查已經(jīng)計(jì)算好的素?cái)?shù)表的方式。經(jīng)過(guò) 和 小節(jié)，所有的大數(shù)運(yùn)算功能都準(zhǔn)備完畢，在此基礎(chǔ)上，本工程將尋找素?cái)?shù)的功能置于類 CBigint 之中。外部只要調(diào)用本類實(shí)例的成員函數(shù) void GetPrime(int bits)。就可以以 bits 為起點(diǎn)，得到一個(gè)數(shù)，這個(gè)數(shù)是素?cái)?shù)的概率很大。下面介紹尋找素?cái)?shù)的原理。本工程在素?cái)?shù)生成時(shí)，通過(guò)數(shù)組 m_ulValue[i]來(lái)存儲(chǔ)生成的素?cái)?shù)，調(diào)用C++已有的函數(shù) Rand()產(chǎn)生隨即數(shù)，再通過(guò)素?cái)?shù)表排除非素?cái)?shù)，最終得到待測(cè)試之素?cái)?shù)。代碼如下：void CBigInt::GetPrime(int bits){ unsigned i。 m_nLength=bits。begin:for(i=0。im_nLength。i++)m_ulValue[i]=rand()*0x10000+rand()。 m_ulValue[0]=m_ulValue[0]|1。for(i=m_nLength1。i0。i){m_ulValue[i]=m_ulValue[i]1。if(m_ulValue[i1]amp。0x80000000)m_ulValue[i]++。}m_ulValue[0]=m_ulValue[0]1。m_ulValue[0]++。 for(i=0。i550。i++){if(Mod(PrimeTable[i])==0)goto begin。} CBigInt S,A,I,K。 (*this)。[0]。 for(i=0。i5。i++){ (rand()*rand())。 ((2))。 ((S,*this))。 if(((!=1)||([0]!=1))amp。amp。((K)!=0))goto begin。}}接下來(lái)，對(duì)可能為素?cái)?shù)的數(shù)用拉賓米勒算法進(jìn)行測(cè)試，測(cè)試通過(guò)，程序就判定這個(gè)數(shù)為找到的素?cái)?shù)，將找到的素?cái)?shù)返回給上層程序使用。拉賓米勒算法是公開(kāi)的測(cè)試素?cái)?shù)算法，直接通過(guò)函數(shù)的調(diào)用實(shí)現(xiàn)，這里就不詳細(xì)介紹。綜上所述，總結(jié)素?cái)?shù)尋找的流程，如圖 21 所示： 圖 21:尋找素?cái)?shù)流程得到了大素?cái)?shù)，即 RSA 算法中的 p、q，就可以計(jì)算出密鑰，進(jìn)行加密等操作了。⑷. 二元一次不定方程在 RSA 算法中，往往要在已知 A、M 的情況下，求 B 的最小值，使得 (AB) mod M = 1。即相當(dāng)于求解 B、N 都是未知數(shù)的二元一次不定方程 ABMN=1 的最小整數(shù)解。開(kāi)始利用 Bits 初始化 m_ulValue[i]m_ulValue[i]=rand()*0x10000+rand()。Mod(PrimeTable[i]==0 為真？YON(*this)。 [0]。[0]。Rab()測(cè)試素?cái)?shù) ？NY完成結(jié)束開(kāi)始而針對(duì)不定方程 axby=1 的最小整數(shù)解，古今中外都進(jìn)行過(guò)詳盡的研究，西方有著名的歐幾里德算法，即一種輾轉(zhuǎn)相除法，中國(guó)有秦九韶的“大衍求一術(shù)” 。歐幾里德算法是一種遞歸算法，較容易理解。下面舉例說(shuō)明用歐幾里德算法求解二元一次不定方程的最小整數(shù)解。給定不定方程 11x49y=1，求最小的 x（1） 11 x 49 y = 1 49 mod 11 = 5（2） 11 x 5 y = 1 11 mod 5 = 1（3） x 5 y = 1 5 mod 1 = 0逆向代入：令 y=0 代入（3）得 x=1令 x=1 代入（2）得 y=2令 y=2 代入（1）得 x=9x=9。y=2 即為所求。程序中，函數(shù) Euc(CBigIntamp。 A)。用來(lái)完成這種算法。對(duì)應(yīng)前面的敘述，參數(shù) a 對(duì)應(yīng) A，函數(shù)返回值即為 X 的最小值。⑸.文件操作本工程的核心是利用蒙哥馬利算法快速實(shí)現(xiàn) RSA 加密，為了便于研究對(duì)字符串的加密過(guò)程，以及記錄字符串的密文樣本，程序把字符串寫(xiě)入 TXT 文檔，再進(jìn)行加密解密操作，這樣就需要對(duì)文件進(jìn)行操作，以二進(jìn)制數(shù)據(jù)流對(duì)文件進(jìn)行讀出寫(xiě)入操作。在這里使用一個(gè) CFILE 類，使用 CFILE 類對(duì)文件進(jìn)行簡(jiǎn)單的讀寫(xiě)操作十分方便，本工程以一個(gè) char 型的指針 data 來(lái)存放獲得的字符串，用 DWORD 型變量 flen 來(lái)存放 Cfile 類中成員函數(shù) GetLength()獲得的字符串長(zhǎng)度，然后直接使用成員函數(shù) read(),write()來(lái)進(jìn)行文件的讀寫(xiě)操作。文件的讀寫(xiě)操作代碼見(jiàn)附。⑹. 按常規(guī) RSA 算法實(shí)現(xiàn)加密與解密最后，類 CDemoDlg 基于前面的準(zhǔn)備工作，實(shí)現(xiàn) RSA 密鑰生成和加解密的界面化功能。 （界面代碼多由 C++編譯器自動(dòng)生成，在此不再贅述）在類 CDemoDlg的構(gòu)造函數(shù)里，執(zhí)行準(zhǔn)備一對(duì)隨機(jī)密鑰的操作。之后可以直接使用類的其他成員進(jìn)行 RSA 加解密操作，也可以載入用戶寫(xiě)入的密鑰或再次隨機(jī)生成密鑰。類中各成員頻繁的用到字符串和 vlong 類型的轉(zhuǎn)換，因?yàn)榇髷?shù)是用字符串置入的，而把大數(shù)讀出，也是保存在字符指針指向的一段內(nèi)存空間里，所以也是字符串。所以，需要實(shí)現(xiàn)一系列的編碼轉(zhuǎn)換函數(shù)，比如將 unsigned 指針指向的一段空間里保存的一個(gè)大數(shù)，表示成十六進(jìn)制形式的字符串文本。編碼轉(zhuǎn)換通常是用 C風(fēng)格的指針操作。由于是對(duì)文件進(jìn)行加密，所以涉及對(duì)文件內(nèi)容進(jìn)行讀寫(xiě)操作，這里使用到了 CFile 類。需要加密和解密的數(shù)據(jù)是通過(guò)字符串參數(shù)置入的。由于字符串的結(jié)尾字符“\