What is more important for 1) encryption 2) decryption for the discrete log problem - g is of prime power order or g mod p is a primitive root?

114 Views Asked by At

The discrete log problem specifies that g must be an element of prime power order, and g mod p is a primitive root. g, x, and p must be large, and p is prime. x is to be found.

$$g^{x}\pmod{p}=h$$

What is more important for

  1. Encryption
  2. Decryption

for the discrete log problem - either g is of prime power order mod p, or g mod p is a primitive root? Why?

I do not know why both conditions are specified - what happens to the system if only one was needed? Does it make the system vulnerable?

My attempt: I am aware from trying some examples that there are the following are possibilities:

  1. g mod p is a primitive root and g is of prime power order mod p - eg g=2, p=3
  2. g mod p is a primitive root and g is not of prime power order mod p. eg g=3, p=7
  3. g mod p is not a primitive root and g is of prime power order mod p. eg g=3, p=11
  4. g mod p is not a primitive root and g is not of prime power order mod p. eg g=2, p=7
1

There are 1 best solutions below

0
On

In general, the DLP does not have these constraints (see Wikipedia). It simply asks us to find a $x$ such that $g^x \equiv h \pmod{p}$. However, there are certain things you can do to make solving this DLP sufficiently hard for an attacker.

  1. We pick $g$ to be a primitive root otherwise we don't visit all the elements modulo $p$ and thus reducing the number of things an attacker must try to attack your message.
  2. $p$ must be sufficiently large because the currently best known method of efficiently solving the DLP takes approximately $\sqrt{p}$ steps to find the solution.
  3. We usually pick $p = 2q + 1$ where $p, q$ are both prime. The Pohlig-Hellman algorithm can solve the DLP by solving smaller DLPs of size $p_i^{e_i}$ where $p_i^{e_i} \mid p - 1$ and $p_i^{e_i + 1} \nmid p - 1$.

I'm not sure where your constraint for $g$ needing to have prime power order comes from. Consider solving $4^x \equiv -1 \pmod{29}$. This is a well formed DLP. Additionally, "$g$ is a primitive root and of prime power order" only works for Fermat primes, as the multiplicative order or a primitive root mod $p$ is $p - 1$, which is always even unless $p = 2^{2^n} + 1$.