Diffie-Hellman private key recover with non-prime modulus Say we have a classic Diffie-Hellman key exchange. We have the following parameters of a public key:

p,g,y


Where $p$ is the modulus, $g$ is the base, $y$ is the public key, and $x$ is the private key in the following equation:

$y = g^x \bmod p$

It happens that the modulus is a composite number, which can be factored into primes.

How can someone find $x$, thus solving in the discrete logarith problem (DLP), by factorizing the modulus into primes, and solving the smaller DLP's with the primes, then combining them with chinese remainder theorem?
We start by finding the factorization of $p$ as $\prod p_i$; then find the $x_i$ with $g^{x_i}\equiv y\pmod{p_i}$ using an auxiliary algorithm to solve the DLP, perhaps Pollard's rho and/or Pohlig-Helman.

I'll assume that the $p_i$ are distinct, which was the case in the original question. They thus are coprime, and by the Chinese Remainder Theorem $g^x\equiv y\pmod p$ is equivalent to $\forall i, g^x\equiv y\pmod{p_i}$.

Fermat's little theorem tells us that $g^{p_i-1}\equiv1\pmod{p_i}$, since $p_i$ is a prime not dividing $g$. Therefore, $g^x\equiv g^{x\bmod(p_i-1)}\pmod{p_i}$. Therefore it is sufficient to find $x$ such that $\forall i,x\equiv x_i\pmod{p_i-1}$ (see final section for a better alternative).

Problem is, the moduli $m_i=p_i-1$ are not coprime: for a start, they all are divisible by $2$. That prevents a different use of the regular CRT to find $x$. We need to reduce the $m_i$ in order to make them coprime, while leaving their Least Common Multiple unchanged.

Assuming that we can fully factor the $m_i$: we collect every prime $q_j$ in these factorizations, and find it's maximal multiplicity $k_j$ (that is the maximal $k_j$ so that $q_j^{k_j}$ divides at least one of the $m_i$). Then for each $q_j$, we select one (of possibly several) $m_i$ that $q_j^{k_j}$ divides, and we divide each other $m_i$ by $q_j$ as many times as possible.
Note 1: Each time we divide an $m_i$ by $q_j^{k_{j,i}}$, we can check that $x_i\equiv x_j\pmod{q_j^{k_{k,j}}}$, and otherwise conclude that there is no solution.
Note 2: We can avoid full factorization of the $m_i$ and use Greatest Common Divisor computations, but that's slightly involved; see this.

If $x\equiv x_i\pmod{p_i-1}$, then $x\equiv x_i\pmod{m_i}$ holds for the reduced $m_i$. The converse holds if we made the checks in note 1. We can now find a suitable $x$ using the regular CRT, requiring coprime $m_i$. We do not need to recompute the $x_i$, but we can reduce them modulo $m_i$.

If we did not perform the checks in note 1, we need a final check that $g^x\equiv y\pmod p$. 



Another issue is that $x\equiv x_i\pmod{p_i-1}$ is a sufficient, but not necessary condition for $g^x\equiv g^{x_i}\pmod{p_i}$ to hold. Thus, the CRT applied as above can find an $x$ that's needlessly larger than needed. A solution to this is to initialize $m_i$ with the order of $g$ modulo $p_i$, that is the smallest positive $m_i$ with $g^{m_i}\equiv1\pmod{p_i}$. That's some divisor of $p_i-1$, not always $p_i-1$ itself.