Solving the discrete logarithm problem for a weak group
The question is about making wonky DH parameters for which discrete logarithm is super-easy to solve. Thus, somebody suggests the following:

Let the modulus $p$ be the product of all small primes from $3$ to some value such that $p$ is adequately large. In this case, we consider the product of all primes from $3$ to $1471$; there are $232$ such primes, and their product is a $2046$-bit integer.

We now have a $y = g^x \bmod p$, for known values $y$ and $g$, and unknown $x$. The task at hand is to find $x$, or at least one value $x$ that matches the equation. There may be several (this is the common case; the algorithm below will usually find a much smaller solution than the original $x$). Crucially, we assume that there is a solution, i.e. that $y$ was obtained by choosing a (random) value $x$ and then computing the modular exponentiation.

Let's called $p_i$ the small primes. Let's define:
\begin{eqnarray}
  g_i &amp;=&amp; g \bmod p_i \\
  y_i &amp;=&amp; y \bmod p_i \\
\end{eqnarray}

The Chinese Remainder Theorem basically tells us that whatever happens modulo $p$ also happens modulo each of the small primes $p_i$, and back; said otherwise, if we can find a $x$ such that $g_i^x = y_i \bmod p_i$ for all $232$ values of $i$, then $x$ is a solution. Note that it is about using the same value $x$ modulo each prime $p_i$.

We now consider each small equation $g_i^x = y_i \bmod p_i$. There are two sub-cases:


$g_i = 0 \bmod p_i$. In that case, $y_i$ must be 0 \bmod $p_i$ (otherwise there would be no solution, and by definition we assume there is at least one); and any value $x$ works here.
$g_i$ is invertible modulo $p_i$ and has a definite multiplicative order $n_i$ which is a divisor of $\phi(p_i) = p_i - 1$. There again, since we assumed the existence of a solution, $y_i$ must be part of the group generated by $g_i$ modulo $p_i$. There is then exactly one value $x_i$ modulo $n_i$ that matches the equation. Since $p_i$ is small (our largest small prime $p_i$), the value $x_i$ can be obtained with the dumbest of brute force, i.e. trying values $0$, $1$, $2$... until $g_i^{x_i} = y_i \bmod p$ is satisfied.


Thus, we end up with a number of values $x_i$. We know that $x = x_i \bmod n_i$ (for all $i$ that match sub-case 2). By the magic of the CRT, this works both ways: if we find a value $x$ such that $x = x_i \bmod n_i$, then it will be a solution to $g^x = y \bmod p$.

Now, each $n_i$ is itself a product of small primes, which can easily be found (the largest $n_i$ is not greater than $1470$ since $n_i$ divides $\phi(p_i) = p_i - 1$). In general, we can write:
$$ n_i = \prod p_j^{a_{i,j}} $$
i.e. $n_i$ is a product of powers of small prime powers.

Let's look at these small primes. For each $p_j$, there will be one of the $n_i$ which maximizes $a_{i,j}$. In other words, we define:
$$ b_j = \max\{ a_{i,j} \} $$
We can then extract some information from the corresponding equation, i.e. we can define $d_j = x_i \bmod p_j^{b_j}$ for the value $x_i$ such that $n_i$ is a multiple of $p_j^{b_j}$ (there may be multiple matching $n_i$, but, by the assumption that there is a solution, they must all agree).

We now have a bunch of prime powers $p_j^{b_j}$, for distinct small primes $p_j$, and equations $x = d_j \bmod p_j^{b_j}$. Since we took care to maximize the $b_j$, the equations are sufficient: any $x$ that matches all of them will be a solution to the original DL problem. And since all the $p_j^{b_j}$ are prime to each other, the CRT applies without any further issue.

The tricky part in this description is that we have two distinct domains in which we use the CRT: one is modulo the small primes $p_i$, the other is in the exponents, which work modulo each order $n_i$. Note that the $n_i$ are not necessarily prime to each other, which is why we have to factorize them all and find the largest prime powers.

Less talk, more code! I wrote a C# implementation of the algorithm above. Main file is EasyDL.cs, that follows the steps above. It uses a generic big-integer implementation that I wrote previously, ZInt.cs. This is easily compiled on a Linux machine with Mono (install package mono-devel on a Ubuntu system):

mono-csc EasyDL.cs ZInt.cs


This produces EasyDL.exe, which can be executed with Mono:

mono EasyDL.exe


On a Windows machine, use the command-line compiler csc.exe, which is typically in C:\Windows\Microsoft.NET\Framework64\v4.0.30319\ (assuming a Windows 8+ machine in 64-bit mode; the code should work also with older .NET versions such as 3.5).

When executed, the program:


rebuilds the modulus $p$ as a product of small primes;
generates random $g$ and $x$, and computes $y = g^x \bmod p$;
applies the algorithm above to recompute a solution $s$ such that $y = g^s \bmod p$.


Values are printed out in hexadecimal.