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

Question

我正在尝试实施 El Gamal 数字签名方案，使用 BigInteger class 生成大素数。 Samantha 生成 public 密钥，私钥，选择一条消息，对其签名，然后 Victor 验证签名。

问题：输出总是说签名没有被验证，即每次执行时验证算法 returns 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 回答的第 4 段考虑了一个 DH 群，其中素数 p=2q+1 且 q 也是素数。对于这种情况下的 DH，如果生成器的阶数为 q or 2q 就足够了，但它的阶数不能太小（2 或 1）。正如他所说，只有 1 有 1 阶，只有 p-1 有 2 阶，所以任何其他组元素都可以用作生成器，通常 2 是为了方便。

OTOH Jus12 的回答解决了（错误地）陈述的问题，即当 p=2k+1 和 k 素数时找到 primitive 根（使用 k 而不是 q 作为 Sophie -Germain prime) 其中 primitive 意味着它的阶数为 2k。为此，需要在 2..p-1（您将其编码为 > 1 和 < p）中测试候选人，以找到顺序为 not 2 或 k（您的 q）的候选人，并且是你的代码所做的。与 DH 不同，ElGamal 确实需要原始根，因此这是找到 g 给定有效 p 和 q 的正确方法。

这两个答案都假设您已经拥有 p=2q+1 和 q 和 p 素数。他们没有找到 p 和 q。您的算法首先找到 q 素数（概率上但这已经足够了），然后只是 computing p=2q+1。但是您不验证 p=2q+1 是否为素数——而且通常不是。尽管此数学符号中的 p 表示质数，但 Java 不会自动使名为 p 的变量成为质数。 当 p 不是素数时，ElGamal 不起作用。

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

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

El Gamal digital signature construction inexplicably failing

java

cryptography

biginteger

digital-signature

elgamal