Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I am trying to implement ElGamal in java without using the in-built libraries. The problem occurs when I am trying to find the generators of the number(in this case 11). Everything works perfectly except that it is returns 10 as a valid generator of 11(which it is not, right?)

public void generateKey()
{
    SecureRandom r = new SecureRandom();
    BigInteger i ;
    //i = new BigInteger(2048, certainty, r);
    i = new BigInteger("11");
    ArrayList<BigInteger> numbers = new ArrayList();
    boolean safePrime = isSafePrime(i);

    numbers = zGenerator(i, safePrime, 10);

    System.out.println(numbers);
}

public boolean isSafePrime(BigInteger i)
{
    return i.subtract(BigInteger.ONE).divide(new BigInteger("2")).isProbablePrime(90);            
}

public ArrayList<BigInteger> zGenerator(BigInteger i, boolean safePrime, int count)
{
    Set<BigInteger> numbers = new TreeSet<BigInteger>();

    if(safePrime)
    {
        BigInteger num = new BigInteger("2");
        BigInteger exp = i.subtract(BigInteger.ONE).divide(new BigInteger("2"));
        do
        {
            if(num.modPow(exp, i).compareTo(BigInteger.ONE) > 0)
                numbers.add(num);
            else
                numbers.add(num.negate().mod(i));
            num = num.add(BigInteger.ONE);
        }while((--count > 0) && (num.compareTo(i) < 0));
    }

    return (new ArrayList<BigInteger>(numbers));
}

Output: [2, 6, 7, 8, 10]

I even tried using $g^q=p-1 \bmod p$

share|improve this question
1  
Write down the criteria defining a valid generator; then the method you use to find them; hopefully that will help. –  fgrieu Jan 28 at 6:36
add comment

1 Answer

up vote 4 down vote accepted

Well, if $g$ is a generator of $\bmod\ p$ for prime $p$; that is, if all values in the range $[1, p-1]$ are possible values for $g^i \bmod p$, then we have $g^a \neq 1 \bmod p$ for any $a = (p-1)/r$ where $r$ is a prime factor of $p-1$.

You select $p$ to be a "safe prime", that is $p-1 = 2 \times q$ where $q$ is also a prime. This implies that, in this case, there are only two values of $a$ that are of interest:

  • $a = q$ (with $r = 2$), this implies the condition that $g^q \ne 1 \bmod p$

  • $a = 2$ (with $r = q$), this implies the condition that $g^2 \ne 1 \bmod p$

Both conditions must be true, however your code tests only the first condition; it doesn't test the second. Now, it turns out that the only possible values of $g$ that do not meet this second condition is $g=1$ (which doesn't pass the first either), and $g=p-1$, or in your case, $g=10$.

Because you're not testing this second condition, you're seeing $g=10$ as looking like a generator when it is not.

Now, $p-1$ is the only value which is excluded by this second condition, in practice it's probably easy just to test values in the range $[2, p-2]$, and not bother explicitly testing this second condition.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.