【正文】 因此，在安全性要求不是特別高的系統(tǒng)中，可以認(rèn)為 RSA 是 安全的。論文 19 (2)因 pq( p q )qpqpq)(p 42 2222 ?????? ，得到rqppqqpqp 4)(4)( 22 ??????? (3)由 2( p q) ) /q)((pp ??? 求出 p。 (2)由 )(q)(p[r] 11 ?? ，求出由 Φ(r) (3)由 Φ (r))(ed m od1?? ，求出 d。 例如 :計(jì)算 322mod 12 桂林理工大學(xué)本科畢業(yè)設(shè)計(jì) (2)如果 b=0，則輸出結(jié)果 c，結(jié)束 。因?yàn)?qn)(u, n) |(bugc d ，所以 1mod ? nbu ， 即對任意 Znb? ，都有 1mod ? nbu ，因此，如果存在 ZnV? ， 使得 1mod ? nuv ，則必然有 1gcd ?(u,n) 。1,0,0,1, 221121 ?????? babaunnn (2) 21, qnnrunq ????????? (3)如果 r=0，則 222g c d b,ba,an( n, u) ??? 。這個(gè)算法就是公元前 300 年，歐 幾 里德在其著作《幾何原本》 )中所闡述的求 兩個(gè)數(shù)的最大公約數(shù)的過程 (即輾轉(zhuǎn)相桂林理工大學(xué)本科畢業(yè)設(shè)計(jì) 一個(gè)直接方法是分解 n，求出因子 p 與 q，進(jìn)而求得解 前的分解能力大約為 130 位十進(jìn)制數(shù)，但 512 比特 (154 位于進(jìn)制數(shù) )模長的 RSA 體制的安全性已經(jīng)受到一定的威脅 。 4)若 a≥n ，則 n可能非素?cái)?shù)，轉(zhuǎn) 3)。 (或pjr)p(2m o d112132m o d11222m o d1121???????? 綜上，若素?cái)?shù) p 滿足 : 1 (m o d s )s12rp ??? r且 ，則稱 p為強(qiáng)素 數(shù)。 定理二：如果 n2 是一個(gè)奇合數(shù)，則至多有 nn1? 個(gè) b， 0bn，使得 n通過以 b為基的 MillerRabin 測試。 (2)概率性素?cái)?shù)產(chǎn)生方法 概率性素?cái)?shù)產(chǎn)生方法產(chǎn)生的數(shù)僅僅是偽素?cái)?shù)。 產(chǎn)生素?cái)?shù)的一般方法可以分為兩類，即確定性素?cái)?shù)產(chǎn)生方法和概率性素?cái)?shù)產(chǎn)生方法。如果 n是素?cái)?shù)，則顯然 n與 k21 p p, p ?都不相同，這與只有 k個(gè)素?cái)?shù)的假設(shè)相矛后。如果合數(shù)通過一個(gè)素性測試的概率足夠小，則這個(gè)素性測試就是很可靠的。 解密 。 桂林理工大學(xué)本科畢業(yè)設(shè)計(jì) RSA 方法既可用于保密、也 能用于簽名和認(rèn)證，許多流行的操作系統(tǒng)如微軟、 Apple, Sun 和Novell 都在其產(chǎn)品上融入了 RSA。因?yàn)閿?shù)越大，對其分解因式的難度也就越大 !對 n 和密鑰長度的選擇取決于用戶保密的需要。因?yàn)楦鶕?jù)歐拉定理， 1)()( ????? qppqn ，又有 pqqpqp 4)()( 22 ???? 據(jù)此列出方程 : ??? ???? ????? pqqpqp qppqn 4)()( 1)()(22 由以上方程組，可以求得 p 和 q。 所以，保密的解密密鑰為 d=147，公開的加密密鑰公鑰為 e=3,n=253。除了用于加密之外，它還能用于數(shù)字簽 名和身份認(rèn)證。而基于公開密鑰機(jī)制的數(shù)字簽名技術(shù)在應(yīng)用中，占有統(tǒng)治地位，尤其是基于 RSA 公鑰的 數(shù)字簽名體制在應(yīng)用中更為廣泛。具有加密 /解密功能的路由器等設(shè)備的出現(xiàn)，使通過廣域網(wǎng)組成局域網(wǎng)成為可能，即所謂的的虛擬專用網(wǎng) (Virtual Private Network, VPN)。 SSL 協(xié)議是一個(gè)比較優(yōu)秀而久經(jīng)考驗(yàn)的網(wǎng)絡(luò)安全協(xié)議，一般情況下能夠抵抗竊聽、篡改、會話劫持、中間人等多種攻擊手段。 在實(shí)際應(yīng)用中，通常是 DES 和 RSA 加密算法同時(shí)使用。簡單地說就是找兩個(gè)很大的質(zhì)數(shù)。 64 位密鑰中，有 8位奇偶校驗(yàn)位，實(shí)際密鑰長度只有 56位。另外使用一個(gè)特定密鑰加密的信息越多，提供給竊聽者的材料也就越多，從某種意義上來講也就越不安全了。這里的“公鑰”是指可以對外公布的，“私鑰”則不能，只能由持有人一個(gè)人知道。70 年代后期出現(xiàn)的數(shù)據(jù)加密標(biāo)準(zhǔn) DES(DataFncryptionStandard)和公開密鑰密碼 (非對稱密碼 )體制 (Publickeycrypto 一 system)是近代密碼學(xué)發(fā)展史上的兩個(gè)重要里程碑。 因此如何保證信息的機(jī)密性、完整性、不可抵賴性、有效性，成為網(wǎng)絡(luò)安全關(guān)注的核心問題。 桂林理工大學(xué)本科畢業(yè)設(shè)計(jì)這時(shí)可通過中國剩余定理進(jìn)行變換，降低指數(shù)的數(shù)量級 . 本課題的主要工作 本文選擇 RSA 數(shù)字加密體制為研究對象，討論了 RSA 實(shí)現(xiàn)過程中，每一步的具體實(shí)現(xiàn)算法。 RSA 算法的缺點(diǎn)是加密速度慢，模數(shù) n 的長度越大，加 /解密運(yùn)算所需要的時(shí)間就越長，算法實(shí)現(xiàn)的速度也就越慢。硬件上，如安全電話、以太網(wǎng)卡和智能卡也多采用 RSA 技術(shù)。 通常保障網(wǎng)絡(luò)信息安全的方法有兩大類 :一是以防火墻技術(shù)為代表的被動(dòng)防衛(wèi)型，二是建立在數(shù)據(jù)加密，用戶授權(quán)確認(rèn)機(jī)制上的開放型網(wǎng)絡(luò)安全保障技術(shù)。 Data munication of the RSA encryption algorithm in the Design 桂林理工大學(xué)本科畢業(yè)設(shè)計(jì)論文 II 摘 要 數(shù)據(jù)通信是依照一定的通信協(xié)議，利用數(shù)據(jù)傳輸技術(shù)在兩個(gè)終端之間傳遞數(shù)據(jù)信息的一種通信方式和通信業(yè)務(wù)。 所以數(shù)據(jù) 加 密成為十分重要的問題 ，它能保證數(shù)據(jù)的安全性和不可篡改性。論文 V 第 5 章 RSA 算法的實(shí)現(xiàn) .................................................21 選定組合算法的準(zhǔn)則 ...............................................21 模冪組合算法的實(shí)現(xiàn) ...............................................21 試驗(yàn)與運(yùn)行結(jié)果 ...................................................22 總結(jié) ...................................................................24 參考文獻(xiàn) ...............................................................25 致謝 ...................................................................26 附錄 ................................................... 錯(cuò)誤 !未定義書簽。按其不同的作用，數(shù)據(jù)加密技術(shù)主要分為數(shù)據(jù) 傳輸、數(shù)據(jù)存儲、數(shù)據(jù)完整性的鑒別以及密鑰管理技術(shù)四種。 RSA 模數(shù) n=pq 是 RSA 算法的安全性的核心。大數(shù)模冪乘運(yùn)算是 RSA算法的核心運(yùn)算，也是運(yùn)算速度提高的關(guān)鍵。但是，在進(jìn)行加密和解密運(yùn)算時(shí)的整數(shù)求冪運(yùn)算耗時(shí)很大，影響了運(yùn)算速度，因此，人們提出了多種實(shí)現(xiàn)算法，以加快運(yùn)算速度，例如本文提到的 SMM 算法和指數(shù) 2K進(jìn)制化法等。由于互聯(lián)網(wǎng)的開放性，我們面臨各種各樣的安全威脅。有記載的最早的密碼系統(tǒng)可能是希一臘歷史學(xué)家 Polybios 發(fā)明的 Polvbios 格板，它是一種替換密碼系統(tǒng)。保障了數(shù)據(jù)的完整性、機(jī)密性，解決了身份認(rèn)證問題和不可抵賴性問題 . 數(shù)據(jù)加密的方法 數(shù)據(jù)加密的方法通常分為兩大類 :對稱式加密體制 (常規(guī)密鑰密碼體制 )和非對稱式加密體制 (公開密鑰密碼體制 )。非對稱加密工作原理如圖22 所示。如果機(jī)構(gòu)的用戶更多，這種辦法就顯然過于平庸。對于 DES 的最后一次評估是在 1994 年，美國己決定 1998 開始 ，不在使用 DES。 DES 被公認(rèn)為世界上第一個(gè)實(shí)用的密碼算法標(biāo)準(zhǔn)。 (1)在電子商務(wù)方面的應(yīng)用 電子商務(wù) (Ebusiness)允許顧客和商家可以在網(wǎng)上進(jìn)行各種商務(wù)活動(dòng)，同時(shí)不必?fù)?dān)心相應(yīng)的商務(wù)信息被盜用，比如信用卡號碼、商品報(bào)價(jià)等。 (2)加密技術(shù)在 VPN 中的應(yīng)用 目前，跨地域國際化的機(jī)構(gòu)越來越多。因此，對普通用戶來說， VPN 在使用過程中和一般 LAN 沒有任何區(qū)別。論文 8 第 3 章 數(shù)據(jù)加密中的 RSA 算法 目前企業(yè)面臨的計(jì)算環(huán)境和過去有很大的變化，許多數(shù)據(jù)資源能夠依靠網(wǎng)絡(luò)來遠(yuǎn)程存取，而且越來越多的通訊依賴于公共網(wǎng)絡(luò)公共網(wǎng)絡(luò)（如 Inter），而這些環(huán)境并不保證實(shí)體間的安全通信，數(shù)據(jù)在傳輸過程可能被其它人讀取或篡改。 (4)計(jì)算 d，滿足 Φ(n))(de mod1? . d 是保密的解密密鑰。 1 1 02 5 3m o d1 6 5 3 ?? C (3)解碼密文 : 165253m od110 147 ?? m A=C，由此可以看出 RSA 算法的一般過程。 為安全起見，對 p 和 q要求 :p 和 q的相差不大 。 1997 年， RSA 組織公布當(dāng)時(shí)密鑰長度的標(biāo)準(zhǔn) :個(gè)人 使用 768 位密鑰，公司使用 1024 位密鑰，而一些非常重要的機(jī)構(gòu)使用 2048 位密鑰。而且?guī)缀跛?Inter 安全協(xié)議如 SMME, SSL 不 II SWAN 都引入了 RSA 加密方法。算法的名字就是發(fā)明者的名字： Ron Rivest, AdiShamir 和Leonard Adleman, 但 RSA 的安全性一直未能得到理論上的證明， RSA 的安全性依賴于大數(shù)的因子分解，但并沒有從理論上證明破譯 RSA 的難度與大數(shù)分解難度等價(jià)。如果這個(gè)隨機(jī)數(shù)能被因子分解，則它不 是素?cái)?shù)，否則它一定是素?cái)?shù)。素?cái)?shù)的分布是極不均勻的，素?cái)?shù)越大，分布也就越稀疏。因此素?cái)?shù)有無窮多個(gè)。假若算法設(shè)計(jì)不佳，便容易構(gòu)造出帶有規(guī)律性的素?cái)?shù)，使密碼分析者能夠分析出素?cái)?shù)的變化，進(jìn)而可以猜到該系統(tǒng)中使用的素?cái)?shù)。本文討論 Mill Rabin 算法。 (2)p1 含有一個(gè)大的素?cái)?shù)因子 r。由于 Miller Rabin 檢測不能百分之百確定一致為素?cái)?shù)，所以要 進(jìn)一步確證。 7)退出。 密鑰的生成及加密和解密 為了建立密碼系統(tǒng)，用戶 A 需要完成以下各步驟 （ 1） A產(chǎn)生兩個(gè)大素?cái)?shù) p和 q； （ 2） A計(jì)算 n=pq 和 )1)(1()( ??? qpn? ； （ 3） A選擇一個(gè)隨機(jī)數(shù) ))(0( naa ??? ，使得 1))(,gc d( ?na ? ； （ 4） A計(jì)算 )(mod1 nab ??? ； （ 5） A將 n 和 a 作 為他的公鑰直接公開 。 (2)2121 , qnnrnnq ????????? (3)如 r=0，則 2n u)gcd(n, ? 。 n求逆 元 運(yùn)算 這里來討論模 n 求逆 元 的算法。 (2)21, qnnrunq ?????????。 舉例說明上述算法，求 13 模 35 的逆元 : 35=213+9,9=135 213, 13=19+4,4=113 19= 135+313, 9=24+1,1=19 24=335 813, 所以 13 模 35的逆元為 (8)mod 35=270 n的大數(shù)冪乘運(yùn)算 RSA 公鑰密碼體制中，加密和解密時(shí)都要進(jìn)行 xrmod n 的 運(yùn)算，下面給出一個(gè)計(jì)算 xrmod n 的快速算法。當(dāng)然，在實(shí)際項(xiàng)目中，根據(jù)要求，某些步驟還尚需要做相應(yīng)的調(diào)整。 (3) )q(p 11gcd ? 都應(yīng)當(dāng)小。 從數(shù)學(xué)上講，求一個(gè)對 n不互素的數(shù) x 就等價(jià)于破譯了算法。 本章小結(jié) RSA 從 20世紀(jì) 80年代產(chǎn)生至今，始終以其成熟的工作體制 和良好的安全性而被桂林理工大學(xué)本科畢業(yè)設(shè)計(jì)將 RSA 和其他算法、體制結(jié)合應(yīng)用， 比如目前在各計(jì)算機(jī)科技期刊上經(jīng)常見到的關(guān)于門限 RSA 體制的 研究成果。 模冪組合算法的實(shí)現(xiàn) 本文前面介紹了一系列大數(shù)模冪運(yùn)算及其改進(jìn)算法，具體的實(shí)現(xiàn)方法步驟如下： （ 1）任 意選取兩個(gè)不同的大質(zhì)數(shù) p和 q，計(jì)算乘積 qpr ?? ； （ 2）任意選取一個(gè)大整數(shù) d， d與 ))*(q(p 11 互質(zhì)，整數(shù) d用做加密密鑰。因此，如何保證計(jì)算機(jī)系統(tǒng)的安全是當(dāng)前一個(gè)需要立即解決的十分嚴(yán)峻的問題。論文 26 致謝 本論文是在導(dǎo)師 ....老師的悉心指導(dǎo)下完成