java - El Gamal 数字签名构建莫名其妙地失败

Question

我正在尝试实现 El Gamal 数字签名方案，使用 BigInteger 类生成大素数。 Samantha 生成公钥、私钥，选择一条消息，对其进行签名，然后 Victor 验证签名。

问题:输出总是说签名尚未经过验证，即验证算法在每次执行时都返回 false，这会再次随机化数字。然而，当使用小的、恒定的数字进行测试时，我得到了正确的结果。

问题:我哪里做错了？我似乎无法得出结论。

到目前为止我的代码:

ElGamal_test - 用于预计算步骤和测试的方法

public static void ElGamal_test(){

    // Samantha picks q, a 1024 bit prime and computes p = 2q + 1
    Random rng = new SecureRandom();
    BigInteger q = BigInteger.probablePrime(1024, rng);
    BigInteger p = q.multiply(BigInteger.valueOf(2)).add(BigInteger.ONE);
    //  BigInteger p = BigInteger.valueOf(467);

    // Samantha computes g, a primitive root modulo p
    BigInteger g;

    while(true){
        g = new BigInteger(1024, rng);
        if(g.compareTo(BigInteger.ONE) > 0 &&
           g.compareTo(p) < 0 &&
           !(g.multiply(g).mod(p).equals(BigInteger.ONE)) &&
           !(g.modPow(q, p).equals(BigInteger.ONE)))
            break;
    }
    //  g = BigInteger.valueOf(2);

    // Samantha computes her private key
    BigInteger s;

    while(true){
        s = new BigInteger(1024, rng);
        if(s.compareTo(BigInteger.ONE) > 0 &&
           s.compareTo(p.subtract(BigInteger.ONE)) < 0)
            break;
    }
    //  s = BigInteger.valueOf(127);

    // Samantha computes her public key
    BigInteger v = g.modPow(s, p);

    // Samantha chooses her message, m
    BigInteger m = new BigInteger("100");

    // Samantha signs her message
    BigInteger[] key = Cryptography.ElGamalSignature(p, g, s, m);

    // Victor verifies the signature
    boolean result = Cryptography.ElGamalVerification(p, g, v, m, key);

    String str = (result == true) ? "The signature has been verified" : "The signature has not been verified";
    System.out.println(str);
}

ElGamalSignature - 用于签名算法的方法

public static BigInteger[] ElGamalSignature(BigInteger prime, BigInteger generator, BigInteger privExp, BigInteger doc){

    BigInteger[] signature = new BigInteger[2];
    Random rng = new SecureRandom();

    // Samantha picks the ephemeral key
    BigInteger e;
    while(true){
        e = new BigInteger(1024, rng);
        if(e.compareTo(BigInteger.ONE) > 0 &&
           e.compareTo(prime.subtract(BigInteger.ONE)) < 0 &&
           e.gcd(prime.subtract(BigInteger.ONE)).equals(BigInteger.ONE))
            break;
    }
    //  e = BigInteger.valueOf(213);

    // Samantha computes the signature
    signature[0] = generator.modPow(e, prime);
    signature[1] = (doc.subtract(privExp.multiply(signature[0])))
                 .multiply(e.modInverse(prime.subtract(BigInteger.ONE)))
                 .mod(prime.subtract(BigInteger.ONE));
    return signature;
}

ElGamalVerification - 用于验证算法的方法

public static boolean ElGamalVerification(BigInteger prime, BigInteger generator, BigInteger publicExp, BigInteger doc, BigInteger[] key){

    BigInteger part1 = (publicExp.modPow(key[0], prime).multiply(key[0].modPow(key[1], prime))).mod(prime);
    BigInteger part2 = generator.modPow(doc, prime);

    if(part1.equals(part2))
        return true;
    else
        return false;
}

Answer 1

从评论中扩展； TLDR，你的 p 不是素数。

您引用https://crypto.stackexchange.com/questions/820/how-does-one-calculate-a-primitive-root-for-diffie-hellman这是关于计算 DH 的生成器 g，而不是 p 和 q。

Thomas Pornin 答案的第四段考虑了一个 DH 群，其中素数 p=2q+1 且 q 也是素数。对于这种情况下的 DH，如果生成器的阶数为 q 或 2q 就足够了，但它的阶数不得非常小(2 或 1)。正如他所说，只有 1 的阶数为 1，只有 p-1 的阶数为 2，因此任何其他群元素都可以用作生成器，通常使用 2 是为了方便。

OTOH Jus12 的回答解决了(错误)所述的问题，即当 p=2k+1 且 k 素数时找到一个原根(使用 k 代替 q 作为 Sophie-Germain 素数)，其中原始意味着它的阶数为 2k。为此，需要测试 2..p-1 中的候选者(您将其编码为 > 1 和 < p)，以找到其顺序不是 2 或 k(您的 q)的候选者，这就是您的代码确实如此。与 DH 不同，ElGamal 确实需要原根，因此这是在给定有效 p 和 q 的情况下查找 g 的正确方法。

这两个答案都假设您已经有 p=2q+1 且 q 和 p 为素数。他们没有找到 p 和 q。您的算法首先找到 q 素数(可能是这样，但这已经足够好了)，然后计算 p=2q+1。但你不会验证 p=2q+1 是否是素数——而且通常不是。尽管 p 在这个数学符号中表示素数，但 Java 不会自动将变量命名为 p 素数。 当 p 不是素数时，ElGamal 不起作用。

您需要生成 q 素数并验证 p=2q+1 也是素数，或者生成 p 素数并验证 q=(p-1)/2 也是素数。