[TSGCTF 2021]Minimalists_Private

• 已知

  $$\begin{gathered} {}^L\equiv 1(\mathrm{mod}N) \\ e\ast d\equiv 1(\mathrm{mod}L) \\ {L}^2\le 10000\ast N \end{gathered}$$

  即$L=\phi (N)/g$，所以有

  KaTeX parse error: Expected 'EOF', got '\right' at position 17: …eft((p-1)*(q-1)\̲r̲i̲g̲h̲t̲)^2 \le 10000*p…

  左边近似

  $${}^2$$

  右边近似

  所以就是

  $$\le 10000\ast g^2$$

  其实就是说明$(p-1,q-1)$有个非常大的因子。

• 考虑使用$Phllard’srho$去分解它。

from xenny.ctf.crypto.modern.asymmetric.rsa.common_prime import factor_the_modulus
from gmpy2 import *
from Crypto.Util.number import long_to_bytes

N, e = (1108103848370322618250236235096737547381026108763302516499816051432801216813681568375319595638932562835292256776016949573972732881586209527824393027428125964599378845347154409633878436868422905300799413838645686430352484534761305185938956589612889463246508935994301443576781452904666072122465831585156151, 65537)
c = 254705401581808316199469430068831357413481187288921393400711004895837418302514065107811330660948313420965140464021505716810909691650540609799307500282957438243553742714371028405100267860418626513481187170770328765524251710154676478766892336610743824131087888798846367363259860051983889314134196889300426

p ,q = factor_the_modulus.big_gamma_factor(N)
assert p*q == N

d = invert(e, (p-1)*(q-1))

print(long_to_bytes(powmod(c, d, N)))
​