【正文】 求解同余方程 RsaTrans，反復(fù)平方算法進(jìn)行冪模運(yùn)算 GetPrime，產(chǎn)生指定長(zhǎng)度的隨機(jī)大素?cái)?shù) 通過(guò) Add， Sub， Mu， Div，實(shí)現(xiàn)四則運(yùn)算函數(shù)，并實(shí)現(xiàn)強(qiáng)制轉(zhuǎn)換運(yùn)算符unsigned，以方便大數(shù)類(lèi)型和普通整數(shù)的互相賦值。內(nèi)部集成眾多算法實(shí)現(xiàn)函數(shù)，可方便的調(diào)用，給編程及調(diào)試帶來(lái)極大的方便，最終本工程選定以 VC++做為平臺(tái) ，進(jìn)行本軟件的開(kāi)發(fā)工作。 ②可以對(duì)加密過(guò)程進(jìn)行精確計(jì)時(shí)，反映在界面處。 ③ 可以裝載加密過(guò)的文件，并用指定的密鑰解密還原出原文件。 RSA加解密運(yùn)算都是模冪運(yùn)算，而模冪運(yùn)算 x170。 影響模乘運(yùn)算速度關(guān)鍵在于模運(yùn)算，模運(yùn)算其實(shí)是除法運(yùn)算，除運(yùn)算相對(duì)與加減乘運(yùn)算要費(fèi)時(shí)的多。速度 一直是 RSA 的缺陷。不管怎樣，分解 n 是最顯然的攻擊方法。用戶(hù)程序可以直接使用 java 標(biāo)準(zhǔn)庫(kù)中提供的 API 進(jìn)行數(shù)字簽名和證書(shū)的各種操作。 JCE(Java Cryptography Extension) 在 JCA 的基礎(chǔ)上作了擴(kuò)展， JCE 也是由幾個(gè)軟件包組成，其中最主要的是 包，此軟件包提供了 JCE 加密技術(shù)操作 API。 RSA 更出現(xiàn)在要求高度安全穩(wěn)定的企業(yè)級(jí)商務(wù)應(yīng)用中。日常應(yīng)用中，有比較著名的工具包 Open SSL(SSL， Security Socket Layer,是一個(gè)安全傳輸協(xié)議，在 Inter 上進(jìn)行數(shù)據(jù)保護(hù)和身份確認(rèn)。 RSA作為最重要的公開(kāi)密鑰算法，在各領(lǐng)域的應(yīng)用數(shù)不勝數(shù)。因此 ，如果在模乘運(yùn)算中不用除法或盡量少用除法將大大提高 RSA 處理的速度。通過(guò)對(duì)冪模運(yùn)算的改進(jìn)，簡(jiǎn)化，提高 RSA 加密效率。隨著越來(lái)越多的商業(yè)應(yīng)用和標(biāo)準(zhǔn)化工作， RSA 已經(jīng)成為最具代表性的公鑰加密技術(shù)。 附 錄 .................................................................... 20 致 謝 .................................................................... 21 聲 明 ................................................................... 24 前言 RSA 公鑰加密算法是第一個(gè)既能 用于數(shù)據(jù)加密也能用于數(shù)字簽名的算法。 Montgomery algorithm。通 過(guò)對(duì)冪模運(yùn)算的改進(jìn)，簡(jiǎn)化，提高 RSA 加密效率。然而， RSA 算法加密速度很慢， 難以像其他加密算法那樣得到更廣泛的應(yīng)用 。 冪模運(yùn)算是 RSA的速度瓶頸，在全過(guò)程中都有使用 。本文主要論述 RSA基本原理以及相關(guān)函數(shù)類(lèi)的 設(shè)計(jì)與實(shí)現(xiàn) ，使用 Microsoft Visual C++ 操作平臺(tái)，實(shí)現(xiàn) RSA加密算法，界面友善，操作方便。 Encryption。它易于理解和操作，也十分流行。 VISA、 MasterCard、 IBM、 Microsoft 等公司協(xié)力制定的安全電子交易標(biāo)準(zhǔn)（ Secure Electronic Transactions， SET）就采用了標(biāo)準(zhǔn) RSA 算法，這使得 RSA 在人們的生活中幾乎無(wú)處不在。 冪模運(yùn)算是 RSA 的速度瓶頸，在全過(guò)程中都有使用。 1985 年， Peter Montgomery 發(fā)現(xiàn)了一種只要乘法和數(shù)的位移就可以實(shí)現(xiàn)模乘運(yùn)算的靈巧算法，這就是著名的蒙哥馬利模乘算法。 RSA 在硬件方面，以技術(shù)成熟的 IC應(yīng)用于各種消費(fèi)類(lèi)電子產(chǎn)品。 Open SSL 是一個(gè)開(kāi)放源代碼的實(shí)現(xiàn)了 SSL 及相關(guān)加密技術(shù)的軟件包，由加拿大的 Eric Yang 等發(fā)起編寫(xiě)的。在當(dāng)今的企業(yè)級(jí)商務(wù)應(yīng)用中，不得不提及使用最廣泛的平臺(tái) j2ee。 中的 Cipher 類(lèi)用于具體的加密和解密。 RSA 算法加密的安全分析 RSA 的安全性依賴(lài)于大數(shù)分解，但是否等同于大數(shù)分解一直未能得到理論上的證明，因?yàn)闆](méi)有證明破解 RSA 就一定需要作大數(shù)分解?，F(xiàn)在，人們已能分解多個(gè)十進(jìn)制位的大素?cái)?shù)。一般來(lái)說(shuō)只用于少量數(shù)據(jù)加密。因此，如果在模乘運(yùn)算中不用除法或盡量少用除法將大大提高 RSA 處理的速度。modn又可以轉(zhuǎn)化為平均 (3e)/2 次的模乘運(yùn)算 ,所以提高 RSA加解密速度的關(guān)鍵在于提高模乘運(yùn)算的速度，影響模乘運(yùn)算速度關(guān)鍵在于模運(yùn)算 ,模運(yùn)算其實(shí)是除法運(yùn)算 ,除法運(yùn)算相對(duì)于加減乘運(yùn)算要費(fèi)時(shí)得多 因此如果在模乘運(yùn)算中不用除法或盡量少用除法將大大提高處理的速度。 ④ 提示信息完整、操作舒適、圖形界面雅觀。 按上述描述，給出 Use Case 和 Statechart 如圖 11： 圖 11：操作流程 根據(jù)以上分析，一般來(lái)說(shuō)，需要進(jìn)行編碼的程序有 ： ① RSA 密鑰生成 ② RSA 加密解密 ③文件的讀取和保存操作 ④各環(huán)節(jié)必要的數(shù)據(jù)編碼轉(zhuǎn)換 ⑤圖形操作界面。 各部分的設(shè)計(jì)與開(kāi)發(fā) 實(shí)現(xiàn) RSA 加密算法的 C++核心類(lèi)庫(kù) ⑴ . 大數(shù)四則運(yùn)算與運(yùn)算符重載 : 根據(jù) RSA 算法的要求，為了實(shí)現(xiàn)大數(shù)的各種復(fù)雜運(yùn)算，需要首先實(shí)現(xiàn)大數(shù)存儲(chǔ)和基本四則運(yùn)算的功能。當(dāng)大數(shù)被強(qiáng)制轉(zhuǎn)換為unsigned 時(shí)，將取其最低四字節(jié)的值。 最簡(jiǎn)單的辦法是將大數(shù)當(dāng)作字符串進(jìn)行處理，也就是將大 數(shù)用 10 進(jìn)制字符數(shù)組進(jìn)行表示，然后模擬人們手工進(jìn)行 “ 豎式計(jì)算 ” 的過(guò)程編寫(xiě)其加減乘除函數(shù)。 本工程使用了 一種介于兩者之間的 方法 ： 將大數(shù)看作一個(gè) n 進(jìn)制數(shù)組，對(duì)于目前的 32位系統(tǒng)而言 n可以取值為 2的32次方，即 0x10000000，假如將一個(gè) 1024 位的大數(shù)轉(zhuǎn)化成 0x10000000 進(jìn)制，它就變成了 32 位，而每一位的取值范圍就不是 01 或 09，而是 00xffffffff。 例如大數(shù) 18446744073709551615，等于 “ffffffff ffffffff” ，它就相當(dāng)于 10進(jìn)制的 “99” ：有兩位，每位都是 ffffffff。所以寫(xiě)一個(gè)RsaTrans 函數(shù)，完成冪模運(yùn)算功能。 r是一個(gè) 2的冪。另外， a*a mod n=(a mod n)*(a mod n)mod n。 （ 3）若 A為偶數(shù)，則 A=A/2,N=(N*N) MOD B。 A, CBigIntamp。 (A)。 } else if((2)==0) { ((2))。 } ⑶ . 尋找素?cái)?shù)與素?cái)?shù)測(cè)試 首先要說(shuō)明的是，事實(shí)上，當(dāng)今的計(jì)算機(jī)還不足以聰明到立刻計(jì)算生成一個(gè)很大的隨機(jī)素?cái)?shù)。就可以以 bits 為起點(diǎn)，得到一個(gè)數(shù)，這個(gè)數(shù)是素?cái)?shù)的概率很大。 m_nLength=bits。 m_ulValue[0]=m_ulValue[0]|1。 if(m_ulValue[i1]amp。 for(i=0。 (*this)。i++) { (rand()*rand())。amp。 綜上所述，總結(jié)素?cái)?shù)尋找的流程，如圖 21所示： 圖 21:尋找素?cái)?shù)流程 得到了大素?cái)?shù)，即 RSA 算法中的 p、 q，就可以計(jì)算出密鑰，進(jìn)行加密等操作了。歐幾里德算法是一種遞歸算法，較容易理解。 [0]。 程序中，函數(shù) Euc(CBigIntamp。 ⑸ .文件操作 本工程的核心是利用蒙哥馬利算法快速實(shí)現(xiàn) RSA 加密，為了便于研究對(duì)字符串的加密過(guò)程，以及記錄字 符串的密文樣本，程序把字符串寫(xiě)入 TXT文檔，再進(jìn)行加密解密操作，這樣就需要對(duì)文件進(jìn)行操作，以二進(jìn)制數(shù)據(jù)流對(duì)文件進(jìn)行讀出寫(xiě)入操作。（界面代碼多由 C++編譯器自動(dòng)生成，在此不再贅述）在類(lèi) CDemoDlg的構(gòu)造函數(shù)里，執(zhí)行準(zhǔn)備一對(duì)隨機(jī)密鑰的操作。編碼轉(zhuǎn)換通常是用 C風(fēng)格的指針操作。 加密解密流程均為標(biāo)準(zhǔn) RSA 算法，具體過(guò)程和使用方 法參見(jiàn)源程序和接口文檔。 圖 22：主要函數(shù)成員 編寫(xiě)測(cè)試各項(xiàng)性能需要的計(jì)時(shí)程序 由于對(duì)幾個(gè)字符的字符串進(jìn)行 RSA 加密，所用時(shí)間只需 10幾毫秒，一般的程序計(jì)時(shí)函數(shù)無(wú)法達(dá)到要求測(cè)試結(jié)果很可能是 0，于是在這里定義了 2個(gè) long型變量 t1,t2 來(lái)分別存儲(chǔ)加密函數(shù)運(yùn)行前后 GetTickCount()函數(shù)獲得的系統(tǒng)時(shí)間 ,然后將兩個(gè)值相減獲得消耗時(shí)間，這樣做還會(huì)有較大誤差，于是再次進(jìn)行了 改進(jìn)，通過(guò)一個(gè)簡(jiǎn)單的 for循環(huán)讓程序運(yùn)行 1000 次 ，然后將 t2t1 的值除 1000，以獲得較為精確的時(shí)間。其中最具影響力的因素顯然是 RSA 加密需要的 n的位數(shù)。 表 31： RSA加密模數(shù) n 與密鑰生成耗時(shí)的關(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)計(jì)數(shù)據(jù)，很容易發(fā)現(xiàn)隨著加密位數(shù)的增加，密鑰生成需要的時(shí)間顯 著增加。 此表僅能從實(shí)驗(yàn)的角度直觀理解，具體到一次密鑰生成的運(yùn)算，所需要的時(shí)間是很不確定的，比如，一次 512 位的密鑰生成，需要的時(shí)間完全可能比一次256 位的密鑰生成時(shí)間短，由于素?cái)?shù)分布規(guī)律非常奧妙，加上測(cè)試運(yùn)算需要的時(shí)間頗長(zhǎng)，這里很難給出對(duì)于一個(gè)具體位數(shù)的密鑰生成所需時(shí)間的統(tǒng)計(jì)模型。密鑰具體數(shù)據(jù)見(jiàn)附錄。對(duì)于 100 字節(jié)的文件來(lái)說(shuō)， 1024bit 的公鑰加密比 512bit 的耗時(shí)多 倍左右； 1024bit 的私鑰解密比 512bit 的耗時(shí)多 以上。因?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)算量差距也迅速加大。 性能分析與改進(jìn)優(yōu)化 經(jīng)過(guò)一系列的 RSA 密鑰生成、文件輸入輸出和蒙哥馬利加密解密測(cè)試，做簡(jiǎn)要的性能分析如下。所以，應(yīng)該將頻繁的讀寫(xiě)操作盡量集中到內(nèi)存，然后一次性寫(xiě)入磁盤(pán)。 ① 在要對(duì)文件進(jìn)行加密解密的時(shí)候，先將文件按一定的數(shù)據(jù)結(jié)構(gòu)讀入內(nèi)存，然后進(jìn)行加密或解密操作。 ③ 在安全性上做進(jìn)一步優(yōu)化，例如在尋找素?cái)?shù)時(shí)，素?cái)?shù) 測(cè)試使用更安全的算法，例如，本系統(tǒng)采用的是查已經(jīng)計(jì)算好的素?cái)?shù)表的方式得到準(zhǔn)確的素?cái)?shù)，但是素?cái)?shù)表的方式給 RSA 的安全性帶來(lái)隱患，因?yàn)楣粽呷绻玫搅嗣荑€生成時(shí)所使用的素?cái)?shù)表，攻破 RSA 加密的難度將會(huì)大大降低。 由于開(kāi)發(fā)時(shí)間 倉(cāng)促等因素，在書(shū)寫(xiě)本文時(shí)，軟件并未完成全面細(xì)致的優(yōu)化。 。 本文是在吳震老師的熱情關(guān)心和指導(dǎo)下完成的，他淵博的知識(shí)和嚴(yán)謹(jǐn)?shù)闹螌W(xué)作風(fēng)使我受益匪淺，對(duì)順利完成本課題起到了極大的作用。j++) { ((E,N))。 m_TM+= 毫秒 。 file = new CFile。 strset(data,0)。 UpdateData(FALSE)。 3. 加密解密測(cè)試時(shí)使用的兩組密鑰 512 位： 3C54793AA7186DEFFD54A9352E929F5A6A78034F2133D367965467322585D2B2537DED86DAB9A6A0E162A2B80A377CCDE790F221D15C917F9F821BDCBF71D045 34F7A974006EA75F1418F77274D0504E2EB9ED95D4BDCEB6DCBA7FDBFC2BB11EC3315F0177DD500463E2F44535324BDF3CC25053E5BF38F74570A9A8A2CBF4A5 1024 位： B3839FCFB21E7B916B62C20B79075C549BD558465F66C9BC5682DCFDE7818C1504D0D14AECEF1B1254C54CE36D7737EB34248E5F62B0FC4E34DA7C54AAC50CECBC9F3BF5C8C40503E4DD67A6744E0E022B995128D3F8EB9DBCB9E8EF1A5CF48B9D3D601D25850307BFE0AA83E6CDBB4FA765BB0FE7880908A3B48A2956F12FA5 25DF04DE0A53C7F9DBCFCFE41FBA5FCE31BA068F821CEB3E6279E52963A7BEE7C8464D81230F2684ED815A41389CC81D44B8D99861F7B8A2BF1FC0CF13DFD263DBF146D654370D17869452FD010E2A63F21EBF7C5FCC8F77DD2807977F1B6ACF447A7277B76D13819494EB6A892B0F7745D6215E5F08AB9D114749276AF51D19 算法可行性