【正文】 經(jīng)歷了各種攻擊的考驗(yàn)，逐漸為人們接受，普遍認(rèn)為是目前最優(yōu)秀的公鑰方案之一。任何一種事物有出現(xiàn)、繁 榮，也不可避免的會(huì)走向滅亡。論文 10 RSA 算法的缺點(diǎn) RSA 的缺點(diǎn)主要有： A)產(chǎn)生密鑰很麻煩，受到素?cái)?shù)產(chǎn)生技術(shù)的限制，因而難以做到一次一密。 1)ql,gcd(p 很小，滿足這樣條件的素?cái)?shù)稱做安全 素?cái)?shù)。雖然在 RSA 的加密與解密密鑰建立后， p和 q不再需要，但 p和 q 也絕不能泄露。 例 : (1)生成密鑰 : 選擇兩個(gè)互質(zhì)的質(zhì)數(shù) 25 323112311 ???? *, n, qp 。 數(shù)據(jù)完整性：防止數(shù)據(jù)被更改。論文 7 數(shù)據(jù)加密技術(shù)的概念，密鑰管理等密碼技術(shù)各方面的內(nèi)容。每一個(gè)機(jī)構(gòu)都有自己的局域網(wǎng) LAN (Local AreaNetwork)。 NETSCAPE公司提供了一種基于 RSA的安全套接層協(xié)議 SSL(Secure Sockets Layer)即為數(shù)據(jù)加密技術(shù)在電子商務(wù)方面應(yīng)用的一個(gè) 典型案例。 DES 現(xiàn)在仍被廣泛應(yīng)用于金融和商業(yè)領(lǐng)域。盡管如此， DES 對(duì)于推動(dòng)密碼理論的發(fā)展和應(yīng)用起了重大作用。為能在互聯(lián)網(wǎng)上提供一個(gè)實(shí)用的解決方案， Kerberos 建立了一個(gè)安全的、可信任的密鑰分發(fā)中心 (Key Distribution Center,KDC)，每個(gè)用戶只要知道一個(gè)和 KDC進(jìn)行會(huì)話的密鑰就可以了，而不需要知道成百上千個(gè)不同的密鑰。論文 5 密鑰的管理 密鑰既然要求保密，這就涉及到密鑰的管理問(wèn)題，密鑰的管理涉及到以下幾個(gè)方面 : (1)密鑰使用的時(shí)效和次數(shù) 如果用戶使用同樣密鑰多次與其他用戶交換信息，那么密鑰也同其它任何密碼一樣存在著一定的安全性。如美國(guó)政府所采用的 DES 加密標(biāo)準(zhǔn)就是一種典 型的“ 對(duì)稱式” 加密法 ，它的 Session Key 長(zhǎng)度 為 56 位。 從密碼史的發(fā)展來(lái)看， 1949 年，信息論的創(chuàng)始人仙農(nóng) (C. )發(fā)表了一篇著名的文章，論證了一般經(jīng)典加密方法都是可以破解的。電子商務(wù)過(guò)程中，信用卡帳號(hào)和密碼可能暴露在第二者面前 。本文通過(guò)分析這些算法的特點(diǎn)，提出了一種綜合性的組合方法，在原有算法的基礎(chǔ)上更進(jìn)一步地加快了運(yùn)算速度。需要每做一次平方或乘法運(yùn)算后，就要作一 次模運(yùn)算，當(dāng) n的值很大時(shí)，做一次模運(yùn)算所需的時(shí)間比做一次平方或一次乘法所需的時(shí)間更多，是影響算法實(shí)現(xiàn)速桂林理工大學(xué)本科畢業(yè)設(shè)計(jì)如果 RSA 算法是安全的，那么 n=pq 必須足夠大，使得因式分解模數(shù) n 在計(jì)算上不可行的。計(jì)算機(jī)網(wǎng)絡(luò)中的加密技術(shù)主要采用鏈路加密和端對(duì)端加密等兩種方式。論文 1 第 1 章 引言 題目背景 在當(dāng)今的信息社會(huì)中，每天都有大量的信息在傳輸、交換、存儲(chǔ)和處理，而這些處理過(guò)程幾乎都要依賴強(qiáng)大的計(jì)算機(jī)系統(tǒng)來(lái)完成。 本文針對(duì)非對(duì)稱性加密 RSA 算法，采用軟件 Visual C++ 進(jìn)行程序編寫。桂林理工大學(xué)本科畢業(yè)設(shè)計(jì)根據(jù)模乘法運(yùn)算和模指數(shù)運(yùn)算的數(shù)學(xué)原理所編寫的程序在進(jìn)行測(cè)試后，能夠通過(guò)輸入兩個(gè)素?cái)?shù)進(jìn)行運(yùn)算從而實(shí)現(xiàn)明文與密文之間的轉(zhuǎn)換，然后通過(guò)對(duì)公鑰和私鑰的管理，對(duì)所傳輸?shù)臄?shù)據(jù)進(jìn)行保護(hù)，讓數(shù)據(jù)只能由發(fā)送者和接收者閱讀，以達(dá)到數(shù)據(jù)通信中數(shù)據(jù)無(wú)法被他人破譯的目的。一旦計(jì)算機(jī)系統(tǒng)發(fā)生安全問(wèn)題，就可能造成信息的丟失、篡改、偽造、假冒，以及系統(tǒng)遭受破壞等嚴(yán)重后果。 通常情況是將這兩種加密模式結(jié)合起來(lái)共同使用，即可保證網(wǎng)內(nèi)用戶的數(shù)據(jù)安全，又可提供用戶之間的身份鑒別與認(rèn)證?；诎踩钥紤]，實(shí)際應(yīng)用中所選擇的素?cái)?shù) p和 q至少應(yīng)該為 100 位以上的十進(jìn)制數(shù)，相應(yīng)的模數(shù) n=pq 將 是 200 位的十進(jìn)制數(shù)。論文 2 度的關(guān)鍵。 本文首先介紹了加密算法的數(shù)學(xué)基礎(chǔ)，從數(shù)學(xué)理論上分析了 RSA 算法的原理 。一些人可能會(huì)假冒合法用戶身份或者假冒網(wǎng)站來(lái)用于一些非法目的，而事后又對(duì)自己的行為進(jìn)行抵賴 :系統(tǒng)可能由于黑客的攻擊而無(wú)法提供有效的服務(wù)。到了 60 年代，隨著電子技術(shù)、信息技術(shù)的發(fā)展及結(jié)構(gòu)代數(shù)、可計(jì)算性理論和復(fù)雜度理論的研究，密碼學(xué)又進(jìn)入了一個(gè)新的時(shí)期。桂林理工大學(xué)本科畢業(yè)設(shè)計(jì)雖然用戶的私鑰是不對(duì)外公開(kāi)的，但是 也很難保證私鑰長(zhǎng)期的保密性，很難保證長(zhǎng)期以來(lái)不被泄漏。 數(shù)據(jù)加密的標(biāo)準(zhǔn) 對(duì)稱密鑰加密算法 DES (Data Encryption Standard)是由工 BM公司在 70 年代發(fā)展起來(lái)的，并經(jīng)政府的加密標(biāo)準(zhǔn)篩選后，于 1977 年被正式批準(zhǔn)并作為美國(guó)聯(lián)邦信息處理標(biāo)準(zhǔn)。 RSA 是另外一種非常著名的公鑰加密體制，由 Ron Rivest, AdiShami:以及Leonard Adleman 于 1978 年提出，一該體制至今仍被公認(rèn)為是一個(gè)安全性能良好的密碼體制。 RSA 則是非對(duì)稱密鑰的桂林理工大學(xué)本科畢業(yè)設(shè)計(jì) SSL2. 0 用電子證書 (Electric certificate)來(lái)實(shí)行身份進(jìn)行驗(yàn)證后，雙方就可以用保密密鑰進(jìn)行安全的會(huì)話了。事實(shí)上，很 多機(jī)構(gòu)一般租用專用線路來(lái)連結(jié)這些虛擬的局域網(wǎng)。此外還對(duì)數(shù)字簽名技術(shù)作了介紹。 身份驗(yàn)證：確保數(shù)據(jù)發(fā)自特定的一方。 220xx ?)) (q(p 取 3e? 。若 n 被分解，則也就不保密， e 公開(kāi)， d 就可以計(jì)算出來(lái)， RSA 便被破譯。 RSA 的出現(xiàn)使得大整數(shù)分解因式這一古老的問(wèn)題再次被重視，近些年來(lái)出現(xiàn)的不少比較高級(jí)的因數(shù)分解方法使“安全素?cái)?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)化。在沒(méi)有找到快速進(jìn)行大整數(shù)分解因式方法的時(shí)候， RSA 顯示了不可比擬的優(yōu)點(diǎn)。 RSA 算法實(shí)現(xiàn)數(shù)據(jù)加密的主要步驟分為： 獲取密鑰，這里是產(chǎn)生密鑰，實(shí)際應(yīng)用中可以從各種存儲(chǔ)介質(zhì)上讀取密鑰 。正確的生成大素?cái)?shù)的方法是對(duì)生成的隨機(jī)數(shù)先測(cè)試它是否為 素?cái)?shù)，而不是對(duì)它進(jìn)行因子分解。假設(shè)正整數(shù)中只有 k個(gè)素?cái)?shù)，設(shè)為 k21 p p, p ? 。論文 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è)。此方法需要求得素?cái)?shù) n1 的全部素因子。論文 13 或者存在一個(gè) r, sr0 ?? ，使得 n)(mb r m od12 ? 則稱 n 通過(guò)以 b 為基的 MillerRabin 測(cè)試。 若 p1 含有一個(gè)大的素?cái)?shù)因子 r，則 ljrp ?? ， j 為整數(shù)，由于 p與 r均為奇數(shù) (大素?cái)?shù) )，所以 j 一定是偶數(shù)。 桂林理工大學(xué)本科畢業(yè)設(shè)計(jì) 如果 P 通過(guò) D(D30)次 Miller Rabin 檢測(cè)，則可 以人為 P是一個(gè)素?cái)?shù)。上一節(jié)，已經(jīng)討論了大素?cái)?shù)的生成算法，這里主要討論最大公因子 gcd、模 n 求逆 namod1 和模 n的大數(shù)冪乘 nxymod 的算法。 利用數(shù)學(xué)歸納法容易證明 :對(duì)任意 0i? ，存在整數(shù) (i)(i) ,b(i) ,a(i) ,ba 2211 使得 ) (( i ) nb)(( i ) na( i )n 00 21111 ?? ) (( i ) nb)(( i ) na( i )n 00 22122 ?? 事實(shí)上，當(dāng) 0?i 時(shí)，取 10000010 2211 ???? )(,b)(,a)(,b)(a 則 顯然有 )()n(b)()n(a)(n )()n(b)()n(a)(n 00000 00000 22122 21111 ?? ?? 假設(shè) i=j 時(shí)，式 (415)和 (416)成立，則當(dāng) i=j+l 時(shí) ， )(( j ) n( j ) q( j ) b) + b(( j ) n( j ) q( j ) a( j ) = ( a( j ) q( j ) n) = n( j +n ) ，(( j ) n) + b(( j ) n( j ) = a) = n( j +n 001 001 221121212 221221 其中 q(j)為 Euclid 算法中第 i次對(duì) q 賦值后 q的值，規(guī)定 ，因此 ( j) ,( j) q ( j) bb)(jb( j) ,( j) q ( j) aa)(ja( j) ,b)(jb( j) ,a)(ja21221221211111???????? 從上面的討論可知，存在整數(shù) a和 b使得 buan(n, u) ??gc d . 桂林理工大學(xué)本科畢業(yè)設(shè)計(jì)使得1mod ? nuv 的充分必要條件是 l(u,n)?gcd 。 舉例說(shuō)明上述算法，求 13 模 35 的逆元 : 35=2 13+9,9=1 352 13, 13=1 9+4,4=1 131 9=1 35+3 9=2 4+1,1=1 92 4=3 358 13, 所以 13 模 35的 逆元為 27035mod8 = )( n的大數(shù)冪乘運(yùn)算 RSA 公鑰密碼體制中，加密和解密時(shí)都要進(jìn)行 運(yùn)算，下面給出一個(gè)計(jì)算 nxrmod的快速算法。 (3)如果 02mod ? b ，則轉(zhuǎn)到第 (5)步 。 RSA 安全性分析 RSA 的安全性，是基于大整數(shù)的素分解問(wèn)題的難解性，即把 n 分解為 p、 q的困難程度。若 pq，則可按以下步驟分解 n: (1)因 p qr? 和由 lq)pq ( p)) ( q( pΦ ( r) ???? 11 求得 1??? Φ(r)qp 。在 n???1 的區(qū)間中有 lq)pq ( p)) ( q( pΦ ( r) ???? 11 個(gè)與 r互素的數(shù)，且有 1(p q) Φ(r)r ?? 個(gè)與 r 非互素的數(shù)。通過(guò)實(shí)踐證明， RSA 在目前的計(jì)算機(jī)運(yùn)行能力 下，還是相對(duì)安全的。論文 21 第 5 章 RSA 算法的實(shí)現(xiàn) 基于前面的分析，本章給出了一種實(shí)現(xiàn) RSA 的快速高效算 法，并介紹了利用組合算法實(shí)現(xiàn)大整數(shù)快速模冪 乘運(yùn)算的具體實(shí)現(xiàn)過(guò)程，以及在實(shí)現(xiàn)過(guò)程中所遇到的關(guān)鍵問(wèn)題及解決方法。論文 22 試驗(yàn)與運(yùn)行結(jié)果 開(kāi)發(fā)環(huán)境： ， 512M 內(nèi)存， 80G 硬盤， 17寸顯示器 操作系統(tǒng)： Windows XP 開(kāi)發(fā)工具： Visusl C++ 仿真結(jié)果： 其中 p,q 為 2位素?cái)?shù)，計(jì)算 p 與 q 的乘積，輸入整數(shù) d， d可以取大于 p,q 的素?cái)?shù)小于 p,q 乘積，要求與 (p－ 1)*(q－ 1)互質(zhì)，計(jì)算 d 的逆元， 輸入明文動(dòng)態(tài)空間 L，要求明文字節(jié)數(shù)不得超過(guò) L，否則任務(wù)終止。文章對(duì) RSA 公鑰密碼體 制的數(shù)學(xué)基礎(chǔ)，加密算法，簽名算法，安全性及參數(shù)的選擇做了詳細(xì)的討論。值此論文完成之際，請(qǐng)導(dǎo)師接受我最衷心的感謝和最誠(chéng)摯的敬意。 感謝桂林理工大學(xué)的各位老師，特別是電子與計(jì)算機(jī)系的領(lǐng)導(dǎo)和老師們。此外，在實(shí)踐中還可能發(fā)現(xiàn)本文研究未涉及的新問(wèn)題，還需不斷的歸納、總結(jié)，并提出相應(yīng)的解決方法。論文 23 分配空間，此時(shí)我規(guī)定的是 64 個(gè)字節(jié)，輸入明文 12345678，通過(guò) ulo r Pe C mod? C = Pe modulo r 計(jì)算將會(huì)轉(zhuǎn)化為密文： 1268 2307 116 838 323 692 440 2366，再通過(guò) ulo rCdP mod? 將其轉(zhuǎn)換回來(lái)就為 12345678 在實(shí)際生活中，取素?cái)?shù) p=11,q=311,公開(kāi)乘積 r,保密 d與逆元 n，當(dāng)小 A 發(fā)出明文 12345678 時(shí)，對(duì)其加密，得到密文 1268 2307 116 838 323 692 440 2366，發(fā)給小 C，他通過(guò)認(rèn)證可得到明文 12345678 桂林理工大學(xué)本科畢業(yè)設(shè)計(jì) 算法必須是有效的，即是高效的算法。 近年來(lái)，隨著電子商務(wù)、電子政務(wù)等網(wǎng)上行為的增加，對(duì)于加密技術(shù)的研究日趨活躍。 以目前的常規(guī)個(gè)人計(jì)算機(jī)為工具來(lái)進(jìn)行因子分解，其工作量是非線性增長(zhǎng)的，分析見(jiàn)表 4l: N的位數(shù) 所需時(shí)間 50 小時(shí) 75 104 天 100 74年 200 109年 300 1015年 500 1025年