DH算法圖解+數(shù)學(xué)證明 淺顯易懂
前幾天和同事討論IKE密鑰交換流程時(shí),提到了Diffie-Hellman交換。DH算法最主要的作用便是在不安全的網(wǎng)絡(luò)上成功公共密鑰(并未傳輸真實(shí)密鑰)。但由于對(duì)于DH算法的數(shù)學(xué)原理則不清楚,因此私下對(duì)DH算法進(jìn)行一個(gè)簡(jiǎn)單學(xué)習(xí)。
1. DH算法的交互流程:
Alice和Bob都有一個(gè)只有自己知道的私鑰,在特定規(guī)則(g, a, p)下生成自己的公鑰A; Alice將自己的公鑰A,連同g, p共同發(fā)給BobBob在收到Alice發(fā)送來的公鑰A, g, p后,先使用相同的規(guī)則((g, a, p))生成自己的公鑰B;在使用Alice的公鑰A計(jì)算生成共享密鑰KBob將自己的公鑰B發(fā)送給Alice即可。(Alice已經(jīng)有g(shù), p, 因此無需在發(fā)送)Alice在接收到Bob的公鑰B后,使用相同的規(guī)則計(jì)算成功共享密鑰K
至此,Alice 和 Bob便同時(shí)擁有了共享密鑰K。此時(shí)由于各自的私鑰a,b未在互聯(lián)網(wǎng)上傳播,因此即使存在窺探者Eve,他僅通過公開的A\B\g\p在短時(shí)間內(nèi)無法破解出a,b,K。因此DH算法便可以在不安全的網(wǎng)絡(luò)上協(xié)商出密鑰,基于此構(gòu)建安全的加密通道。
2. 疑問:Alice和Bob最后計(jì)算的K值一樣嗎?
對(duì)于DH整個(gè)交互流程來說,比較簡(jiǎn)單,基本都可以理解。但是忽然說最后的K值相等,這多少有點(diǎn)突然和難以置信,讓人有點(diǎn)猝不及防。
書本上都是這樣解釋的:
所以Alice和Bob的共享密鑰K是相同的。但是,總感覺沒有g(shù)et到要領(lǐng)和精髓。因?yàn)槲也恢續(xù)od(求余)的運(yùn)算規(guī)則,不知道如下等式是否成立???
因此半夜凌晨1點(diǎn)從剛暖熱乎的被窩又爬了出來,想要證明下他們給的公式是否正確( 其實(shí)當(dāng)成定理記住也就OK了,不過我嘛,還是爬起來了)。證明這個(gè)公式也很簡(jiǎn)單:將求余運(yùn)算轉(zhuǎn)換為加減乘除運(yùn)算,然后利用二項(xiàng)式展開公式便可以得到答案。
至于為什么要將求余運(yùn)算轉(zhuǎn)換為加減乘除四則運(yùn)算,原因是我不知道求余算法的規(guī)則,不然我也不需要多此一舉了。
證明開始:
令:
則:
根據(jù)①②式可得:
將③帶入上式可得:
使用二項(xiàng)式展開公式將
- 上一篇:怎樣做好指甲保養(yǎng)?
- 下一篇:ECDH算法介紹