1

We are studying discrete logarithms and how they are used in cryptography. When working in $\mathbb{Z}_{p}^*$ I understand the importance of using a safe prime as the modulus so as to avoid being able to break the discrete logarithm into smaller sub groups that are solvable. But is having your generator be in a subgroup of large prime order sufficient for security? Why then does it seem like all the problems make sure to explicitly state the use of a prime modulus? Is it just because it's easy to find a primitive root or to keep the size of the transmitted information smaller as you aren't using some artificially large composite modulus, or is there a way you could go wrong with a composite modulus even if you made sure to use a generator whose order is a large prime?

edit: I've been reading a bunch of papers and looking for info, and I haven't found anything that indicates a discrete log with a large prime order generator could be insecure, but I also haven't found anything that definitively states it's not nor that a prime modulus should be used or why it is that the modulii seem to always be prime. Would love if someone could tell me definitively, because then I can either rest easy knowing that my understanding is in order, or learn what it is I am missing and help further my understanding. Thanks

XRBtoTheMOON
  • 1,031

1 Answers1

0

Ok, so after a bunch more reading I feel I have the answers to my question.

First, having your generator be in a large prime order subgroup is not sufficient for security, as depending on the value of the generator and the modulus there are cases where the DLP can be solved very easily, regardless of how large the group is. But these seem to be kind of "trick" situations, and would be easy to spot.

The main reason I think that these schemes use a prime number for the modulus is for the sake of trust. You could very easily construct a trapdoor modulus where for example $N = p*q$ for large primes $p,q$ and it is impossible for anyone to know whether or not the DLP is computationally solvable, because they can't factor $N$ and so can't know the smoothness of $p$ and $q$. Nor can they find the order of the generator. Where if a prime is used, especially a safe prime, they can quickly tell if it is vulnerable.

So yes having a large prime order subgroup would be sufficient for security in almost all cases, and a prime modulus is not a requirement, however without a prime modulus it is either unnecessary or puts the person using the scheme in a position where they can't know if it is secure or not.

XRBtoTheMOON
  • 1,031