8
$\begingroup$

Given two distinct safe primes $p_1 = 2 \cdot q_1 + 1$, $p_2 = 2 \cdot q_2 +1$, consider the following two instances of the discrete logarithm problem with the same unknown exponent $x$.

$$ g_1^x \equiv y_1 \mod p_1 $$ $$ g_2^x \equiv y_2 \mod p_2 $$ where the multiplicative orders of $g_1, g_2$ are $q_1, q_2$ respectively.

In general, we can solve the two discrete logarithms independently to find $(x \mod q_1)$ and $(x \mod q_2)$, then combine with the Chinese Remainder Theorem to get $(x \mod q_1 q_2)$.

Can we do better if we know that $x$ satisfies $ 0 < x < \min(q_1, q_2)$? Is there any approach faster than solving one of the discrete logarithms?

$\endgroup$
  • 1
    $\begingroup$ While I'm no expert, it seems difficult to use the additional information without finding some relationship between $g_1$ and $g_2$ (potentially in some group that contains the homomorphic image of both $\mathbb{Z}/p_i\mathbb{Z}$'s). For homomorphisms $\phi_i:\mathbb{Z}/p_i\mathbb{Z}\to G$, this reduces to finding a relationship between $\phi_1(g_1)$ and $\phi_2(g_2)$, the most obvious way to do so is via computing the discrete logarithm in $G$. This can give you some slight advantage if the generators are fixed and $x$ is randomly chosen (as it allows for precomputation), <continued> $\endgroup$ – Mark Sep 16 at 15:10
  • 1
    $\begingroup$ But the most obvious way to apply a non-trivial solution to this problem is attacking weak implementations of TLS 1.3's handshake (specifically client keyshares that re-use the randomly chosen exponent), where I'd hope that generators are additionally randomly chosen (but don't know what most implementations do). $\endgroup$ – Mark Sep 16 at 15:12
  • $\begingroup$ if $x/g_1$ or $x/g_2$ has a particularly short ( = good ) continued fraction ($x \equiv a b^{-1} \mod q$ with small $a,b$), then that discrete log would be "easy/easier" to solve. One way to look at this problem is: what values of $x$ have a bad continued fraction for both denominators $q_1$ and $q_2$. $\endgroup$ – robertkin Sep 17 at 3:20
  • $\begingroup$ Interestingly, it doesn't seem like there's a way to convert a solution to this problem into a better attack on composite-modulus discrete log in general. Which makes me think that a solution to this problem might exist. $\endgroup$ – robertkin Sep 17 at 3:43
2
+50
$\begingroup$

For $i\in\{1,2\}$ it is given prime $p_i$ with $q_i=(p_i-1)/2$ also prime, integer $g_i$ of multiplicative order $q_i$, and integer $y_i$ such that for some untold integer $x$ common to both $i$, it holds ${g_i}^x\equiv y_i\pmod{p_i}$.

With the additional information that $0<x<\min(q_1, q_2)$, if we can solve either of the two Discrete Logarithm Problems, then we can solve the other with a single modular reduction.

Proof: WLoG, say we solved for $x$ the DLP ${g_1}^x\equiv y_1\pmod{p_1}$ and a solution is $x=x_1$ (swap the indices if we solved the other DLP). Compute $s=x_1\bmod q_1$. It holds that all solutions to that DLP are of the form $x=k\,q_1+s$ with $k\in\Bbb Z$. And $x=s$ is the only solution to that first DLP with $0\le x<q_1$. Hence $s$ is the only possible solution to that first DLP matching the stronger condition $0<x<\min(q_1, q_2)$. Hence that $s$ must be a solution to both DLP, and the only such one (formally, we do not even need to check that $0<s<\min(q_1, q_2)$ and ${g_2}^s\equiv y_2\pmod{p_2}$, even though in practice we would).

Since we need to solve only one DLP, and anyone of the two possibly according to which we find easier, that's "better" than "solv(ing) the two discrete logarithms independently"; and that improvement is directly enabled by $0<x<\min(q_1, q_2)$. This answers in the affirmative a possible reading of the question.

But we are told that the question really asks: assuming $0<x<\min(q_1, q_2)$, is there an approach which solves the two DLPs simultaneously that is faster than solving either DLP? That's a much harder question, and right now I have no clue.


Note: even the weaker additional information $0<x<\max(q_1,q_2)$ and solving one of the two DLPs in isolation would greatly help towards solving both. When $p_1\ge p_2$, the $s$ computed as above would be the only possible $x$. And for $p_1<p_2$ we could reduce the search of $x$ to the search of $k$ in a DLP of the form $g^k\equiv y\pmod{p_2}$ with $0\le k<\lceil q_2/q_1\rceil$, making the search easier (by enumerating $k$ when $p_1$ and $p_2$ have about the same size, or Baby-Step/Giant-Step if they differ by a few dozen bits). $g$ and $y$ are easily computed as $g={g_2}^{q_1}\bmod p_2$ and $y={g_2}^{-s}\,y_2\bmod p_2$.

$\endgroup$
  • 2
    $\begingroup$ Yes, solving either DLP yields a solution to both. The question is, does knowing this make the first DLP any easier to solve? Is there an approach which solves the two DLP simultaneously that is faster than solving either DLP (when $0<x<\max(q_1,q_2) $ ) $\endgroup$ – robertkin Sep 11 at 18:52

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.