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