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

ECDH算法介紹

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

1.1、橢圓曲線(xiàn)介紹

ECC(Elliptic Curves Cryptography,橢圓曲線(xiàn)加密)是一種公開(kāi)密鑰算法。1985年,Neal Koblitz和Victor Miller分別獨立提出了ECC?;拘螤羁梢詤⒖既缦聢D:

 

圖3:橢圓曲線(xiàn)示例

1.2、圖解橢圓曲線(xiàn)

橢圓曲線(xiàn)有兩個(gè)特點(diǎn):

如果你在上方隨便畫(huà)一個(gè)點(diǎn),那么下方也一定有一個(gè)對稱(chēng)的點(diǎn),上下方距離水平線(xiàn)X軸是相同的。隨便在圖形上畫(huà)兩個(gè)點(diǎn),讓這兩個(gè)點(diǎn)連成線(xiàn)然后延長(cháng)會(huì )經(jīng)過(guò)第三個(gè)點(diǎn),當然除了垂直線(xiàn)以外。

 

圖4:曲線(xiàn)A點(diǎn)到E點(diǎn)步驟

根據這兩個(gè)特點(diǎn)我們就可以做文章了。如果有A,B兩個(gè)點(diǎn),延長(cháng)以后會(huì )經(jīng)過(guò)第三個(gè)點(diǎn),而這第三個(gè)點(diǎn)以X軸為中心是會(huì )有一個(gè)點(diǎn)與其對稱(chēng),我們就把這個(gè)對稱(chēng)的點(diǎn)先稱(chēng)為C點(diǎn)。這里頭就像是運算過(guò)程,A和B得出C,在這里我就把運算過(guò)程稱(chēng)為 “點(diǎn)運算”,A點(diǎn)B得到C,這個(gè) “點(diǎn)運算”其實(shí)就是橢園曲線(xiàn)上的加法運算,但為了讓你們不與傳統加法運算弄混,這里先使用“點(diǎn)運算”的說(shuō)法。

現在我們把A和C進(jìn)行連線(xiàn),同樣經(jīng)過(guò)了第三個(gè)點(diǎn),第三個(gè)點(diǎn)也有一個(gè)對稱(chēng)的點(diǎn),這里稱(chēng)為D點(diǎn),也就是A點(diǎn)C得到D,我們再把A和D連線(xiàn),也經(jīng)過(guò)了第三個(gè)點(diǎn),第三個(gè)點(diǎn)也有一個(gè)對稱(chēng)的點(diǎn),這里稱(chēng)為E點(diǎn),也就是A點(diǎn)D得到E。

問(wèn)題:已知起點(diǎn)是A,終點(diǎn)是E,請問(wèn)起點(diǎn)A經(jīng)過(guò)多少次點(diǎn)運算得到E?我們很難知道經(jīng)過(guò)了多少次,這就很符合我們前面說(shuō)的公鑰加密的特點(diǎn):正向簡(jiǎn)單,逆向困難

 

圖5:加密容易,解密困難

我們還要考慮一種特殊情況,如果我們取一個(gè)點(diǎn),命名為P,然后畫(huà)一條直線(xiàn),結果發(fā)現這條直線(xiàn)只能與橢圓曲線(xiàn)相交于一個(gè)點(diǎn),而不是剛剛所說(shuō)的一共有三個(gè)點(diǎn),這種情況怎么定義運算呢?

首先解釋一下這是一條切線(xiàn),如果不記得什么是切線(xiàn),那就想象這里有一個(gè)圓,而切線(xiàn)是垂直于經(jīng)過(guò)切點(diǎn)的半徑,還不明白也沒(méi)關(guān)系,現在點(diǎn)P身處的這條直線(xiàn)相交橢圓曲線(xiàn)后,也有一個(gè)對稱(chēng)的點(diǎn),這里先命名為Q點(diǎn), 現在重點(diǎn)來(lái)了!因為點(diǎn)P初始沒(méi)有和其他點(diǎn)連成線(xiàn),不是剛剛那種開(kāi)始就有兩個(gè)點(diǎn)來(lái)連線(xiàn),因此這里就認為是P點(diǎn)P的運算,也就是自己點(diǎn)自己,所以Q就是P點(diǎn)P的運算結果,也就是兩介P得到Q,我們就把點(diǎn)Q稱(chēng)為2P,因為是兩個(gè)P得出的點(diǎn),你也可以理解為P+P=2P。

 

圖6:曲線(xiàn)中的切線(xiàn)

現在P與2P連線(xiàn),也經(jīng)過(guò)了第三個(gè)點(diǎn),第三個(gè)點(diǎn)也有一個(gè)對稱(chēng)的點(diǎn),P+2P就等于3P,這個(gè)點(diǎn)就是3P,那么這個(gè)過(guò)程可以一直延續下去,我們是可以得到6P這個(gè)點(diǎn)的,6P這個(gè)點(diǎn)就很有靈性了,比如3P點(diǎn)3P,兩次的話(huà)可以得到6P,也就是3P乘以2得到6P,那2P點(diǎn)2P,三次的話(huà)也可以得到6P,也就是2P乘以3得到6P,其實(shí)就是簡(jiǎn)單的乘法問(wèn)題,只不過(guò)是橢園曲線(xiàn)上的,不要小看這簡(jiǎn)單的表示方法,等會(huì )你可能就會(huì )對著(zhù)屏幕說(shuō)“握草”。

 

圖7:6P的生成

1.3、笛福赫爾曼(Diffie-Hellman)算法

DH 算法又稱(chēng)“Diffie–Hellman 算法”,像往常的算法名字一樣,這是用倆個(gè)數學(xué)牛人的名字來(lái)命名的算法,實(shí)現安全的密鑰交換,通訊雙方在完全沒(méi)有對方任何預先信息的條件下通過(guò)不安全信道創(chuàng )建起一個(gè)密鑰。

