DH密鑰交換算法ppt課件

1、明文傳輸,通信安全,明文直接暴露與網(wǎng)絡(luò)中,通信安全,對(duì)稱加密,信息加密后，變成密文，避免信息泄露,通信安全,對(duì)稱加密,由于對(duì)稱密鑰長(zhǎng)時(shí)間不改變，密鑰存在泄露風(fēng)險(xiǎn)，如果密鑰泄露一樣可以造成信息暴露,通信安全,Alice,Bob,我們這次通訊，密鑰采用aaa,沒問題,協(xié)商的密鑰是YYY，*的意思是余額250元，嘿嘿,對(duì)稱加密,不采用固定密鑰，Alice與Bob每次通信采用協(xié)商的密鑰進(jìn)行加密，可以避免長(zhǎng)時(shí)間存放密鑰造成密鑰泄露，但是協(xié)商的密鑰仍然是暴露的,通信安全,直接非對(duì)稱加密,用非對(duì)稱加密加密對(duì)稱密鑰，對(duì)稱密鑰加密傳輸信息,DH密鑰協(xié)商,常見的解決方案,DH算法,迪菲赫爾曼密鑰交換（Diffie

2、Hellmankey exchange，簡(jiǎn)稱“DH”） 是一種安全協(xié)議。它可以讓雙方在完全沒有對(duì)方任何預(yù)先信息的條件下通過不安全信道建立起一個(gè)密鑰。這個(gè)密鑰可以在后續(xù)的通訊中作為對(duì)稱密鑰來加密通訊內(nèi)容,原根與階,性質(zhì)： 1）所有的素?cái)?shù)都有原根。 2）不是所有的整數(shù)都有原根,一些數(shù)學(xué)概念,DH算法,定理證明,定理： 設(shè) p 1，gcd(a,p) = 1，則a0, a1, a2, . aord(a)-1 模p兩兩不同余。 證明：反證法 如若存在K,L(0=LKord(a) 使得 aK aL mod p 則aK = aL + xp （x為整數(shù)） 又gcd (a , p)=1，即存在aL的逆a-L，

3、https:/ http:/ 等式兩邊乘上a(-L) a(K-L) =（aL+xp）a-L 即a(K-L) =1+（a-L）xp 即存在K-L,使得a(K-L) 1 mod p等式成立， 而K-L ord(a)，與階的定義矛盾。故假設(shè)不成立,推論： 如果a是素?cái)?shù)p的一個(gè)原根，那么數(shù)值： a modp，a2 modp，a(p-1) modp 是各不相同的整數(shù)，且以某種排列方式組成了從1到p-1的所有整數(shù),DH算法,定理、原根舉例,gcd(a, p) = 1，a與p互質(zhì)，互質(zhì)的數(shù)必須是自然數(shù)，所以a從1開始取。 例：取p=7，a=1，2，3 a=1 11mod 7=1 階：1 a=2 21mod

4、7=2 22mod 7=4 23mod 7=1 階：3 a=3 31mod 7=3 32mod 7=2 33mod 7=6 34mod 7=4 35mod 7=5 36mod 7=1 階：6 與 相等，說明a=3是7的一個(gè)原根,DH算法,DH算法證明,思考： 為什么DH算法p需要是素?cái)?shù)？a要是p的原根,DH算法,算法本質(zhì),Diffie-Hellman 算法的有效性依賴于計(jì)算離散對(duì)數(shù)的難度，其含義是：當(dāng)已知大素?cái)?shù)p和它的一個(gè)原根a后，對(duì)給定的Y，要計(jì)算x，被認(rèn)為是很困難的，而給定x計(jì)算Y卻相對(duì)容易,DH算法,例1： 按照參數(shù)的選區(qū)原則，p取一個(gè)素?cái)?shù)，a是p的一個(gè)原根，取 (a, p) = (3,

5、 7) （1）Alice 選擇一個(gè)范圍在1, p-1的隨機(jī)數(shù)，為Xa= 5 （2）Alice 計(jì)算Ya = aXa mod p = 35 mod 7 = 5 （3）Bob選擇一個(gè)范圍在1, p-1的隨機(jī)數(shù)，為Xb = 6 （4）Bob計(jì)算Yb = aXb mod p = 36 mod 7 = 1 （5）Alice和Bob交換Ya和Yb （6）Alice計(jì)算共享密鑰K = YbXa mod p = 15 mod 7 = 1 （7）Bob計(jì)算共享密鑰K = YaXb mod p = 56 m 7 = 1,算法舉例,DH算法,例2： 隨意取一個(gè)二元組 (a, p) = (7, 15) （1）Alic

