1
$\begingroup$

For encryption methods there is a need for (very large) prime numbers. So for Elgamal digital signature there is the problem of finding a primitive root of $(p)$ where $p$ must be very large prime number (1024) or (2048) bits length.

My question is: how does the encrypter solve this problem?

I presume a loop to check all the possibilities is an option.

$\endgroup$
8
$\begingroup$

When considering a big prime $p$, the group of invertible integers modulo $p$ are all integers from $1$ to $p-1$. There are $p-1$ of them. The order of an integer $g$ modulo $p$ is the smallest integer $k > 0$ such that $g^k = 1 \pmod p$. Group theory states that the powers of an element $g$, i.e. $1$, $g$, $g^2$... are collectively a subgroup of the group of invertible integers modulo $p$, and the order of $g$ is really the size of that subgroup (called "the subgroup generated by $g$"). The cardinal of a subgroup is always a divisor of the cardinal of the group that contains it. Thus, $k$ divides $p-1$.

A primitive element $g$ is one such that the subgroup it generates really is all of the invertible integers modulo $p$, not just some of them. Therefore, to verify whether an integer $g$ is primitive or not, all you have to do is check that its order is $p-1$ but not one of the other possible subgroup orders. That is, you check that $g^{k'} \neq 1 \pmod p$ for all $k' < p - 1$ such that $k'$ divides $p-1$.

The problem can be simplified as follows: suppose that there is a $k' < p-1$, such that $k'$ divides $p-1$, and $g^{k'} = 1 \pmod p$. We can consider $\alpha = (p-1)/k'$, which is an integer greater than 1, and thus a product of some prime integers (since every integer can be decomposed as a product of prime factors). Let's call $r$ one of the prime factors of $\alpha$ (i.e. we write $\alpha = r\beta$ for some integer $\beta$). Since $\alpha$ divides $p-1$, so does $r$, and we can compute: $$ k'' = (p-1)/r = \beta k' $$ Thus: $$ g^{k''} = (g^{k'})^\beta = 1^\beta = 1 \pmod p $$

In other words, if $g$ is not primitive, then there must be a prime integer $r$ that divides $p-1$ such that $g^{(p-1)/r} = 1 \pmod p$.

This means that in order to test whether a given $g$ is primitive, then it suffices to apply the following test:

Let $p$ be a prime, and $g$ a non-zero integer modulo $p$. If, for all primes $r$ that divide $p-1$, $g^{(p-1)/r} \neq 1 \pmod p$, then $g$ is primitive, i.e. its order modulo $p$ is exactly $p-1$.

Now comes the actual difficulty: you must somehow know the list of prime factors of $p-1$. This is easy if you generate $p$ "specially", as a so-called "safe prime" (the terminology "safe" here is traditional and does not actually imply that the prime is inherently "safer" than any other, but it makes our problem easier). A "safe prime" is an integer $p$ which is such that both $p$ and $(p-1)/2$ are prime. If you generate your modulus for ElGamal signatures are a "safe prime", then there are only two prime factors of $p-1$: these are $2$, and $(p-1)/2$. The test above now becomes the following:

  • Get a random non-zero $g$ modulo $p$.
  • Check that $g^2 \neq 1 \pmod p$. Note that there are only two integers $g$ modulo $p$ such that $g^2 = 1 \pmod p$, and these are $1$ and $p-1$. Thus, it suffices to choose $g$ greater than $1$ and lower than $p-1$ to fulfill that condition.
  • Check that $g^{(p-1)/2} \neq 1 \pmod p$. If that condition is not met, then you must start over with another $g$. Otherwise, that's it, you have a primitive $g$.

No specific value of $g$ is better than any other with regards to resistance to discrete logarithm, so you might just as well try small values of $g$, that offer a small performance boost; you start with $g = 2$ and simply increment it until you reach a primitive value. Exactly half of the integers from $2$ to $p-2$ are primitives, so you do not have to try many times before reaching such a value.

IMPORTANT: Take care that the test above is for a "safe prime". In the general case, if given a prime $p$ without any knowledge of how it was generated, you would have to factorize $p-1$ into its prime factors, a problem which is, in all generality, quite hard to solve for large integers.

While the ElGamal scheme is nominally defined with a primitive root that generates all invertible integers modulo $p$, it can also be applied to a subgroup, at which point it becomes mostly the same thing as DSA. In DSA, it is customary to generate $p$ as follows:

  • Let $q$ be a random medium-sized prime (e.g. 256 bits).
  • Let $p$ be a random large prime (e.g. 2048 bits) such that $q$ divides $p-1$. In practice, this means that random integers $z$ are produced, and, for each, $p$ is computed as $p = qz+1$, until a prime $p$ is obtained.
  • To make an element $g$ of order exactly $q$, a random integer $m$ modulo $p$ is generated, and we set $g = m^{(p-1)/q} \bmod p$. It is easily shown that $g^q = 1 \pmod p$, which means that the order of $g$ is a divisor of $q$. Since $q$ has been chosen to be prime, the order of $g$ can be either $1$ or $q$. If $g \neq 1$, then its order cannot be $1$. Therefore, $g$ will have order exactly $q$ as long as it is not equal to $1$. Probability of $g$ being equal to $1$ is very very small, but even if that happened, then you would just have to start again with another value $m$.

Summary: to get a primitive element modulo $p$, you get random values and then check whether you obtained a primitive element. Primitive elements are not rare, so this works well in practice. However, to do the check, you have to know the factorization of $p-1$, and that is difficult in the general case. Thus, the usual method is to produce the modulus $p$ with a generation method that also lets you know the factorization of $p-1$, e.g. you make $p$ as a "safe prime". Alternatively, you do not look for a primitive element, but for the generator of a subgroup of known prime size (as is done in DSA).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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