已知部分信息的 Diffie-Hellman 破解

Question

这是学校作业。

我遇到了在 DH 交换中找到双方私钥的问题。测试中涉及的数字不够大，任务基本上是蛮力的。在任务中，我可以获得素数p、生成器g和Alice的public密钥A。我还获得了使用自定义密钥加密消息和解密消息的方法。

现在我只得到 a 通过简单地遍历整数 i=1...p 并检查是否 g^i mod p == g^A mod p 并立即返回满足要求的第一个值。

但是，根据自动化测试，我的解决方案并不总是正确的。任何人都知道如何甚至是否有可能使用给定的信息找到 a 和 b？

Answer 1

感谢第三方，我破解了DH密码：

public Integer crackAlice() {
        // TODO
        Integer alicePrivate = 0;

        int p = session.getP();
        int g = session.getG();
        int A = session.getAlicesPublicKey();
        // A = g^a mod p


        System.out.println("Alice public A: "+A);
        String message = String.valueOf(156215);

        for (int i = 1; i < p; i++) {
            if (BigInteger.valueOf(g).pow(i).mod(BigInteger.valueOf(p)).equals(BigInteger.valueOf(A))) {
                //System.out.println("\t\t\t\t"+BigInteger.valueOf(g).pow(i));
                alicePrivate = i;
                System.out.println("Potential Alice private a: "+i);
                //break;
            }
        }
        return alicePrivate;
    }

和

public Integer crackBob() {
        // TODO

        Integer bobPrivate = 0;
        Integer a = crackAlice();
        int p = session.getP();
        int g = session.getG();
        int A = session.getAlicesPublicKey();
        String mainMessage = "teade";

        String msg = null;
        try {
            msg = session.getEncrypted(mainMessage);
        } catch (Exception e) {
            e.printStackTrace();
        }

        for (int i = 1; i < p; i++) {
            int ai = a*i;
            int Ai = A*i;
            //System.out.println("a*b = "+ai);
            BigInteger bigintP = BigInteger.valueOf(p);
            if (((BigInteger.valueOf(g).pow(a).mod(bigintP)).pow(i)).mod(bigintP)
                    .equals(((BigInteger.valueOf(g).pow(i).mod(bigintP)).pow(a)).mod(bigintP))) {
                String decrypt = null;
                try {
                    decrypt = session.getDecryptedWithCustomKey(msg, BigInteger.valueOf(g).pow(a*i).mod(bigintP).intValue());
                } catch (Exception e) {
                    e.printStackTrace();
                }
                if (decrypt != null && decrypt.trim().equals(mainMessage)) {
                    bobPrivate = i;
                    break;
                }
            }
        }
        return bobPrivate;
    }

我希望这能帮助其他有类似问题的人。

已知部分信息的 Diffie-Hellman 破解

Diffie-Hellman crack with partial info known

java

algorithm

diffie-hellman