【正文】 較高級的因數(shù)分解方法使“安全素數(shù)”的概念也在不停的演化。由于高速計算機的出現(xiàn)，以前認為己經(jīng)很具安全性的 512 位密鑰長度己經(jīng)不再滿足人們的需要。 B)分組長度太大，為保證安全性， n 至少也要 600 bits 以上，使運算代價很高，尤其是速度較慢，較對稱密碼算法慢幾個數(shù)量級；且隨著大數(shù)分解技術(shù)的發(fā)展，這個長度還在增加，不利于數(shù)據(jù)格式的標準化。硬件上，如安全電話、以太網(wǎng)卡和 I智能卡也多采用 RSA技術(shù)。在沒有找到快速進行大整數(shù)分解因式方法的時候， RSA 顯示了不可比擬的優(yōu)點。它易于理解和操作，也很流行。 RSA 算法實現(xiàn)數(shù)據(jù)加密的主要步驟分為： 獲取密鑰，這里是產(chǎn)生密鑰，實際應用中可以從各種存儲介質(zhì)上讀取密鑰 。顯然，通過對一個隨機數(shù)進行因子分解，我們可以判斷這個隨機數(shù)是否為素數(shù)。正確的生成大素數(shù)的方法是對生成的隨機數(shù)先測試它是否為 素數(shù)，而不是對它進行因子分解。 要討論素數(shù)的生成問題，首先要討論素數(shù)的分布。假設正整數(shù)中只有 k個素數(shù)，設為 k21 p p, p ? 。故 p與 k21 p p, p ? 都不相同，這與只有 k 個素數(shù)的假設想矛盾。論文 12 (x)? 為不大于 x 的整數(shù)的個數(shù)，則 1)ln()(lim ??? xxxx? 根據(jù)素數(shù)定理，可以估計出長度為 t 位的素數(shù)大約有2ln)1( )2(22ln22ln2111tt tttttt? ?????? 個。然而其產(chǎn)生的素數(shù)卻帶有一定的限制。此方法需要求得素數(shù) n1 的全部素因子。 此類方法是生成大素數(shù)的主要方法，其中著名有 :Miller Rabin 與 Solovay Strassen 算法等。論文 13 或者存在一個 r, sr0 ?? ，使得 n)(mb r m od12 ? 則稱 n 通過以 b 為基的 MillerRabin 測試。強素數(shù)的概念 Gordon J 于 1984 年提出，強素數(shù) p應 該滿足 4個條件 : (1)p 是一個位數(shù)足夠暢的隨機選取素數(shù) 。 若 p1 含有一個大的素數(shù)因子 r，則 ljrp ?? ， j 為整數(shù)，由于 p與 r均為奇數(shù) (大素數(shù) )，所以 j 一定是偶數(shù)。基本思想如算法流程圖 41所示下： 若 C 為任意正整數(shù)，則每 ln(c)個數(shù)中有一個素數(shù)，所以在 m 附近找 Ln(m)次后仍末成功，便可重新生成隨 機數(shù) m，繼續(xù)在 m附 近尋找。 桂林理工大學本科畢業(yè)設計否則轉(zhuǎn) 3): 6) 1m o d1)1( ??? na jqn ，則 n 是素數(shù)，否則轉(zhuǎn) 3)。 如果 P 通過 D(D30)次 Miller Rabin 檢測，則可 以人為 P是一個素數(shù)。 由于密碼長度直接影響系統(tǒng)運行的速度，所以對要不是特別高的系統(tǒng)，可以適當?shù)臏p少密碼的長度。上一節(jié)，已經(jīng)討論了大素數(shù)的生成算法，這里主要討論最大公因子 gcd、模 n 求逆 namod1 和模 n的大數(shù)冪乘 nxymod 的算法。 設定 n和 u 兩個正整數(shù)，則一定存在整數(shù) q和 r使得 n=qu+r,其中 ur0 ?? ，不難看出， (u, r)(n, u) gc dgc d ? 由此，我們得到求兩個正整數(shù)的最大公因子的 Euclid算法如下 : (1) unnn ?? 21 , 。 利用數(shù)學歸納法容易證明 :對任意 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 ?? 事實上，當 0?i 時，取 10000010 2211 ???? )(,b)(,a)(,b)(a 則 顯然有 )()n(b)()n(a)(n )()n(b)()n(a)(n 00000 00000 22122 21111 ?? ?? 假設 i=j 時，式 (415)和 (416)成立，則當 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) ??gc d . 桂林理工大學本科畢業(yè)設計 以上即為擴展的 Euclid 算法，該算法在計算模 n求逆時，頗有 用處。使得1mod ? nuv 的充分必要條件是 l(u,n)?gcd 。 由上述定理的充要性證明可以得知，利用擴展的 Euclid 算法可 以求得 u 模 n 的逆，以擴展的 Euclid 算法為基礎，可以得到模 n求 逆的算法如下： (1) 1b0,b1,au,nn,n 21121 ????? 。 舉例說明上述算法，求 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ù)冪乘運算 RSA 公鑰密碼體制中，加密和解密時都要進行 運算，下面給出一個計算 nxrmod的快速算法。 (4) n a) m o d(aab / 2 ,b ??? 轉(zhuǎn)第 (3)步 :， (5) n a) m o d(cc1,bb ??? ，轉(zhuǎn)第 (2)步。 (3)如果 02mod ? b ，則轉(zhuǎn)到第 (5)步 。以上算法，均從數(shù)論的角度加以論證，在理論上切實可行。 RSA 安全性分析 RSA 的安全性，是基于大整數(shù)的素分解問題的難解性，即把 n 分解為 p、 q的困難程度。 (2)(p1)和 (q1)都應含有大的素數(shù)因子，以增加加攻擊者猜算 出 Φ(r) 的困難性 。若 pq，則可按以下步驟分解 n: (1)因 p qr? 和由 lq)pq ( p)) ( q( pΦ ( r) ???? 11 求得 1??? Φ(r)qp 。 這樣求得了 P和 q，完成了對 r的因子分解。在 n???1 的區(qū)間中有 lq)pq ( p)) ( q( pΦ ( r) ???? 11 個與 r互素的數(shù)，且有 1(p q) Φ(r)r ?? 個與 r 非互素的數(shù)。但由于其良好的安全性和成熟的密鑰管理機制， RSA 在實際工作中，被廣泛采用。通過實踐證明， RSA 在目前的計算機運行能力 下，還是相對安全的。由于 RSA 本身框架的成熟，因此，對于 RSA 的研究主要體 現(xiàn)在，對其子步驟算法的改進和研究，比如對于模 n求逆算法的改 進、最大公因子算法的改進 。論文 21 第 5 章 RSA 算法的實現(xiàn) 基于前面的分析，本章給出了一種實現(xiàn) RSA 的快速高效算 法，并介紹了利用組合算法實現(xiàn)大整數(shù)快速模冪 乘運算的具體實現(xiàn)過程，以及在實現(xiàn)過程中所遇到的關(guān)鍵問題及解決方法。 要求算法確實可行，不僅是在理論上是正確的，還要求在實際上也能達到預期的效果。論文 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)發(fā)生安全問題，就可造成信息的丟失、篡改、偽造、假冒、失密，以及系 統(tǒng)遭受搗亂、破壞等嚴重后果，輕者造成計算機系統(tǒng)運行效率低下，重者造成計算機系統(tǒng)的徹底癱瘓。文章對 RSA 公鑰密碼體 制的數(shù)學基礎，加密算法，簽名算法，安全性及參數(shù)的選擇做了詳細的討論。論文 25 參考文獻 [1]盧開澄，郭保安，戴一奇等計算機系統(tǒng)安全 .重慶 :重慶出版社， 1999 [2]李海泉，李鍵 .計算機系統(tǒng)安全技術(shù) .北京 :人民郵電出版社， 20xx [3]黃元飛，陳麟，唐三平 .信息安全與加密解密核心技術(shù) .上海 :浦東電 子出版社， 20xx [4]李紅軍，繆旭東 .數(shù)據(jù) 加密在網(wǎng)絡安全中的應用 .微型機與應用， 20xx(10):3133 [5]Steve Practical Guide to Managing Information :Artech House Books,20xx [6]王育民，劉建偉．通信網(wǎng)的安全．西安：西安電子科技大學出版社， 1999， 50213 [7]王宇潔，張曉丹，徐占文等．一種新的組合快速 RSA 算法．沈陽 工業(yè)大學學報，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]胡建軍，李愛武．中國剩余定理提高 RSA 解密速度的分析．現(xiàn)代 計算機， 20xx，2(21)： 1011 [11]馮登國等，《密碼學導引》，科學出版社， ,412 [12]曹珍富，《公鑰密碼學》，黑龍江教育出版社， ,1528 [13]談嫻茹，基于 DES和 RSA的網(wǎng)絡數(shù)據(jù)安全系統(tǒng)，中國民航學院學 報， (A02)，133136 [14]Bruce Schneier 著 .吳世忠等譯《，應用密碼學協(xié)議算法與 c 源程序》， 機械工業(yè)出版社， 20xx,118132 [15]顧冠群等，密鑰管理的設計與實現(xiàn)，電信科學， ,4751 [16]王立勝等，數(shù)據(jù)加密標準 DES 分析及其攻擊研究，計算機工程， 20xx,29(13)，130132 [17]王克苑等， SSL 安全性分析研究，合肥工業(yè)大學學報 (自然科學版 )20xx,27(1)，8791 [18]劉鐵民等， VPN 網(wǎng)絡隧道技術(shù)的研究，電信工程技術(shù)與標準化， 20xx(12).5557 [19]張燕，數(shù)字簽名技術(shù)的研究，計算機時代， 1998(5),2022 [20]賀衛(wèi)紅等， RSA 公鑰 密碼體制在數(shù)字簽名中的應用，微機發(fā)展， 20xx(9)， 4951 桂林理工大學本科畢業(yè)設計值此論文完成之際，請導師接受我最衷心的感謝和最誠摯的敬意。 此致 致謝 。 感謝桂林理工大學的各位老師，特別是電子與計算機系的領導和老師們。從論文選題、資料收集、數(shù)據(jù)整理到論文的撰寫，每個環(huán)節(jié) ....老師都給予了我無微不至的關(guān)懷和毫無保留的指導，提出了許多寶貴的意見和建議。此外，在實踐中還可能發(fā)現(xiàn)本文研究未涉及的新問題，還需不斷的歸納、總結(jié)，并提出相應的解決方法。密碼學的基本目的是使在不安全信道中通信的兩方以一種使他們的對手不能明白和理解的通信內(nèi)容的方式進行通信。論文 23 分配空間，此時我規(guī)定的是 64 個字節(jié)，輸入明文 12345678，通過 ulo r Pe C mod? C = Pe modulo r 計算將會轉(zhuǎn)化為密文： 1268 2307 116 838 323 692 440 2366，再通過 ulo rCdP mod? 將其轉(zhuǎn)換回來就為 12345678 在實際生活中，取素數(shù) p=11,q=311,公開乘積 r,保密 d與逆元 n，當小 A 發(fā)出