素数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同理计算出密钥.
那么,这两个密钥是相同的.
上面的等式我试了一下成立,但还没有理解,先求个余数再乘n次方居然也可以保持结果相同,数学真有意思.
就这样,用户AB都自己随便凑了个数,得到了相同密钥,中间人监听也得不到有用信息.不过,如果中间人假冒A与B,同时拿两份密钥,DH算法一样可以被攻破.