全球首创：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

folklore

想法很好啊， 就是 a^n的n比较大， 计算a^n没什么问题， 从1循环到n要老命了。

windoze

大哥，DH现在一般都要1024，也就是说N大约是2^1024这么大，你确定你真想遍历一遍？

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就行了

windoze

回复 4# zuoyuandh

你这个“破解”方式其实就是遍历密钥空间的暴力破解，任何一种加密算法都无法“抵御”这种“破解”。
但在DH中，X^N mod Q这一类离散对数运算成本很高，而且一般实际应用中N和Q都有几百几千位，你不可能有足够的计算资源干这事。
不信你自己试试DH128之类的短密钥就可以估算一下破解成本。

folklore

回复 5# zuoyuandh


    不用·1024·位， 你试一下：

1. volatile int k=0;
   
2. for(int i=0; i<2^128; i++){
   
3.   k++;
   
4. }

复制代码

看要算几年。

zuoyuandh

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

zuoyuandh

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

zuoyuandh

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