【正文】 （ 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解密為明文； 具體程序 見附錄。 算法必須是有效的，即是高效的算法。 本章主要討論了 RSA內(nèi)部各步驟的算法實(shí)現(xiàn) 。 近年來，隨著電子商務(wù)、電子政務(wù)等網(wǎng)上行為的增加，對于加密技術(shù)的研究日趨活躍。論文 20 廣泛的應(yīng)用于實(shí)際項(xiàng)目之中。 以目前的常規(guī)個人計算機(jī)為 工具來進(jìn)行因子分解，其工作量是非線性增長的，分析見表 4l: N的位數(shù) 所需時間 50 小時 75 104 天 100 74年 200 109年 300 1015年 500 1025年 因此，在安全性要求不是特別高的系統(tǒng)中，可以認(rèn)為 RSA 是 安全的。 這是因?yàn)椋?x 和 r 的 gcd 可能等于 P 或者 q，而其值可以用歐幾里 德算法計算出來。論文 19 (2)因 pq( p q )qpqpq)(p 42 2222 ?????? ，得到rqppqqpqp 4)(4)( 22 ??????? (3)由 2(p q ))/q)((pp ??? 求出 p。 使用 RSA 公鑰密碼體制，要求用戶選擇兩個素數(shù) p和 q，其中 p 和 q 是保密的，并要求 p與 q不相等，對 p和 q的乘積 qpn? 可以公開。 (2)由 )(q)(p[r] 11 ?? ，求出由 Φ(r) (3)由 Φ( r))(ed m od1?? ，求出 d。 RSA算法分析 RSA 公鑰密碼體制是目前常用的一種密碼體制，無論從數(shù)論的 角度，還是從實(shí)踐的角度，都己經(jīng)證明了 RSA 的正確性。 例如 :計算 322mod 12 桂林理工大學(xué)本科畢業(yè)設(shè)計 (1)a←x,b←r,c←1。 (2)如果 b=0，則輸出結(jié)果 c，結(jié)束 。 (3)如果 r≠0 ， 則 2122221 qbb,bbr , t,nnn ????? ； 桂林理工大學(xué)本科畢業(yè)設(shè)計因?yàn)?qn)(u,n)|(bugcd ，所以 1mod ? nbu ， 即對任意 Znb? ，都有 1mod ? nbu ，因此，如果存在 ZnV? ， 使得 1mod ? nuv ，則必然有 1gcd ?(u,n) 。設(shè) n 和 u 都是正整數(shù)， uvu ?? 模 n 的逆就是滿足 n)(uv mod1? 的整數(shù) v, uv??0 。1,0,0,1, 221121 ?????? babaunnn (2) 21, qnnrunq ????????? (3)如果 r=0， 則 222g c d b,ba,an(n ,u ) ??? 。 (4)如果 r≠0 ，則 21 nn ? ， rn2? ，轉(zhuǎn)第 (2)步。這個算法就是公元前 300 年，歐 幾 里德在其著作《幾何原本》 )中所闡述的求 兩個數(shù)的最大公約數(shù)的過程 (即輾轉(zhuǎn)相桂林理工大學(xué)本科畢業(yè)設(shè)計 （ 6） 加密變換和解密變換。 一個直接方法是分解 n，求出因子 p與 q，進(jìn)而求得解 前的分解能力大約為 130 位十進(jìn)制數(shù)，但 512比特 (154 位 于 進(jìn)制數(shù) )模長的 RSA 體制的安全性已經(jīng)受到一定的威脅。 (3)生成強(qiáng)偽素數(shù) 首先，根據(jù) s求出 r，使 s)(sr mod1? ，令 r形 樣利用 21s,s 找到并確證 r的素性。 4)若 a≥n ，則 n 可能非素數(shù)，轉(zhuǎn) 3)。 (2)素數(shù)的確證 基于 Lucas定理，確 定 s是否為素數(shù)，算法基本思想如 下 1)分解 n1，使 q， ????rj jqn 11為不同素數(shù) 。 (或pjr)p(2m o d112132m o d11222m o d1121???????? 綜上，若素數(shù) p滿足 : 1 ( m o d s )s12rp ??? r且 ，則稱 p 為強(qiáng)素 數(shù)。 (3)p+1 含有一個大的素數(shù)因子 s。 定理二：如果 n2 是一個奇合數(shù)，則至多有nn1?個 b， 0bn，使得 n通過以 b為基的 MillerRabin 測試。 Miller Rabin 素性測試法 Miller Rabin 素性測試法是在實(shí)際中應(yīng)用非常廣的一種素性測試方案，可以用來判定某隨機(jī)數(shù)是否為素數(shù)。 (2)概率性素數(shù)產(chǎn)生方法 概率性素數(shù)產(chǎn)生方法產(chǎn)生的數(shù)僅僅是偽素數(shù)。此類方法主要有兩類，即基于 Lucas定理和基于 Pocklington 定理的確定性素數(shù)產(chǎn)生方法。 大素數(shù)生成的方法 產(chǎn)生素數(shù)的一般方法可以分為兩類，即確定性素數(shù)產(chǎn)生方法和概率性素數(shù)產(chǎn)生方法。 其次，我們可以根據(jù)素數(shù)定理，發(fā)現(xiàn)素數(shù)的分布情況。如果 n是素數(shù)，則顯然 n與 k21 p p, p ?都不相同，這與只有 k 個素數(shù)的假設(shè)相矛后。 首先，存在無窮多個素數(shù)。如果合數(shù)通過一個素性測試的概率足夠小，則這個素性測試就是很可靠的。但是，大素數(shù)的因子分解是一個復(fù)雜的問題，到現(xiàn)在還沒有找到一個快速有效的算法來對大整數(shù)進(jìn)行因子分解。 解密 。即RSA 的重大缺陷是無法從理論上把握它的保密性能如何，而且密碼學(xué)界多數(shù)人士傾向于因子分解不是 NPC問題， RSA 算法是第一個能同時用于加密和數(shù)字簽名的算法，也易于理解和操作。 桂林理工大學(xué)本科畢業(yè)設(shè)計 IS09796 標(biāo)準(zhǔn)把 RSA 列為一種兼容的加密算法，使得 RSA的應(yīng)用目前非常廣泛。 RSA 方法既可用 于 保密、也能用 于 簽名和認(rèn)證，許多流行的操作系統(tǒng)如微軟、 Apple, Sun 和Novell 都在其產(chǎn)品上融入了 RSA。 桂林理工大學(xué)本科畢業(yè)設(shè)計因?yàn)閿?shù)越大，對其分解因式的難度也就越大 !對 n 和密鑰長度的選擇取決于用戶保密的需要。(p1)和 (q1)有大素數(shù)因子 。因?yàn)楦鶕?jù)歐拉定理， 1)()( ????? qppqn ，又有 pqqpqp 4)()( 22 ???? 據(jù)此列出方程 : ??? ???? ????? pqqpqp qppqn 4)()( 1)()(22 由以上方程組，可以求得 p 和 q。 RSA公鑰密碼體制安全性分析 RSA 體制中，加密密鑰 e 與大整數(shù) n 是公開的， 而 解密密鑰 d 與大素數(shù) p 和 q是保密的。 所以，保密的解密密鑰為 d=147，公開的加密密鑰公鑰為 e=3,n=253。 (5)加密變換 :對明文 Znc? ,明文為 (Zn 為明文空間 ) nmc e mod? (6)解 密變換 :對密文 Znc? ,明文為 ncm d mod? 可以證明，解密變換是加密變換的逆變換。除了用 于 加密之外，它還能用 于 數(shù)字簽名和身份認(rèn)證。 加密將防止數(shù)據(jù)被查看或修改，并在原本不安全的信道上提供安全的通信信道，它達(dá)到以下目的： 保密性：防止用戶的標(biāo)識或數(shù)據(jù)被讀取。 而 基于 公開密鑰機(jī)制的數(shù)字簽名技術(shù)在應(yīng)用中，占有統(tǒng)治地位，尤其是 基于 RSA 公鑰的數(shù)字簽名體制在應(yīng)用中更為廣泛。 本章小結(jié) 本章對數(shù)據(jù)加密技術(shù)作了簡要的介紹，其中包括數(shù)據(jù)加密技術(shù)的起源、發(fā)展，桂林理工大學(xué)本科畢業(yè)設(shè)計具有加密 /解密功能的路由器等設(shè)備的出現(xiàn)，使通過廣域網(wǎng)組成局域網(wǎng)成為可能，即所謂的的虛擬專用網(wǎng) (Virtual Private Network, VPN)。一個機(jī)構(gòu)在多個城市、國家設(shè)有分支機(jī)構(gòu)。 SSL 協(xié)議是一個比較優(yōu)秀 而 久經(jīng)考驗(yàn)的網(wǎng)絡(luò)安全協(xié)議，一般情況下能夠抵抗竊聽、篡改、會話劫持、中間人等多種攻擊手段。 RSA 的出現(xiàn)，提高網(wǎng)上交易的安全性，從 而 使電子商務(wù)走向?qū)嵱贸蔀?可能。 在實(shí)際應(yīng)用中，通常是 DES 和 RSA 加密算法同 時使用。它的出現(xiàn)適應(yīng)了電子化和信息化的要求，是一種加 /解密標(biāo)準(zhǔn)，適合 于 硬件實(shí)現(xiàn)，因此它的算法被制成專門的芯片，應(yīng)用 于 加密機(jī)中。簡單地說就是找兩個很大的質(zhì)數(shù)。目前，新的加密標(biāo)準(zhǔn) AES 正在征集、評估和制定中。 64 位密鑰中，有 8位奇偶校驗(yàn)位，實(shí)際密鑰長度只有 56位。 Kerberos 提供了一種解決這個較好方案，它是由 MIT 發(fā)明的，使保密密鑰的管理和分發(fā)變得十分容易，但這種方法本身還存在一定的缺點(diǎn)。另外使用一個特定密 鑰加密的信息越多，提供給竊聽者的材料也就越多，從某種意義上來講也就越不安全了。 發(fā)送者 加 密 相同的密 鑰 加密的信息 接受者 解 密 明文 明 文 21 對稱密碼算法示意圖 解密密鑰DB（保密） EB≠ DB ≠DB 22 非對稱性密碼算法示意圖 發(fā)送者 加 密 加密密鑰 EB（ 公開 ） 加密的信息 接受者 解 密 明文 明 文 加密密鑰EB 桂林理工大學(xué)本科畢業(yè)設(shè)計這里的“公鑰”是指可以對外公布的，“私鑰”則不能，只能 由持有人一個人知道。 對稱式加密就是加密和解密使用同一個密鑰，通常稱之為 Session Key”這種加密技術(shù)曾經(jīng)被廣泛采用，其原理如圖 21所示。70 年代后期出現(xiàn)的數(shù)據(jù)加密標(biāo)準(zhǔn) DES(DataFncryptionStandard)和公開密鑰密碼 (非對稱密碼 )體制 (Publickeycrypto 一 system)是近代密碼學(xué)發(fā)展史上的兩個重要里程碑。人們很早以前將密碼系統(tǒng)分為代替和換位密碼兩種。 因此如何保證信息的機(jī)密性、完整性、不可抵賴性、有效性，成為網(wǎng)絡(luò)安全關(guān)注的核心問題。網(wǎng)上傳輸?shù)泥]件可能被截取，信息的內(nèi)容可能被篡改 。 桂林理工大學(xué)本科畢業(yè)設(shè)計這些算法都是從某一方面入手，在一定程度上加快了運(yùn)算速度。這時可通過中國剩余定理進(jìn)行變換，降低指數(shù)的數(shù)量級 . 本文選擇 RSA 數(shù)字 加密 體制為研究對象，討論了 RSA 實(shí)現(xiàn)過程中，每一步的具體 實(shí)現(xiàn)算法。高效的大數(shù)模冪乘算法可以有效提高系統(tǒng)速度。 RSA 算法的缺點(diǎn)是加密速 度慢 ，模數(shù) n的長度越大，加 /解密運(yùn)算所需要的時間就越長，算法實(shí)現(xiàn)的速度也就越慢。如果模數(shù) n被分解，則 RSA 體制立刻被攻破。硬件上，如安全電話、以太網(wǎng)卡和智能卡也多采用 RSA 技術(shù)。加密技術(shù)是通過計算機(jī)網(wǎng)絡(luò)中的加密機(jī)構(gòu)，把網(wǎng)絡(luò)中的各種原始數(shù)字信息 (明文 )按照某種特定的加密算法變換成與 明文完全不同的數(shù)字信息，即轉(zhuǎn)換成密文。 通常保障網(wǎng)絡(luò)信息安全的方法有兩大類 :一是以防火墻技術(shù)為代表的被動防衛(wèi)型，二是建立在數(shù)據(jù)加密，用戶授權(quán)確認(rèn)機(jī)制上的開放型網(wǎng)絡(luò)安全保障技術(shù)。 桂林理工大學(xué)本科畢業(yè)設(shè)計 桂林理工大學(xué)本科畢業(yè)設(shè)計 RSA 加密算法以它難以破譯的優(yōu)點(diǎn)，被廣泛的使用在電子商務(wù)和 VPN 中。論文 II 摘 要 數(shù)據(jù)通信是依照一定的 通信協(xié)議，利用數(shù)據(jù)傳輸技術(shù)在兩個終端之間傳遞數(shù)據(jù)信息的一種通信方式和通信業(yè)務(wù)。論文 1 桂林理工大學(xué) GUILIN UNIVERSITY OF TECHNOLOGY 本科畢業(yè)設(shè)計 (論文 ) 題目： 數(shù)據(jù)通信中的 RSA 加密算法的設(shè)計與實(shí)現(xiàn) 系 ( 院 )： 電子與計算機(jī)系 專業(yè) (方向 )： 電子信息工程 (信息處理 ) 班 級： 學(xué) 生： 指 導(dǎo) 教 師 ： 桂林理工大學(xué)本科畢業(yè)設(shè)計 所以數(shù)據(jù) 加 密成為十分重要的問題 ，它 能保證數(shù)據(jù)的安全性和不可篡改性 。 關(guān)鍵詞 :RSA 算法 ，數(shù) 據(jù)通信 ， 加密 , 解密 。論文 V RSA 時間復(fù)雜度分析 ......................................... 19 ........................................................ 19 第 5章 RSA 算法的實(shí)現(xiàn) ..............................