【正文】 unsigned p = pl[i]。 for (i=0。首先，在類 Prime_factory_san 被構(gòu)造的時(shí)候，構(gòu)造函數(shù)中從 2 開(kāi)始搜尋一些小素?cái)?shù)，記錄在數(shù)組 pl[]中，共記錄 NP 個(gè)。 函數(shù) find_prime 先把 b[]的所有元素賦值為 1，然后按參數(shù) start 給標(biāo)記數(shù)組 b[]的各元素賦 0 值。最后，只需對(duì)那些 b[]中為 1 的元素對(duì)應(yīng)的大數(shù)進(jìn)行比較確切的素?cái)?shù)測(cè)試即可，只要被測(cè)試的數(shù)是素?cái)?shù)概率達(dá)到一定門(mén)限，就判這個(gè)數(shù)為素?cái)?shù)。b[0]到 b[SS]分別對(duì)應(yīng)大數(shù) start 到 start+SS。 首先在需要尋找素?cái)?shù)的整數(shù)范圍內(nèi)對(duì)整數(shù)進(jìn)行篩選，把所有確知為合數(shù)的整數(shù)排除出去。 start )就可以以大數(shù) start 為起點(diǎn)，得到一個(gè)數(shù)，這個(gè)數(shù)是素?cái)?shù)的概率很大。 經(jīng)過(guò) 和 小節(jié)，所有的大數(shù)運(yùn)算功能都準(zhǔn)備完畢，在此基礎(chǔ)上，本工程將尋找素?cái)?shù)的功能置于類 Prime_factory_san 之中。本程序起初使用素?cái)?shù)表的方式，后來(lái)考慮到安全性問(wèn)題，生成密鑰的方式改為隨機(jī)計(jì)算生成。一般來(lái)說(shuō)，要得到 100%準(zhǔn)確的大素?cái)?shù)，都是通過(guò)查已經(jīng)計(jì)算好的素?cái)?shù)表的方式。全局函數(shù) modexp 初始化 monty對(duì)象并調(diào)用其 exp 方法，使用的時(shí)候直接調(diào)用 modexp 即可。 } return D*R1 (mod n)。 if(i==E 的二進(jìn)制位數(shù) )break。 while(true) { if(E 的當(dāng)前二進(jìn)制位 Ei==1)D=M(D*P)。 P=C*R mod n。 return x。 x = (m + k*n ) / R。 將上述乘模算法結(jié)合前面敘述的冪模算法，構(gòu)成標(biāo)準(zhǔn) Montgomery 冪模算法，即本軟件所使用的流程，敘述如下。雖然 M(A*B)并不是乘模所需要的真正結(jié)果，但只要在冪模算法中進(jìn)行相應(yīng)的修改，就可以調(diào)用這個(gè)乘模算法進(jìn)行計(jì)算了。由于 RnRnnm ???? ?0 ， M(m) 中 t 結(jié)果 范圍是 0≤ t2n，返回時(shí)如果 t 不小于 n，應(yīng)返回 tn。 } 因?yàn)?Rmmn nn m o d39。)m od( ? ?? ?? ??? if (t≥ n) return (tn)。對(duì)于 0≤ mRn 的任意整數(shù) ,Montgomery給出求模乘法 mR1 mod n 的快速算法 M(m): M(m) { Rnmt RRnRm /)( 0。 選擇與模數(shù) n 互素的基數(shù) R=2k， n 滿足 2k－ 1≤ n2k， n 應(yīng) 為奇數(shù) 。本軟件僅僅是應(yīng)用 Montgomery(蒙哥馬利 )算法，算法的具體推導(dǎo)證明需要頗多數(shù)論知識(shí)，不在本畢業(yè)論文（設(shè)計(jì)） 13 文的討論范圍內(nèi)，如需了解可參見(jiàn)蒙哥馬利的相關(guān)著作。一般情況下， n 是數(shù)百位乃至千位以上的二進(jìn)制整數(shù)，用普通的除法求模而進(jìn)行乘模運(yùn)算是不能滿足速 度的要求的。 剩下的問(wèn)題就是乘模運(yùn)算了。 } 有些文獻(xiàn)將上述算法稱為平方乘積二進(jìn)制快速算法，例如參考文獻(xiàn)中的《基于 RSA算法的一種新的加密核設(shè)計(jì)》，其實(shí)這種算法本質(zhì)上和圖 24 的流程完全一致，只是把根據(jù)指數(shù)奇偶分開(kāi)的減一和除以二合并成對(duì)指數(shù)二進(jìn)制各位的判斷而已。 P=P*P(mod n)。 P=C mod n。同樣是計(jì)算 nCD E mod? ，下面給出從右到左掃描二進(jìn)制位進(jìn)行的冪模算法描述，設(shè)中間變量 D,P,E 的二進(jìn)制各位下標(biāo)從左到右為 u,u1,u2,…,0 。 ② 求 13mod28 的值 開(kāi)始 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 即為所求。 ① 求 17mod215 的值 開(kāi)始 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 開(kāi)始 D=1。 nCnCCC m o dm o d 21 ??? nCnCCC m o dm o d 312 ??? nCnCCC m o dm o d 6223 ??? nCnCCC m odm od 734 ??? nCnCCC m o dm o d 14445 ??? nCnCCC m o dm o d 1556 ??? 歸納分析以上方法，對(duì)于任意 指數(shù) E，可采用如圖 24 的算法流程計(jì)算 。經(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)算 化簡(jiǎn)為乘模運(yùn)算。所以寫(xiě)一個(gè) vlong 的友元，完成冪模運(yùn)算功能。 2. 大數(shù)冪模與乘模運(yùn)算 ?Montgomery 冪模算法 在實(shí)現(xiàn)了 vlong 類型后，大數(shù)的存儲(chǔ)和四則運(yùn)算的功能都完成了。這樣，當(dāng)我們操作 vlong 大數(shù)對(duì)象的時(shí)候，就可以像使用一個(gè)簡(jiǎn)單類型一樣使用各種運(yùn)算符號(hào)了。而乘除法和取余也都是按照豎式運(yùn)算的原理實(shí)現(xiàn)，并進(jìn)行了必要的優(yōu)化。當(dāng)大數(shù)被強(qiáng)制轉(zhuǎn)換為 unsigned 時(shí)，將取其最低四字節(jié)的值。圖 23 形象的說(shuō)明了大數(shù)存儲(chǔ)類 flex_unit 對(duì)大數(shù)的管理。結(jié)合指針 a，有兩個(gè)重要的無(wú)符號(hào)整數(shù)來(lái)控制存儲(chǔ)， unsigned z 和 unsigned n， z 是被分配空間的單元數(shù)，隨數(shù)字變大不斷增大，不會(huì)自己緊縮，而 n 是當(dāng)前存儲(chǔ)的大數(shù)所占的單元數(shù)，組成一個(gè)大數(shù)的各 unsigned 單元的存入和讀出由 set、 get方法完成，變量 n是只讀的。類 flex_unit 中，用一個(gè)無(wú)符號(hào)整數(shù)指針 unsigned * a 指向一塊內(nèi)存空間的首地址，這塊內(nèi)存空間用來(lái)存儲(chǔ)一個(gè)大數(shù)，所以可以說(shuō)，大數(shù)是被存儲(chǔ)在一個(gè)以 unsigned為單元的線性組中。 最先完成的功能是大數(shù)的存儲(chǔ)，存儲(chǔ)功能由 flex_unit 類提供。當(dāng)今開(kāi)源的大數(shù)運(yùn)算 C++類有很多，多用于數(shù)學(xué)分析、天文計(jì)算等，本文選用了一個(gè)流行的大數(shù)類型，并針對(duì) RSA 算法和本項(xiàng)目的具體需要對(duì)其進(jìn)行了擴(kuò)充和改進(jìn)。 考慮到工作量，本軟件加解密數(shù)據(jù)沒(méi)有嚴(yán)格遵從 RSA 標(biāo)準(zhǔn) PKCS 1，而是在滿足設(shè)計(jì)要求的前提下，以一種盡可能簡(jiǎn)單的方式實(shí)現(xiàn)加 密和解密。整個(gè)工程分四層，實(shí)現(xiàn) RSA 加密算法的 C++核心類庫(kù)、封裝 C++核心類庫(kù)的 DLL 組件、引用 DLL 的 .Net 類、實(shí)現(xiàn)文件操作功能的 .Net窗體應(yīng)用程序。圖 22 形象的說(shuō)明了分層設(shè)計(jì)給復(fù)用帶來(lái)的好處。這種開(kāi)發(fā)方式，核心功能集中在最底層，在不斷的封裝中針對(duì)具體環(huán)境對(duì)組件功能不斷擴(kuò)充，任意一個(gè)層面的封裝都可以被直接應(yīng)用到其他項(xiàng)目，比如在畢業(yè)論文（設(shè)計(jì)） 8 Web 使用以前為某窗體程序?qū)懙慕M件、給嵌入式設(shè)備交叉編譯算法庫(kù)等。核心的 RSA 算法由 C++類庫(kù)實(shí)現(xiàn)，針對(duì)用戶所在的操作系統(tǒng)封裝成本地化組件。這種開(kāi)發(fā)方式比起前兩種，缺點(diǎn)就是設(shè)計(jì)開(kāi)發(fā)模式陳舊，代碼煩瑣，不方便維護(hù)；流行的 .Net 上的語(yǔ)言引用各種功能比較麻煩。但是對(duì)于非 PC 設(shè)備，只能方便的移植到運(yùn)行 Windows 嵌入式操作系統(tǒng)的設(shè)備，向其他操作系統(tǒng)移植困難，需要重新編寫(xiě)大量代碼。其他各功能的設(shè)計(jì)開(kāi)發(fā)，如文件操作、數(shù)據(jù)編碼轉(zhuǎn)換和圖形界面等，可以使用 ATL、 MFC或 Windows API 實(shí)現(xiàn)。缺點(diǎn)是只能在有微軟 .Net Framework 的環(huán)境運(yùn)行，在 Windows 操作系統(tǒng)， .Net Framework 的機(jī)器效率好于 java 平臺(tái)，但是相比于本地化的代碼，還是十分拖沓的。但是缺點(diǎn)也很明顯，如果想把核心算法和功能應(yīng)用到非 PC 設(shè)備 (例如嵌入式手持設(shè)備 )，則要求設(shè)備上有支持前面提及的加密類庫(kù)的CVM；對(duì)于在 PC 上運(yùn)行， JVM 的數(shù)據(jù)運(yùn)算速度要遠(yuǎn)遠(yuǎn)落后于本地化代碼在 PC 上的運(yùn)算速度，本軟件需要進(jìn)行大量運(yùn)算，這一點(diǎn)不適合由 java 完成。因?yàn)橛袕?qiáng)大的標(biāo)準(zhǔn)庫(kù)支持，文件的讀取和保存操作、各環(huán)節(jié)必要的數(shù)據(jù)編碼轉(zhuǎn)換、圖形操作界面的實(shí)現(xiàn)也很簡(jiǎn)單 (使用 或 等包 )，如果結(jié)合一種快速開(kāi)發(fā)的 IDE，比如 JBuilder，整個(gè)軟件可以在很短的時(shí)間內(nèi)編碼完成。 1. 整個(gè)工程使用 java 平臺(tái)實(shí)現(xiàn) RSA 密鑰生成、 RSA 加密解密的功能實(shí)現(xiàn)十分簡(jiǎn)單，因?yàn)闃?biāo)準(zhǔn)庫(kù)中集成幾乎所有功能，不需要從 RSA 算法出發(fā)進(jìn)行編碼。 圖 21 本項(xiàng)目的 Use Case 和 Statechart 根據(jù)以上分析，一般 來(lái)說(shuō)，需要進(jìn)行編碼的程序有 ① RSA 密鑰生成 ② RSA 加密解密 ③任意文件的讀取和保存操作 ④各環(huán)節(jié)必要的數(shù)據(jù)編碼轉(zhuǎn)換 ⑤圖形操作界面。 ④ 可以裝載加密過(guò)的文件，并用指定的密鑰解密還原出原文件。 ② 可以保存密鑰和裝載密鑰，密鑰保存為純文本。②非對(duì)稱加密后的數(shù)據(jù)變換成文本，使得我們可以通過(guò)幾乎任何方式安全傳遞任意文件，比如在只有 的環(huán)境使用xml 方式。為了適合前面敘述的在公共 BBS 與特定的某人交流重要保密信息的情況，加密生成的數(shù)據(jù)應(yīng)該是文本，這樣可以方便復(fù)制粘貼。這樣，我們自己維護(hù)自己的私有密鑰，利用簡(jiǎn)單并且公開(kāi)的方式，可以安全傳送任意小型數(shù)據(jù)，包括一切二進(jìn)制文件。例如，我們可以將任意一個(gè)文件畢業(yè)論文（設(shè)計(jì)） 5 用某人的公開(kāi)密鑰加密變換成一段可以復(fù)制粘貼的文本，然后粘貼在公眾互聯(lián)網(wǎng)上，對(duì)方只需把需要解密的文本復(fù)制保存成一個(gè)文本文件，在本地機(jī)用自己的私有密鑰解密即可。在這 種情況下，我們需要使用公開(kāi)密鑰方式，并自己維護(hù)私有密鑰。②如果發(fā)送郵件，雖然傳送過(guò)程是加密的，但是密碼畢竟是由郵件服務(wù)器維護(hù)，所以系統(tǒng)管理員通常也有辦法看到內(nèi)容。這種情況要保證安全，在當(dāng)今互聯(lián)網(wǎng)絡(luò)上是比較棘手的。 一種更實(shí)際的情況是，我們想通過(guò) Inter 上的公眾論壇或郵件發(fā)送重要保密信息給某人。李四和王五只要把留給自己的文件用自己的私有密鑰解密，就可以得到留給自己的文件了。只要大家都在這臺(tái)計(jì)算機(jī)或這臺(tái)計(jì)算機(jī)可以訪問(wèn)到的地方，留下自己的公開(kāi)密鑰，一切就變的容易解決了。如果需要在這臺(tái)公共計(jì)算機(jī)上留十個(gè)文件給不同的人，自己就要記和十個(gè)人約定好的密碼，這樣以來(lái)交流起來(lái)不夠方便，因?yàn)閷?duì)于張三，要自己維護(hù)太多的密鑰。如果采用對(duì)稱密鑰加密，張三和李四提前約好一個(gè)密碼就可以。在某些情況下，使用對(duì)稱密鑰加密文件，交流使用不夠方便。②如果借助功能強(qiáng)大的大型多用戶數(shù)據(jù)保護(hù)程序維護(hù)幾個(gè)小型文件，顯得十分煩瑣，好比殺雞用牛刀?？尚械姆椒ㄎ幢厥潜匾?，本小節(jié)討論何種文件適合用非對(duì)稱密鑰加密，即 RSA 加密文件的意義所在。 文件加密使用 RSA 的意義 如 節(jié)所述，小型文件加密可以使用 RSA。通常記錄如銀行帳號(hào)密碼等重要數(shù)據(jù)的文本文件大小不足百字節(jié)，加密只需要數(shù)秒鐘。 本文的第 3 章將根據(jù)實(shí)際調(diào)試好的軟件，測(cè)試給出具體的時(shí)間消耗數(shù)據(jù)。所以，要在普通PC 用幾百位以上的長(zhǎng)密鑰 RSA 加密文件，文件不能過(guò)大，一般可以接受的上限是幾 KB。當(dāng)然，如果文件更大，加密就顯得十分漫長(zhǎng)了。對(duì)于較大的文件，如果分成與數(shù)字簽名同樣大小的段 (這里假設(shè)數(shù)字簽名較短，不分段一次計(jì)算加密完成 )，分開(kāi)的各段逐一進(jìn)行加密運(yùn)算，那所需要的時(shí)間也只是按文件大小線性的增長(zhǎng)。這個(gè)時(shí)間并不是非常長(zhǎng)。在一臺(tái)普通配置的 PC 機(jī)上對(duì)一個(gè)整數(shù)進(jìn)行冪模運(yùn)算，因?yàn)楣_(kāi)密鑰的 e通常取的較小，所以指數(shù)取一個(gè)小整數(shù)，比如 C353，模一個(gè) 70 字節(jié)長(zhǎng)的整數(shù) (140 位十六進(jìn)制，大數(shù)單元以線性組方式實(shí)現(xiàn)，對(duì)應(yīng)到 RSA 算法中，這相當(dāng)于約 560bit 的 n)，調(diào)試一個(gè)函數(shù)測(cè)試，按初等數(shù)論中的知識(shí)對(duì)程序進(jìn)行算法優(yōu)化，最終在一臺(tái)配置為 AMD Athron2800+，外頻 333MHZ，物理內(nèi)存 512MB 的 PC上測(cè)試需 要約 45 毫秒時(shí)間。 雖然 RSA 加密運(yùn)算的速度十分慢，但是在 PC 性能越來(lái)越好的今天，對(duì)于幾千字 節(jié)的數(shù)據(jù)進(jìn)行一次幾百位密鑰的 RSA 加密，所消耗的時(shí)間應(yīng)該是可以接受的。正是因?yàn)檫@樣，把 RSA 應(yīng)用于普通文件加密的想法一直被忽略。 RSA 應(yīng)用于文件加密的分析 文件加密使用 RSA 的 可行性 通過(guò) 節(jié)的論述，不難看出 RSA 當(dāng)今的應(yīng)用多在于數(shù)字簽名和證書(shū)等方面。在上述軟件包的實(shí)現(xiàn)中，集成了應(yīng)用 RSA 算法的各種數(shù)據(jù)加密規(guī)范 (RSA 算法應(yīng)用規(guī)范介紹參見(jiàn)： ，這些 API 內(nèi)部支持的算法不僅僅只有 RSA，但是 RSA 是數(shù)字簽名和證書(shū)中最常用的 )，用戶程序可以直接使用 java 標(biāo)準(zhǔn)庫(kù)中提供的 API 進(jìn)行數(shù)字簽名和證書(shū)的各種操作。 JCE(Java Cryptography Extension) 在 JCA 的基礎(chǔ)上作了擴(kuò)展， JCE 也是由幾個(gè)軟件包組成，其中最主