當前位置首頁(yè) > 電腦常識

DH算法圖解+數學(xué)證明 淺顯易懂

閱讀次數:4089 次  來(lái)源:管理員  發(fā)布時(shí)間:

前幾天和同事討論IKE密鑰交換流程時(shí),提到了Diffie-Hellman交換。DH算法最主要的作用便是在不安全的網(wǎng)絡(luò )上成功公共密鑰(并未傳輸真實(shí)密鑰)。但由于對于DH算法的數學(xué)原理則不清楚,因此私下對DH算法進(jìn)行一個(gè)簡(jiǎn)單學(xué)習。

1. DH算法的交互流程:

Alice和Bob都有一個(gè)只有自己知道的私鑰,在特定規則(g, a, p)下生成自己的公鑰A; Alice將自己的公鑰A,連同g, p共同發(fā)給BobBob在收到Alice發(fā)送來(lái)的公鑰A, g, p后,先使用相同的規則((g, a, p))生成自己的公鑰B;在使用Alice的公鑰A計算生成共享密鑰KBob將自己的公鑰B發(fā)送給Alice即可。(Alice已經(jīng)有g(shù), p, 因此無(wú)需在發(fā)送)Alice在接收到Bob的公鑰B后,使用相同的規則計算成功共享密鑰K

至此,Alice 和 Bob便同時(shí)擁有了共享密鑰K。此時(shí)由于各自的私鑰a,b未在互聯(lián)網(wǎng)上傳播,因此即使存在窺探者Eve,他僅通過(guò)公開(kāi)的A\B\g\p在短時(shí)間內無(wú)法破解出a,b,K。因此DH算法便可以在不安全的網(wǎng)絡(luò )上協(xié)商出密鑰,基于此構建安全的加密通道。

2. 疑問(wèn):Alice和Bob最后計算的K值一樣嗎?

對于DH整個(gè)交互流程來(lái)說(shuō),比較簡(jiǎn)單,基本都可以理解。但是忽然說(shuō)最后的K值相等,這多少有點(diǎn)突然和難以置信,讓人有點(diǎn)猝不及防。

書(shū)本上都是這樣解釋的:

所以Alice和Bob的共享密鑰K是相同的。但是,總感覺(jué)沒(méi)有g(shù)et到要領(lǐng)和精髓。因為我不知道mod(求余)的運算規則,不知道如下等式是否成立???

因此半夜凌晨1點(diǎn)從剛暖熱乎的被窩又爬了出來(lái),想要證明下他們給的公式是否正確( 其實(shí)當成定理記住也就OK了,不過(guò)我嘛,還是爬起來(lái)了)。證明這個(gè)公式也很簡(jiǎn)單:將求余運算轉換為加減乘除運算,然后利用二項式展開(kāi)公式便可以得到答案。

至于為什么要將求余運算轉換為加減乘除四則運算,原因是我不知道求余算法的規則,不然我也不需要多此一舉了。

證明開(kāi)始:

令:

則:

根據①②式可得:

將③帶入上式可得:

使用二項式展開(kāi)公式將

上一篇:怎樣做好指甲保養?
下一篇:ECDH算法介紹