4
$\begingroup$

I am trying to solve the Diffie-Hellman problem modulo a composite number $N$, which I have factored. In this question, it was answered how to deal with such a situation. But how can I solve the problem if I don't know $g$? $$y = g^x \pmod{N}$$

The exact numbers are: $$N=442101689710611$$ $$g^a = 421049228295820 \pmod{N}$$ $$g^b = 105262307073955\pmod{N}$$

And I need to find $g^{ab}\bmod N$.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Without knowledge of $g$, you could obtain $h^{\left(\log_h\left(g^a\right) \cdot \log_h\left(g^b\right)\right)} = \left(g^{a b}\right)^{\log_h(g)}$ by choosing an arbitrary generator as $h$. Maybe some possibilities can be eliminated due to small subgroup avoidance and elements that don't contain the targets in their orbit, but it seems that you'll need to know something about $g$ to make progress. $\endgroup$
    – MickLH
    Commented Mar 16, 2017 at 0:33
  • $\begingroup$ Rigt now, I feel like your problem is that you have two equations and one unknown, which means you can't recover all unknowns. The best solution: Use your context to find another equation. $\endgroup$
    – SEJPM
    Commented Mar 16, 2017 at 10:34
  • $\begingroup$ @SEJPM but he doesn't actually need all the unknowns if he wants to break DH he just needs any fitting g, a and b which might be easy to find using brute-force if the subgroups are small. $\endgroup$
    – Elias
    Commented Mar 16, 2017 at 11:22
  • $\begingroup$ I have edited your question to point out (in the title and the text) the actual problem. A single discrete logarithm could be anything if $g$ is unknown, but asking whether more can be said about the Diffie-Hellman situation is a good question. If you disagree with my changes or I misunderstood something you said, please feel free to change it back or clarify. $\endgroup$
    – yyyyyyy
    Commented Mar 16, 2017 at 18:20
  • $\begingroup$ @yyyyyyy I would argue against the usage of the term "Diffie-Hellman" here: since $g$ is not coprime with $N$, it does not generate a group, and DH in non-groups is... weird. I'm not even sure "discrete logarithm" makes sense either, since weird things happen here too. $\endgroup$
    – fkraiem
    Commented Mar 17, 2017 at 11:52

1 Answer 1

Reset to default
5
$\begingroup$

In general, there are a huge number of possible values for $g^{ab}$, depending on what $g$ is.

However, in this case, whoever set up this problem took care to radically reduce the number of possibilities.

Here's how you would attack this problem:

  • Step 1: factor $N$

  • Step 2: for each prime power factor $q^k$ of $N$, we need to determine the set of values of $g^{ab} \bmod q^k$. Two special cases where this is easy:

    • If $g^a = 0 \pmod q$, then obviously $(g^a)^b = g^{ab} = 0 \pmod {q^k}$, and so we have one solution to this subproblem.

    • If $g^a = 1 \pmod{q^k}$, then $(g^a)^b = g^{ab} = 1 \bmod {q^k}$, and so we have one solution to this subproblem.

In practice, these special cases don't come up that often, in this case, it does.

  • Step 3: once we have the set of possible solutions to each of the subproblems, we can use the Chinese Remainder Theorem to join them together to come up with the set of solutions to the original problem.

Now, normally, each subproblem comes up with a large number of potential solutions, and so the combinatorics of step 3 comes up with a truly huge number of solutions.

However, in this case, it turns out to be only two solutions to the overall problem (and, as luck would have it, you really don't need the CRT to join those solutions in step 3; there's a simpler way to compute them).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.