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

　　

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