Qiwi Infosec CTF 2016: Crypto 400_2

,

http://factordb.com/に投げたら$n$は平方数だって言われたので即終了。 $e^{\phi(n)} \equiv 1 \pmod n$で使うEuler関数$\phi(p^2) = p^2(1 - \frac{1}{p}) = p(1-p)$なことに注意。

#!/usr/bin/env python3
n = 158168890645747636339512652656727367370140893295030333823920833363025940906055891357316994482461476576118114207681214323912652527927215053128809927932495206979837034713724140745400652922252749994983891690894724877897453440237829719520264826887839607084620792280551479756249230842706713662875715392719130358089
e = 65537
c = 140823625180859595137593494178968497314300266616869468408596741823165198698204065579249727536890649445240801729293482339393915146972721826733382396566284303449925618355682242041225432010603850355326962069585919704623290128021782032477132287121179121257196031074006842188551083381364957799238533440938240326919

import gmpy2
p = gmpy2.isqrt(n)
assert p * p == n

d = gmpy2.invert(e, (p-1)*p)
m = pow(c, d, n)
flag = bytes.fromhex(hex(m)[2:]).decode()
print(flag)