【文章內(nèi)容簡(jiǎn)介】 y) i=1,2,…,16 (ks表示密鑰運(yùn)算函數(shù) ,產(chǎn)生 48位的子密鑰 ) ? Li=Ri1/Ri=Li1?f (Ri1,Ki) ? (Ri1,Ki)中涉及到 E變換、 S盒代替、 P盒變換和異或運(yùn)算等步驟 ? C64=IP1(L16,R16) 79 (9) DES解密過(guò)程的數(shù)學(xué)模型 ? L16R16=IP(C64) ? Ki=ks(i,key) i=16,15,…,1 ? Ri1 = Li ? Li1 = Ri ?? (Ri,Ki) ? M64=IP1(L0,R0) 80 (10) DES的特點(diǎn)及應(yīng)用 ? DES算法具有算法容易實(shí)現(xiàn)、速度快、通用性強(qiáng)等優(yōu)點(diǎn)，但也存在密鑰位數(shù)少，保密強(qiáng)度較差和密鑰管理復(fù)雜的缺點(diǎn)。 ? DES主要的應(yīng)用范圍有： ? 計(jì)算機(jī)網(wǎng)絡(luò)通信 ? 電子資金傳送系統(tǒng) ? 保護(hù)用戶文件 ? 用戶識(shí)別 81 3. 對(duì)稱密碼體制的其它算法簡(jiǎn)介 (1) TDEA算法 (三重 DES算法 )： ? 三重 DES算法需要執(zhí)行三次 DES的加密。一般三重 DES算法使用兩個(gè) DES密鑰。其算法步驟為： ? 發(fā)送端用密鑰 K1進(jìn)行 DES加密； ? 發(fā)送端用密鑰 K2對(duì)上一結(jié)果進(jìn)行 DES解密； ? 發(fā)送端用密鑰 K1對(duì)上一結(jié)果進(jìn)行 DES加密； ? 接收方則相應(yīng)地使用 K1解密， K2加密，再使用 K1解密 。 82 K1 E M K2 D K3 E K3 D C K2 E K1 D M C 三重 DES的加密解密過(guò)程 83 (2) 國(guó)際數(shù)據(jù)加密算法 (IDEA) ? IDEA是分組密碼算法，分組長(zhǎng)度為 64位，但密鑰長(zhǎng)度 128位。 ? 該算法是用 128位密鑰對(duì) 64位二進(jìn)制碼組成的數(shù)據(jù)組進(jìn)行加密的，也可用同樣的密鑰對(duì) 64位密文進(jìn)行解密變換。 ? IDEA的密鑰比 DES的多一倍，增加了破譯難度，被認(rèn)為是多年后都有效的算法。 84 ? IDEA算法也是通過(guò)一系列的加密輪回操作的，每輪中也使用壓縮函數(shù)進(jìn)行變換，只是不使用移位置換。 ? IDEA中使用的運(yùn)算有： ? 異或 ? 模 216加法 ? 模 216+1乘法 ? 這三種運(yùn)算彼此混合可產(chǎn)生很好的效果。運(yùn)算時(shí) IDEA把數(shù)據(jù)分為四個(gè)子分組，每個(gè) 16位。 85 5． 4 公開(kāi)密鑰密碼體制 公鑰體制概述 1．公鑰體制的概念 ? 加密密鑰與解密密鑰不同，且由其中一 個(gè)不容易得到另一個(gè)，則這種密碼系統(tǒng)是非對(duì)稱密鑰系統(tǒng)。往往其中一個(gè)密鑰是公開(kāi)的，另一個(gè)是保密的。因此，相應(yīng)的密碼體制叫公開(kāi)密鑰密碼體制。 86 ? 1976年在 IEEE Information 刊物上發(fā)表了 “ New Direction in Cryptography”文章，提出了“公開(kāi)密鑰密碼體制”的概念，開(kāi)創(chuàng)了密碼學(xué)研究的新方向。 87 ?在公開(kāi)密鑰密碼體制中 ， 加密密鑰是公開(kāi)的 ， 解密密鑰是保密的 ， 加 /解密算法都是公開(kāi)的 。 ?公開(kāi)密鑰密碼體制的主要算法有 RSA、背包算法 、 Elgamal、 Rabin、 DH等 。 88 公鑰體制加 /解密模型 加密(E) 解密(D) 發(fā)送 M 接收 M Ke Kd 密文 C=E(M,Ke) 89 2. 公鑰體制的特點(diǎn) ?用 Ke對(duì)明文加密后，再用 Kd解密，即可恢復(fù)出明文，即 M=D Kd{E Ke(M)} ? 加密和解密運(yùn)算可以對(duì)調(diào)，即 M=D Kd{E Ke(M)} = E Ke {D Kd (M)} 90 ? 但加密密鑰不能用來(lái)解密，即 M≠D Ke{E Kd(M)} ? 在計(jì)算上很容易產(chǎn)生密鑰對(duì) Ke和 Kd ? 已知 Ke是不能推導(dǎo)出 Kd的，或者說(shuō)從Ke得到 Kd是“計(jì)算上不可能的”。 91 數(shù)論基礎(chǔ) (1) 模運(yùn)算 ?若 a=b+kn對(duì)某些整數(shù) k成立 則 a ? b (mod n ) ?稱 b 為 a模 n的余數(shù) ， 或 a與 b是模 n的同余 92 (2) 素?cái)?shù) ?一個(gè)只能被 1和它本身整除的正整數(shù)。如以下各數(shù)為素?cái)?shù)： 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47，53,59,61,67,71,73,79,83,89,97,101,103,107,109,113, …,2521,2365347734339,27568391等都是素?cái)?shù)。 93 (3) 兩數(shù)互素 ?兩個(gè)數(shù)的最大公因子為 1， 則兩數(shù)互素 。 gcd(a,n)=1 a和 n互素 ? 15與 28互素 ， 13與 500互素 ， 而 15與 27不是互素 ?一個(gè)素?cái)?shù)與它的倍數(shù)以外的任何其它數(shù)都是互素的 94 (4) 求模逆元 ? 什么是逆元呢？對(duì)于算術(shù)加法來(lái)說(shuō)， 5和 5互為逆元，因?yàn)?5+(5)=0；對(duì)于乘法來(lái)說(shuō)， 4的逆元是 1/4，因?yàn)?4?1/4=1。所謂的逆元，相對(duì)不同的運(yùn)算，其含義是不同的。 ? 在模運(yùn)算領(lǐng)域，該問(wèn)題更復(fù)雜。如果 ? a?b≡1 (mod n) ，也可寫(xiě)成 ? b≡a1 (mod n) ? 可以說(shuō)， a與 b對(duì)于模 n的乘法是互為逆元的。 ? 解決逆元的問(wèn)題很復(fù)雜，有時(shí)有結(jié)果，有時(shí)沒(méi)有結(jié)果。比如 5模 14的逆元是 3，因?yàn)? ? 5?3=15≡1 (mod 14) ? 而 2模 12則沒(méi)有逆元。 ? 一般，如果 a和 n是互素的，那么 a1≡b (mod n)有惟一解，即存在惟一的逆元；如果 a和 n不是互素的，那么 a1≡b (mod n)沒(méi)有解，即沒(méi)有逆元；如果 n是一個(gè)素?cái)?shù)，則從 1到 n1的每一個(gè)數(shù)與 n都是互素的，且在這個(gè)范圍內(nèi)各有一個(gè)逆元。 ? 計(jì)算逆元有一系列方法，歐幾里德算法就是其中之一。在公開(kāi)密鑰密碼體制的 RSA算法中，就是用歐幾里德算法求逆元的。 95 (5)歐拉函數(shù)和費(fèi)爾馬小定理 ? 模 n的余數(shù)化簡(jiǎn)集是余數(shù)完全集合的子集，該子集中的數(shù)與 n互素。例如：模 12的余數(shù)化簡(jiǎn)集是 {1， 5， 7， 11}，如果 n是素?cái)?shù)，那么模 n的余數(shù)化簡(jiǎn)集是從 1到 n1的所有整數(shù)集合。對(duì) n不等于 1的數(shù)，數(shù) 0不是余數(shù)化簡(jiǎn)集的元素。 ? 歐拉函數(shù)（記為 ф(n)），表示模 n的余數(shù)化簡(jiǎn)集中元素的數(shù)目，即 ф(n)表示與 n互素的小于 n的正整數(shù)的數(shù)目 (n1)。 ? 如果 n是素?cái)?shù)，那么 ? (n)=n1；如果 n=p?q，且 p和 q互素，那么 ? (n)=(p1)(q1)。 ? 如果 n是一個(gè)素?cái)?shù)，且 a不是 n的倍數(shù)，則有： ? an1≡1 (mod n)。 ? 這就是費(fèi)爾馬小定理。因此，可以利用 b=aф(n)1 (mod n)來(lái)計(jì)算 a模 n。 ? 例如，計(jì)算 5模 7的逆元。 7是素?cái)?shù)， ? (7)=71=6。因此模 7的逆元是 ? 561=55=3 mod 7 ? 計(jì)算逆元的兩種方法都可以推廣到一般性的問(wèn)題中求解 b(如果 gcd(a,n)=1)： ? （ a?b） =x (mod n) ? 用歐拉函數(shù)求解逆元： ? b=(x?aф(n)1) mod n ? 用歐幾里德算法求解逆元： ? b=(x?（ a1 mod n） ) mod n ? 通常歐幾里德算法在計(jì)算逆元方面比歐拉函數(shù)更快，特別是對(duì)于 500位范圍內(nèi)的數(shù)。 ? 如果 gcd(a,n)≠1，也并非一切都無(wú)用。在這種情況下，（ a?b） =x (mod n)，可能有多個(gè)解或無(wú)解。 96 (6) 因子分解 ?對(duì)于一個(gè)數(shù)進(jìn)行因子分解 ， 就是找出其各個(gè)素?cái)?shù)因子 ， 如： 15=3?5， 80=2? 2?2?2?5， 252601=41?61?101等 。 ?在數(shù)論中 ， 因子分解是一個(gè)古老的問(wèn)題 。分解一個(gè)數(shù)很簡(jiǎn)單 ， 但其過(guò)程很費(fèi)時(shí) 。目前最好的因子分解算法有： 97 ? 數(shù)域篩選法 ：對(duì)大于 110位字長(zhǎng)的數(shù) ， 數(shù)域篩選法是已知的最快的因子分解算法 。 當(dāng)它最初被提出時(shí) ， 還不算實(shí)用 ， 但隨著后來(lái)的一系列改進(jìn) ， 成為新的一種因子分解實(shí)用算法 。 ? 二次篩選法： 對(duì)于低于 110位的十進(jìn)制數(shù) ，二次篩選法是已知的最快算法 ， 且已得到廣泛應(yīng)用 。 該算法最快的版本叫多重多項(xiàng)式二次篩選的雙重大素?cái)?shù)算法 。 98 ?橢圓曲線法： 該算法曾用于尋找 43位長(zhǎng)數(shù)字的因子 ， 對(duì)于更大的數(shù)是無(wú)用的 。 ?此外 ， 還有蒙特卡羅算法 、 連分式算法 、試除法等因子分解算法 。 99 RSA算法簡(jiǎn)介 1． RSA算法 RSA算法 是 1978年由三名美國(guó) MIT科學(xué)家Rivest, shamir和 Adelman提出的一種著名的公開(kāi)密鑰密碼算法 (以該三位姓氏的第一個(gè)字母命名 )。 100 ?經(jīng)過(guò)多年的分析研究 ,在眾多的公鑰體制中， RSA倍受推崇，已被 ISO/TC97的數(shù)據(jù)加密技術(shù)分委員會(huì) SC20推薦為公鑰數(shù)據(jù)加密標(biāo)準(zhǔn)。 ? RSA算法 是建立在 素?cái)?shù)理論 (Euler函數(shù)和歐幾里德定理 )基礎(chǔ)上的算法。 101 ?由數(shù)論知識(shí)可知，將一個(gè)具有大素?cái)?shù)因子的合數(shù)進(jìn)行分解是很困難的，或者說(shuō)這個(gè)計(jì)算量是令人望而生畏的。 RSA正是建立在這個(gè)理論基礎(chǔ)之上的。 ? RSA算法的加密密鑰 Ke是公開(kāi)的，而解密密鑰 Kd是保密的。 102 ?在此不介紹 RSA的理論基礎(chǔ) (復(fù)雜的數(shù)學(xué)分析和理論推導(dǎo) )，只簡(jiǎn)單介紹密鑰的選取和加、解密的實(shí)現(xiàn)過(guò)程。 ?假設(shè)用戶 A要對(duì)發(fā)送給 B的數(shù)據(jù)加密，則可根據(jù)以下步驟選擇密鑰和進(jìn)行密碼變換： 103 (1) 隨機(jī)地選取兩個(gè)不同的大素?cái)?shù) p和 q(一般為 100位以上的十進(jìn)制數(shù) )予以保密； (2) 計(jì)算 n = p q，作為 A的公開(kāi)模數(shù)； (3) 計(jì)算 Euler 函數(shù) ?(n)=(p1) (q1) (mod n ) (4) 隨機(jī)地選取一個(gè)與 (p1) (q1)互素的整數(shù) e，作為 A的公開(kāi)密鑰； 104 (5) 用歐幾里德算法，計(jì)算滿足同余方程 E?D?1 (mod ?(n)) 的解 d，作為 A用戶的保密密鑰； (6) 任何向 A發(fā)送明文的用戶，均可用 A的公開(kāi)密鑰 e 和公開(kāi)模數(shù) n，根據(jù)式 C=Me (mod n) 得到密文 C 105 (7) 用戶 A收到 C后，可利用自己的保密密鑰 d，根據(jù) M=Cd (mod n) 得到明文 M 106 2． RSA算法舉例 對(duì)“ HI”進(jìn)行加密： (1) 選密鑰 ? 設(shè) p=5,q=11， ? 則 n=55, ?(n)=40 ? 取 e=3(公鑰 )， ? 則 d=27 (mod 40)(私鑰 ) 107 (2) 加密 ? 設(shè)明文編碼為： 空格 =00,A=01,B=02, …,Z=26 ? 則明文 HI=0809 ? C1=(08)3=512 ? 17 (mod 55) ? C2=(09)3=729 ? 14 (mod 55) ? N=14,Q=17 ? 所以，密文為 QN 108 (3) 恢復(fù)明文 ? M1=Cd=(17)27 ? 08 (mod 55) ? M2=Cd=(14)27 ? 09 (mod 55) ? 因此明文為“ HI”。 109 DES和 RSA算法的特點(diǎn)和比較 (1) DES的特點(diǎn) ? 可靠性較高 (16輪變化，增大了混亂性和擴(kuò)散性，輸出不殘存統(tǒng)計(jì)信息 )； ? 加密 /解密速度快； ? 算法容易實(shí)現(xiàn) (可由軟件和硬件實(shí)現(xiàn)，硬件實(shí)現(xiàn)速度快 )， 通用性強(qiáng)； 110 ? 算法具有對(duì)稱性，密鑰位數(shù)少，存在弱密鑰和半弱密鑰，便于窮盡攻擊； ? 密鑰管理復(fù)雜。 111 (2) RSA算法的特點(diǎn) ? 密鑰管理簡(jiǎn)單 (網(wǎng)上每個(gè)用戶僅保密一個(gè)密鑰，且不需密鑰配送 )； ? 便于數(shù)字簽名； ? 可靠性較高 (取決于分解大素?cái)?shù)的難易程度 )； ? 算法復(fù)雜，加密 /解密速度慢 , 難于實(shí)現(xiàn)。 112 混合加密方法 ? 對(duì)稱密鑰密碼算法的特點(diǎn)是算法簡(jiǎn)單，加 /解密運(yùn)算速度快；但其密鑰管理復(fù)雜，不便于數(shù)字簽名。而公開(kāi)密鑰密碼算法的特點(diǎn)是密鑰管理簡(jiǎn)單，便于數(shù)字簽名；但算法的理論復(fù)雜，加 /解密運(yùn)算速度慢。兩者的優(yōu)缺點(diǎn)互補(bǔ)。 113 ? 因此，在實(shí)際應(yīng)用中，公開(kāi)密鑰密碼系統(tǒng)并沒(méi)有完全取代對(duì)稱密鑰密碼系統(tǒng)。而是采用對(duì)稱密鑰加密方法與公開(kāi)密鑰加密方