1
$\begingroup$

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 ?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – Daniel S
    May 4 at 13:57

1 Answer 1

Reset to default
0
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ 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). $\endgroup$
    – Ayumi80s
    May 4 at 15:17
  • $\begingroup$ 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}$. $\endgroup$
    – fgrieu ♦
    May 4 at 16:45
  • 1
    $\begingroup$ 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? $\endgroup$
    – Ayumi80s
    May 5 at 8:39
  • $\begingroup$ 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$. $\endgroup$
    – fgrieu ♦
    May 5 at 8:47

Your Answer

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

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