全球首创：Diffie-Hellman攻击方法

zuoyuandh

我们先来看下Diffie-Hellman算法

算法描述基于原根的定义及性质，可以定义Diffie-Hellman密钥交换算法.该算法描述如下：
1，有两个全局公开的参数，一个素数q和一个整数a,a是q的一个原根.
2，假设用户A和B希望交换一个密钥，用户A选择一个作为私有密钥的随机数XA(XA<q)，并计算公开密钥YA=a^XA mod q。A对XA的值保密存放而使YA能被B公开获得。类似地，用户B选择一个私有的随机数XB<q，并计算公开密钥YB=a^XB mod q。B对XB的值保密存放而使YB能被A公开获得.
3，用户A产生共享秘密密钥的计算方式是K = (YB)^XA mod q.同样，用户B产生共享秘密密钥的计算是K = (YA)^XB mod q.这两个计算产生相同的结果： K = (YB)^XA mod q = (a^XB mod q)^XA mod q = (a^XB)^XA mod q （根据取模运算规则得到） = a^(XBXA) mod q = (a^XA)^XB mod q = (a^XA mod q)^XB mod q = (YA)^XB mod q 因此相当于双方已经交换了一个相同的秘密密钥.
4，因为XA和XB是保密的，一个敌对方可以利用的参数只有q,a,YA和YB.因而敌对方被迫取离散对数来确定密钥.例如，要获取用户B的秘密密钥，敌对方必须先计算 XB = inda,q(YB) 然后再使用用户B采用的同样方法计算其秘密密钥K. Diffie-Hellman密钥交换算法的安全性依赖于这样一个事实：虽然计算以一个素数为模的指数相对容易，但计算离散对数却很困难.对于大的素数，计算出离散对数几乎是不可能的. 下面给出例子.密钥交换基于素数q = 97和97的一个原根a = 5.A和B分别选择私有密钥XA = 36和XB = 58.每人计算其公开密钥 YA = 5^36 = 50 mod 97 YB = 5^58 = 44 mod 97 在他们相互获取了公开密钥之后，各自通过计算得到双方共享的秘密密钥如下： K = (YB)^XA mod 97 = 44^36 = 75 mod 97 K = (YA)^XB mod 97 = 50^58 = 75 mod 97 从|50,44|出发，攻击者要计算出75很不容易. 下图给出了一个利用Diffie-Hellman计算的简单协议.

那么我们的攻击方法来了 a^1 a^2 a^3 穷举 到某个值应该就循环了 有限对的XA-YA XB-YB   a^n mod q=1时就进入循环了 那么知道a和q 基本就可以破解了 产生的YA YB 肯定在穷举列表中了
                                                                                                            作者 湖南长沙 左远 2016/3/2

zuoyuandh

不用遍历一遍 a^n mod q的值有重复就进入循环了 而且N大约是2^1024 不错 但对于一个加密系统来说N是固定的 遍历到有重复就行 应该是花费很小的 构造N都需要很多CPU时间 一次算出来意味可以破解所有这个a-N的加密 花费是值得的

zuoyuandh

算法的话 a^(n+1) mod q =(a^n mod q)*a mod q 上一个值可以利用 也就是说 *a 取mod就行了

zuoyuandh

算出来计算量到不会很大 大数乘法和减法就行 倒是存储空间可能不够 极端时比如2^1024 会有 2^1024个数据(抽屉原理 mod值没有重复) 没地方存放 计算这种可能需要很大硬盘的计算机

zuoyuandh

如果较少的数值时就进入循环了 那计算量和空间是够的

zuoyuandh

倒是怎么储存 或者有什么办法缩减储存 比如1000个数存一个数 比较时临时再做乘法 用计算量换储存空间

zuoyuandh

应该还有其他办法可以可以改进

zuoyuandh

如果对手是很重要的系统 把值算到有重复时是值得的

zuoyuandh

而且还可以想办法 比如用个bit数据组 有这个数相应位置1 没有为0 那么算到有重复的时 相应位为1

zuoyuandh

还可以分 a为大数 a为比较小的数(小于q开方) 较小的数有个特点 就是mod q的值很可能是 a的倍数 那么拿到YA时先除a 到小于a时 再在已知列表里找