Diffie-Hellman算法的安全性基于在有限域上计算离散对数非常困难

Diffie-Hellman算法的安全性基于在有限域上计算离散对数非常困难

Diffie-Hellman算法的安全性基于在有限域上计算离散对数非常困难。

定义素数p的本原根(Primitive Root)为一种能生成[1, p-1]所有数的一个数，即如果a为p的本原根，则：

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

两两互不相同，构成[1, p-1]的全体数的一个排列(比如：p=11，a=2)。

对于任意数b(bb = a^i mod p, 0<=i<=p-1

称指数i为以a为底模p的b的离散对数。

如果Tom和Kite想在不安全的信道上交换密钥，他们可以采用如下步骤：

1、Tom和Kite协商一个大素数p及p的本原根a，a和p可以公开；

2、Tom秘密生成一个随机数x，计算X=a^x mod p，然后把X发送给Kite；

3、Kite秘密生成一个随机数y，计算Y=a^y mod p，然后把Y发送给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的数值，但是除非能计算出离散对数，恢复出x和y(i=log_a(p*z+b),z是大于等于0的整数)，否则就无法得到k，因此k为Tom和Kite相互通信的秘密密钥，可作为对称加密的密钥。