Complexity of solving the discrete logarithm problem for the group formed from product of 2 safe primes The complexity of solving the discrete logarithm problem depends on the choice of the group $G$. A popular choice is $Z_p^*$ where $p$ is a safe prime (${p=2p' +1}$ and $p'$ is also prime). In this case, $G$ is a group of prime order so every element in it is a generator. We can do then:


Pick ${g}$ as a random element from $Z_p^*$ 
Pick a random $x$ 
Evaluate ${y = g^x \: mod \: p}$


Now we can assume solving $x = {log_g(y)}$ is hard if $p$ is large enough.

However, I often see the group $G$ is chosen as $Z_N^*$ where $N=pq$ and both $p$ and $q$ are safe primes. The algorithm is as follows:


Pick $g$ as a random element from $Z_N^*$
Pick $x$ as a random element from $(0, N')$ where ${N' =  p' q'}$ where ${p=2p' + 1}$ and ${q=2q' + 1}$
Evaluate ${y = g^x \: mod \: N}$


This construction is used in various publications from MacKenzie and Fujisaki&amp;Okamoto.

What's that group? Does $Z_N^*$ guarantee computing discrete logarithm is hard? Since ${Z_N^*}$ is not a group of a prime order, is there any guarantee $g$ is a generator?
What's that group?


Algebraically, it is isomorphic to the group $\mathbb{Z}_{p-1} \times \mathbb{Z}_{q-1} = \mathbb{Z}_{p'} \times \mathbb{Z}_{q'} \times \mathbb{Z}_2 \times \mathbb{Z}_2$.


  Does $\mathbb{Z}_N^*$ guarantee computing discrete logarithm is hard?


It can be shown that it is at least as hard as factoring $N$ (as if you can compute discrete logs, you can factor).

Hence, if factoring $N$ is infeasible, so is computing discrete logs.


  Since $\mathbb{Z}_N^*$ is not a group of a prime order, is there any guarantee $g$ is a generator.


Actually, there is a guarantee that $g$ is not a generator for the entire group; that's because $\mathbb{Z}_N^*$ is not a cyclic group, and hence does not have a generator.

In particular, the subgroup generated by a single value $g$ will never contain both elements $a$ and $b$ where:


$a \bmod p$ is a Quadratic Residue $\bmod p$, and $a \bmod q$ is a Quadratic Nonresidue $\bmod q$
$b \bmod p$ is a Quadratic Nonresidue $\bmod p$, and $b \bmod q$ is a Quadratic Residue $\bmod q$


(Such elements $a$ and $b$ will always exist in $\mathbb{Z}_N^*$)