# [CH] Ultra Easy RSA
###### tags: `Writeup` `Crypto` `Chinese`
> [name=Curious]

## 先備知識

### 費馬分解
$p$ 和 $q$ 是 $n$ 的兩個因數，如果 $|p - q|$ 很小，可以假設 $p \gt q$

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

因為 $p - q$ 很小，所以 $b$ 也會很小，所以可以讓 $a$ 是
$$
\sqrt n + 1, \sqrt n + 2, \sqrt n + 3, ...
$$

當 $\sqrt{a^2 - n} \in \mathbb N$ 時，就可以計算得知 $a$ 和 $b$，進而分解 $n$

---
## 思路和解法
從 `chal.py` 可以看到 `p` 和 `q` 都是由 `base + 1` 加上一個 32 bits 的質數構建而來的，所以 `p` 和 `q` 基本上不會距離很遠，所以可以用費馬分解來分解 `n`，分解之後就可以計算出密鑰 `d` 來解密 `c`

> 實際上可以直接把 `n` 那去 http://factordb.com 就可以分解出 `p` 和 `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 %}