> For the complete documentation index, see [llms.txt](https://r3yc0n1c.gitbook.io/writeups/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://r3yc0n1c.gitbook.io/writeups/2021/tmuctf/common-factor.md).

# Common Factor

Source files and Solve Script: [TMUCTF/Common%20Factor](https://github.com/r3yc0n1c/CTF-Writeups/tree/main/2021/TMUCTF/Common%20Factor)

### Factoring N:

If we look closely at the first *hint*, we can find one of the factors of **N**,

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

From here, we can proceed to find another prime by solving the quadratic from (1)

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

From the *2nd hint,* we can find another factor

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

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. $$Flag \leq 3\*2048 ;bits$$ then we can decrypt it with these 3 primes we found! 

So, I used $$N = p\_1 \cdot p\_2 \cdot p\_3$$ and got the flag!

```python
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))
```

{% hint style="success" %}
Flag: TMUCTF{Y35!!!\_\_M4Y\_N0t\_4lW4y5\_N33d\_4ll\_p21M3\_f4c70R5}
{% endhint %}

### Note:

The flag is small enough(**423 bits** only). Thus we can use only **one prime** to solve this challenge!

```python
>>> 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}'
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://r3yc0n1c.gitbook.io/writeups/2021/tmuctf/common-factor.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.