# Solve congruent equation likes N = p*q c1 = (2*p + 3*q)**e1 mod N c2 = (5*p + 7*q)**e2 mod N

Here is a CTF crypto challenge likes(its write up is public on https://ctftime.org/writeup/15438): $$N = p*q\\ c1 = (2*p + 3*q)^{e_{1}} mod N\\ c2 = (5*p + 7*q)^{e_{2}} mod N$$ After i transform these: $$(c^{e_2}_1)\equiv (2p)^{e_1e_2}+(3q)^{e_1e_2}\pmod{N}\\ (c^{e_1}_2)\equiv (5p)^{e_1e_2}+(7q)^{e_1e_2}\pmod{N}$$ After product $$5^{e_1e_2},2^{e_1e_2}$$ to cancel p from two equations,I can solve this problem until get equation liks: $$(c^{e_2}_1)*(5)^{e_1e_2}-(c^{e_1})*(2)^{e_1e_2}\equiv q^{e_1e_2}*(15^{e_1e_2}-14^{e_1e_2})\pmod{N}$$ which means divides the difference between left side and right side.

But i don't know why p or q can get from: $$gcd((c^{e_2}_1)*(5)^{e_1e_2}-(c^{e_1})*(2)^{e_1e_2},N)$$

Could anyone explain the knowledge or why ?

• Both arguments to the $\mathrm{GCD}$ function are divisible by $q$ and so the output is divisible by $q$. As the only divisors of $N$ are $1,p,q$ and $pq$, the GCD will be $q$ unless $p$ also divides the first argument. It is vanishingly unlikely that $p$ does divide this. May 4 at 13:57

The question has shown $${c_1}^{e_2}\times5^{e_1e_2}-{c_2}^{e_1}\times2^{e_1e_2}\equiv q^{e_1e_2}(15^{e_1e_2}-14^{e_1e_2})\pmod{pq}$$ If a congruence holds modulo a product of two integers, then it holds modulo each integer. Thus the congruence holds modulo $$q$$.

The right hand side of the congruence is a multiple of $$q$$. Therefore $${c_1}^{e_2}\times5^{e_1e_2}-{c_2}^{e_1}\times2^{e_1e_2}$$ is a multiple of $$q$$.

$$N$$ also is a multiple of $$q$$. Therefore, $$q$$ is a divisor of $${c_1}^{e_2}\times5^{e_1e_2}-{c_2}^{e_1}\times2^{e_1e_2}$$ and of $$N$$.

The only divisors of $$N$$ are $$1$$, $$p$$, $$q$$, $$N$$, and $$q$$ divides only the later two ones. Therefore, $$\gcd\left({c_1}^{e_2}\times5^{e_1e_2}-{c_2}^{e_1}\times2^{e_1e_2},N\right)$$ is either $$q$$ or $$N$$. The later would hold only if $$p$$ divided $${c_1}^{e_2}\times5^{e_1e_2}-{c_2}^{e_1}\times2^{e_1e_2}$$, which has no particular reason to hold and thus is very unlikely.

Thus in all likelihood $$\gcd\left({c_1}^{e_2}\times5^{e_1e_2}-{c_2}^{e_1}\times2^{e_1e_2},N\right)$$ is $$q$$. We can compute $${c_1}^{e_2}\times5^{e_1e_2}-{c_2}^{e_1}\times2^{e_1e_2}$$, or more efficiently $${c_1}^{e_2}\times5^{e_1e_2}-{c_2}^{e_1}\times2^{e_1e_2}\bmod N$$, then take it's GCD with $$N$$ by the Euclidean algorithm, and factorize $$N$$.

• Thanks for your answer. I still have several questions. I used $a \equiv b \pmod{N}$, which means $a-b = k \times p \times q$, and that implies $p | (a-b)$ and $q | (a-b)$. This leads to $a \equiv b \pmod{p}$ and $a \equiv b \pmod{q}$. I wonder if my method is correct. Although it has solved my problem, I still want to know if your statement "no particular reason to hold and thus is very unlikely" is based on intuition or if there is another way to prove it (I know we can use "N divides the left side" to prove it). May 4 at 15:17
• Yes your method at start of the above comment is correct. ${c_1}^{e_2}\times5^{e_1e_2}-{c_2}^{e_1}\times2^{e_1e_2}$ is constructed in a way such that it is a multiple of $q$, by mean of the choice of the factors $5^{e_1e_2}$ and $2^{e_1e_2}$. There is noting similar w.r.t. $p$, so (baring better analysis) ${c_1}^{e_2}\times5^{e_1e_2}-{c_2}^{e_1}\times2^{e_1e_2}\bmod p$ is essentially random in $[0,p)$, with $0$ no more likely than anything else. Thus $p$ is unlikely to divide ${c_1}^{e_2}\times5^{e_1e_2}-{c_2}^{e_1}\times2^{e_1e_2}$.
– fgrieu
May 4 at 16:45
• Thank you for your help so far! It's more than helpful. When I finally reached the last step, I tried to calculate gcd(N, long number), and its O(n) was too large. However, when I used modulo N, it could be solved easily, and I thought it might be because of the Euclidean algorithm.Here's what I thought: When calculating gcd(N, the long number), it means calculating gcd(N, ( long number) mod N). This is similar to how gcd(A, B) can be expressed as gcd(B, A % B). So, it seems that we can reduce the O(n) complexity by using the Euclidean algorithm. Am I understanding this correctly? May 5 at 8:39
• This is correct too. Indeed, since we know that the first computational step of $\gcd\left({c_1}^{e_2}\times5^{e_1e_2}-{c_2}^{e_1}\times2^{e_1e_2},N\right)$ by the Euclidean algorithm will be to reduce ${c_1}^{e_2}\times5^{e_1e_2}-{c_2}^{e_1}\times2^{e_1e_2}$ modulo $N$, we can (and should) compute ${c_1}^{e_2}\times5^{e_1e_2}-{c_2}^{e_1}\times2^{e_1e_2}\bmod N$ rather than the full ${c_1}^{e_2}\times5^{e_1e_2}-{c_2}^{e_1}\times2^{e_1e_2}$, to save on computation time. That may even be necessary for large $e_1$ or $e_2$.
– fgrieu
May 5 at 8:47