【文章內(nèi)容簡介】 k i （ 56 位） （ 48 位） 64 位密鑰 置換選擇 1 C 0 （ 28 位） D 0 （ 28 位） 循環(huán)左移 循環(huán)左移 C 1 （ 28 位） D 1 （ 28 位） 循環(huán)左移 循環(huán)左移 C i （ 28 位） D i （ 28 位） 置換選擇 2 置換選擇 2 密鑰表的計算邏輯 循環(huán)左移： 1 1 9 1 2 1 10 2 3 2 11 2 4 2 12 2 5 2 13 2 6 2 14 2 7 2 15 2 8 2 16 1 65 置換選擇 1(PC1)和置換選擇2(PC2) 總結(jié)－ DES示意圖 67 DES的安全性分析 ? DES的安全性完全依賴于密鑰，與算法本身沒有關(guān)系。 ? 主要研究內(nèi)容： ? 密鑰的互補(bǔ)性； ? 弱密鑰與半弱密鑰； ? 密文 明文相關(guān)性； ? 密文 密鑰相關(guān)性； ? S盒的設(shè)計； ? 密鑰搜索。 68 弱密鑰 ? 弱密鑰： 由密鑰 k 確定的加密函數(shù)與解密函數(shù)相同 ，即 。 ? DES的弱密鑰： 如果各輪產(chǎn)生的子密鑰一樣，則加密函數(shù)與解密函數(shù)相同。 ? DES至少有 4個弱密鑰 ： ? 0101010101010101 ? 1f1f1f1f0e0e0e0e ? e0e0e0e0f1f1f1f1 ? fefefefefefefefe )()( 1 ??? ? kk DE SDE S69 半弱密鑰 ? 半弱密鑰：對于密鑰 k ，存在一個不同的密鑰 ，滿足 。 ? DES的半弱密鑰：子密鑰生成過程中只能產(chǎn)生兩個不同的子密鑰或四個不同的子密鑰，互為對合。 ? DES至少有 12個半弱密鑰。 *k )()( * ??? kk DE SDE S70 S 盒的設(shè)計原則 S 盒的設(shè)計原理沒有公開，一些原則如下： ? 所有 S盒的每一行是 0,1,… ,15的一個置換； ? 所有 S盒的輸出都不是輸入的線性函數(shù)或仿射函數(shù)； ? S盒的輸入改變?nèi)我庖晃欢紩疠敵鲋兄辽賰晌话l(fā)生變化； ? 對于任何輸入 x（ 6位）， S(x)與 S(x⊕ 001100)至少有兩位不同； ? 對于任何輸入 x（ 6位）， S(x)與 S(x⊕ 00ef00)不相等， e, f取 0或 1； ? 對于任意一個輸入位保持不變而其他五位變化時，輸出中 0和 1的數(shù)目幾乎相等。 71 針對 DES的攻擊方法 攻擊 DES的方法主要有： ? 密鑰窮搜索攻擊， DES算法總的密鑰量為 ， 1998年使用高級計算機(jī)的情況下，破譯 DES只需 56小時； ? 差分攻擊； ? 線性攻擊，較有效的方法； ? 相關(guān)密鑰攻擊等。 1756 102 ?72 DES的破譯 ? 1990年，以色列密碼學(xué)家 Eli Biham和Adi Shamir提出了 差分密碼分析法 ，可對 DES進(jìn)行選擇明文攻擊。 ? 線性密碼分析 比差分密碼分析更有效 73 公鑰密碼 ? 公開密鑰算法中用作加密的密鑰不同于用作解密的密鑰 ， 而且解密密鑰不能根據(jù)加密密鑰計算出來（ 至少在合理假定的長時間內(nèi) ） ， 所以加密密鑰能夠公開 ， 每個人都能用加密密鑰加密信息 ， 但只有解密密鑰的擁有者才能解密信息 。 ? 在公開密鑰算法系統(tǒng)中 ， 加密密鑰叫做公開密鑰（ 簡稱公鑰 ） ， 解密密鑰叫做秘密密鑰 （ 私有密鑰 ，簡稱私鑰 ） 。 ? 公開密鑰算法主要用于加密 /解密 、 數(shù)字簽名 、 密鑰交換 。 74 討論議題 ? 為什么要設(shè)計公鑰密碼算法 ? 密鑰分配 ? 公鑰密碼體制概述及其應(yīng)用 ? 公鑰密碼算法的實現(xiàn) ? DiffieHellman密鑰交換算法 ? 背包算法 ? RSA算法 ? EIGamal算法 ? 橢圓曲線密碼算法 ECC 75 1. 為什么要設(shè)計公鑰密碼體制 76 密鑰分配（ Key Distribution） ? 保密通信雙方需共享密鑰 ? 共享密鑰要經(jīng)常更換 – A選擇密鑰并手工傳遞給 B – 第三方 C選擇密鑰分別手工傳遞給 A,B – 用 A,B原有共享密鑰傳送新密鑰 – 與 A,B分別有共享密鑰的第三方 C傳送新密鑰給A和 /或 B ? N個用戶集需要 N(N1)/2個共享密鑰 ? 密鑰分發(fā)中心 (Key Distribution Center) 77 密鑰分發(fā)中心（ KDC） ?每個用戶與 KDC有共享密鑰 (Master Key) ?N個用戶 ,KDC只需分發(fā) N個 Master Key ?兩個用戶間通信用會話密鑰 (Session Key) ?用戶必須信任 KDC ?KDC能解密用戶間通信的內(nèi)容 78 （ 1）密鑰管理量的困難 傳統(tǒng)密鑰管理：兩兩分別用一對密鑰時，則 n個用戶需要 C(n,2)=n(n1)/2個密鑰，當(dāng)用戶量增大時，密鑰空間急劇增大。如 : n=100 時， C(100,2)=4,995 n=5000時， C(5000,2)=12,497,500 （ 2）數(shù)字簽名的問題 傳統(tǒng)加密算法無法實現(xiàn)抗抵賴的需求。 問題的提出 79 起源 ? 公鑰密碼又稱為雙鑰密碼和非對稱密碼，是1976年由 Diffie和 Hellman在其 ? 密碼學(xué)新方向 ? 一文中提出的，見劃時代的文獻(xiàn)： and , New Directrions in Cryptography, IEEE Transaction on Information Theory, , Nov 1976, ? RSA公鑰算法是由 Rivest,Shamir和Adleman在 1978年提出來的 , 見 Communitions of the ACM. . Feb. 1978, 80 公開密鑰密碼的重要特性 ? 加密與解密由不同的密鑰完成 加密 : m?c: c = EK(m) 解密 : c?m: m = DB(c) = DB(EK(m)) ? 知道加密算法 ,從加密密鑰得到解密密鑰在計算上是不可行的 ? 兩個密鑰中任何一個都可以用作加密而另一個用作解密 (不是必須的 ) m = DB(EK(m)) = EK(DB(m)) 81 2. 公鑰密碼體制的應(yīng)用概述 82 公鑰加密算法 ? 傳統(tǒng)加密過程 加密和解密使用相同密鑰 明文 明文 密文 83 公鑰加密算法 ? 公鑰密碼算法 加密和解密使用不同密鑰 明文 明文 密文 84 用公鑰密碼實現(xiàn)保密 B39。39。BBB39。39。kkkkk)kkA l i c e B ob c E mB ob D c D E m m?用 戶 擁 有 密 鑰 對 （ k,公 鑰 公 開 ， 私 鑰 保 密： ＝ （ ）： （ ） ＝ （ （ ） ） ＝85 基于公開密鑰的 加密過程 86 用公鑰密碼實現(xiàn) 認(rèn)證 39。A39。A A A39。39。kk k kk)kkA l i c e B ob c E mB ob D c D E m m?用 戶 擁 有 密 鑰 對 （ k,公 鑰 公 開 ， 私 鑰 保 密： ＝ （ ）： （ ） ＝ （ （ ） ） ＝87 基于公開密鑰的 認(rèn)證過程 88 用公鑰密碼實現(xiàn) 保密與認(rèn)證 39。BAABAB39。39。A B B A39。39。kkkkkkk k k kk)kkA l i c e B ob c E D mB ob DDD E D mm?用 戶 擁 有 密 鑰 對 （ k,公 鑰 公 開 ， 私 鑰 保 密： ＝ （ （ ） ）： （ E (c) ） ＝ （ E (c) ） ＝ （ E( （ （ ） ） ) ） ＝89 公鑰密鑰的應(yīng)用范圍 ?加密 /解密 ?數(shù)字簽名 (身份鑒別 ) ?密鑰交換 算法 加 /解密 數(shù)字簽名 密鑰交換 RSA 是 是 是 DieffieHellman 否 否 是 DSS 否 是 否 90 3. 公鑰密碼算法 91 基本思想和要求 ? 涉及到各方：發(fā)送方、接收方、攻擊者 ? 涉及到數(shù)據(jù)：公鑰、私鑰、明文、密文 ? 公鑰算法的條件： ? 產(chǎn)生一對密鑰是計算可行的 ? 已知公鑰和明文，產(chǎn)生密文是計算可行的 ? 接收方利用私鑰來解密密文是計算可行的 ? 對于攻擊者，利用公鑰來推斷私鑰是計算不可行的 ? 已知公鑰和密文，恢復(fù)明文是計算不可行的 ? (可選 )加密和解密的順序可交換 92 陷門單向函數(shù) 單向陷門函數(shù)是滿足下列條件的函數(shù) f： (1)給定 x，計算 y=fk(x)是容易的； (2)給定 y, 計算 x使 x=fk1(y)是不可行的。 (3)存在 k，已知 k 時 ,對給定的任何 y，若相應(yīng)的 x存在，則計算 x使 fk1(y)是容易的。 93 公鑰密碼基于的數(shù)學(xué)難題 ? 背包問題 ? 大 整 數(shù) 分 解 問 題 （ The Integer Factorization Problem,RSA體制 ） ? 有限域的乘法群上的離散對數(shù)問題 (The Discrete Logarithm Problem, ElGamal體制 ） ? 橢圓曲線上的離散對數(shù)問題 （ The Elliptic Curve Discrete Logarithm Problem, 類比的 ElGamal體制 ） 94 一、背包問題 ? 背包問題： ? 已知一長度為 B的背包，及長度分別為a1,a2,...,an的 n個物品。假定這些物品的半徑和背包相同，若從這 n個物品中選出若干個正好裝滿這個背包?，F(xiàn)在反過來問：究竟是哪些物品？ 95 背包問題數(shù)學(xué)描述 ii112x 0 1 1 , 2 , .. ., ,a, , .. ., bniininxba a a????求 ＝ 或 ， 使 其 滿 足 ：其 中 和 都 是 整 數(shù)96 背包問題求解 N P N P背 包 問 題 屬 于 完 備 類 （ 問 題 中 難 度 最 大 的 一 類 ）對 這 一 問 題 沒 有 有 效 算 法11( 2 , 3 , . . . , )ijja i n?????1 2 ni但 是 ， 如 果 序 列 a , a , . . . , a 是 超 遞 增 序 列 ：a背 包 問 題 有 多 項 式 解 法97 超遞增序列背包問題求解方法 1 2 3 4 5 62 4 8 16 32 43x x x x x x? ? ? ? ? ?n1 2 n例 :已 知 序 列 a ,a ,...,a 是 超 遞 增 序 列 ： 1,2,4,8,...,2求 背 包 問 題 的 解思路： xi取值只可能為 0或者 1；如果為 0，表示不能裝入對應(yīng)的物體，否則可以裝入。 98 超遞增序列背包問題求解方法 1 2 3 4 5 61 2 3 4 52 4 8 1 6 3 2 4 3