3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Hint: you have found $x_i$ with $g^{x_i} \bmod p_i = y \bmod p_i=g^x \bmod p_i$. Using Fermat's little theorem, what's a large divisor $d_i$ of $x-x_i$? Are these $d_i$ coprime, which would be ideal to apply the CRT? Can we workaround that issue and find a suitable $x$ (or the lowest positive one)? $\endgroup$ – fgrieu Feb 6 at 14:24
  • $\begingroup$ I'm not quite sure what you mean. What role does Fermat's little theorem play in finding x after solving the discrete log problems? I know that all the primes for the factoring of p is coprime. $\endgroup$ – Not J. Doe Feb 6 at 15:25
  • $\begingroup$ Thanks for your response. However, I'm fairly new to this, and I'm a bit unsure how to implement it. From here on, what should I calculate, and what should I pass to CRT. I saw an implementation somewhere else (github.com/pberba/ctf-solutions/blob/master/20180913_sect/…) which seemed to work fine, but when I plot my parameters the correct places, _h = y, etc., then crt returns an error saying something alike that gcd(m,n) does not divide a, b. These are parameters of sage's own crt. $\endgroup$ – Not J. Doe Feb 6 at 17:12
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for you help @fgrieu. Sorry for no formatting in the following scenario. So, if I understands it correctly, I can factor mi to other primes, and then find a smaller mi, which is coprime, and thus applicable to CRT. But I'm not quite sure how I do that. I'm a bit confused by your notation as I am fairly new to this. Lets take an example, where pi - 1 = 18072481203497442510. This can be factored to 2 · 3^2 · 5 · 29 · 109 · 727 · 1583 · 4327 · 12757. But at this point, it didn't understand the rest. What is next step to finding the smaller mi? $\endgroup$ – Not J. Doe Feb 6 at 20:20
  • $\begingroup$ Also, when I have found all smaller mi. Can I use them with my xi from the previous calculations, or do I have to solve DLP for them all again with my new mi? I hope you understand. $\endgroup$ – Not J. Doe Feb 6 at 20:21
  • $\begingroup$ Thanks man, finally got it! I wish I could upvote x1000 $\endgroup$ – Not J. Doe Feb 6 at 23:50

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.