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