DH密鑰交換算法ppt課件

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

2、Hellmankey exchange，簡稱“DH”） 是一種安全協(xié)議。它可以讓雙方在完全沒有對方任何預先信息的條件下通過不安全信道建立起一個密鑰。這個密鑰可以在后續(xù)的通訊中作為對稱密鑰來加密通訊內容,原根與階,性質： 1）所有的素數(shù)都有原根。 2）不是所有的整數(shù)都有原根,一些數(shù)學概念,DH算法,定理證明,定理： 設 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)，與階的定義矛盾。故假設不成立,推論： 如果a是素數(shù)p的一個原根，那么數(shù)值： a modp，a2 modp，a(p-1) modp 是各不相同的整數(shù)，且以某種排列方式組成了從1到p-1的所有整數(shù),DH算法,定理、原根舉例,gcd(a, p) = 1，a與p互質，互質的數(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的一個原根,DH算法,DH算法證明,思考： 為什么DH算法p需要是素數(shù)？a要是p的原根,DH算法,算法本質,Diffie-Hellman 算法的有效性依賴于計算離散對數(shù)的難度，其含義是：當已知大素數(shù)p和它的一個原根a后，對給定的Y，要計算x，被認為是很困難的，而給定x計算Y卻相對容易,DH算法,例1： 按照參數(shù)的選區(qū)原則，p取一個素數(shù)，a是p的一個原根，取 (a, p) = (3,

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

6、e 選擇一個范圍在1, p-1的隨機數(shù)，為Xa= 3 （2）Alice 計算Ya = aXa mod p =73 mod 15 = 13 （3）Bob選擇一個范圍在1, p-1的隨機數(shù)，為Xb = 2 （4）Bob計算Yb = aXb mod p = 72 mod 15 = 4 （5）Alice和Bob交換Ya和Yb （6）Alice計算共享密鑰K = YbXa mod p = 43 mod 15 = 4 （7）Bob計算共享密鑰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的結果一共才4種，并且周期循環(huán)。 這也就意味著中間人獲取到了Yb = 4，攻擊者不一定需要知道Alice原始的隨機值（私鑰）是什么，只要在1 , 14中隨便選擇一個滿足7Xa mod 15 = 13的值進行計算K = YbXa mod p = 43 mod 15 = 47 mod 15 = 4 都能正確計算共享密鑰。換句話說，攻擊者不需要暴力遍歷1 , 14中的所有數(shù)就能計算共享密鑰,思

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

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