2

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

问题：输出总是说签名没有被验证，即验证算法在每次执行时都返回假，这会再次随机化数字。但是，当使用小的常数进行测试时，我得到了正确的结果。

问题：我在哪里做错了什么？我似乎无法得出结论。

到目前为止我的代码：

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;
}
4

1 回答 1

2

从评论扩展；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或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 也是素数。

于 2017-11-01T07:42:34.063 回答