【文章內(nèi)容簡(jiǎn)介】 a=aXa mod p – 用戶 B選擇一個(gè)隨機(jī)數(shù) Xb p，計(jì)算 Yb=aXb mod p – 每一方保密 X值，而將 Y值通過(guò)公開(kāi)信道交換給對(duì)方（ Ya和 Yb無(wú)需保密 ） – 用戶 A計(jì)算出 K=YbXa mod p=(aXb)Xa mod p =aXbXa mod p – 用戶 B計(jì)算出 K39。=YaXb mod p=(aXa)Xb mod p =aXaXb mod p – 雙方獲得一個(gè)共享密鑰 K=K39。=aXaXbmod p 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。版權(quán)所有 ,引用請(qǐng)注明出處 DiffieHellman密鑰交換 ? 由于 Xa和 Xb是私有的，且是隨機(jī)選擇的，所以攻擊者只能通過(guò)公開(kāi)的 p， a， Ya， Yb來(lái)進(jìn)行攻擊，這樣他就必須先計(jì)算離散對(duì)數(shù) Xa=logaYa 或 Xb=logaYb ，然后才能像用戶 A或 B那樣計(jì)算出會(huì)話秘鑰 K。 ? 接下來(lái)，雙方以共享密鑰 K=aXaXb mod p作為加 /解密密鑰，以傳統(tǒng)的 對(duì)稱密鑰密碼算法 進(jìn)行保密通信。 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。版權(quán)所有 ,引用請(qǐng)注明出處 DiffieHellman密鑰交換 ? 舉例 A和 B需用 DH密鑰交換算法進(jìn)行密鑰交換，二者協(xié)商后決定采用大素?cái)?shù) p=353及其一個(gè)本原根 a=3。 A選擇隨機(jī)數(shù) x=97， B選擇隨機(jī)數(shù) y=233。 計(jì)算過(guò)程如下： ① A計(jì)算 X=ax mod p=397 mod 353＝ 40，并發(fā)送給 B。 ② B計(jì)算 Y=ay mod p=3233 mod 353＝ 248，并發(fā)送給 A ③ A計(jì)算 k=Yx mod p＝ 24897 mod 353= ④ B計(jì)算 k39。=Xy mod p＝ 40233 mod 353= ⑤因?yàn)?k=k’ =160,所以 160即為 A和 B共享的“會(huì)話密鑰” 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。版權(quán)所有 ,引用請(qǐng)注明出處 DiffieHellman密鑰交換 ? 優(yōu)點(diǎn) (1)任何兩個(gè)用戶都可通過(guò)協(xié)商計(jì)算出會(huì)話密鑰 ,不需事先擁有對(duì)方的公開(kāi)或秘密信息。 (2)每次密鑰交換后不必再保留各自秘密的信息 ,減少了保密的負(fù)擔(dān)。 (3)前提條件 :必須進(jìn)行身份認(rèn)證 ,確保不是與假冒的用戶進(jìn)行密鑰交換 ,否則不能抵抗 中間人攻擊 。 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。版權(quán)所有 ,引用請(qǐng)注明出處 DiffieHellman密鑰交換的攻擊 ? “中間人攻擊”是一種主動(dòng)攻擊方式。 ? 一個(gè)主動(dòng)的竊聽(tīng)者 O可能截取 A發(fā)給 B的消息以及 B發(fā)給 A的消息，并且他用自己的消息替換這些消息。 ? 然后分別與 A和 B完成一個(gè) DiffieHellman密鑰交換。 ? 密鑰交換協(xié)議完成后， A實(shí)際上和 O建立了一個(gè)共享密鑰， B實(shí)際上和 O也建立了一個(gè)共享密鑰。 ? 當(dāng) A加密一個(gè)消息發(fā)送給 B時(shí)， O能解密而 B不能。類似地，當(dāng) B加密一個(gè)消息發(fā)送給 A時(shí)， O能解密而 A不能。 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。版權(quán)所有 ,引用請(qǐng)注明出處 44 DiffieHellman密鑰交換的攻擊 ? 舉例 – A和 B選擇素?cái)?shù) p以及 p的一個(gè)本原根 a(假定 O知道 ) – A選擇 Xap,計(jì)算 Ya=aXa mod p, A?B: Ya – O截獲 Ya,選 Xo,計(jì)算 Yo=aXo mod p,冒充 A?B:Yo – B選擇 Xbp,計(jì)算 Yb=aXb mod p, B?A: Yb – O截獲 Yb,冒充 B?A:Yo – A計(jì)算 : (Yo)Xa?(aXo)Xa?aXoXa mod p – B計(jì)算 : (Yo)Xb?(aXo)Xb?aXoXb mod p – O計(jì)算 : (Ya)Xo?aXaXo mod p, (Yb)Xo?aXbXo mod p ? 在這種攻擊方式中， O無(wú)法計(jì)算出 A和 B期望獲得的會(huì)話密鑰 K=aXaXb mod p，但 O與 A和 B分別建立了共享密鑰aXaXo mod p和 aXbXo mod p。 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。版權(quán)所有 ,引用請(qǐng)注明出處 DiffieHellman密鑰交換的攻擊 接下來(lái)， A和 B 之間的通信以下列方式泄密： (1)A發(fā)送一份加過(guò)密的消息 M： EaXaXo mod p(M) (2)O截獲該密文，并進(jìn)行解密恢復(fù)出 M。 (3)第一種情況： O將 EaXbXo mod p(M)發(fā)送給 B 第二種情況： O將 EaXbXo mod p(M’ )發(fā)送給 B，其中 M’是任意的消息。 ? 第一種情況 O只是簡(jiǎn)單地偷聽(tīng) A與 B之間的通信 ? 第二種情況 O想篡改 A發(fā)送給 B的消息。 ★防止 DiffieHellman密鑰交換算法中間人攻擊的一個(gè)方法是讓 A和 B分別對(duì)消息進(jìn)行認(rèn)證，即加上 數(shù)字簽名 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。版權(quán)所有 ,引用請(qǐng)注明出處 46 內(nèi)容提要 ? 公開(kāi)密鑰密碼經(jīng)典算法 – DiffieHellman密鑰交換算法 – 背包算法 – RSA算法 – ElGamal算法 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。版權(quán)所有 ,引用請(qǐng)注明出處 背包算法 ? 背包算法是最早提出的公鑰密碼體制，也是第一個(gè)推廣的公鑰加密算法。 ? 背包算法只能用于加密 /解密。 ? 背包算法的安全性基于“背包問(wèn)題”。 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。版權(quán)所有 ,引用請(qǐng)注明出處 48 背包問(wèn)題 ? 背包問(wèn)題描述： 已知有 n個(gè)物品 ,它的重量分別為W1,W2,W3,……,W n,以及總重量 S。對(duì)于每個(gè) ai∈ {0,1},能否找到一組系數(shù) a1,a2,……,a n,使得 S = a1W1+a2W2 +...+ anWn成立，即為背包問(wèn)題。其中，“ W1,W2,W3,……,W n”稱為“背包序列” 。 ? 背包問(wèn)題的數(shù)學(xué)描述： 給定 n個(gè)不同的正整數(shù)的集合 A={a1, a2, …,a n}及正整數(shù) S，求一個(gè)由 0、 1組成的向量 X=(x1,x2, …,x n)，其中 xi∈ {0,1},使得： x1a1+x2a2+……+x nan=S成立。 其中 A=(a1, a2, …,a n)稱為背包向量， S稱為背包容積。 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。版權(quán)所有 ,引用請(qǐng)注明出處 背包問(wèn)題 ? 舉例 假設(shè)重量分別為 85,13,9,7,47,27,99,86。需要的 總重量是 S=172。那么該問(wèn)題存在的一個(gè)解是： X=(x1,x2,x3,x4,x5,x6,x7,x8)=(11001100)。因?yàn)? 85 1+13 1+9 0+7 0+47 1+27 1+99 0+86 0=172 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。版權(quán)所有 ,引用請(qǐng)注明出處 背包算法的思想 ? 背包問(wèn)題用于公鑰密碼學(xué)的基本做法是：假設(shè)明文為 X（即明文為二進(jìn)制向量）， S為密文。 ? 有兩類背包，一類可以在線性時(shí)間內(nèi)求解 ——易解的背包 ；另一類則不能 ——難解的背包 。 ◆易解的背包可以修改成難解的背包。 ◆ 難解的背包作為公鑰 ，可以實(shí)現(xiàn)加密。 ◆ 易解的背包作為私鑰 ，可以實(shí)現(xiàn)解密，不知道私鑰的人只能求解困難的背包問(wèn)題（即單向函數(shù)問(wèn)題）。 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。版權(quán)所有 ,引用請(qǐng)注明出處 51 易解的背包問(wèn)題 ——超遞增背包 ——私鑰 ? 超遞增背包問(wèn)題是： 如果物品重量的序列為一個(gè) “超遞增序列 ”，則此背包問(wèn)題容易解決。 ? 超遞增序列時(shí)滿足下列特征的序列： 其中的每個(gè)元素都大于前面所有元素之和，即 ：ai ∑aj(j=1,2,...,i1)。這樣的背包也稱為 “簡(jiǎn)單背包 ”。 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。版權(quán)所有 ,引用請(qǐng)注明出處 易解的背包問(wèn)題 ——超遞增背包 ——私鑰 ? 超遞增背包的求解過(guò)程為： 從最大的 ai開(kāi)始，如果 S大于這個(gè)數(shù)，則減去 ai，并記 xi為 1，否則記 xi為 0，如此下去，直 到最小的 ai。 設(shè)：背包序列為 {2,3,6,13,27,52}，求解 密文 S=70的 明文 X。 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。版權(quán)所有 ,引用請(qǐng)注明出處 易解的背包問(wèn)題 ——超遞增背包 ——私鑰 解： ∵ S=70＞ a6=52 ∴ 7052=18 且 x6=1 ∵ 18＜ a5=27 ∴ x5=0 ∵ 18＞ a4=13 ∴ 1813=5 且 x4=1 ∵ 5＜ a3=6 ∴ x3=0 ∵ 5＞ a2=3 ∴ 53=2 且 x2=1 ∵ 2=a1=2 ∴ x1=1 所以，密文 S=70對(duì)應(yīng)的明文 X=(x1x2x3x4x5x6)=110101, 即： x1a1+x2a2+x3a3+x4a4+x5a5+x6a6=1 2+1 3+0 6+1 13+0 27 +1 52=70 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。版權(quán)所有 ,引用請(qǐng)注明出處 54 轉(zhuǎn)換背包（普通背包） ——難解的背包 ——公鑰 ◆選擇一個(gè)整數(shù) m作為模數(shù) ,m∑ai(i=1,2,...,n)。 ◆選擇一個(gè)與 m互素的整數(shù) w，并計(jì)算 ai’ =wai(mod m)（ i=1,2,...,n）。這樣得到的背包 A’ =(a1’ ,a2’ ,...,an’ )是非超遞增背包 ——普通背包。 ◆ m與 w是保密的。 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。版權(quán)所有 ,引用請(qǐng)注明出處 55 背包算法的加密 /解密過(guò)程 ? 加密 – 將明文分為長(zhǎng)度為 n的塊 X=(x1,…,x n) – 然后用轉(zhuǎn)換背包 —公鑰 A 39。 = (a1 39。, …, a n 39。)，將明文變?yōu)槊芪?S = E(X) = ∑ai 39。 xi （ i=1,2,...,n） ? 解密 計(jì)算 w在模 m下的乘法逆元 w1，即滿足 ww1≡1mod m。 w1又稱