Diffle-Hellman密钥交换

数学基础

计算离散对数很困难。

离散对数

素数n的本原根a满足，a的1次方到a的n-1次方 mod n结果不同并且对应1到n-1。（换句话说是1到p-1的置换序列）

对于y=a^x mod p，已知a、x、p计算y容易，但已知y、a、 p ，计算x困难，x被称为离散对数。

至于为什么困难，涉及到相应算法的时间复杂度。计算a的有限次方还行，但猜x的话，就需要遍历了。

算法

借助数学特性，现在我们公开y与a，也就是素数和它的本原根。

用户A随机选择一个秘密的Xa，作为x计算出Ya。用户B同理计算出Yb。

用户A通过计算Yb^Xa mod q产生密钥。用户B同理计算出密钥。

那么，这两个密钥是相同的。

为什么相同呢？毕竟Yb^Xa mod q=(a^Xb mod q)^Xa mod q，也就是a^(Xb*Xa)mod q。

上面的等式我试了一下成立，但还没有理解，先求个余数再乘n次方居然也可以保持结果相同，数学真有意思。

就这样，用户AB都自己随便凑了个数，得到了相同密钥，中间人监听也得不到有用信息。不过，如果中间人假冒A与B，同时拿两份密钥，DH算法一样可以被攻破。