如下圖示例:首先兩個(gè)要溝通的對象需要確定兩個(gè)參數,參數P和參數G,參數P,故名意思是一個(gè)質(zhì)數,因為P是Prime的縮寫(xiě),而參數G是Generator的縮寫(xiě),這里就不詳細解釋G的緣由了,因為涉及到一些數學(xué)的知識。這里我選一個(gè)簡(jiǎn)單的質(zhì)數23,因為23乘以1等于23,沒(méi)有其它整數相乘可以得到23了,而參數G這里選擇5,這兩個(gè)參數是可以公開(kāi)的,所以黑客知道也沒(méi)關(guān)系。

 

圖8:DH算法示例

現在就可以套用公式1了,5的隨機數次方除以23來(lái)求余數,這個(gè)公式也是公開(kāi)的,黑客知道也沒(méi)毛病,現在兩邊要各自生成一個(gè)隨機數,蒜老大生成了6,油大叔生成了15,各自生成的隨機數套入這個(gè)公開(kāi)的公式,也就是蒜老大進(jìn)行5的6次方要除以23得到余數8,油大叔進(jìn)行5的15次方要除以23得到余數19,各自把生成的余數發(fā)送給對方。

對方收到后套用公式2,各自收到的余數的隨機數次方除以參數P求出新的余數,對于蒜老大,就是用收到的19進(jìn)行6次方運算再除以23得到余數2,這里的數字6就是蒜大哥自己生成的隨機數,23就是前面定義好的參數P,對于油大叔來(lái)說(shuō),就是用收到的8進(jìn)行15次方運算再除以23得到余數2,這里的數字15就是油大叔自己生成的隨機數,23也是前面定義好的參數P,現在大家可以看到兩邊得到的余數都是一樣的,都是數字2,兩邊就可以用這個(gè)數字2來(lái)對后續的對話(huà)進(jìn)行加密了,沒(méi)人知道原來(lái)他們用這個(gè)2來(lái)加密后續的對話(huà),當然了實(shí)際上的隨機數和質(zhì)數其實(shí)并沒(méi)有這么簡(jiǎn)單,通常都建議質(zhì)數至少要有2048比特的長(cháng)度,就是為了防止破解。

1.4、ECDH算法

ECDH是Elliptic Curve Diffie-Hellman,它一種基于ECC的密鑰協(xié)商算法。ECDH是笛福赫爾曼(Diffie-Hellman)算法的變種,它是一種密鑰協(xié)商協(xié)議,定義了密鑰怎么樣在通信雙方之間生成和交換。其思路過(guò)程與笛福赫爾曼密鑰協(xié)商算法基本相同,只是在具體的協(xié)商計算中使用ECC。

如下圖示例:Alice需要生成一個(gè)私鑰小a,然后再確定橢圓曲線(xiàn)上的一個(gè)點(diǎn):G,這個(gè)G點(diǎn)是公開(kāi)的,是大家都可以有的G點(diǎn),接著(zhù)Alice需要生成公鑰大A,公鑰就利用前面說(shuō)到的橢圓曲線(xiàn)來(lái)運算,也就是公鑰大A等于小a點(diǎn)G,這里的意思就是G這個(gè)點(diǎn)進(jìn)行點(diǎn)運算,次數是a,也就是G點(diǎn)G點(diǎn)G點(diǎn)…一共a次,得到了橢圓曲線(xiàn)上的點(diǎn)大A,現在A(yíng)lice把大A和G發(fā)送給Bob,也就是大A和G是公開(kāi)的,有同學(xué)可能就在想,別人知道大A和G,那小a不就很容易算出來(lái)嗎?其實(shí)前面已經(jīng)說(shuō)了,一定不容易,知道起點(diǎn)和終點(diǎn),但是中間經(jīng)歷多少次是非常難知道的,這就是把橢園曲線(xiàn)加進(jìn)來(lái)的奧義。

 

圖9:ECDH算法示例

Bob收到后,也生成了一個(gè)私鑰小b,然后生成橢園曲線(xiàn)上的一個(gè)新點(diǎn)(大B),這個(gè)大B就是G點(diǎn)進(jìn)行小b次運算得到的,也就是G點(diǎn)G點(diǎn)G點(diǎn)…一共b次,現在Bob把生成的大B發(fā)送給Alice,別人知道大B和大G兩個(gè)點(diǎn)也很難得到小b,還是那句話(huà):中間經(jīng)歷多少次很難知道?,F在A(yíng)lice用私鑰小a和收到的大B進(jìn)行運算得到新的密鑰,Bob用私鑰小b和收到的大A進(jìn)行運算也得到了新的密鑰,這個(gè)新的密鑰就只有他們知道,也就是會(huì )話(huà)密鑰,而且這個(gè)密鑰必須是相同的。相信你對于這個(gè)運算還有點(diǎn)懵,你們看Alice這邊,大B其實(shí)就等于小b點(diǎn)G,直接從Bob那邊把等式代入就明白了,而在Bob這邊,大A其實(shí)就等于小a點(diǎn)G,直接從Alice那邊把等式代入就明白了,這樣一看就知道密鑰是相同的,只不過(guò)小a和小b互換了位置。如果你還看不出,假設a等于3,b等于2,不管是2乘以3,還是3乘以2,其實(shí)就等于6G了,也就是前面提及到的運算方法,這個(gè)密鑰交換過(guò)程也就是ECDHE的原理,ECDHE就是橢園曲線(xiàn)和DH混合起來(lái)的密鑰交換算法。

上一篇:DH算法圖解+數學(xué)證明 淺顯易懂
下一篇:沒(méi)有了