> [name=Curious]

## 思路和解法
從 `chal.py` 可以知道 `n` 大約是 2048 bits，但是 `d` 只有 `500` bits，很明顯 $d \lt \frac{1}{3}n^{\frac{1}{4}}$，所以可以使用 Wiener Attack 來分解 `n`。

> 雖然有現成的 [Wiener Attack](https://github.com/orisano/owiener) 可以使用，但是我覺得自己刻一個可以跟了解這個攻擊

Solve Script :

from sage.all import Integer
from gmpy2 import iroot
from Crypto.Util.number import long_to_bytes

def wiener_attack(n: int, e: int):
    """
    - input : `n (int)`, `e (int)`
    - output : `(p, q, d) (int, int, int)`
    """

    continued_fraction_list = (Integer(e) / Integer(n)).continued_fraction()
    for i in range(2, len(continued_fraction_list)):
        cf = continued_fraction_list.convergent(i)
        k = cf.numerator()
        d = cf.denominator()
        if ((e * d - 1) % k) != 0:
            continue
        b = (e * d - 1) // k - n - 1
        if (b ** 2 - 4 * n) < 0:
            continue
        D = iroot(int(b ** 2 - 4 * n), 2)
        if not D[1]:
            continue
        p, q = ((-int(b) + int(D[0])) // 2), ((-int(b) - int(D[0])) // 2)
        if p * q == n:
            return p, q, int(d)


n, e = (???, ???)
c = ???

p, q, d = wiener_attack(n, e)

print(long_to_bytes(pow(c, d, n)))

{%hackmd M1bgOPoiQbmM0JRHWaYA1g %}