裂解diffie-hellman

Question

我想要做一个应用程序，演示对表现不佳的diffie-hellman的攻击。为了计算密钥，我需要实现一个可以使用共享变量的算法。在寻找资源的时候，我不断地遇到僵局攻击。但是，我不能真正过滤掉从所有HTTP协议信息中运行的数字。

如果有人能提供som资源来指出正确的方向，或者是如何从已知变量成功地计算密钥的公式。非常感谢！

编辑

我找到了这个资源，看起来很有希望。http://index-of.es/Miscellanous/How%20To%20Backdoor%20Diffie-Hellman.pdf

第6页写着

要攻击Diffie-Hellman密钥交换，可以从对等方的公钥ya =ya (mod p)中提取密钥a。然后，可以使用另一个对等方的公钥yb =yb (mod p)计算共享密钥g (mod p)。这样做的简单方法是计算g的每个幂(同时跟踪指数)，直到找到公钥为止。这被称为试乘，平均需要q2运算才能找到一个解(Q是基的顺序)。更有效的是，在期望的√q步骤中计算离散对数的算法

我把这个翻译成

计算g g^1 mod(p), g^2 mod(p), g^3 mod(p)..g^n mod(p)的每个幂

这是可行的，但它需要将指数与公式分开才能工作。这对我来说很难。

如何将a从p^a mod(p)中分离出来？

Answer 1

对Diffie-Hellman的一个有趣的密码分析攻击是小子群限制攻击.如果不谨慎地选择DH参数，则攻击有效。以下是对其工作原理的简要说明。

？生署在乘法组工作。假设我们在Z^*_p工作。由于p是素数，该群(p-1)的阶是复合的，因此根据拉格朗日定理存在子群。攻击者通过干扰和修改通信，基本上将密钥空间缩小到其中一个具有小得多的订单的子组。

让我们的DH组是(Z_p^*,*)，\alpha是使用的原始根。通常，Alice计算一个随机的s_a并将其保密。艾丽斯将\alpha^{s_a}发送给鲍勃，但攻击者伊芙首先收到了。Eve通过搜索(p-1)的因子来查找可能的子组，并找到一个小的因子q。根据拉格朗日定理，她知道存在一个阶q子群。她计算t=\frac{p-1}{q}并发送Bob (\alpha^{s_a})^t。Bob还计算他的秘密随机值s_b和共享秘密(\alpha^{ts_a})^{s_b}。鲍勃然后发送爱丽丝\alpha^{s_b}，但夏娃拦截。伊芙发送爱丽丝(\alpha^{s_b})^t，爱丽丝也将共享的秘密计算为(\alpha^{ts_b})^{s_a}。两者都有共同的秘密，是的，但他们的共享秘密是形式(\alpha^t)^x。这种形式的数字是由生成\alpha^t的子群生成的，该子群已知为q阶。由于q很小(根据我们对DH参数选择不当的假设)，Eve可以通过蛮力简单地计算DH离散对数问题，因为试验要少得多。

如何保护？

选择p，以便p=2q+1，其中q也是素数(参见苏菲-杰曼素数)。有了这个属性，组顺序将是p-1=2q。由于q是素数，只有p-1的因子为2和q。因此，当设置与DH共享的秘密时，请检查您的组订单是否为2。如果是这样的话，您知道您已被攻击。