【導(dǎo)讀】息的一種通信方式和通信業(yè)務(wù)。隨著數(shù)據(jù)通信的迅速發(fā)展而帶來(lái)了數(shù)據(jù)失密問(wèn)題。所以數(shù)據(jù)加密成為十分重要的問(wèn)題，它能保證數(shù)據(jù)的安全性和不可篡改性。RSA加密算法以它難以破譯的優(yōu)點(diǎn)，被廣泛的使用在電子商務(wù)和VPN中。本文針對(duì)非對(duì)稱性加密RSA算法，采用軟件VisualC++進(jìn)行程序編寫(xiě)。法被他人破譯的目的。

　　

【正文】 難解性，即把 n 分解為 p、 q的困難程度。攻擊者破譯 RSA 公鑰密碼體制的步驟為 : (1)分解 n求出 p、 q。 (2)由 )(q)(p[r] 11 ?? ，求出由 Φ(r) (3)由 Φ (r))(ed m od1?? ，求出 d。 為了更好地防范分解攻擊， RSA 體制的發(fā)明者認(rèn)為要仔細(xì)地選 擇素?cái)?shù) p和 q，在選擇 p和 q 時(shí)還要注意以下方面 : (1)p 和 q在位數(shù)上要相差幾位數(shù)字 。 (2)(p1)和 (q1)都應(yīng)含有大的素?cái)?shù)因子，以增加加攻擊者猜算 出 Φ(r) 的困難性 。 (3) )q(p 11gcd ? 都應(yīng)當(dāng)小。 使用 RSA 公鑰密碼體制，要求用戶選擇兩個(gè)素?cái)?shù) p和 q，其中 p 和 q是保密的，并要求 p與 q 不相 等，對(duì) p和 q的乘積 qpn? 可以公開(kāi)。實(shí)際上，所謂攻擊者破譯 RSA 密碼體制，指的是由 e,n 來(lái)推 算 d, Φ(r) 。若 pq，則可按以下步驟分解 n: (1)因 p qr? 和由 lq)pq ( p)) ( q( pΦ ( r) ???? 11 求得 1??? Φ(r)qp 。 桂林理工大學(xué)本科畢業(yè)設(shè)計(jì)論文 19 (2)因 pq( p q )qpqpq)(p 42 2222 ?????? ，得到rqppqqpqp 4)(4)( 22 ??????? (3)由 2( p q) ) /q)((pp ??? 求出 p。 (4)q=r/p。 這樣求得了 P和 q，完成了對(duì) r的因子分解。 從數(shù)學(xué)上講，求一個(gè)對(duì) n不互素的數(shù) x 就等價(jià)于破譯了算法。 這是因?yàn)椋?x和 r的 gcd 可能等于 P或者 q，而其值可以用歐幾里 德算法計(jì)算出來(lái)。實(shí)際上，若 r足夠大，則沒(méi)必要擔(dān)心由 x這個(gè)數(shù) 來(lái)破譯算法。在 n???1 的區(qū)間中有 lq)pq ( p)) ( q( pΦ ( r) ???? 11 個(gè)與 r互素的數(shù)，且有 1(p q) Φ(r)r ?? 個(gè)與 r 非互素的數(shù)。所以偶 然出現(xiàn)含有 p 或 q 作為因子的一個(gè) 數(shù)的概率等于 : /q/p) / pqq(pr Φ Φ ( r) 111 ???? 對(duì)于數(shù)值很大的 p 和 q，這個(gè)概率是非常小的。 以目前的常規(guī)個(gè)人計(jì)算機(jī)為工具來(lái)進(jìn)行因子分解，其工作量是非線性增長(zhǎng)的，分析見(jiàn)表 4l: N的位數(shù) 所需時(shí)間 50 小時(shí) 75 104 天 100 74年 200 109年 300 1015年 500 1025年 因此，在安全性要求不是特別高的系統(tǒng)中，可以認(rèn)為 RSA 是 安全的。 RSA 時(shí)間復(fù)雜度分析 RSA 運(yùn)算過(guò)程涉及到大量的計(jì)算，所需時(shí)間相對(duì)于 DES 等加 密算法來(lái)說(shuō)，運(yùn)算時(shí)間較長(zhǎng)。但由于其良好的安全性和成熟的密鑰管理機(jī)制， RSA 在實(shí)際工作中，被廣泛采用。 本章小結(jié) RSA 從 20世紀(jì) 80年代產(chǎn)生至今，始終以其成熟的工作體制 和良好的安全性而被桂林理工大學(xué)本科畢業(yè)設(shè)計(jì)論文 20 廣泛的應(yīng)用于實(shí)際項(xiàng)目之中。 RSA 的安全性雖 然沒(méi)有通過(guò)數(shù)學(xué)上的論證，因此，其安全性主要體現(xiàn)在大素?cái)?shù)的分解這一復(fù)雜問(wèn)題上。通過(guò)實(shí)踐證明， RSA 在目前的計(jì)算機(jī)運(yùn)行能力 下，還是相對(duì)安全的。 RSA 在未來(lái)的很長(zhǎng)一段時(shí)間中，必將保持旺 盛的生命力。 近年來(lái)，隨著電子商務(wù)、電子政務(wù)等網(wǎng)上行為的增加，對(duì)于加密技術(shù)的研究日趨活躍。而對(duì) 于 RSA 的研究，同樣處于活躍的 狀態(tài)。由于 RSA 本身框架的成熟，因此，對(duì)于 RSA 的研究主要體 現(xiàn)在，對(duì)其子步驟算法的改進(jìn)和研究，比如對(duì)于模 n求逆算法的改 進(jìn)、最大公因子算法的改進(jìn) 。將 RSA 和其他算法、體制結(jié)合應(yīng)用， 比如目前在各計(jì)算機(jī)科技期刊上經(jīng)常見(jiàn)到的關(guān)于門限 RSA 體制的 研究成果。 本章主要討論了 RSA 內(nèi)部各步驟的算法實(shí)現(xiàn) 。 桂林理工大學(xué)本科畢業(yè)設(shè)計(jì)論文 21 第 5 章 RSA 算法的實(shí)現(xiàn) 基于前面的分析，本章給出了一種實(shí)現(xiàn) RSA 的快速高效算 法，并介紹了利用組合算法實(shí)現(xiàn)大整數(shù)快速模冪 乘運(yùn)算的具體實(shí)現(xiàn)過(guò)程，以及在實(shí)現(xiàn)過(guò)程中所遇到的關(guān)鍵問(wèn)題及解決方法。 選定組合算法的準(zhǔn)則 一個(gè)算法必須滿足它自身是正確的，即可以得到想要的計(jì)算結(jié)果。 算法必須是有效的，即是高效的算法。 簡(jiǎn)單性原則不僅要使算法要盡量的容易實(shí)現(xiàn)，而且要盡量使程序容易被用戶使用。 要求算法確實(shí)可行，不僅是在理論上是正確的，還要求在實(shí)際上也能達(dá)到預(yù)期的效果。 模冪組合算法的實(shí)現(xiàn) 本文前面介紹了一系列大數(shù)模冪運(yùn)算及其改進(jìn)算法，具體的實(shí)現(xiàn)方法步驟如下： （ 1）任 意選取兩個(gè)不同的大質(zhì)數(shù) p和 q，計(jì)算乘積 qpr ?? ； （ 2）任意選取一個(gè)大整數(shù) d， d與 ))*(q(p 11 互質(zhì)，整數(shù) d用做加密密鑰。注重d的選取是很輕易的，例如所有大于 p 和 q 的質(zhì)數(shù)都可用 .； （ 3）確定解密密鑰 n，由 ))) *( q( ( pdn 11m od1?? ，根據(jù) d， p和 q可以輕易地計(jì)算出 n，即為逆元 ； （ 4）公開(kāi)整數(shù) r和 d，但是不公開(kāi) n； （ 5） 規(guī)定明文動(dòng)態(tài)分布空間 L，輸入明文，通過(guò)計(jì)算成為密文 ； （ 6）將密文 C 解密為明文； 具體程 序見(jiàn)附錄。 桂林理工大學(xué)本科畢業(yè)設(shè)計(jì)論文 22 試驗(yàn)與運(yùn)行結(jié)果 開(kāi)發(fā)環(huán)境： ， 512M 內(nèi)存， 80G 硬盤， 17寸顯示器 操作系統(tǒng)： Windows XP 開(kāi)發(fā)工具： Visusl C++ 仿真結(jié)果： 其中 p,q 為 2位素?cái)?shù)，計(jì)算 p 與 q 的乘積，輸入整數(shù) d， d可以取大于 p,q 的素?cái)?shù)小于 p,q 乘積，要求與 (p－ 1)*(q－ 1)互質(zhì)，計(jì)算 d 的逆元， 輸入明文動(dòng)態(tài)空間 L，要求明文字節(jié)數(shù)不得超過(guò) L，否則任務(wù)終止。 系統(tǒng)計(jì)算密文，然后計(jì)算明文 舉例如圖： 輸入 2 個(gè)素?cái)?shù)： p=11,q=311,當(dāng)輸入不是素?cái)?shù)時(shí)會(huì)提示如下 計(jì)算出 p與 q的乘積 r 為 3421，（ p1） 于 (q1)乘積為 3100，輸入隨機(jī)大整數(shù)例如 353，與 3100 僅有公約數(shù) 1，如輸入錯(cuò)誤時(shí)會(huì)有如下提示 計(jì)算 353 的逆元 ,由 n*d=1mod((p－ 1)*(q－ 1))可得逆元為 2617，規(guī)定明文動(dòng)態(tài)桂林理工大學(xué)本科畢業(yè)設(shè)計(jì)論文 23 分配空間，此時(shí)我規(guī)定的是 64 個(gè)字節(jié)，輸入明文 12345678，通過(guò) ulo r Pe C mod? C = Pe modulo r 計(jì)算將會(huì)轉(zhuǎn)化為密文： 1268 2307 116 838 323 692 440 2366，再通過(guò) ulo rCdP mod? 將其轉(zhuǎn)換回來(lái)就為 12345678 在實(shí)際生活中，取素?cái)?shù) p=11,q=311,公開(kāi)乘積 r,保密 d與逆元 n，當(dāng)小 A 發(fā)出明文 12345678 時(shí)，對(duì)其加密，得到密文 1268 2307 116 838 323 692 440 2366，發(fā)給小 C，他通過(guò)認(rèn)證可得到明文 12345678 桂林理工大學(xué)本科畢業(yè)設(shè)計(jì)論文 24 總結(jié) 在當(dāng)今的信息社會(huì)中，每天都有大量的信息在傳輸、交換存儲(chǔ)和處理，而這些處理過(guò)程幾乎都要依賴強(qiáng)大的計(jì)算機(jī)系統(tǒng)來(lái)完成。一旦計(jì)算機(jī)系統(tǒng)發(fā)生安全問(wèn)題，就可造成信息的丟失、篡改、偽造、假冒、失密，以及系 統(tǒng)遭受搗亂、破壞等嚴(yán)重后果，輕者造成計(jì)算機(jī)系統(tǒng)運(yùn)行效率低下，重者造成計(jì)算機(jī)系統(tǒng)的徹底癱瘓。因此，如何保證計(jì)算機(jī)系統(tǒng)的安全是當(dāng)前一個(gè)需要立即解決的十分嚴(yán)峻的問(wèn)題。密碼學(xué)的基本目的是使在不安全信道中通信的兩方以一種使他們的對(duì)手不能明白和理解的通信內(nèi)容的方式進(jìn)行通信。本文對(duì)密碼學(xué)與信息安全方面做了簡(jiǎn)要的概述，具體論述了 RSA 公鑰密碼體制， RSA 已經(jīng)成為一種國(guó)際公認(rèn)的公 鑰密碼體制，在實(shí)際應(yīng)用中也最為廣泛。文章對(duì) RSA 公鑰密碼體 制的數(shù)學(xué)基礎(chǔ)，加密算法，簽名算法，安全性及參數(shù)的選擇做了詳細(xì)的討論。在當(dāng)今還沒(méi)有一個(gè)較 RSA 公鑰密碼系統(tǒng)更為優(yōu)秀的密碼系 統(tǒng)出現(xiàn)之前，能夠有效地改進(jìn) RSA 密碼算法的運(yùn)行速度也是當(dāng)今 密碼學(xué)主要的一個(gè)研究方向。此外，在實(shí)踐中還可能發(fā)現(xiàn)本文研究未涉及的新問(wèn)題，還需不斷的歸納、總結(jié)，并提出相應(yīng)的解決方法。 桂林理工大學(xué)本科畢業(yè)設(shè)計(jì)論文 25 參考文獻(xiàn) [1]盧開(kāi)澄，郭保安，戴一奇等計(jì)算機(jī)系統(tǒng)安全 .重慶 :重慶出版社， 1999 [2]李海泉，李鍵 .計(jì)算機(jī)系統(tǒng)安全技術(shù) .北京 :人民郵電出版社， 20xx [3]黃元飛，陳麟，唐三平 .信息安全與加密解密核心技術(shù) .上海 :浦東電 子出版社， 20xx [4]李紅軍，繆旭東 .數(shù)據(jù) 加密在網(wǎng)絡(luò)安全中的應(yīng)用 .微型機(jī)與應(yīng)用， 20xx(10):3133 [5]Steve Practical Guide to Managing Information :Artech House Books,20xx [6]王育民，劉建偉．通信網(wǎng)的安全．西安：西安電子科技大學(xué)出版社， 1999， 50213 [7]王宇潔，張曉丹，徐占文等．一種新的組合快速 RSA 算法．沈陽(yáng) 工業(yè)大學(xué)學(xué)報(bào)，20xx， 27(2)： 224227 [8]D Lou， C Chang． An adaptive exponentiation method． The Journal ofsystems and software， 1998， 42： 5969 [9]Phillips B J， Burgess N． Implementing 1024bits RSA exponentiation on a 32bits processor core． IEEE International conference on Application Specific Systems， Architecture and processor(A SAP’00) ， 20xx [10]胡建軍，李愛(ài)武．中國(guó)剩余定理提高 RSA 解密速度的分析．現(xiàn)代 計(jì)算機(jī)， 20xx，2(21)： 1011 [11]馮登國(guó)等，《密碼學(xué)導(dǎo)引》，科學(xué)出版社， ,412 [12]曹珍富，《公鑰密碼學(xué)》，黑龍江教育出版社， ,1528 [13]談嫻茹，基于 DES和 RSA的網(wǎng)絡(luò)數(shù)據(jù)安全系統(tǒng)，中國(guó)民航學(xué)院學(xué) 報(bào)， (A02)，133136 [14]Bruce Schneier 著 .吳世忠等譯《，應(yīng)用密碼學(xué)協(xié)議算法與 c 源程序》， 機(jī)械工業(yè)出版社， 20xx,118132 [15]顧冠群等，密鑰管理的設(shè)計(jì)與實(shí)現(xiàn)，電信科學(xué)， ,4751 [16]王立勝等，數(shù)據(jù)加密標(biāo)準(zhǔn) DES 分析及其攻擊研究，計(jì)算機(jī)工程， 20xx,29(13)，130132 [17]王克苑等， SSL 安全性分析研究，合肥工業(yè)大學(xué)學(xué)報(bào) (自然科學(xué)版 )20xx,27(1)，8791 [18]劉鐵民等， VPN 網(wǎng)絡(luò)隧道技術(shù)的研究，電信工程技術(shù)與標(biāo)準(zhǔn)化， 20xx(12).5557 [19]張燕，數(shù)字簽名技術(shù)的研究，計(jì)算機(jī)時(shí)代， 1998(5),2022 [20]賀衛(wèi)紅等， RSA 公鑰 密碼體制在數(shù)字簽名中的應(yīng)用，微機(jī)發(fā)展， 20xx(9)， 4951 桂林理工大學(xué)本科畢業(yè)設(shè)計(jì)論文 26 致謝 本論文是在導(dǎo)師 ....老師的悉心指導(dǎo)下完成的。從論文選題、資料收集、數(shù)據(jù)整理到論文的撰寫(xiě)，每個(gè)環(huán)節(jié) ....老師都給予了我無(wú)微不至的關(guān)懷和毫無(wú)保留的指導(dǎo)，提出了許多寶貴的意見(jiàn)和建議。 ....老師淵博的學(xué)術(shù)知識(shí)、嚴(yán)謹(jǐn)?shù)目蒲袘B(tài)度和誨人不倦的治學(xué)精神都在潛移默化的感染著我，使我受益匪淺，終生難忘。值此論文完成之際，請(qǐng)導(dǎo)師接受我最衷心的感謝和最誠(chéng)摯的敬意。 感謝 ..........等幾位同學(xué)在工作、學(xué)習(xí)中給予我的關(guān)心和支持， 我們互相幫助，共同渡過(guò)了研究生階段學(xué)習(xí)的美好時(shí)光。 感謝桂林理工大學(xué)的各位老師，特別是電子與計(jì)算機(jī)系的領(lǐng)導(dǎo)和老師們。他們?cè)谖业膶W(xué)習(xí)和論文撰寫(xiě)、答辯過(guò)程中，均給予了我莫大的幫助。 此致 致謝