AIS3 2019 - RSA202 (Crypto, 209)

Challenge

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

N1=rnext_prime(r)N1 = r * next\_prime(r)

N2=pqN2 = 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

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

p=r4+r3+r2+r+1\Rightarrow p = r^4 + r^3 + r^2 + r + 1

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

分解 N1N1,N2N2 之後就是一般的 RSA 解密了。

AIS3{S0me7im3s_I_h4tE_factorDB}

Server : server.py

solve.py

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