密碼學(xué)專題 - 密鑰交換算法

10. 密鑰交換算法

10.1 Diffie-Hellman 算法

Diffie-Hellman 算法是第一個(gè)公開密鑰算法，早在 1976 年就發(fā)明了。其安全性源于在有限域上計(jì)算離散對(duì)數(shù)比計(jì)算指數(shù)更為困難。Diffie-Hellman 算法能夠用于密鑰分配 (Alice 和 Bob 能用它產(chǎn)生秘密密鑰)，但是它不能用于加密或解密消息。

數(shù)學(xué)原理很簡單。首先，Alice 和 Bob 協(xié)商一個(gè)大的素?cái)?shù) $n$ 和 $g$ ， $g$ 是模 $n$ 的本原元。這兩個(gè)整數(shù)不必是秘密的，故 Alice 和 Bob 可以通過即使是不安全的途徑協(xié)商它們。它們可在一組用戶中公用。

協(xié)議如下：

Alice 選取一個(gè)大的隨機(jī)整數(shù) $x$ ，并發(fā)送給 Bob： $X=g^x \ mod \ n$ 。
Bob 選取一個(gè)大的隨機(jī)整數(shù) $y$ ，并發(fā)送給 Alice： $Y=g^y \ mod \ n$ 。
Alice 計(jì)算 $k = Y^x \ mod \ n$ 。
Bob計(jì)算 $k' = X^y \ mod \ n$ 。

$k$ 和 $k'$ 都等于 $g^{xy} \ mod \ n$ 。即使線路上的竊聽者也不可能計(jì)算出這個(gè)值，他們只知道 $n$ 、 $g$ 、 $X$ 、 $Y$ 。除非他們計(jì)算離散對(duì)數(shù)，恢復(fù) $x$ 、 $y$ ，否則無濟(jì)于事。因此 $k$ 是 Alice 和 Bob 獨(dú)立計(jì)算的秘密密鑰。

$g$ 和 $n$ 的選取對(duì)系統(tǒng)的安全性有很大的影響。 $(n-1)/2$ 也應(yīng)該是一個(gè)素?cái)?shù)。最重要的是 $n$ 應(yīng)該很大：因?yàn)橄到y(tǒng)的安全性取決于與 $n$ 同樣長度的數(shù)的因子分解的難度?？梢赃x擇任何滿足模 $n$ 的本原元 $g$ ，沒有理由不選擇所能選擇的最小 $g$ —— 通常只是個(gè) 1 位數(shù) (實(shí)際上 $g$ 不必是素?cái)?shù)，但它必須能產(chǎn)生一個(gè)大的模 $n$ 的乘法組子群)。