【正文】 F21EBF7C5FCC8F77DD2807977F1B6ACF447A7277B76D13819494EB6A892B0F7745D6215E5F08AB9D114749276AF51D19 算法可行性的證明 求證： 命題 11 若 p, q 是相異素數(shù) , e d ＝ 1 mod (p1) (q1), a 是任意一個正整數(shù) , )m o d (),m o d ( qpbcqpab de ???? 則有 c ＝ a mod (p q) 證明： ∵ d e ＝ 1 mod (p1) (q1) ∴ d e ＝ k (p1) (q1) + 1, 其中 k 是整數(shù) ∵ 在 mod 中是 preserve 乘法的 (x ＝ y mod z and u ＝ v mod z x u ＝ y v mod z), ∴ )m o d ()( )1)1()1(()( qpaaabc qpkedded ????? ?????? 首先，素數(shù) p、 q要么能整除 a，要么與 a 互素。 fileWrite(m_OUT, len1)。 UpdateData(FALSE)。 fileRead(data, flen)。 strset(data,0)。//打開文件 flen = fileGetLength()。 file = new CFile。 CFile *file。 m_TM+= 毫秒 。 } long t2=GetTickCount()。j++) { ((E,N))。 for(int j=1。 本文是在吳震老師的熱情關(guān)心和指導(dǎo)下完成的，他淵博的知識和嚴(yán)謹(jǐn)?shù)闹螌W(xué)作風(fēng)使我受益匪淺，對順利完成本課題起到了極大的作用。文中除了特別加以標(biāo)注地方外，不包含他人已經(jīng)發(fā)表或撰寫過的 研究成果，也不包含為獲得成都信息工程學(xué)院或其他教學(xué)機(jī)構(gòu)的學(xué)位或證書而使用過的材料。 。而要實現(xiàn)較為快速的RSA 文件加密系統(tǒng)，對冪模運算的優(yōu)化是核心，只要充分利用蒙哥馬利冪模運算原理，對 RSA 加密算法進(jìn)行適當(dāng)?shù)母倪M(jìn)， RSA文件加密將通過瓶頸，在小型文件加密上有著巨大的發(fā)展空間。 由于開發(fā)時間 倉促等因素，在書寫本文時，軟件并未完成全面細(xì)致的優(yōu)化。 ④ 對 C++核心類庫進(jìn)行重點優(yōu)化，使其運算效率盡可能提高。 ③ 在安全性上做進(jìn)一步優(yōu)化，例如在尋找素數(shù)時，素數(shù) 測試使用更安全的算法，例如，本系統(tǒng)采用的是查已經(jīng)計算好的素數(shù)表的方式得到準(zhǔn)確的素數(shù)，但是素數(shù)表的方式給 RSA 的安全性帶來隱患，因為攻擊者如果得到了密鑰生成時所 使用的素數(shù)表，攻破 RSA 加密的難度將會大大降低。 ② 在對加密或解密完成的數(shù)據(jù)進(jìn)行寫出的時候，都是將其直接寫到指定好的文件，即直接寫入磁盤。 ① 在要對文件進(jìn)行加密解密的時候，先將文件按一定的數(shù)據(jù)結(jié)構(gòu)讀入內(nèi)存，然后進(jìn)行加密或解密操作。 針對以上三點，軟件應(yīng)進(jìn)行一系列改進(jìn)和優(yōu)化。所以，應(yīng)該將頻繁的讀寫操作盡量集中到內(nèi)存，然后一次性寫入磁盤。其中，冪模運算和尋找素數(shù)對時間的消耗最大，在核心優(yōu)化時應(yīng)優(yōu)先考慮。 性能分析與改進(jìn)優(yōu)化 經(jīng)過一系列的 RSA 密鑰生成、文件輸入輸出和蒙哥馬利加密解密測試，做簡要的性能分析如下。現(xiàn)測試蒙哥馬利算法改進(jìn)過的加密算法與普通 RSA加密算法，使用相同密鑰對，對相同文件加密所用時間。因為根據(jù)PCKS 1 的 RSA 的應(yīng)用建議， e是比較短的，而 d 和 n的長度差不多，這就 使得求與 d、 n 有關(guān)的冪模運算量比與 e、 n 有關(guān)的冪模運算量大很多，而且隨著 n的增加，兩組冪模運算的運算量差距也迅速加大。對于一定大小的文件，使用 512bit 的密鑰，私有密鑰解密需要的時間是公開密鑰加密需要時間的 3倍左右；而如果使用 1024bit 的密鑰，私有密鑰解密需要的時間是公開密鑰加密需要時間的 倍以上。對于 100 字節(jié)的文件來說， 1024bit 的公鑰加密比 512bit 的耗時多 倍左右； 1024bit 的私鑰解密比 512bit 的耗時多 以上。統(tǒng)計消耗時間情況如表 32： 表 32：加密消耗時間測試 n 位數(shù) 文件大小 20Byte（毫秒） 40Byte 60Byte 80Byte 100Byte 512bit公鑰加密 119 123 125 128 138 512bit私鑰解密 330 453 473 503 508 1024bit 公鑰加密 442 464 469 473 479 1024bit 私鑰解密 681 721 721 741 743 從表 3可以看出，使用同一公開密鑰加密不同大小的文件，消耗時間隨著文件大小的增加線性的增加，和 小節(jié)分析的完全一致。密鑰具體數(shù)據(jù)見附錄。這里給出幾組不同角度進(jìn)行測 試的數(shù)據(jù)。 此表僅能從實驗的角度直觀理解，具體到一次密鑰生成的運算，所需要的時間是很不確定的，比如，一次 512 位的密鑰生成，需要的時間完全可能比一次256 位的密鑰生成時間短，由于素數(shù)分布規(guī)律非常奧妙，加上測試運算需要的時間頗長，這里很難給出對于一個具體位數(shù)的密鑰生成所需時間的統(tǒng)計模型。也就是說對于長密鑰來說， RSA 隨機(jī)生成密鑰消耗時間的可能范圍較大。 表 31： RSA加密模數(shù) n與密鑰生成耗時的關(guān)系 加密位數(shù) n (bit) 第一次 （毫秒） 第二次（毫秒） 第三次（毫秒） 第四次（毫秒） 第五次（毫秒） 平均值（毫秒） 128 22 20 21 21 21 21 256 126 125 118 131 130 126 512 844 875 812 935 770 847 1024 7030 3205 4785 3926 6399 5069 （紅色為行中最大，蘭色為行中最小） 觀察表上的統(tǒng)計數(shù)據(jù)，很容易發(fā)現(xiàn)隨著加密位數(shù)的增加，密鑰生成需要的時間顯 著增加。測試 PC 配置為 CPU 奔騰 4 845 UltraAD 芯片組，下文測試中，未說明 PC 配置的也都在同一 PC 完成，不再重復(fù)。其中最具影響力的因素顯然是 RSA 加密需要的 n 的位數(shù)。 測試數(shù)據(jù)與分析改進(jìn) 密鑰生成測試 生成密鑰運算最費時的工作是尋找素數(shù)。 圖 22：主要函數(shù)成員 編寫測試各項性能需要的計時程序 由于對幾個字符的字符串進(jìn)行 RSA 加密，所用時間只需 10 幾毫秒，一般的程序計時函數(shù)無法達(dá)到要求測試結(jié)果很可能是 0，于是在這里定義了 2 個 long型變量 t1,t2 來分別存儲加密函數(shù)運行前后 GetTickCount()函數(shù)獲得的系統(tǒng)時間 ,然后將兩個值相減獲得消耗時間，這樣做還會有較大誤差，于是再次進(jìn)行了改進(jìn)，通過一個簡單的 for循環(huán)讓程序運行 1000 次 ，然后將 t2t1 的值除 1000， 以獲得較為精確的時間。 表 21： RSA加密算法的 C++類庫中的類 CBigInt 主要包含大數(shù)四則運算，素數(shù)生成，檢測，密鑰生成，存儲， RSA 核心算法等。 加密解密流程均為標(biāo)準(zhǔn) RSA 算法，具體過程和使用方 法參見源程序和接口文檔。需要加密和解密的數(shù)據(jù)是通過字符串參數(shù)置入的。編碼轉(zhuǎn)換通常是用 C風(fēng)格的指針操作。類中各成員頻繁的用到字符串和 vlong 類型的轉(zhuǎn)換，因為大數(shù)是用字符串置入的，而把大數(shù)讀出，也是保存在字符指針指向的一段內(nèi)存空間里，所以也是字符串。（界面代碼多由 C++編譯器自動生成，在此不再贅述）在類 CDemoDlg的構(gòu)造函數(shù)里，執(zhí)行準(zhǔn)備一對隨機(jī)密鑰的操作。 文件的讀寫操作代碼見附。 ⑸ .文件操作 本工程的核心是利用蒙哥馬利算法快速實現(xiàn) RSA 加密，為了便于研究對字符串的加密過程，以及記錄字 符串的密文樣本，程序把字符串寫入 TXT文檔，再進(jìn)行加密解密操作，這樣就需要對文件進(jìn)行操作，以二進(jìn)制數(shù)據(jù)流對文件進(jìn)行讀出寫入操作。用來完成這種算法。 程序中，函數(shù) Euc(CBigIntamp。 Rab()測試素數(shù) ？ N Y 完成 結(jié)束 開始 給定不定方程 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=9 x=9。 [0]。 開始 利用 Bits 初始化 m_ulValue[i] m_ulValue[i]=rand()*0x10000+rand()。歐幾里德算法是一種遞歸算法，較容易理解。即相當(dāng)于求解 B、 N 都是未知數(shù)的二元一次不定方程 ABMN=1 的最小整數(shù)解。 綜上所述，總結(jié)素數(shù)尋找的流程，如圖 21所示： 圖 21:尋找素數(shù)流程 得到了大素數(shù)，即 RSA 算法中的 p、 q，就可以計算出密鑰，進(jìn)行加密等操作了。 } } 接下來，對可能為素數(shù)的數(shù)用拉賓米勒算法進(jìn)行測試，測試通過，程序就判定這個數(shù)為找到的素數(shù)，將找到的素數(shù)返回給上層程序使用。amp。 ((S,*this))。i++) { (rand()*rand())。 for(i=0。 (*this)。i++){if(Mod(PrimeTable[i])==0)goto begin。 for(i=0。 } m_ulValue[0]=m_ulValue[0]1。 if(m_ulValue[i1]amp。i0。 m_ulValue[0]=m_ulValue[0]|1。im_nLength。 m_nLength=bits。 本工程在素數(shù)生成時，通過數(shù)組 m_ulValue[i]來存儲生成的素數(shù)，調(diào)用 C++已有的函數(shù) Rand()產(chǎn)生隨即數(shù)，再通過素數(shù)表排除非素數(shù)，最終得到待測試之素數(shù)。就可以以 bits 為起點，得到一個數(shù)，這個數(shù)是素數(shù)的概率很大。 經(jīng)過 和 小節(jié)，所有的大數(shù)運算功能都準(zhǔn)備完畢，在此基礎(chǔ)上，本工程將尋找素數(shù)的功能置于類 CBigint 之中。 } ⑶ . 尋找素數(shù)與素數(shù)測試 首先要說明的是，事實上，當(dāng)今的計算機(jī)還不足以聰明到立刻計算生成一個很大的隨機(jī)素數(shù)。 ((B))。 } else if((2)==0) { ((2))。 //A=A1,X=(X*N) MOD B ((Y))。 (A)。 (1)。 A, CBigIntamp。 （ 5）此時的 X即為所求結(jié)果 。 （ 3）若 A為偶數(shù)，則 A=A/2,N=(N*N) MOD B。 蒙哥馬利算法求乘方的模 調(diào)用方式： (A,B) 返回 值： X=N^A MOD B （ 1） X=1。另外， a*a mod n=(a mod n)*(a mod n)mod n。為 r在模 m 下的逆元，那么運算 mm（ a,b,m） =a*b*R39。 r是一個 2的冪。經(jīng)查閱相關(guān)數(shù)學(xué)著作，發(fā)現(xiàn)通常都是依據(jù)乘模的性質(zhì)nnbnanba m o d))m o d()m o d((m o d)( ??? ，先將冪模運算化簡為乘模運算。所以寫一個RsaTrans 函數(shù)，完成冪模運算功能。 如 果 要 計 算1844674407370955161618446744073709551615，就類似于 10099： 00000001 00000000 00000000 ffffffff ffffffff = 0 0 1 ⑵ . 大數(shù)冪模與乘模運算 Montgomery 冪模算法 在實現(xiàn)了 CBigInt 類型后，大數(shù)的存儲和四則運算的功能都完成了。 例如大數(shù) 18446744073709551615，等于 “ffffffff ffffffff” ，它就相當(dāng)于 10進(jìn)制的 “99” ：有兩位，每位都是 ffffffff。所以 1024 位的大數(shù)就是一個有 32 個元素的 unsigned long 數(shù)組。 本工程使用了 一種介于兩者之間的 方法 ： 將大數(shù)看作一個 n 進(jìn)制數(shù)組，對于目前的 32位系統(tǒng)而言 n可以取值為 2的32次方，即 0x10000000，假如將一個 1024 位的大數(shù)轉(zhuǎn)化成 0x10000000 進(jìn)制，它就變成了 32 位，而每一位的取值范圍就不是 01 或 09，而是 00xffffffff。當(dāng)然其優(yōu)點是算法符合人們的日常習(xí)慣，易于理解。 最簡單的辦法是將大數(shù)當(dāng)作字符串進(jìn)行處理，也就是將大 數(shù)用 10 進(jìn)制字符數(shù)組進(jìn)行表示，然后