Challenge

連線後，會收到兩組透過 RSA 加密的 FLAG

$N1 = r * next_prime(r)$

$N2 = p * q$

並提示 ：
p,q,r is prime
((p-1) % r)**2 + ((r**5 - 1) % p)**2 == 0

Solution

由於，質數與質數之間的距離不會太遠，我們可以由 Fermat’s factorization 來分解由兩個相近質數組成的合數。

而另一個題提示： ((p-1) % r)**2 + ((r**5 - 1) % p)**2 == 0

$\Rightarrow r\ |\ (p-1),\ \ \ p\ |\ (r^{5}-1)$

$\Rightarrow p = r^4 + r^3 + r^2 + r + 1$

由 Fermat’s factorization 得來的 r，可以直接計算出 ｐ

分解 $N1$,$N2$ 之後就是一般的 RSA 解密了。

AIS3{S0me7im3s_I_h4tE_factorDB}

Server : server.py

solve.py

P.S. 這題原本是 task.py，不過不知道是誰把他上傳到 Factordb，為了公平性所以重出了 QwQ … 拜託各位以後解題不要做這種事啦 QwQ … 。