# [EN] Ultra Easy RSA
###### tags: `Writeup` `Crypto` `English`
> [name=Curious]

## Prior Knowledge

### Fermat Factorization

$p$ and $q$ are two factors of $n$, and if $|p - q|$ is small, we can assume that $p > q$

$$
\begin{cases}
p = a + b\\
q = a - b
\end{cases}
\;\Rightarrow\;
n = pq = a^2 - b^2
\;\Rightarrow\;
n + b^2 = a^2
$$

Since $p - q$ is small, it follows that $b$ will also be small. Therefore, we can let $a$ be

$$
\sqrt n + 1, \sqrt n + 2, \sqrt n + 3, ...
$$

When $\sqrt{a^2 - n} \in \mathbb{N}$, we can calculate the values of $a$ and $b$, and thereby factorize $n$.

---
## Train Of Thought & Solution
From `chal.py`, it can be seen that both `p` and `q` are constructed by adding a 32-bit prime number to `base + 1`. Therefore, `p` and `q` are generally not far apart. This suggests that we can use Fermat factorization to factorize `n`. Once factored, we can calculate the decryption key `d` to decrypt `c`.

> You can simply input `n` into http://factordb.com to obtain the values of `p` and `q`

Solve Script :

from gmpy2 import isqrt, iroot
from Crypto.Util.number import long_to_bytes

def fermat_factor(n: int):
    """
    - input : `n (int)`
    - output : `(p, q) (int, int)`
    """

    a = int(isqrt(n)) + 1
    b = iroot(a ** 2 - n, 2)
    while not b[1]:
        a += 1
        b = iroot(a ** 2 - n, 2)
        print(a)
    b = int(b[0])
    return (a - b), (a + b)

n = ...
e = 65537
c = ...

p, q = fermat_factor(n)
d = pow(e, -1, (p - 1) * (q - 1))
m = pow(c, d, n)

print(long_to_bytes(m))

{%hackmd M1bgOPoiQbmM0JRHWaYA1g %}