数学基础

计算离散对数很困难。

离散对数

素数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算法一样可以被攻破。