【文章內(nèi)容簡介】 ，而是在滿足設(shè)計(jì)要求的前提下，以一種盡可能簡單的方式實(shí)現(xiàn)加密和解密。 各部分的設(shè)計(jì)與開發(fā) 實(shí)現(xiàn) RSA 加密算法的 C++核心類庫 1. 大數(shù)存儲(chǔ)和四則運(yùn)算 根據(jù) RSA 算法的要求，為了實(shí)現(xiàn)大數(shù)的各種復(fù)雜運(yùn)算，需要首先實(shí)現(xiàn)大數(shù)存儲(chǔ)和基本四則運(yùn)算的功能。當(dāng)今開源的大數(shù)運(yùn)算 C++類有很多，多用于數(shù)學(xué)分析、天文計(jì)算等，本文選用了一 個(gè)流行的大數(shù)類型，并針對(duì) RSA 算法和本項(xiàng)目的具體需要對(duì)其進(jìn)行了擴(kuò)充和改進(jìn)。下面簡單介紹大數(shù)存儲(chǔ)和四則運(yùn)算的實(shí)現(xiàn)原理。 最先完成的功能是大數(shù)的存儲(chǔ)，存儲(chǔ)功能由 flex_unit 類提供。和普通的類型一樣，每一個(gè)大數(shù)對(duì)應(yīng)一個(gè) flex_unit 的實(shí)例。類 flex_unit 中，用一個(gè)無符號(hào)整數(shù)指針 unsigned * a 指向一塊內(nèi)存空間的首地址，這塊內(nèi)存空間用來存儲(chǔ)一個(gè)大數(shù)，所以可以說，大數(shù)是被存儲(chǔ)在一個(gè)以 unsigned為單元的線性組中。在方法 void reserve( unsigned x )中通過 C++的 new 來給 a 開辟空間，當(dāng) flex_unit 的實(shí)例中被存入比當(dāng)前存儲(chǔ)的數(shù)更大的數(shù)時(shí)，就會(huì)調(diào)用 reserve 來增加存儲(chǔ)空間，但是當(dāng) flex_unit 的實(shí)例中被存入比當(dāng)前存儲(chǔ)的數(shù)更小的數(shù)青島 大學(xué)本科生畢業(yè)論文（設(shè)計(jì)） 9 時(shí)，存儲(chǔ)空間并不會(huì)自動(dòng)緊縮，這是為了在運(yùn)算的時(shí)候提高執(zhí)行效率。結(jié)合指針 a，有兩個(gè)重要的無符號(hào)整數(shù)來控制存儲(chǔ)， unsigned z 和 unsigned n， z 是被分配空間的單元數(shù)，隨數(shù)字變大不斷增大，不會(huì)自己緊縮，而 n 是當(dāng)前存儲(chǔ)的大數(shù)所占的單元數(shù)，組成一個(gè)大數(shù)的各 unsigned 單元的存入和讀出由 set、 get方法完成，變量 n是只讀的。類型 unsigned在 32 位機(jī)是 32 位的，所以對(duì)于 flex_unit 這個(gè)大數(shù)類來說，每個(gè)大數(shù)最大可以達(dá)到 個(gè)字節(jié)長，這已經(jīng)超過了 32 位機(jī)通常的最大內(nèi)存容量，所以是足夠進(jìn)行 RSA 所需要的各種運(yùn)算的。圖 23 形象的說明了大數(shù)存儲(chǔ)類 flex_unit 對(duì)大數(shù)的管理。 圖 23 flex_unit 對(duì)大數(shù)的管理 在 flex_unit 的存儲(chǔ)功能基礎(chǔ)上，將其派生，得到 vlong_value，在 vlong_value 中實(shí)現(xiàn)四則運(yùn)算函數(shù)，并實(shí)現(xiàn)強(qiáng)制轉(zhuǎn)換運(yùn)算符 unsigned，以方便大數(shù)類型和普通整數(shù)的互相賦值。當(dāng)大數(shù)被強(qiáng)制轉(zhuǎn)換為 unsigned 時(shí)，將取其最低四字節(jié)的值。四則運(yùn)算實(shí)現(xiàn)的原理十分簡單，都是按最基本的算術(shù)原理實(shí)現(xiàn)的，四則運(yùn)算過程的本質(zhì)就是按一定數(shù)制對(duì)數(shù)字的計(jì)算，比如相加，就是低位單元對(duì)齊，逐單元相加并進(jìn)位，減法同理。而乘除法和取余也都是按照豎式運(yùn)算的原理實(shí)現(xiàn)，并進(jìn)行了必要的優(yōu)化。雖然實(shí)現(xiàn)了四則運(yùn)算函數(shù)，但是若是程序里的運(yùn)算都要調(diào)用函數(shù)，顯得煩瑣而且看起來不美觀，所以我們另寫一個(gè)類 vlong，關(guān)聯(lián) (Associate，即使用 vlong_value 類型的對(duì)象或其指針 作為成員 )vlong_value，在 vlong 重載運(yùn)算符。這樣，當(dāng)我們操作 vlong 大數(shù)對(duì)象的時(shí)候，就可以像使用一個(gè)簡單類型一樣使用各種運(yùn)算符號(hào)了。之所以將 vlong_value 的指針作為成員而不是直接構(gòu)造的對(duì)象，也是為了提高執(zhí)行效率，因?yàn)榇笮蛯?duì)象的拷貝要消耗不少機(jī)器時(shí)間。 2. 大數(shù)冪模與乘模運(yùn)算 ?Montgomery 冪模算法 在實(shí)現(xiàn)了 vlong 類型后，大數(shù)的存儲(chǔ)和四則運(yùn)算的功能都完成了?？紤]到 RSA 算法需要進(jìn)行冪模運(yùn)算，需要準(zhǔn)備實(shí)現(xiàn)這些運(yùn)算的方法。所以寫一個(gè) vlong 的友元，完成冪模運(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ì) nnbnanba m o d))m o d()m o d((m o d)( ??? ，先將冪模運(yùn)算化簡為乘模運(yùn)算。 *a unsigned 類型的指針 大數(shù)占 n 個(gè)單元 開辟了 z 個(gè)單元大的內(nèi)存 內(nèi)存空間 青島 大學(xué)本科生畢業(yè)論文（設(shè)計(jì)） 10 通常的分解習(xí)慣是指數(shù)不斷的對(duì)半分，如果指數(shù)是奇數(shù)，就先減去一變成偶數(shù)，然后再對(duì)半分，例如求 D= nCE mod ， E=15， 可分解為如下 6 個(gè)乘模運(yùn)算。 nCnCCC m o dm o d 21 ??? nCnCCC m o dm o d 312 ??? nCnCCC m o dm o d 6223 ??? nCnCCC m o dm o d 734 ??? nCnCCC m o dm o d 14445 ??? nCnCCC modmod 1556 ??? 歸納分析以上方法，對(duì)于任意指數(shù) E，可采用如圖 24 的算法流程計(jì)算 。 青島 大學(xué)本科生畢業(yè)論文（設(shè)計(jì)） 11 圖 24 冪模運(yùn)算分解為乘模運(yùn)算的一種流程 按照上述流程，列舉兩個(gè)簡單的冪模運(yùn)算實(shí)例來形象的說明這種方法。 ① 求 17mod215 的值 開始 D = 1 P = 2 mod 17 = 2 E = 15 E 奇數(shù) D = DP mod n = 2 P = PP mod n = 4 E = (E1)/2 =7 E 奇數(shù) D = DP mod n = 8 P = PP mod n = 16 E = (E1)/2 =3 開始 D=1。P=C mod n E0? E 為奇數(shù) ? nPDD m od)( ?? E=E1 nPPP m od)( ?? E 為偶數(shù) ? E=E/2 Yes No Result=D 結(jié)束 Yes Yes No No 青島 大學(xué)本科生畢業(yè)論文（設(shè)計(jì)） 12 E 奇數(shù) D = DP mod n = 9 P = PP mod n = 1 E = (E1)/2 =1 E 奇數(shù) D = DP mod n = 9 P = PP mod n = 1 E = (E1)/2 =0 最終 D = 9 即為所求。 ② 求 13mod28 的值 開始 D = 1 P = 2 mod 17 = 2 E = 8 E 偶數(shù) D = 1 P = PP mod n = 4 E = E/2 =4 E 偶數(shù) D = 1 P = PP mod n = 3 E = E/2 =2 E 偶數(shù) D = 1 P = PP mod n = 9 E = E/2 =1 E 奇數(shù) D = DP mod n = 9 P = 不需要計(jì)算 E = (E1)/2 =0 最終 D = 9 即為所求。 觀察上述算法，發(fā)現(xiàn) E 根據(jù)奇偶除以二或減一除以二實(shí)際就是二進(jìn)制的移位操作，所以要知道需要如何乘模變量，并不需要反復(fù)對(duì) E 進(jìn)行除以二或減一除以二的操作，只需要驗(yàn)證 E 的二進(jìn)制各位是 0 還是 1 就可以了。同樣是計(jì)算 nCD E mod? ，下面給出從右到左掃描二進(jìn)制位進(jìn)行的冪模算法描述，設(shè)中間變量 D,P,E 的二進(jìn)制各位下標(biāo)從左到右為 u,u1,u2,…,0 。 Powmod(C,E,n) { D=1。 P=C mod n。 for i=0 to u do { if(Ei=1)D=D*P(mod n)。 P=P*P(mod n)。 } return D。 } 有些文獻(xiàn)將上述算法稱為平方乘積二進(jìn)制快速算法，例如參考文獻(xiàn)中的《基于 RSA算法的一種新的加密核設(shè)計(jì)》，其實(shí)這種算法本質(zhì)上和圖 24 的流程完全一致，只是把根據(jù)指數(shù)奇偶分開的減一和除以二合并成對(duì)指數(shù)二進(jìn)制各 位的判斷而已。在本軟件的代碼中采用直接掃描 vlong 二進(jìn)制各位的辦法。 剩下的問題就是乘模運(yùn)算了。提高乘模運(yùn)算的速度是提高模冪運(yùn)算速度的關(guān)鍵。一般情況下， n 是數(shù)百位乃至千位以上的二進(jìn)制整數(shù)，用普通的除法求模而進(jìn)行乘模運(yùn)算是不能滿足速度的要求的。為此， Montgomery 在 1983 年提出了一種模加右移的乘模算法 （主要著作發(fā)表于 1985 年） ，從而避免了通常求模算法中費(fèi)時(shí)的除法步驟。本軟件僅僅是應(yīng)用 Montgomery(蒙哥馬利 )算法，算法的具體推導(dǎo)證明需要頗多數(shù)論知識(shí)，不在本青島 大學(xué)本科生畢業(yè)論文（設(shè)計(jì)） 13 文的討論范圍內(nèi)，如需了解可參見蒙哥馬 利的相關(guān)著作。下面簡單描述 RSA 中常用的Montgomery(蒙哥馬利 )算法供參考理解源程序。 選擇與模數(shù) n 互素的基數(shù) R=2k， n 滿足 2k－ 1≤ n2k， n 應(yīng) 為奇數(shù) 。并且選擇 R1及n’，滿足 0 R1n, 0 n’n,使得 RR1nn’＝ 1。對(duì)于 0≤ mRn 的任意整數(shù) ,Montgomery給出求模乘法 mR1 mod n 的快速算法 M(m): M(m) { Rnmt RRnRm /)( 0。m o d39。)m o d( ? ?? ?? ??? if (t≥ n) return (tn)。 else return t。 } 因?yàn)?Rmmnnn m o d39。 ???? ，故 t 為整數(shù)；同時(shí) nmtR mod? ，得 nmRt mod1?? 。由于 RnRnnm ???? ?0 ， M(m) 中 t 結(jié)果范圍是 0≤ t2n，返回時(shí)如果 t 不小于 n，應(yīng)返回 tn。 本軟件程序中， RSA 核心運(yùn)算使用的乘模算法就是 M(A*B)。雖然 M(A*B)并不是乘模所需要的真正結(jié)果，但只要在冪模算法中進(jìn)行相應(yīng)的修改，就可以調(diào)用這個(gè)乘模算法進(jìn)行計(jì)算了。本軟件起初未使用 Montgomery 乘模算法時(shí) ，加密速度比使用Montgomery 乘模算法慢，但速度相差不到一個(gè)數(shù)量級(jí)。 將上述乘模算法結(jié)合前面敘述的冪模算法，構(gòu)成標(biāo)準(zhǔn) Montgomery 冪模算法，即本軟件所使用的流程，敘述如下。 M(m) { k = ( m * n’ ) mod R。 x = (m + k*n ) / R。 if (x=n) x = n。 return x。 } exp(C,E,n) { D=Rn。 P=C*R mod n。 i=0。 while(true) { if(E 的當(dāng)前二進(jìn)制位 Ei==1)D=M(D*P)。 //從低位到高位檢測二進(jìn)制位 青島 大學(xué)本科生畢業(yè)論文（設(shè)計(jì)） 14 i+=1。 if(i==E 的二進(jìn)制位數(shù) )break。 P=M(P*P)。 } return D*R1 (mod n)。 } 在具體的實(shí)現(xiàn)中，對(duì)應(yīng) monty 類的 mul 和 exp 方法。全局函數(shù) modexp 初始化 monty對(duì)象并調(diào)用其 exp 方法，使用的時(shí)候直接調(diào)用 modexp 即可。 3. 尋找素?cái)?shù) ?Eratosthenes 篩 選與 Fermat 素?cái)?shù)測試 首先要說明的是，事實(shí)上，當(dāng)今的計(jì)算機(jī)還不足以聰明到立刻計(jì)算生成一個(gè)很大的隨機(jī)素?cái)?shù)。一般來說，要得到 100%準(zhǔn)確的大素?cái)?shù)，都是通過查已經(jīng)計(jì)算好的素?cái)?shù)表的方式。但是素?cái)?shù)表的方式給 RSA 的安全性帶來隱患，因?yàn)楣粽呷绻玫搅嗣荑€生成時(shí)所使用的素?cái)?shù)表，攻破 RSA 加密的難度將會(huì)大大降低。本程序起初使用素?cái)?shù)表的方式，后來考慮到安全性問題，生成密鑰的方式改為隨機(jī)計(jì)算生成。這樣，短時(shí)間內(nèi)如果要得到一個(gè) 100%準(zhǔn)確的大素?cái)?shù)是很困難的，只能以盡可能高的概率得到一個(gè)大素?cái)?shù)。 經(jīng)過 和 小節(jié)，所有的大數(shù)運(yùn)算功能都準(zhǔn)備完畢，在此基礎(chǔ)上，本工程將尋找素?cái)?shù)的功能置于類 Prime_factory_san 之中。外部只要調(diào)用本類實(shí)例的成員 vlong find_prime( vlong amp。 start )就可以以大數(shù) start 為起點(diǎn)，得到一個(gè)數(shù)，這個(gè)數(shù)是素?cái)?shù)的概率很大。下面介紹尋找素?cái)?shù)的原理。 首先在需要尋找素?cái)?shù)的整數(shù)范圍內(nèi)對(duì)整數(shù)進(jìn)行篩選，把所有確知為合數(shù)的整數(shù)排除出去。程序中構(gòu)造了一個(gè)數(shù)組 b[]，大小為一輪素?cái)?shù)搜索的范圍，記搜索范圍大小為 SS。b[0]到 b[SS]分別對(duì)應(yīng)大數(shù) start 到 start+SS。 b[]中所有元素先初始化為 1，如果對(duì)應(yīng)的大數(shù)確定為合數(shù)，就將 b[]中對(duì)應(yīng)的元素置為 0。最后，只需對(duì)那些 b[]中為 1 的元素對(duì)應(yīng)的大數(shù)進(jìn)行比較確切的素?cái)?shù)測試即可，只要被測試的數(shù)是素?cái)?shù)概率達(dá)到一定門限，就判這個(gè)數(shù)為素?cái)?shù)。這樣做既保證了這段程序可以在短時(shí)間內(nèi)執(zhí)行完，又保證了可以以比較高的準(zhǔn)確度得到素?cái)?shù)。 函數(shù) find_prime 先把 b[]的所有元素賦值為 1，然后按參數(shù) start 給標(biāo)記數(shù)組 b[]的各元素賦 0 值。下面描述標(biāo)記數(shù)組 b[]的賦 0 值算法。首先，在類 Prime_factory_san 被構(gòu)造的時(shí)候，構(gòu)造 函數(shù)中從 2 開始搜尋一些小素?cái)?shù)，記錄在數(shù)組 pl[]中，共記錄 NP 個(gè)。這些小素?cái)?shù)用來當(dāng)作因子，他們的倍數(shù)將被從大素?cái)?shù)搜索范圍內(nèi)剔除 (即把數(shù)組 b[]的對(duì)應(yīng)元素標(biāo)記為 0)，剔除的程序