第一篇：Diffie-Hellman算法的安全性基于在有限域上計算離散對數(shù)非常困難

Diffie-Hellman算法的安全性基于在有限域上計算離散對數(shù)非常困難

Diffie-Hellman算法的安全性基于在有限域上計算離散對數(shù)非常困難。

定義素數(shù)p的本原根(Primitive Root)為一種能生成[1, p-1]所有數(shù)的一個數(shù)，即如果a為p的本原根，則：

a mod p, a^2 mod p,..., a^p-1 mod p

兩兩互不相同，構(gòu)成[1, p-1]的全體數(shù)的一個排列(比如：p=11，a=2)。

對于任意數(shù)b(b

b = a^i mod p, 0<=i<=p-1

稱指數(shù)i為以a為底模p的b的離散對數(shù)。

如果Tom和Kite想在不安全的信道上交換密鑰，他們可以采用如下步驟：

1、Tom和Kite協(xié)商一個大素數(shù)p及p的本原根a，a和p可以公開；

2、Tom秘密生成一個隨機數(shù)x，計算X=a^x mod p，然后把X發(fā)送給Kite；

3、Kite秘密生成一個隨機數(shù)y，計算Y=a^y mod p，然后把Y發(fā)送給Tom；

4、Tom計算k1=Y^x mod p;

5、Kite計算k2=X^y mod p；

則k1和k2是恒等的，因為：

k1=Y^x mod p=(a^y)^x mod p=a^x)^y mod p=X^y mod p=k2

搭線竊聽者可以得到a、p、X和Y的數(shù)值，但是除非能計算出離散對數(shù)，恢復(fù)出x和y(i=log_a(p*z+b),z是大于等于0的整數(shù))，否則就無法得到k，因此k為Tom和Kite相互通信的秘密密鑰，可作為對稱加密的密鑰。