Solving the discrete logarithm problem for a weak group

Question

I was reading an answer about an attack on a weak group for the discrete logarithm problem and wanted to formalize and verify that the attack was correct. That is, that it was guaranteed to always find $x$ (and quickly) given $g$, $h$, and $p$ for $h \equiv g^x \pmod p$. Please read the answer here. In the process I think I found a mistake on the author's part, but figured out how to quickly solve the problem anyway. A number of other questions came up in the process that I'll ask below.

1. I'll start by proving the first assumption of the attack. How do we know $\forall i: \exists x_i: g^{x_i} \equiv h \pmod {a_i}$?

We know $a_i | p$. Let $b_i = p / a_i$. We also know $g^{x} = py + h$ for some $y \in \mathbb N$. This implies $g^{x} = a_i \cdot b_i \cdot y + h$, so $g^x \equiv a_i \cdot b_i \cdot y + h\equiv h \pmod {a_i}$. Thus, $x$ satisfies $x_i$ in the equation above, so $\forall i$ there is at least one solution and $x \equiv x_i \pmod {a_i}$.

2. How do we most efficiently compute the $x_i$?

It seems like according to these records listed on Wikipedia that a number field sieve algorithm will be the fastest since these are fields of form $(\mathbb Z / p \mathbb Z)^\times$, $p$ prime, and that's what the records are for. On the other hand, it must be faster, even for the best implementation of this algorithm to simply do trial multiplication until $p$ is at least so large.

3. How do we know that $\exists x': \forall i: x' \equiv x_i \pmod {\phi(a_i)}$?

Now, the author suggests using the Chinese Remainder Theorem (CRT), but because the $\phi(a_i)$ are not pairwise coprime (in particular, $2$ is a divisor for each $\phi(a_i)$), this doesn't follow. This really threw me off because for a while I was trying to prove that such an $x'$ existed, and was trying to understand how the group order of each cyclic subgroup was relevant to finding $x$.

If you think can explain where the author may have been going, please let me know.

What we're actually looking for is a $x'$ such that $x' \equiv x_i \pmod {a_i}$ holds $\forall i$. By the CRT we know that such a $x'$ exists, and is unique (up its residue modulo $p$). Thus we know $x' \equiv x \pmod p$.

Now we just need to efficiently compute $x'$.

4. How do we efficiently compute $x$ that satisfies the $x \equiv x_i \pmod {a_i}$ equivalences?

Again, reading from Wikipedia it lists solving the equivalences for the first two moduli using the extended Euclidean algorithm and Bézout's identity, followed by extending the solution to all equations as the fastest way to solve this. Will any optimized algorithm, in general or in particular, such as a number field sieve or the Pollard rho method work faster than the two steps listed above? That is when the group is "weak" (or when it is "weak" in this particular way being a composite of many small primes) is there such an algorithm that will always work faster and implicitly take advantages of the weaknesses?

5. Am I missing any important ideas? Is there a more illuminating way to explain anything I did above?

Answer 1

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 &=& g \bmod p_i \\ y_i &=& 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:

1. $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.

2. $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.