El Gamal digital signature construction inexplicably failing

Question

I am trying to implement the El Gamal digital signature scheme, using the BigInteger class for generating large prime numbers. Samantha generates the public key, the private key, chooses a message, signs it and then Victor verifies the signature.

Problem: The output always says that the signature has not been verified, i.e. the verification algorithm returns false upon every execution, which randomizes the numbers yet again. However, when using small, constant numbers for testing I get the correct result.

Question: Where am I doing something wrong? I can't seem to get to a conclusion.

My code so far:

ElGamal_test - method used for the precomputation step and testing

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 - method used for the signing algorithm

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 - method used for the verification algorithm

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

Expanded from comment; TLDR your p is not prime.

You cite https://crypto.stackexchange.com/questions/820/how-does-one-calculate-a-primitive-root-for-diffie-hellman which is about calculating the generator g, not p and q, for DH.

The 4th para of Thomas Pornin's answer considers a DH group with prime p=2q+1 with q also prime. For DH in this case it is sufficient if the generator has order q or 2q, but it must not have very small order (2 or 1). As he says only 1 has order 1 and only p-1 has order 2, so any other group element can be used as a generator and usually 2 is for convenience.

OTOH Jus12's answer addresses the question as (wrongly) stated, namely finding a primitive root when p=2k+1 with k prime (using k instead of q for the Sophie-Germain prime) where primitive means it has order 2k. To do that requires testing candidates in 2..p-1 (which you code as > 1 and < p) to find one whose order is not 2 or k (your q) and that is what your code does. Unlike DH, ElGamal does require a primitive root, so this is the correct way of finding g given valid p and q.

Both of those answers assume you already have p=2q+1 with q and p prime. They do not find p and q. Your algorithm starts by finding q prime (probablistically but that's good enough) and then just computing p=2q+1. But you don't verify if p=2q+1 is prime -- and it usually isn't. Even though p in this math notation means prime, Java doesn't automatically make a variable named p prime. And when p is not prime, ElGamal doesn't work.

You need to either generate q prime and verify p=2q+1 also prime, or generate p prime and verify q=(p-1)/2 also prime.