【正文】 配空間的單元數(shù)，隨數(shù)字變大不斷增大，不會(huì)自己緊縮，而 n 是當(dāng)前存儲(chǔ)的大數(shù)所占的單元數(shù)，組成一個(gè)大數(shù)的各 unsigned 單元的存入和讀出由 set、 get方法完成，變量 n是只讀的。當(dāng)大數(shù)被強(qiáng)制轉(zhuǎn)換為 unsigned 時(shí)，將取其最低四字節(jié)的值。這樣，當(dāng)我們操作 vlong 大數(shù)對(duì)象的時(shí)候，就可以像使用一個(gè)簡(jiǎn)單類(lèi)型一樣使用各種運(yùn)算符號(hào)了。所以寫(xiě)一個(gè) vlong 的友元，完成冪模運(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 odm od 734 ??? nCnCCC m o dm o d 14445 ??? nCnCCC m o dm o d 1556 ??? 歸納分析以上方法，對(duì)于任意 指數(shù) E，可采用如圖 24 的算法流程計(jì)算 。 ② 求 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 即為所求。 P=C mod n。 } 有些文獻(xiàn)將上述算法稱為平方乘積二進(jìn)制快速算法，例如參考文獻(xiàn)中的《基于 RSA算法的一種新的加密核設(shè)計(jì)》，其實(shí)這種算法本質(zhì)上和圖 24 的流程完全一致，只是把根據(jù)指數(shù)奇偶分開(kāi)的減一和除以二合并成對(duì)指數(shù)二進(jìn)制各位的判斷而已。一般情況下， n 是數(shù)百位乃至千位以上的二進(jìn)制整數(shù)，用普通的除法求模而進(jìn)行乘模運(yùn)算是不能滿足速 度的要求的。 選擇與模數(shù) n 互素的基數(shù) R=2k， n 滿足 2k－ 1≤ n2k， n 應(yīng) 為奇數(shù) 。)m od( ? ?? ?? ??? if (t≥ n) return (tn)。由于 RnRnnm ???? ?0 ， M(m) 中 t 結(jié)果 范圍是 0≤ t2n，返回時(shí)如果 t 不小于 n，應(yīng)返回 tn。 將上述乘模算法結(jié)合前面敘述的冪模算法，構(gòu)成標(biāo)準(zhǔn) Montgomery 冪模算法，即本軟件所使用的流程，敘述如下。 return x。 while(true) { if(E 的當(dāng)前二進(jìn)制位 Ei==1)D=M(D*P)。 } return D*R1 (mod n)。一般來(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ù)的功能置于類(lèi) Prime_factory_san 之中。 首先在需要尋找素?cái)?shù)的整數(shù)范圍內(nèi)對(duì)整數(shù)進(jìn)行篩選，把所有確知為合數(shù)的整數(shù)排除出去。最后，只需對(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ù)。首先，在類(lèi) Prime_factory_san 被構(gòu)造的時(shí)候，構(gòu)造函數(shù)中從 2 開(kāi)始搜尋一些小素?cái)?shù)，記錄在數(shù)組 pl[]中，共記錄 NP 個(gè)。i++) { unsigned p = pl[i]。 r += p。 圖 25 在素?cái)?shù)搜索范圍內(nèi)剔除小素?cái)?shù)因子 p 的倍數(shù) 接下來(lái)，對(duì)可能為素?cái)?shù)的數(shù) (即標(biāo)記數(shù)組 b[]中值為 1 的元素對(duì)應(yīng)的數(shù) )進(jìn)行素?cái)?shù)測(cè)試。按這種原理，我們編寫(xiě)素?cái)?shù)測(cè)試函數(shù)如下。 //測(cè)試用的底數(shù) for ( unsigned i=0。 //這里 modexp 計(jì)算 any[i]p1mod p。對(duì)于這種情況， RSA算法加密解密是否還可以實(shí)現(xiàn)，是一個(gè)需要從數(shù)學(xué)角度論證的問(wèn)題。 圖 26 函數(shù) find_prime 尋找素?cái)?shù)的流程框圖 得到了大素?cái)?shù)，即 RSA 算法中的 p、 q，我們就可以計(jì)算出密鑰，進(jìn)行加密等操作了。歐幾里德算法是一種遞歸算法，較容易理解。i+=1 結(jié)束 返回素?cái)?shù)尋找結(jié)果 start Yes Yes Yes No No No 畢業(yè)論文（設(shè)計(jì)） 17 （ 3） x 5 y = 1 5 mod 1 = 0 逆向代入： 令 y=0 代入（ 3）得 x=1 令 x=1 代入（ 2）得 y=2 令 y=2 代入（ 1）得 x=9 x=9。m )用來(lái)完成這種算法。之后可以直接使用類(lèi)的其他成員進(jìn)行 RSA 加解密操作，也可以載入以前保存的密鑰或再次隨機(jī)生成密鑰。 需要加密和解密的數(shù)據(jù)也是通過(guò)字符串參數(shù)置入的。 加密 解密流程均為標(biāo)準(zhǔn) RSA 算法，具體過(guò)程和使用方法參見(jiàn)源程序和接口文檔。 class vlong_value 是 flex_unit 的派生類(lèi)，在靈活大數(shù)存儲(chǔ)的基礎(chǔ)上實(shí)現(xiàn)四則運(yùn)算函數(shù)。 class RSA_san 在前 5 個(gè)類(lèi)的基礎(chǔ)上，實(shí)現(xiàn) RSA 核心算法的類(lèi)。由于核心類(lèi)庫(kù)的對(duì)外功能都使由 RSA_san 類(lèi)提供的，所以在新 cpp文件中全局的聲明一個(gè) RSA_san 類(lèi)的對(duì)象指針 (RSA_san *WRSA)，全局函數(shù) int start_RSA_san()初始化 *WRSA 對(duì)象，在初始化成功后，其他全局函數(shù)通過(guò)調(diào)用 *WRSA對(duì)象的公開(kāi)方法實(shí)現(xiàn)各種功能，如加密、讀取密鑰等。 C 接口的 DLL 組件可以被諸如 VB、 Delphi 等開(kāi)發(fā)環(huán)境方便的引用。 文件操作使用 .Net 基礎(chǔ)類(lèi)庫(kù)中的 中的類(lèi)實(shí)現(xiàn)。 圖 28 本軟 件的 Visual Studio 解決方案 畢業(yè)論文（設(shè)計(jì)） 20 第 3 章 軟件整體測(cè)試與分析改進(jìn) 編寫(xiě)測(cè)試各項(xiàng)性能需要的精確計(jì)時(shí)類(lèi) 由于 .Net 基礎(chǔ)類(lèi)庫(kù)提供的計(jì)時(shí)功能十分不精確，無(wú)法勝任軟件性能測(cè)試的工作，這里使用 Windows API 函數(shù) QueryPerformanceCounter 和 QueryPerformanceFrequency 進(jìn)行精確計(jì)時(shí)。 測(cè)試數(shù)據(jù)與分析改進(jìn) 密鑰生成測(cè)試 生成密鑰運(yùn)算最費(fèi)時(shí)的工作是尋找素?cái)?shù)。 1. 測(cè)試加密使用的 n 的位數(shù)對(duì)耗時(shí)的影響 即 在固定 A、 NP、 SS 等變量的情況下，改變加密位數(shù) n，測(cè)試密鑰生成的時(shí)間消耗情況。 表 中 各 項(xiàng) 對(duì) 應(yīng) 的 全 部 測(cè) 試 數(shù) 據(jù) 見(jiàn) ，包括兩個(gè)作為素?cái)?shù)搜索起點(diǎn)的隨機(jī)數(shù)和生成的素?cái)?shù) p、 q 以及 e、 d、 n。這是因?yàn)閷?duì)于大整數(shù)來(lái)說(shuō)，可能出現(xiàn)在較長(zhǎng)一段區(qū)間中沒(méi)有素?cái)?shù)的情況。這是因?yàn)?，?shí)際作為參數(shù)設(shè)置的是兩個(gè)大素?cái)?shù)的搜索起點(diǎn)。 2. 測(cè)試底數(shù) A 對(duì)耗時(shí)的影響 為了保證生成素?cái)?shù)的成功率， A 至少要有 4 個(gè)。而取 6 個(gè)值以上，測(cè)試算法失敗的概率已經(jīng)非常小，沒(méi)有什么實(shí)用意義，所畢業(yè)論文（設(shè)計(jì)） 22 以這里測(cè)試 A 從 4 個(gè)到 6 個(gè)的情況。 表 32 素?cái)?shù)測(cè)試底數(shù) A對(duì)密鑰生成時(shí)間的影響 A 的設(shè)置 測(cè)試 5 次 n 為 512bit 時(shí)密鑰生成需要的時(shí)間 (秒 ) 平均耗間 (秒 ) 2,3,5,7 2,3,5,7,11 2,3,5,7,11,13 A 的設(shè)置 測(cè)試 5 次 n 為 1024bit 時(shí)密鑰生成需要的時(shí)間 (秒 ) 平均耗間 (秒 ) 2,3,5,7 2,3,5,7,11 2,3,5,7,11,13 由表 32 可以看出，對(duì)于 512bit 密鑰， A 取從 4 個(gè)到 6 個(gè)，對(duì)隨機(jī)密鑰的產(chǎn)生時(shí)間影響不大。測(cè)試結(jié)果如表 33 所示。 而且通過(guò)本次測(cè)試還可以發(fā)現(xiàn)，表 33 中 NP 為 200， n 為 1024bit 測(cè)試的一行，變量設(shè)置和表 32 中 A 設(shè)置為 11， n 為 1024bit 的一行完全一致（對(duì)應(yīng)還有一行 n 為 512bit 的數(shù)據(jù)變量設(shè)置一致），但是耗時(shí)平均差距相差 4 秒之多（ 512bit 的一行差距不到 1 秒）。 4. 測(cè)試 SS 對(duì)耗時(shí)的影響 同樣未發(fā)現(xiàn)明顯規(guī)律，在使用中設(shè)置 SS 為 1000。在配置為CPU /UTA133 2M緩存硬盤(pán)的 PC 上，讀入一個(gè) 100KB的文件僅需要 35 毫秒，寫(xiě)出一個(gè) 100KB的文件需要 29 毫秒。加密時(shí)使用的測(cè)試文件、各密鑰文件以及加解密后生成的文件可以從以下地址下載： 內(nèi)附說(shuō)明。統(tǒng)計(jì)消耗時(shí)間情況如表 34 所示，統(tǒng)計(jì)數(shù)據(jù)以曲線表示如圖 31。對(duì)于一定的加密位數(shù)來(lái)說(shuō)，私鑰解密所需要的時(shí)間比公鑰加密需要的時(shí)間長(zhǎng)。因?yàn)楦鶕?jù) PCKS 1 的 RSA 的應(yīng)用建議， e 是比較短的，而 d 和 n的長(zhǎng)度差不多，這就使得求與 d、 n 有關(guān)的冪模運(yùn)算量比與 e、 n 有關(guān)的冪模運(yùn)算量大很多，而且 隨著 n 的增加，兩組冪模運(yùn)算的運(yùn)算量差距也迅速加大。 表 35 本軟件生成的加密文件大小測(cè)試 (文件大小單位： Byte) n位數(shù) 文件大小 50Byte 100Byte 150Byte 200Byte 250Byte 512bit 公鑰加密 6,557 12,977 19,397 25,817 32,237 1024bit 公鑰加密 12,986 25,835 38,684 51,533 64,382 從表 35 的數(shù)據(jù)可以發(fā)現(xiàn)，對(duì)于同樣的文件進(jìn)行加密，使用 1024bit 密鑰加密所得到的文件大小是使用 512bit 加密的 2 倍左右。所以同樣的信息量，采用十六進(jìn)制文本要比原始數(shù)據(jù)大一倍。根據(jù)這些數(shù)據(jù)，可以總結(jié)出本軟件使用的加密方式，加密前后文件大小的近似換算公式如下： 1 0 24260 NAB ??? ， 其中 A 是待加密文件數(shù)據(jù)長(zhǎng)度， B 是加密后文件長(zhǎng)度， N 是 RSA 加密位數(shù)， N8。下面測(cè)試多字節(jié)為步長(zhǎng)的加密執(zhí)行效率。這都是 因?yàn)樵龃罅瞬介L(zhǎng)后，文件被分成的塊數(shù)少了，冪模運(yùn)算次數(shù)下降。數(shù)據(jù)見(jiàn)表37。在2020 年初主流配置的 PC 上運(yùn)行此軟件，逐字節(jié)加密 1KB 大小的文件，消耗時(shí)間均在 。在此 PC 測(cè)試填寫(xiě)表 36，同樣得到了類(lèi)似規(guī)律的數(shù)據(jù)，在此不再羅列。 4. 在更快的 PC，對(duì)進(jìn)行文件加密測(cè)試 在一些性能更好的 PC 上，本軟件可以獲得更好的性能，測(cè)試數(shù)據(jù)同樣可以分析得到以上段落敘述的結(jié)論。統(tǒng)計(jì)數(shù)據(jù)如表 36 所示。按此原理，冪模運(yùn)算結(jié)果長(zhǎng)度近似為加密模數(shù) n 的長(zhǎng)度，加密后數(shù)據(jù)長(zhǎng)度是加密前的 N/8 倍（ N 是加密位數(shù)），而轉(zhuǎn)換為十六進(jìn)制文本后長(zhǎng)度又增大1 倍，加密后得到的文本長(zhǎng)度就是加密前原始數(shù)據(jù)大小的 N/4 倍，所以 B=A N/4，這與畢業(yè)論文（設(shè)計(jì)） 26 前面從實(shí)驗(yàn)結(jié)果總結(jié)得到的公式基本一致，可以把公式中的 260 修正為更精確一些的256。 從表 35 的數(shù)據(jù)還可以看出，對(duì)于同樣的密鑰，隨著原始文件大小的線性增長(zhǎng)，加密后的文件大小也基本呈線性增長(zhǎng)?？梢詮膬蓚€(gè)角度來(lái)理解文件在加密后增大：（ 1） 因?yàn)槟?shù) n 通常較大，所以加密冪模運(yùn)算的結(jié)果通常很大，這使得逐字節(jié)加密時(shí) ，密文比明文長(zhǎng)很多。 2. 用同樣的密鑰對(duì)不同大小的文件公鑰加密，加密后生成的文件大小與待加密文件大小的關(guān)系 在上一組測(cè)試進(jìn)行完之后，我們得到了一些加密文件，下面詳細(xì)分析這些加密后生成的文本文件大小。畢業(yè)論文（設(shè)計(jì)） 25 再測(cè)試幾個(gè) 1280bit 的密鑰加解密，發(fā)現(xiàn)私有密鑰解密所需要的時(shí)間相對(duì)于公鑰加密時(shí)間更長(zhǎng)。對(duì)于較大的文件，加密位數(shù)對(duì)時(shí)間的影響十分明顯。密鑰具體數(shù)據(jù)見(jiàn)附錄（ n的實(shí)際位數(shù)有微小差距）。 加密解密測(cè)試 進(jìn)行對(duì)任意文件加密與解密的測(cè)試，這里給出幾組從不同角度進(jìn)行測(cè)試的數(shù)據(jù)。實(shí)際上就是測(cè)試 .Net 基礎(chǔ)類(lèi)庫(kù)中實(shí)現(xiàn)文件操作的 中的 StreamReader、 StreamWriter 等類(lèi)的讀寫(xiě)性能。這里也正是因?yàn)榍懊嫣岬降?，?duì)于大整數(shù)來(lái)說(shuō)，可能出現(xiàn)在較長(zhǎng)一段區(qū)間中沒(méi)有素?cái)?shù)的情況，使得同樣設(shè)置的各次密鑰生成耗時(shí)的可能范圍很大，再加上大素?cái)?shù)分布規(guī)律奧妙，觀察 5 次測(cè)試結(jié)果的均值對(duì)于不很明顯的規(guī)律顯得意義 不大。 表 33 小素?cái)?shù)因子個(gè)數(shù) NP 對(duì)密鑰生成時(shí)間的影響 NP 測(cè)試 5 次 n 為 512bit 時(shí)密鑰生成需要的時(shí)間 (秒 ) 平均耗間 (秒 ) 100 200 300 400 500 測(cè)試 5 次 n 為 1024bit 時(shí)密鑰生成需要的時(shí)間 (秒 ) 平均耗間 (秒 ) 100 畢業(yè)論文（設(shè)計(jì)） 23 200 300 400 500 不同顏色的單元格表示每行中的最大值和最小值 這種顏色代表行中最大值 這種顏色代表行中最小值 由于測(cè)試時(shí)間漫長(zhǎng)，測(cè)試的數(shù)據(jù)量比較有限。為了同時(shí)保證密鑰生成速度和素?cái)?shù)的準(zhǔn)確程度，我們?cè)趯?shí)際使用時(shí)取 A 為 5 個(gè)值，即 11。從理論上說(shuō)，對(duì)于同樣的起點(diǎn)，素?cái)?shù)測(cè)試次數(shù)越多，需要的時(shí)間就越長(zhǎng)。 小節(jié)曾經(jīng)提到，如果素?cái)?shù)測(cè)試通過(guò)了