【正文】 感謝 ..........等幾位同學在工作、學習中給予我的關心和支持， 我們互相幫助，共同渡過了研究生階段學習的美好時光。在當今還沒有一個較 RSA 公鑰密碼系統(tǒng)更為優(yōu)秀的密碼系 統(tǒng)出現(xiàn)之前，能夠有效地改進 RSA 密碼算法的運行速度也是當今 密碼學主要的一個研究方向。 系統(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è)設計 選定組合算法的準則 一個算法必須滿足它自身是正確的，即可以得到想要的計算結果。 RSA 在未來的很長一段時間中，必將保持旺 盛的生命力。所以偶 然出現(xiàn)含有 p 或 q 作為因子的一個 數(shù)的概率等于 : /q/p) / pqq(pr Φ Φ ( r) 111 ???? 對于數(shù)值很大的 p 和 q，這個概率是非常小的。 桂林理工大學本科畢業(yè)設計攻擊者破譯 RSA 公鑰密碼體制的步驟為 : (1)分解 n求出 p、 q。 (4) n a) m o d(aab / 2 ,b ??? b←b/2, 轉第 (3)步 :， (5) n a) m o d(cc1,bb ??? ，轉第 (2)步。 (1)a←x,b←r,c←1。 證明必要性 :對于任意 Znb? ，存在整數(shù) q 使得 nbuqn??0 , bu qn nbu ?m od 假設 1gcd ?(u,n) 。論文 16 可以對 Euclid 算法做一點修改，使之可以同時求出 gcd(n,u)和滿足上式的整數(shù)a和 b，稱之擴展 Euclid 算法，此 算法描述如下 : (1) 。 gcd運算 這里采用經(jīng)典的 Euclid 算法為 基礎進行運算 C。 大素數(shù)的選取對 RSA 系統(tǒng)的安全而言至關重要。論文 14 3)a←a+l。由此，也可以用如下 三個等式來表示強素數(shù) p: t ) . (或rt)r(s ) : (或pk s )p(r ) 。下面是 MillerRabin 素性測試的依據(jù)，包括兩個定理 : 定理一：設 p是一個素數(shù)，對任意整數(shù) b，如果 1gcd(bp) ，則 p 一定可以通過以 b 為基的 MillerRabin 測試。 Lucas 定理：設Nn? ，存在一個正整數(shù) naa,1 ?? 且 n) 1(moda 1n ? ，且對于 n1 的每一個素 q，均滿足 ln moda /q1)(n ?a，則 n 為素數(shù)。例如，一個長度為 256 位的隨機數(shù)的素數(shù)的概率為 254 ??? 而一個長度為 64 位的隨機數(shù)的素數(shù)的概率為 0 2 64 ??? 由此可見，位數(shù)越多，素數(shù)的分布越為稀疏。令 1pppn k21 ?? ? ,則 n1。這種素性測試比因子分解要容易得多，己經(jīng)有許多素性測試方法能夠確定一個隨機數(shù)是否為素數(shù)。 加密 。而當分解因式不再是難題的時候，RSA 算法也就將失去存在的價值。 本章小結 RSA 算法在理論上的重大缺陷就是并不能證明分解因數(shù)絕對是困難的。所以，選擇傳統(tǒng)上認為是“安全素數(shù)”并不一定有效的增加安全性，比較保險的方法就是選擇足夠大的素數(shù)。己知 n，求得 )(n? ，則 P和 q可以求得。 由 1(mod22 0) de ?，得 d=147。 RSA 公鑰密碼體制概述 RSA 公鑰密碼體制于 1978 年，由美國麻省理工學院 Rivest,Shami:和 Adleman二人提出的，至今為止仍被公認為是公鑰密碼體制中最優(yōu)秀的加密算法，被認為是密碼學發(fā)展史上的第二個里程碑 .它是一種特殊的可逆摸指數(shù)運算的加密體制，其理論基礎是數(shù)論中的一條重要論斷 :求兩個大素數(shù)之積是容易的，而將一個具有大素數(shù)因子的合數(shù)進行分解卻是非常困難的。數(shù)字簽名技術實際上是數(shù)據(jù)加密技術在應用上的延伸，是目前網(wǎng)上交易活動中，身份驗證技術的重要組成部分。這種情況下，機構內(nèi)部的重要文件、數(shù)據(jù)是通過廣域網(wǎng)進行傳輸，因此網(wǎng)絡的安全問題最為重要。它同時使用“對稱”和“非對稱”加密方法，在客戶與電子商務的服務器進行溝通的過程中，客戶會產(chǎn)生一個 Session Key，然后客戶用服務器端的公鑰將 Session Key 進行加密，再傳給服務器端，在雙方都知道 Session Key 后，傳輸?shù)臄?shù)據(jù)都是以 Session Key 進行加密與解密的，但服務器端發(fā)給用戶的公鑰必需先向有關發(fā)證機關中請，以得到公證。論文 6 實際標準。該算法是基于大數(shù)不可能被質(zhì)因數(shù)分解假設的公鑰體系。 DES 使用 64位密鑰對 64 位的數(shù)據(jù)塊進行加密，并對 64 位的數(shù)據(jù)塊進行 16 輪編碼。如果入侵者偶然地知道了用戶的密鑰，那么用戶曾經(jīng)和其他用戶交換的每一條消息都不再是保密的。論文 4 非對稱式加密就是加密和解密所使用的不是同一個密鑰，通常有兩個密鑰，稱為“公鑰”和“私鑰’夕，它們兩個必需配對使用，否則不能打開加密文件。我們當前所應用的密碼體制，都是屬于近代非經(jīng)典的密碼體制。這些問題給計算機從業(yè)人員揭示信息安 全問題的嚴重性。然后通過 C++程序進行實現(xiàn)。但在實際加密解密過程中， n可能是幾個數(shù)的乘積，如 RSA 算法中， n 是兩個大素數(shù)的乘積。 C E Shannon 建議使用至少 100 位長度的大素數(shù)，從而得到長度為 200位以上的大整數(shù)模數(shù) n。 國內(nèi)外現(xiàn)狀 RSA 被廣泛應用于各種安全或認證領域，如 web 服務器和瀏覽器信息安全、 Email的安全和認證、對遠程登錄的安全保證和各種電子信 用卡系統(tǒng)的核心。因此，如何保證計算機系統(tǒng)的安 全，是當前一個需要立即解決的十分嚴峻的問題。 關鍵詞 :RSA 算法，數(shù)據(jù)通信，加密 , 解密 。論文 1 桂林理工大學 GUILIN UNIVERSITY OF TECHNOLOGY 本科畢業(yè)設計 (論文 ) 題目： 數(shù)據(jù)通信中的 RSA 加密算法的設計與實現(xiàn) 桂林理工大學本科畢業(yè)設計 RSA 加密算法以它難以破 譯的優(yōu)點，被廣泛的使用在電子商務和 VPN 中。 桂林理工大學本科畢業(yè)設計加密技術是通過計算機網(wǎng)絡中的加密機構，把網(wǎng)絡中的各種原始數(shù)字信息 (明文 )按照某種特定的加密算法變換成與 明文完全不同的數(shù)字信息，即轉換成密文。如果模數(shù) n 被分解，則 RSA 體制立刻被攻破。高效的大數(shù)模冪乘算法可以有效提高系統(tǒng)速度。這些算法都是從某一方面入手，在一定程度上加快了運算速度。網(wǎng)上傳輸?shù)泥]件可能被截取，信息的內(nèi)容可能被篡改 。人們很早以前將密碼系統(tǒng)分為代替和換位密碼兩種。 對稱式加密就是加密和解密使用同一個密鑰，通常稱之為 Session Key”這種加密技術曾經(jīng)被廣泛采用，其原理如圖 21 所示 。 發(fā)送者 加 密 相同的密 鑰 加密的信息 接受者 解 密 明文 明 文 21 對稱密碼算法示意圖 解密密鑰DB（保密） EB≠ DB ≠DB 22 非對稱性密碼算法示意圖 發(fā)送者 加 密 加密密鑰 EB（公開） 加密的信息 接受者 解 密 明文 明 文 加密密鑰EB 桂林理工大學本科畢業(yè)設計 Kerberos 提供了一種解決這個較好方案，它是由 MIT 發(fā)明的，使保密密鑰的管理和分發(fā)變得十分容易，但這種方法本身還存在一定的缺點。目前，新的加密標準 AES 正在征集、評估和制定中。它的出現(xiàn)適應了電子化和信息化的要求，是一種加 /解密標準，適合于硬件實現(xiàn)，因此它的算法被制成專門的芯片，應用于加密機中。 RSA 的出現(xiàn)，提高網(wǎng)上交易的安全性，從而使電子商務走向實用成為可能。一個機構在多個城市、國家設有分支機構。 本章小結 本章對數(shù)據(jù)加密技術作了簡要的介紹，其中包括數(shù)據(jù)加密技術的起源、發(fā)展，桂林理工大學本科畢業(yè)設計 加密將防止數(shù)據(jù)被查看或修改，并在原本不安全的信道上提供安全的通信信道，它達到以下目的： 保密性：防 止用戶的標識或數(shù)據(jù)被讀取。 (5)加密變換 :對明文 Znc? ,明文為 (Zn 為明文空間 ) nmc e mod? (6)解密變換 :對密文 Znc? ,明文為 ncm d mod? 可以證明，解密變換是加密變換的逆變換。 RSA 公鑰密碼體制安全性分析 RSA 體制中，加密密鑰 e 與大整數(shù) n 是公開的 ，而解密密鑰 d 與大素數(shù) p 和 q是保密的。(p1)和 (q1)有大素數(shù)因子 。 桂林理工大學本科畢業(yè)設計 IS09796 標準把 RSA 列為一種兼容的加密算法，使得 RSA 的應用目前非常廣泛。即RSA 的重大缺陷是無法從理論上把握它的保密性能如何，而且密碼學界多數(shù)人士傾向于因子分解不是 NPC 問題， RSA 算法是第一個能同時用于加密和數(shù)字簽名的算法，也易于理解和操作。但是，大素數(shù)的因子分解是一個復雜的問題，到現(xiàn)在還沒有找到一個快速有效的算法來對大整數(shù)進行因子分解。 首先，存在無窮多個素數(shù)。 其次，我們可以根據(jù)素數(shù)定理，發(fā)現(xiàn)素數(shù)的分布情況。此類方法主要有兩類，即基于 Lucas定理和基于 Pocklington 定理的確定性素數(shù)產(chǎn)生方法。 Miller Rabin素性測試法 Miller Rabin 素性測試法是在實際中應用非常廣的一種素性測試方案，可以用來判定某隨機數(shù)是否為素數(shù)。 (3)p+1 含有一個大的素數(shù)因子 s。 (2)素數(shù)的確證 基于 Lucas 定理，確 定 s是否為素數(shù)，算法基本思想如 下 1)分解 n1，使 q， ????rj jqn 11為不同素數(shù) 。 (3)生 成強偽素數(shù) 首先，根據(jù) s求出 r，使 s)(sr mod1? ，令 r 形 樣利用 21s,s 找到并確證 r的素性。 （ 6） 加密變換和解密變換。 (4)如果 r≠0 ，則 21 nn ? ， rn2? ，轉第 (2)步。設 n和 u 都是正整數(shù)， uvu ?? 模 n的逆 就是滿足 n)(uv mod1? 的整數(shù) v, uv??0 。 (3)如果 r≠0 ， 則 2122221 qbb,bbr ,t,nnn ????? ； 桂林理工大學本科畢業(yè)設計 (1)a←x,b←r,c←1。 RSA 算法分析 RSA 公鑰密碼體制是 目前常用的一種密碼體制，無論從數(shù)論的 角度，還是從實踐的角度，都己經(jīng)證明了 RSA 的正確性。 使用 RSA 公鑰密碼體制，要求用戶選擇兩個素數(shù) p和 q，其中 p 和 q是保密的，并要求 p與 q 不相 等，對 p和 q的乘積 qpn? 可以公開。 這是因為： x和 r的 gcd 可能等于 P或者 q，而其值可以用歐幾里 德算法計算出來。論文 20 廣泛的應用于實際項目之中。 本章主要討論了 RSA 內(nèi)部各步驟的算法實現(xiàn) 。注重d的選取是很輕易的，例如所有大于 p 和 q 的質(zhì)數(shù)都可用 .； （ 3）確定解密密鑰 n，由 ))) *( q( ( pdn 11m od1?? ，根據(jù) d， p和 q可以輕易地計算出 n，即為逆元 ； （ 4）公開整數(shù) r和 d，但是不公開 n； （ 5） 規(guī)定明文動態(tài)分布空間 L，輸入明文，通過計算成為密文 ； （ 6）將密文 C 解密為明文； 具體程 序見附錄。密碼學的基本目的是使在不安全信道中通信的兩方以一種使他們的對手不能明白和理解的通信內(nèi)容的方式進行通信。從論文選題、資料收集、數(shù)據(jù)整理到論文的撰寫，每個環(huán)節(jié) ....老師都給予了我無微不至的關懷和毫無保留的指導，提出了許多寶貴的意見和建議。 此致 致謝 。論文 25 參考文獻 [1]盧開澄，郭保安，戴一奇等計算機系統(tǒng)安全 .重慶 :重慶出版社， 1999 [2]李海泉，李鍵 .計算機系統(tǒng)安全技術 .北京 :人民郵電出版社， 20xx [3]黃元飛，陳麟，唐三平 .信息安全與加密解密核心技術 .上海 :浦東電 子出版社， 20xx [4]李紅軍，繆旭東 .數(shù)據(jù) 加密在網(wǎng)絡安全中的應用 .微型機與應用， 20