江苏龙网

  1. 主页 > 生活百科 > >

DH算法原理( 二 )

DH算法


7^x mod 15：
7^1 mod 15 = 7
7^2 mod 15 = 4
7^3 mod 15 = 13
7^4 mod 15 = 1
7^5 mod 15 = 7
7^6 mod 15 = 4
7^7 mod 15 = 13
7^7 mod 15 = 1
......
看到规律了吗？7^x mod 15的结果一共才4种，并且周期循环 。
这也就意味着中间人获取到了Pb = 4，中间人不一定需要知道Alice原始的随机值（私钥）是什么，只要在[1 , 14]中随便选择一个满足7^x mod 15 = 13的值进行计算S = 4^7 mod 15 = 4^11 mod 15 = 4 都能正确计算共享密钥 。换句话说，中间人不需要暴力遍历[1 , 14]中的所有数就能计算共享密钥 。
所以我们选择(b, p)的原则就是，G = b^x mod p,
当x遍历[1, p -1]时，G也遍历了一遍[1, p -1]，这样中间人即使暴力破解，在P很大的时候，暴力破解是非常难的 。
DH背后的数学&DH算法证明
设 已知 二元组(q, p)
Alice 生成随机值a，计算q^a mod p = Ga
Bob 生成随机值b，计算q^b mod p = Gb
Alice 计算Sa =Gb^a mod p
Bob 计算Sb = Ga^b mod p
我们需要证明Sa=Sb
Sa = Gb^a mod p
= (q^b mod p)^a mod p
令q^b mod p = T，则q^b = kp + T，也即T = q^b - kp
Sa = (q^b mod p)^a mod p
= (T)^a mod p
=(q^b - kp)^a mod p
由于对 (q^b - kp)^a展开，除了第一项为q^(ab)以及最后一项为(kp)^a，其余每一
项均存在p，所以计算(q^b - kp)^a mod p之后，只保留了第一项，即Sa = q^(ab) mod p
同理可正Sb = q^(ba) mod p = Sa
原根
我们在上一节例二中讲到，我们选择的(q, p)尽可能的使得当x遍历[1, p -1]时，
b^x mod p也遍历了一遍[1, p -1] 。我们就来介绍一下原根 。


推荐阅读


上一篇：拿破仑说过什么话 一句话评价拿破仑

下一篇：梦见螃蟹从自己身体里出来 梦见从身上拽下好多螃蟹