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

　　

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