6、e 選擇一個(gè)范圍在1, p-1的隨機(jī)數(shù)，為Xa= 3 （2）Alice 計(jì)算Ya = aXa mod p =73 mod 15 = 13 （3）Bob選擇一個(gè)范圍在1, p-1的隨機(jī)數(shù)，為Xb = 2 （4）Bob計(jì)算Yb = aXb mod p = 72 mod 15 = 4 （5）Alice和Bob交換Ya和Yb （6）Alice計(jì)算共享密鑰K = YbXa mod p = 43 mod 15 = 4 （7）Bob計(jì)算共享密鑰K = YaXb mod p = 132 mod 15 = 4,算法舉例,看起來是協(xié)商成功了，那問題在哪？ 7x mod 15： 71 mod 15 = 7 72 m

7、od 15 = 4 73 mod 15 = 13 74 mod 15 = 1 75 mod 15 = 7 76 mod 15 = 4 77 mod 15 = 13 77 mod 15 = 1,7x mod 15的結(jié)果一共才4種，并且周期循環(huán)。 這也就意味著中間人獲取到了Yb = 4，攻擊者不一定需要知道Alice原始的隨機(jī)值（私鑰）是什么，只要在1 , 14中隨便選擇一個(gè)滿足7Xa mod 15 = 13的值進(jìn)行計(jì)算K = YbXa mod p = 43 mod 15 = 47 mod 15 = 4 都能正確計(jì)算共享密鑰。換句話說，攻擊者不需要暴力遍歷1 , 14中的所有數(shù)就能計(jì)算共享密鑰,思

8、考： 為什么DH算法p需要是素?cái)?shù)？a要是p的原根,ECDH,ECDH算法,ECC算法和DH結(jié)合使用，用于密鑰磋商，這個(gè)密鑰交換算法稱為ECDH。交換雙方可以在不共享任何秘密的情況下協(xié)商出一個(gè)密鑰。ECC是建立在基于橢圓曲線的離散對(duì)數(shù)問題上的密碼體制，給定橢圓曲線上的一個(gè)點(diǎn)P，一個(gè)整數(shù)k，求解Q=kP很容易；給定一個(gè)點(diǎn)P、Q，知道Q=kP，求整數(shù)k確是一個(gè)難題。ECDH即建立在此數(shù)學(xué)難題之上,ECDH,ECDH算法,密鑰磋商過程： 假設(shè)密鑰交換雙方為Alice、Bob，其有共享曲線參數(shù)（橢圓曲線E、階N、基點(diǎn)G）。 Ep(a,b)確定橢圓曲線方程，p為質(zhì)數(shù)； 階數(shù)N為質(zhì)數(shù)，確定有限域； G確定初

9、始點(diǎn)； 1) Alice生成隨機(jī)整數(shù)a(aN)，計(jì)算A=a*G。 2) Bob生成隨機(jī)整數(shù)b(bN)，計(jì)算B=b*G。 3) Alice將A傳遞給Bob。A的傳遞可以公開，即攻擊者可以獲取A。 由于橢圓曲線的離散對(duì)數(shù)問題是難題，所以攻擊者不可以通過A、G計(jì)算出a。 4) Bob將B傳遞給Alice。同理，B的傳遞可以公開。 5) Bob收到Alice傳遞的A，計(jì)算Q =b*A 6) Alice收到Bob傳遞的B，計(jì)算Q=a*B 證明： 因?yàn)樵跈E圓曲線的有限域Fp內(nèi)運(yùn)算滿足交換律、結(jié)合律 所以Q=b*A=b*(a*G)=(b*a)*G=(a*b)*G=a*(b*G)=a*B=Q (交換律和結(jié)合律,總結(jié),算法缺陷,存在問題： 迪菲赫爾曼密鑰交換本身并沒有提供通訊雙方的身份驗(yàn)證服務(wù)，因此它很容易受到中間人攻擊。 一個(gè)中間人在信道的中央進(jìn)行兩次迪菲赫爾曼密鑰交換，一次和Alice另一次和Bob，就能夠成功的向Alice假裝自己是Bob，反之亦然。而攻擊者可以解密（讀取和存儲(chǔ)）任何一個(gè)人的信息并重新加密信息，然后傳遞給另一個(gè)人。因此通常都需要一