【文章內(nèi)容簡(jiǎn)介】 通過廣域網(wǎng)進(jìn)行傳輸，因此網(wǎng)絡(luò)的安全問題最為重要。具有加密 /解密功能的路由器等設(shè)備的出現(xiàn)，使通過廣域網(wǎng)組成局域網(wǎng)成為可能，即所謂的的虛擬專用網(wǎng) (Virtual Private Network, VPN)。當(dāng)數(shù)據(jù)離開發(fā)送者所在的局域網(wǎng)時(shí)，該數(shù)據(jù)首先被用戶湍連接到互聯(lián)網(wǎng)上 的路由器進(jìn)行硬件加密，數(shù)據(jù)在互聯(lián)網(wǎng)上是以加密的形式傳送的，當(dāng)達(dá)到目的 LAN 的路由器時(shí)，該路由器就會(huì)對(duì)數(shù)據(jù)進(jìn)行解密，這樣目的 LAN 中的用戶就可以看到真正的信息了。 而 加密解密過程對(duì) 于 普通的非網(wǎng)絡(luò)管理用戶來(lái)說(shuō)，是透明的，既普通用戶無(wú)需考慮 VPN及加密解密的相關(guān)問題。因此，對(duì)普通用戶來(lái)說(shuō)， VPN在使用過程中和一般 LAN 沒有任何區(qū)別。 本章小結(jié) 本章對(duì)數(shù)據(jù)加密技術(shù)作了簡(jiǎn)要的介紹，其中包括數(shù)據(jù)加密技術(shù)的起源、發(fā)展，桂林理工大學(xué)本科畢業(yè)設(shè)計(jì)論文 7 數(shù)據(jù)加密技術(shù)的概念，密鑰管理等密碼技術(shù)各方面的內(nèi)容。此外還對(duì)數(shù)字簽名技術(shù)作了介紹。數(shù)字簽名技術(shù)實(shí) 際上是數(shù)據(jù)加密技術(shù)在應(yīng)用上的延伸，是目前網(wǎng)上交易活動(dòng)中，身份驗(yàn)證技術(shù)的重要組成部分。 而 基于 公開密鑰機(jī)制的數(shù)字簽名技術(shù)在應(yīng)用中，占有統(tǒng)治地位，尤其是 基于 RSA 公鑰的數(shù)字簽名體制在應(yīng)用中更為廣泛。在接下來(lái)的一章，就將詳細(xì)介紹 基于 RSA的數(shù)字簽名體制。 桂林理工大學(xué)本科畢業(yè)設(shè)計(jì)論文 8 第 3 章 數(shù) 據(jù) 加密 中的 RSA算法 目前企業(yè)面臨的計(jì)算環(huán)境和過去有很大的變化，許多數(shù)據(jù)資源能夠依靠網(wǎng)絡(luò)來(lái)遠(yuǎn)程存取，而且越來(lái)越多的通訊依賴于公共網(wǎng)絡(luò)公共網(wǎng)絡(luò)（如 Inter），而這些環(huán)境并 不保證實(shí)體間的安全通信，數(shù)據(jù)在傳輸過程可能被其它人讀取或篡改。 加密將防止數(shù)據(jù)被查看或修改，并在原本不安全的信道上提供安全的通信信道，它達(dá)到以下目的： 保密性：防止用戶的標(biāo)識(shí)或數(shù)據(jù)被讀取。 數(shù)據(jù)完整性：防止數(shù)據(jù)被更改。 身份驗(yàn)證：確保數(shù)據(jù)發(fā)自特定的一方。 RSA公鑰密碼體制概述 RSA 公鑰密碼體制 于 1978 年，由美國(guó)麻省理工學(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ù)字簽名和身份認(rèn)證。 RSA 公鑰密碼體制過程描述如下 : (1)選取兩個(gè)大素?cái)?shù) p 和 q . (2)計(jì)算 pqn? （ 公開 )， 1)()( ????? qppqn 歐拉函數(shù) )。 (3)隨機(jī)選取正整數(shù) e, (n)el ??? ，滿足 1(gcd ?n))(e,Φ , e 是公開的加密密鑰。 (4)計(jì)算 d，滿足 Φ(n))(de mod1? . d是保密的解密密鑰。 (5)加密變換 :對(duì)明文 Znc? ,明文為 (Zn 為明文空間 ) nmc e mod? (6)解 密變換 :對(duì)密文 Znc? ,明文為 ncm d mod? 可以證明，解密變換是加密變換的逆變換。 例 : (1)生成密鑰 : 選擇兩個(gè)互質(zhì)的質(zhì)數(shù) 25323112311 ???? *, n, qp 。 22021 ?)) (q(p 取 3e? 。 由 1(mod220) de ?，得 d=147。 所以，保密的解密密鑰為 d=147，公開的加密密鑰公鑰為 e=3,n=253。明文空間為桂林理工大學(xué)本科畢業(yè)設(shè)計(jì)論文 9 }, , , {Zn 252251210 ??? (2)加密原文 : 假設(shè)原文 m的數(shù)字為 16_5，用公鑰加密原文。 110253m o d1 6 5 3 ?? C (3)解 碼密文 : 165253m o d110 147 ?? m A=C，由此可以看出 RSA 算法的一般過程。 RSA公鑰密碼體制安全性分析 RSA 體制中，加密密鑰 e 與大整數(shù) n 是公開的， 而 解密密鑰 d 與大素?cái)?shù) p 和 q是保密的。雖然在 RSA 的加密與解密密鑰建立后， p和 q不再需要，但 p 和 q 也絕不能泄露。若 n 被分解，則也就不保密， e 公開， d 就可以計(jì)算出來(lái)， RSA 便被破譯。己知 n，求得 )(n? ，則 P和 q可以求得。因?yàn)楦鶕?jù)歐拉定理， 1)()( ????? qppqn ，又有 pqqpqp 4)()( 22 ???? 據(jù)此列出方程 : ??? ???? ????? pqqpqp qppqn 4)()( 1)()(22 由以上方程組，可以求得 p 和 q。因?yàn)?p 和 q 都是大素?cái)?shù)，根據(jù)現(xiàn)在已知的結(jié)果，因子分解 n是最好的算法，此時(shí)復(fù)雜性為 : )ln(ln)ln( nne 若 n為 200 位 于 進(jìn)制數(shù)，則用每秒 107次運(yùn)算的高速計(jì)算機(jī)，也要 108年才能得到計(jì)算結(jié)果?？梢姡?RSA 的素?cái)?shù)分解確實(shí)存在一定的難度 。 為安全起見，對(duì) p和 q要求 :p 和 q 的相差不大 。(p1)和 (q1)有大素?cái)?shù)因子 。 1)ql,gcd(p 很小，滿足這樣條件的素?cái)?shù)稱做安全素?cái)?shù)。 RSA 的出現(xiàn)使得大整數(shù)分解因式這一古老的問題再次被重視，近些年來(lái)出現(xiàn)的不少比較高級(jí)的因數(shù)分解方法使“安全素?cái)?shù)”的概念也在不停的演化。所以，選擇傳統(tǒng)上認(rèn)為是“安全素?cái)?shù)”并不一定有效的增加安全性，比較保險(xiǎn)的方法就是選擇足夠大的素?cái)?shù)。因?yàn)閿?shù)越大，對(duì)其分解因式的難度也就越大 !對(duì) n 和密鑰長(zhǎng)度的選擇取決于用戶保密的需要。密鑰長(zhǎng)度越大，安全性也就越高，但 是相應(yīng)的計(jì)算速度也就越慢。由于 高速計(jì)算機(jī)的出現(xiàn)，以前認(rèn)為己經(jīng)很具安全性的 512位密鑰長(zhǎng)度己經(jīng)不再滿足人們的需要。 1997 年， RSA組織公布當(dāng)時(shí)密鑰長(zhǎng)度的標(biāo)準(zhǔn) :個(gè)人使用 768 位密鑰，公司使用 1024 位密鑰，而一些非常重要的機(jī)構(gòu)使用 2048 位密鑰。 桂林理工大學(xué)本科畢業(yè)設(shè)計(jì)論文 10 RSA 算法的缺點(diǎn) RSA 的缺點(diǎn)主要有： A)產(chǎn)生密鑰很麻煩，受到素?cái)?shù)產(chǎn)生技術(shù)的限制，因而難以做到一次一密。 B)分組長(zhǎng)度太大，為保證安全性， n 至少也要 600 bits 以上，使運(yùn)算代價(jià)很高，尤其是速度較慢，較對(duì)稱密碼算法慢幾個(gè)數(shù)量級(jí)；且隨著大數(shù)分解技 術(shù)的發(fā)展，這個(gè)長(zhǎng)度還在增加，不利于數(shù)據(jù)格式的標(biāo)準(zhǔn)化。 本章小結(jié) RSA 算法在理論上的重大缺陷就是并不能證明分解因數(shù)絕對(duì)是困難的。 RSA 方法既可用 于 保密、也能用 于 簽名和認(rèn)證，許多流行的操作系統(tǒng)如微軟、 Apple, Sun 和Novell 都在其產(chǎn)品上融入了 RSA。同時(shí)， RSA 也被廣泛應(yīng)用 于 各種安全或認(rèn)證領(lǐng)域，如 web服務(wù)器和瀏覽器信息安全、 Email 的安全和認(rèn)證、對(duì)遠(yuǎn)程登錄的安全保證和各種電子信用卡系統(tǒng)的核心。硬件上，如安全電話、以太 網(wǎng)卡和 I 智能卡也多采用 RSA技術(shù)。而且?guī)缀跛?Inter 安全協(xié)議如 SMME, SSL 不 II SWAN 都引入了 RSA 加密方法。 IS09796 標(biāo)準(zhǔn)把 RSA 列為一種兼容的加密算法，使得 RSA的應(yīng)用目前非常廣泛。任何一種事物有出現(xiàn)、繁榮，也不可避免的會(huì)走向滅亡。在沒有找到快速進(jìn)行大整數(shù)分解因式方法的時(shí)候， RSA 顯示了不可比擬的優(yōu)點(diǎn)。而當(dāng)分解因式不再是難題的時(shí)候，RSA 算法也就將失去存在的價(jià)值。 桂林理工大學(xué)本科畢業(yè)設(shè)計(jì)論文 11 第 4 章 RSA數(shù) 據(jù)加密中的 實(shí)現(xiàn) RSA 算法 ,它是第一個(gè)既能用于數(shù)據(jù)加密也能用于數(shù)字簽名的算法。它易于理解和操作，也很流行。算法的名字就是發(fā)明者的名字： Ron Rivest, AdiShamir 和Leonard Adleman, 但 RSA 的安全性一直未能得到理論上的證明， RSA 的安全性依賴于大數(shù)的因子分解，但并沒有從理論上證明破譯 RSA 的難度與大數(shù)分解難度等價(jià)。即RSA 的重大缺陷是無(wú)法從理論上把握它的保密性能如何，而且密碼學(xué)界多數(shù)人士?jī)A向于因子分解不是 NPC問題， RSA 算法是第一個(gè)能同時(shí)用于加密和數(shù)字簽名的算法，也易于理解和操作。 RSA 是被研究得最廣泛的公鑰算法，從提出到現(xiàn)在已近二十年，經(jīng)歷了各種攻擊的考驗(yàn)，逐漸為人們接受，普遍認(rèn)為是目前最優(yōu)秀的公鑰方案之一。 RSA 算法實(shí)現(xiàn)數(shù)據(jù)加密的主要步驟分為： 獲取密鑰，這里是產(chǎn)生密鑰，實(shí)際應(yīng)用中可以從各種存儲(chǔ)介質(zhì)上讀取密鑰 。 加密 。 解密 。 隨機(jī)大素?cái)?shù)的產(chǎn)生 公鑰密碼學(xué)需要大素?cái)?shù)，因此，大素?cái)?shù)的快速有效隨機(jī)生成方法是公鑰密碼學(xué)中的一個(gè)重要問題，具有非常顯著的實(shí)用價(jià)值。顯然，通過對(duì)一個(gè)隨機(jī)數(shù)進(jìn)行因子分解，我們可以判斷這個(gè)隨機(jī)數(shù)是否為素?cái)?shù)。如果這個(gè)隨機(jī)數(shù)能被因子分解，則它不是素?cái)?shù)，否則它一定是素?cái)?shù)。但是，大素?cái)?shù)的因子分解是一個(gè)復(fù)雜的問題，到現(xiàn)在還沒有找到一個(gè)快速有效的算法來(lái)對(duì)大整數(shù)進(jìn)行因子分解。因此，不 能試圖通過對(duì)隨機(jī)數(shù)進(jìn)行因子分解來(lái)生成大素?cái)?shù)。正確的生成大素?cái)?shù)的方法是對(duì)生成的隨機(jī)數(shù)先測(cè)試它是否為 素?cái)?shù)，而不是對(duì)它進(jìn)行因子分解。這種素性測(cè)試比因子分解要容易得多，己經(jīng)有許多素性測(cè)試方法能夠確定一個(gè)隨機(jī)數(shù)是否為素?cái)?shù)。如果合數(shù)通過一個(gè)素性測(cè)試的概率足夠小，則這個(gè)素性測(cè)試就是很可靠的。實(shí)際上，對(duì) 于 許多素性測(cè)試方法，合數(shù)通過測(cè)試的概率可以受到人為的控制，即是可以把合數(shù)通過測(cè)試的概率設(shè)定的足夠小。 素?cái)?shù)的分布 要討論素?cái)?shù)的生成問題，首先要討論素?cái)?shù)的分布。素?cái)?shù)的分布是極不均勻的，素?cái)?shù)越大，分布也就越稀疏 。 首先，存在無(wú)窮多個(gè)素?cái)?shù)。對(duì)此，我們可以證明。假設(shè)正整數(shù)中只有 k個(gè)素?cái)?shù)，設(shè)為 k21 p p, p ? 。令 1pppn k21 ?? ? ,則 n1。如果 n是素?cái)?shù)，則顯然 n與 k21 p p, p ?都不相同，這與只有 k 個(gè)素?cái)?shù)的假設(shè)相矛后。如果 n不是素?cái)?shù)，則 n 一定有一個(gè)素?cái)?shù) 因子 ippp ?? , k 2, 1,i ?? ，否則由 于 k21 ppp|p ? 以及 n|p ,所以 1|p ,這與 p 是素?cái)?shù)相矛 盾 。故 p與 k21 p p, p ? 都不相同，這與只有 k 個(gè)素?cái)?shù)的假設(shè)想矛 盾 。因此素?cái)?shù)有無(wú)窮多個(gè)。 其次，我們可以根據(jù)素?cái)?shù)定理，發(fā)現(xiàn)素?cái)?shù)的分布情況。素?cái)?shù)定理的描述為 :設(shè) 0x? , 桂林理工大學(xué)本科畢業(yè)設(shè)計(jì)論文 12 (x)? 為不大 于 x的整數(shù)的個(gè)數(shù)，則 1)ln()(lim ??? xxxx? 根據(jù)素?cái)?shù)定理，可以估計(jì)出長(zhǎng)度為 t位的素?cái)?shù)大約有2ln)1( )2(22ln22ln2111tt tttttt? ?????? 個(gè)。 例如，一個(gè)長(zhǎng)度為 256 位的隨機(jī)數(shù)的素?cái)?shù)的概率為 2ln256255 254 ??? 而一個(gè)長(zhǎng)度為 64 位的隨機(jī)數(shù)的素?cái)?shù)的概率為 2ln6463 64 ??? 由此可見，位數(shù)越多，素?cái)?shù)的分布越為稀疏。 大素?cái)?shù)生成的方法 產(chǎn)生素?cái)?shù)的一般方法可以分為兩類，即確定性素?cái)?shù)產(chǎn)生方法和概率性素?cái)?shù)產(chǎn)生方法。 （ 1） 確定性素?cái)?shù)產(chǎn)生方法 確定性素?cái)?shù)產(chǎn)生方法產(chǎn)生的數(shù)必然是素?cái)?shù)。然而其產(chǎn)生的素?cái)?shù)卻帶有一定的限制。假若算法設(shè)計(jì)不佳，便容易構(gòu)造出帶有規(guī)律性的 素?cái)?shù)，使密碼分析者能夠分析出素?cái)?shù)的變化，進(jìn)而可以猜到該系統(tǒng)中使用的素?cái)?shù)。此類方法主要有兩類，即基于 Lucas定理和基于 Pocklington 定理的確定性素?cái)?shù)產(chǎn)生方法。這里簡(jiǎn)單介紹基于 Lucas 定理的確定性素?cái)?shù)產(chǎn)生方法。此方法需要求得素?cái)?shù) n1 的全部素因子。 Lucas 定理：設(shè)Nn? ，存在一個(gè)正整數(shù) naa,1 ?? 且 n) 1(moda 1n ? ，且對(duì)于 n1的每一個(gè)素 q，均滿足 ln moda /q1)(n ?a，則 n為素?cái)?shù)。 (2)概率性素?cái)?shù)產(chǎn)生方法 概率性素?cái)?shù)產(chǎn)生方法產(chǎn)生的數(shù)僅僅是偽素?cái)?shù)。其缺點(diǎn)在于，盡管其產(chǎn)生合數(shù)的可能性很小，但是這種可能性仍然存在 :其優(yōu)點(diǎn)是產(chǎn)生的偽素?cái)?shù)沒有規(guī)律性，而且產(chǎn)生的速度也比較快。 此類方法是生成大素?cái)?shù)的主要方法，其中著名有 :Miller Rabin 與 Solovay Strassen 算法等。本文討論 Mill Rabin 算法。 Miller Rabin 素性測(cè)試法 Miller Rabin 素性測(cè)試法是在實(shí)際中應(yīng)用非常廣的一種素性測(cè)試方案，可以用來(lái)判定某隨機(jī)數(shù)是否為素?cái)?shù)。其定義如