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

Ayumi80s

5/4/24, 1:38 PM

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 ?

147

1 + 1

attack

congruence

Daniel S

5/4/24, 1:57 PM

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.

Score:0

Crypto

fgrieu

5/4/24, 2:06 PM

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$.

+ 4

Ayumi80s

5/4/24, 3:17 PM

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).

fgrieu

5/4/24, 4:45 PM

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}$.

Ayumi80s

5/5/24, 8:39 AM

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?

fgrieu

5/5/24, 8:47 AM

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$.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

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

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.