0
$\begingroup$

One of the basic requirements of DSA is to choose some prime $p$ of certain bit length. The security then lies in the intractability of solving $y = g^x \pmod{p}$ for $x$.

Is there any “easy” way to solve the discrete log problem when $p$ is composite? I thought about the Chinese Remainder Theorem but can't seem to figure out how it would work. If there is no obvious way to solve for $p$ composite then what is the need for $p$ to be prime?

$\endgroup$
2
$\begingroup$

Is there any “easy” way to solve the discrete log problem when $p$ is composite?

If you know the factorization of $p = rs$, then it can be reduced to solving the problem $y = g^x \pmod r$ and $y = g^x \pmod s$, and then combining the two solutions; hence you're reduced the hardness of the problem to the harder of the $r, s$ subproblems.

If you don't know the factorization of $p$, then it is at least as difficult as factoring $p$ (if you can solve arbitrary discrete logs modulo $p$, then you can factor $p$).

That would imply that the person who generated $p$ might be able to give himself a backdoor (as he'd have an easier time solving discrete logs than anyone else).

On the other hand, that's not the complete story.

You specified DSA; DSA places more requirements on the group it runs in. For one, it actually operates in a prime-sized subgroup that is both considerably smaller than the modulus size, and which must be listed in the global parameters (as the verifier needs it). And, in case you're wondering, the fact that the subgroup is prime is important, if it were composite, you could factor it, and attack each of the factors independently.

So, suppose we had $p = rs$ (where the factorization is secret), and we have a generator $g$ with $g^q = 1 \pmod p$ (for some moderate sized prime $q$).

That immediately implies that we have $g^q = 1 \pmod r$ and $g^q = 1 \pmod s$; however, if we have $g = 1 \pmod r$, then a simple computation of $\operatorname{gcd}(g-1, p)$ would reveal the factorization, and hence to be secure, we must have $g \ne 1 \pmod r$ and $g \ne 1 \pmod s$.

This implies that $r - 1 = 0 \pmod q$ and $s - 1 = 0\pmod q$, or in other words, we have:

$$p = (aq +1)(bq+1)$$

where $q$ is public, and $a, b$ are some unknown integers.

If we go through the size of $q$ (perhaps 256 bits), and the sizes of $r = aq+1$, $s = bq+1$ (perhaps 1024 bits each, hence $a, b$ may be 768 bits each), it's not immediately clear whether current lattice based factorization methods would work, but it's closer than anyone would trust.

$\endgroup$
1
$\begingroup$

There is a small error in the understanding of the hardness of the DLOG problem: Not for every large prime $p$ it is hard. It is important that $\phi(p)=p-1$ has at least one large prime factor, which is the order of the group. Otherwise the Pohlig-Hellman attack can be used to solve the DLOG problem in each subgroup and then assemble the general solution with the CRT.

This means as a rule of thumb: Only the size of the largest prime factor of $p-1$ matters for the DLOG problem. As an example: If $p$ has $2048$ bit, we look at 2 possible situations: $p = 2q+1$ with $q$ prime, and $p=ab+1$ with $|a| = |b|$. In the first situation, the length of $q$ is $2047$ bit, in which we have to solve the DLOG problem. In the second situation, we have to solve the DLOG problem in two groups, both with $1024$ bit moduli, and then combine them. That is much, much easier than solving one DLOg problem with a $2047$ bit modulus.

The above is true for any kind of modulus: For a composite modulus (better to call this $n$ instead of $p$) its totient would also require a large prime factor, and only the largest prime factor matters. Having multiple large primes gives very little benefit but immediately increases the size of the modulus by a lot.

Regarding the cryptosystem, if the modulus isn't prime, then Fermant's little theorem $a^{n-1} = 1 \mod n$ is almost surely not true any more for composite $n$ (with the exception of Carmichael numbers), which might have to be taken into account. Also, some cryptosystems even work with a generator of a subgroup of prime order $q$ instead of a generator for the full group of order $p-1$ - exactly because all those other small groups don't add anything to security but might actually leak information (e.g. quadratic residuosity).

$\endgroup$
  • $\begingroup$ Perhaps it would be useful to mention the obvious more explicitly: if $n$ is of known factorization, then the problem of finding $x$ with $y\equiv g^x\pmod n$ can be solved independently for each prime factor $p$ of $n$, becoming $y\equiv g^{x_p}\pmod p$ (likely easier since $p\ll n$), and the resulting values of $x_p$ (defined modulo $p-1$) can be combined into $x$ using the Chineese Remainder Theorem. In this comment, I skipped the complexities of $n$ possibly not being squarefree, and conflicts that conceivably could occur when the $p-1$ share a prime factor other than $2$. $\endgroup$ – fgrieu Oct 11 '17 at 16:40
  • 1
    $\begingroup$ The text you wrote in the second paragraph isn't accurate; you appear to be assuming that if you have $p = kq+1$, that you could split the problem into a $k$-sized modulus and a $q$-sized modulus; you can't. If the size of the subgroup is so small that generic group attacks work, you can take advantage of that; however there's nothing particularly weak if we use $p = kq+1$, with a 2048 bit $p$ and a 256 bit $q$ (which is a very common scenario with DSA) $\endgroup$ – poncho Oct 11 '17 at 19:46

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.