ECC(5):ECC Diffie-Hellman 密鑰交換算法
關於 Diffie-Hellman 算法,請參見《漂洋過海來看你》,本文不再重複,本文只講述基於 ECC 構建的 Diffie-Hellman 密鑰交換算法。
無論是原生的還是基於 ECC 構建的,Diffie-Hellman 算法的場景和目標都是一樣的,如圖1所示。
圖1 Diffie-Hellman 算法的場景和目標
圖1講述的是對稱加密機制中密鑰交換(分發)的故事。對稱加密中,通信的雙方(加密/解密)使用的是相同的密鑰 K。密鑰 K 是對稱加密的靈魂,如果 K 洩密,那什麼樣的加密算法都沒有意義。
假設 A 生成了密鑰 K,他該用什麼方法告知 B 密鑰是 K 呢?通過明文將 K 發送給 B?顯然,這種方法非常容易洩密。用飛鴿傳書?似乎更加不可行 .
Diffie-Hellman 算法開創了密鑰安全分發的先河——更準確地說,是開創了公鑰加密的先河——圖1是對它的一個抽象表達。
A 通過明文給 B 發送了一個 x,B 也通過明文給 A 發送了一個 y。A 利用 x,B 利用 y,兩者獨立計算,但是他們所計算出的數值 K 相同,而其他人即使知道了 x 和 y(因為 x 和 y 都是明文傳輸,其他人很容易獲得),也無法計算出 K。
這就是 Diffie-Hellman 密鑰交換的基本思想——用於生產密鑰的原材料 x、y 都是公開的,卻能構建出安全的密鑰 K。
基於 ECC 的 Diffie-Hellman 算法,當然離不開橢圓曲線:Ep(a, b)。需要強調的是,這裡的 p,a,b 都是公開的。另外,在橢圓曲線上選擇一個點 G,G 也是公開的,只不過要求 G 的階數 s 要非常大——具體有多大,請參見《橢圓曲線的 G 點》。
基於橢圓曲線的計算公式:Q = kG,ECC 定義:
(1)k 是私鑰(k 也需要相當大)
(2)Q 是公鑰
ECC 的 Diffie-Hellman 算法,也是從這個公式出發。
首先,對於 A 來說,他選擇 kA 作為自己的私鑰,並且計算出相應的公鑰,
QA = kAG
對於 B 來說,也是同理。他選擇 kB 作為自己的私鑰,並且計算出相應的公鑰,
QB = kBG
下一步就是互相交換。A 將自己的公鑰 QA 通過明文發送給 B,B 將自己的公鑰 QB 發送給 A,如圖2所示。
圖2 交換公鑰
因為 QA,QB 都是公鑰,所以圖2中,兩者的發送都是採用明文形式。
當 A 收到 B 發送過來的 QB 時,他做如下計算
PA = kA * QB
B 也如此,
PB = kB * QA
那麼,PA 和 PB 是什麼關係呢?我們繼續計算
PA = kA * QB = kA * kB * G
PB = kB * QA = kB * kA * G
可以看到,
PA = PB = kA * kB * G
也就是說,
PA = PB = K
K = kA * kB * G
這就意味著,A 和 B 通過互相交換的 QA 和 QB,殊途同歸,得到了同一個值 K,如圖3所示。
圖3 計算密鑰
圖3對於攻擊者而言,由於只能知曉 QA 和 QB,根據橢圓曲線的數學難題,他是無法破解出 K 的。
所以,圖3中的 K(K = kA * kB * G),就可以作為 A 和 B 接下來做對稱加密通信時的對稱密鑰。
當然,K 是橢圓曲線上的一個點,它的表現形式是一個坐標(x,y),而對稱密鑰是一串數字(字符),K 若想稱為對稱密鑰,還需要經過編碼變換——這個話題,且聽下回分解。