【正文】 此致 致謝 。 感謝桂林理工大學(xué)的各位老師，特別是電子與計算機(jī)系的領(lǐng)導(dǎo)和老師們。值此論文完成之際，請導(dǎo)師接受我最衷心的感謝和最誠摯的敬意。從論文選題、資料收集、數(shù)據(jù)整理到論文的撰寫，每個環(huán)節(jié)陳飛老師都給予了我無微不至的關(guān)懷和毫無保留的指導(dǎo)，提出了許多寶貴的意見和建議。論文 25 參考文獻(xiàn) [1]盧開澄，郭保安，戴一奇等計算機(jī)系統(tǒng)安全 .重慶 :重慶出版社， 1999 [2]李海泉，李鍵 .計算機(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é)報，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ī)， 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é) 報， (A02)，133136 [14]Bruce Schneier 著 .吳世忠等譯《，應(yīng)用密碼學(xué)協(xié)議算法與 c源程序》， 機(jī)械工業(yè)出版社， 2021,118132 [15]顧冠群等，密鑰管理的設(shè)計與實現(xiàn)，電信科學(xué)， ,4751 [16]王立勝等，數(shù)據(jù)加密標(biāo)準(zhǔn) DES 分析及其攻擊研究，計算機(jī)工程， 2021,29(13)，130132 [17]王克苑等， SSL 安全性分析研究，合肥工業(yè)大學(xué)學(xué)報 (自然科學(xué)版 )2021,27(1)，8791 [18]劉鐵民等， VPN 網(wǎng)絡(luò)隧道技術(shù)的研究，電信工程技術(shù)與標(biāo)準(zhǔn)化， 2021(12).5557 [19]張燕，數(shù)字簽名技術(shù)的研究，計算機(jī)時代， 1998(5),2022 [20]賀衛(wèi)紅等， RSA 公鑰密碼體制在數(shù)字簽名中的應(yīng)用，微機(jī)發(fā)展， 2021(9)， 4951 桂林理工大學(xué)本科畢業(yè)設(shè)計此外，在實踐中還可 能發(fā)現(xiàn)本文研究未涉及的新問題，還需不斷的歸納、總結(jié)，并提出相應(yīng)的解決方法。文章對 RSA公鑰密碼體 制的數(shù)學(xué)基礎(chǔ)，加密算法，簽名算法，安全性及參數(shù)的選擇做了詳細(xì)的討論 。密碼學(xué)的基本目的是使在不安全信道中通信的兩方以一種使他們的對手不能明白和理解的通信內(nèi)容的方式進(jìn)行通信。一旦計算機(jī)系統(tǒng)發(fā)生安全問題，就可造成信息的丟失、篡改、偽造、假冒、失密，以及系統(tǒng)遭受搗亂、破壞等嚴(yán)重后果，輕者造成計算機(jī)系統(tǒng)運(yùn)行效率低下，重者造成計算機(jī)系統(tǒng)的徹底癱瘓。論文 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，當(dāng)小 A 發(fā)出明文 12345678 時， 對其加密，得到密文 1268 2307 116 838 323 692 440 2366，發(fā)給小 C，他通過認(rèn)證可得到明文 12345678 桂林理工大學(xué)本科畢業(yè)設(shè)計論文 22 試驗與運(yùn)行結(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，否則任務(wù)終止。注重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解密為明文； 具體程序 見附錄。 要求算法確實可行，不僅是在理論上是正確的，還要求在實際上也能達(dá)到預(yù)期的效果。 算法必須是有效的，即是高效的算法。論文 21 第 5 章 RSA算法的實現(xiàn) 基于前面的分析，本章給出了一種實現(xiàn) RSA 的快速高效算 法，并介紹了利用組合算法實現(xiàn)大整數(shù)快速模冪乘運(yùn)算的具體實現(xiàn)過程，以及在實現(xiàn)過程中所遇到的關(guān)鍵問題及解決方法。 本章主要討論了 RSA內(nèi)部各步驟的算法實現(xiàn) 。由于 RSA 本身框架的成熟，因此，對于 RSA 的研究主要體 現(xiàn)在，對其子步驟算法的改進(jìn)和研究，比如對 于模 n求逆算法的改 進(jìn)、最大公因子算法的改進(jìn) 。 近年來，隨著電子商務(wù)、電子政務(wù)等網(wǎng)上行為的增加，對于加密技術(shù)的研究日趨活躍。通過實踐證明， RSA 在目前的計算機(jī)運(yùn)行能力 下，還是相對安全的。論文 20 廣泛的應(yīng)用于實際項目之中。但由于其良好的安全性和成熟的密鑰管理機(jī)制， RSA 在實際工作中，被廣泛采用。 以目前的常規(guī)個人計算機(jī)為 工具來進(jìn)行因子分解，其工作量是非線性增長的，分析見表 4l: N的位數(shù) 所需時間 50 小時 75 104 天 100 74年 200 109年 300 1015年 500 1025年 因此，在安全性要求不是特別高的系統(tǒng)中，可以認(rèn)為 RSA 是 安全的。在 n???1 的區(qū)間中有 lq)p q ( p)) ( q ( p Φ( r ) ???? 11 個與 r互素的數(shù)，且有 1(pq)Φ(r)r ?? 個與 r 非互素的數(shù)。 這是因為： x 和 r 的 gcd 可能等于 P 或者 q，而其值可以用歐幾里 德算法計算出來。 這樣求得了 P和 q，完成了對 r 的因子分解。論文 19 (2)因 pq( p q )qpqpq)(p 42 2222 ?????? ，得到rqppqqpqp 4)(4)( 22 ??????? (3)由 2(p q ))/q)((pp ??? 求出 p。若 pq，則可按以下步驟分解 n: (1)因 p qr? 和由 lq)p q ( p)) ( q ( p Φ( r ) ???? 11 求得 1??? Φ(r)qp 。 使用 RSA 公鑰密碼體制，要求用戶選擇兩個素數(shù) p和 q，其中 p 和 q 是保密的，并要求 p與 q不相等，對 p和 q的乘積 qpn? 可以公開。 (2)(p1)和 (q1)都應(yīng)含有大的素數(shù)因子，以增加加攻擊者猜算 出 Φ(r) 的困難性 。 (2)由 )(q)(p[r] 11 ?? ，求出由 Φ(r) (3)由 Φ( r))(ed m od1?? ，求出 d。 RSA 安全性分析 RSA 的安全性，是基于大整數(shù)的素分解問題的難解性，即把 n分解為 p、 q的困難程度。 RSA算法分析 RSA 公鑰密碼體制是目前常用的一種密碼體制，無論從數(shù)論的 角度，還是從實踐的角度，都己經(jīng)證明了 RSA 的正確性。以上算法，均從數(shù)論的角度加以論證，在理論上切實可行。 例如 :計算 322mod 12 桂林理工大學(xué)本科畢業(yè)設(shè)計 (3)如果 02mod ? b ，則轉(zhuǎn)到第 (5)步 。 (1)a←x,b←r,c←1。 (4) n a ) m o d(aab /2 ,b ??? 轉(zhuǎn)第 (3)步 :， (5) n a ) m o d(cc1,bb ??? ，轉(zhuǎn)第 (2)步。 (2)如果 b=0，則輸出結(jié)果 c，結(jié)束 。 舉例說明上述算法，求 13 模 35 的逆元 : 35=2 13+9,9=1 352 13, 13=1 9+4,4=1 131 9=1 35+3 9=2 4+1,1=1 92 4=3 358 13, 所以 13 模 35 的逆元為 27035mod8 = )( 模 n的大數(shù)冪乘運(yùn)算 RSA 公鑰密碼體制中，加密和解密時都要進(jìn)行 運(yùn)算， 下面給出一個計算 nxrmod的快速算法。 (3)如果 r≠0 ， 則 2122221 qbb,bbr , t,nnn ????? ； 桂林理工大學(xué)本科畢業(yè)設(shè)計 由上述定理的充要性證明可以得知，利用擴(kuò)展的 Euclid 算法可 以求得 u 模 n 的逆，以擴(kuò)展的 Euclid 算法為基礎(chǔ)，可以得到模 n 求 逆的算法如下： (1) 1b0,b1,au,nn,n 21121 ????? 。因為 qn)(u,n)|(bugcd ，所以 1mod ? nbu ， 即對任意 Znb? ，都有 1mod ? nbu ，因此，如果存在 ZnV? ， 使得 1mod ? nuv ，則必然有 1gcd ?(u,n) 。使得1mod ? nuv 的充分必要條件是 l(u,n)?gcd 。設(shè) n 和 u 都是正整數(shù)， uvu ?? 模 n 的逆就是滿足 n)(uv mod1? 的整數(shù) v, uv??0 。 以上即為擴(kuò)展的 Euclid 算法，該算法在計算模 n 求逆時，頗有 用處。1,0,0,1, 221121 ?????? babaunnn (2) 21, qnnrunq ????????? (3)如果 r=0， 則 222g c d b,ba,an(n ,u ) ??? 。 利 用數(shù)學(xué)歸納法容易證明 :對任意 0i? ，存在整數(shù) (i)(i),b(i),a(i),ba 2211 使得 ) (( i) nb)(( i) na( i)n 00 21111 ?? ) (( i) nb)(( i) na( i)n 00 22122 ?? 事實上，當(dāng) 0?i 時，取 10000010 2211 ???? )(,b)(,a)(,b)(a 則 顯然有 )()n(b)()n(a)(n )()n(b)()n(a)(n 00000 00000 22122 21111 ?? ?? 假設(shè) i=j 時，式 (415)和 (416)成立，則當(dāng) i=j+l 時 ， )((j )n(j )q (j )b)+ b((j )n(j )q (j )a(j )= (a(j )q (j )n)= n(j +n ) ，((j )n)+ b((j )n(j )= a)= n(j +n 001 001 221121212 221221 其中 q(j)為 Euclid 算法中第 i 次對 q賦值后 q的值，規(guī)定 ，因此 ( j ) ,( j ) q ( j ) bb)(jb( j ) ,( j ) q ( j ) aa)(ja( j ) ,b)(jb( j ) ,a)(ja21221221211111???????? 從上面的討論可知，存在整數(shù) a 和 b 使得 buan(n,u) ??gcd . 桂林理工大學(xué)本科畢業(yè)設(shè)計 (4)如果 r≠0 ，則 21 nn ? ， rn2? ，轉(zhuǎn)第 (2)步。 設(shè)