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