Source files and Solve Script: TMUCTF/Common%20Factor
Factoring N:
If we look closely at the first hint , we can find one of the factors of N ,
n = p 1 ⋅ p 2 ⋅ p 3 ⋅ p 4 ⋅ p 5 x 2 + x 3 + y 1 = p 2 2 + p 1 p 2 + p 1 2 p 2 + p 2 2 p 1 = p 2 ( p 1 + p 2 ) ( p 1 + 1 ) = h 1 ( s a y ) ∴ p 2 = gcd ( n , h 1 ) \begin{align}
n &= p_1 \cdot p_2 \cdot p_3 \cdot p_4 \cdot p_5 \\
x_2 + x_3 + y_1 &= p_2^2 + p_1p_2 + p_1^2p_2 + p_2^2p_1 = p_2 (p_1 + p_2)(p_1 + 1) = h_1 (say) \tag{1} \\
\therefore p_2 &= \gcd(n, h_1)
\end{align} n x 2 + x 3 + y 1 ∴ p 2 = p 1 ⋅ p 2 ⋅ p 3 ⋅ p 4 ⋅ p 5 = p 2 2 + p 1 p 2 + p 1 2 p 2 + p 2 2 p 1 = p 2 ( p 1 + p 2 ) ( p 1 + 1 ) = h 1 ( s a y ) = g cd( n , h 1 ) ( 1 ) From here, we can proceed to find another prime by solving the quadratic from (1)
p 1 2 p 2 + ( p 2 2 + p 2 ) p 1 + ( p 2 − h 1 ) = 0 ∴ p 1 = − ( p 2 2 + p 2 ) ± ( p 2 2 + p 2 ) 2 − 4 p 2 ( p 2 − h 1 ) 2 p 2 p_1^2p_2 + (p_2^2+p_2)p_1 + (p_2 - h1) = 0 \\~\\
\therefore p_1 = \frac{-(p_2^2+p_2) \pm \sqrt{(p_2^2+p_2)^2 - 4p_2(p_2-h1)}}{2p_2} p 1 2 p 2 + ( p 2 2 + p 2 ) p 1 + ( p 2 − h 1 ) = 0 ∴ p 1 = 2 p 2 − ( p 2 2 + p 2 ) ± ( p 2 2 + p 2 ) 2 − 4 p 2 ( p 2 − h 1 ) From the 2nd hint, we can find another factor
y 2 + y 3 = p 2 2 ⋅ ( p 3 + 1 ) − 1 + p 1 ⋅ p 2 ⋅ ( p 3 + 1 ) − 1 = h 2 ( s a y ) h 2 + 2 = ( p 3 + 1 ) ⋅ ( p 2 2 + p 1 ⋅ p 2 ) p 3 = ( h 2 + 2 ) ( p 2 2 + p 1 ⋅ p 2 ) − 1 \begin{align}
y_2 + y_3 &= p_2^2 \cdot (p_3 + 1) - 1 + p_1 \cdot p_2 \cdot (p_3 + 1) - 1 = h_2 (say) \\
h_2 + 2 &= (p_3 + 1) \cdot (p_2^2 + p_1 \cdot p_2) \\
p_3 &= \frac{(h_2 + 2)}{(p_2^2 + p_1 \cdot p_2)} - 1
\end{align} y 2 + y 3 h 2 + 2 p 3 = p 2 2 ⋅ ( p 3 + 1 ) − 1 + p 1 ⋅ p 2 ⋅ ( p 3 + 1 ) − 1 = h 2 ( s a y ) = ( p 3 + 1 ) ⋅ ( p 2 2 + p 1 ⋅ p 2 ) = ( p 2 2 + p 1 ⋅ p 2 ) ( h 2 + 2 ) − 1 At this point, we have 3/5 primes and I don't know how to find the other 2. Then I had a wild thought that if the flag is small enough i.e. F l a g ≤ 3 ∗ 2048 b i t s Flag \leq 3*2048 \;bits Fl a g ≤ 3 ∗ 2048 bi t s
So, I used N = p 1 ⋅ p 2 ⋅ p 3 N = p_1 \cdot p_2 \cdot p_3 N = p 1 ⋅ p 2 ⋅ p 3
Copy N = p1*p2*p3
phi = (p1-1)*(p2-1)*(p3-1)
d = inverse(e, phi)
m = pow(c,d,N)
print(long_to_bytes(m))
Flag: TMUCTF{Y35!!!__M4Y_N0t_4lW4y5_N33d_4ll_p21M3_f4c70R5}
Note:
The flag is small enough(423 bits only). Thus we can use only one prime to solve this challenge!
Copy >>> p = 1790219150350431869249298318142647942912962940213432230093208907326419345731236923512405137703813455383171193311389221185396503166624248089450563913208309573240948978311631888770208
037787020200330113206552400119653261709264824328655007715928842654045773778279140586789508769027787206630445038315928935749253664040823298242382518017657335777114151740646677810822170721506
713319579227314265304324964929132392176156378849185348482575059832856778341315394429786594340752606742856546151539956126744508119509530051475559345042049323799727243545914017129273580301983
6543947409733063944596031206583742779877774484876687058741
>>> phi = (p-1)
>>> e = 65537
>>> d = inverse(e,(p-1))
>>> long_to_bytes(pow(c,d,p))
b'TMUCTF{Y35!!!__M4Y_N0t_4lW4y5_N33d_4ll_p21M3_f4c70R5}'
