# Diffie-Hellman private key recover with non-prime modulus

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?

• 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)? – fgrieu Feb 6 at 14:24
• 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. – Not J. Doe Feb 6 at 15:25
• 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. – Not J. Doe Feb 6 at 17:12

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.

• 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? – Not J. Doe Feb 6 at 20:20
• 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. – Not J. Doe Feb 6 at 20:21
• Thanks man, finally got it! I wish I could upvote x1000 – Not J. Doe Feb 6 at 23:50