ez_fac

转 无趣的浅

n = a_{0}^{2} + e*b_{0}^{2}

n = a_{1}^{2} + e*b_{1}^{2}

\Rightarrow b_{0}^{2}*n - b_{1}^{2}*n = b_{0}^{2}*(a_{1}^{2} + e*b_{1}^{2}) - b_{1}^{2}*(a_{0}^{2} + e*b_{0}^{2})

\Rightarrow (b_{0}^{2} - b_{1}^{2})*n = b_{0}^{2}*a_{1}^{2} - b_{1}^{2}*a_{0}^{2}

\Rightarrow (b_{0}^{2} - b_{1}^{2})*n = (b_{0}*a_{1} - b_{1}*a_{0})*(b_{0}*a_{1}+b_{1}*a_{0})

\Rightarrow p = gcd(n,(b_{0}*a_{1}+b_{1}*a_{0}))

from gmpy2 import *
from Crypto.Util.number import *
from pwn import *

# ------------ 交互部分 ------------
host = 'node4.anna.nssctf.cn'
port = 28052
conn = remote(host, port)
conn.interactive()

c= 49822450398039686880486254487101437483448254235092826961284551737144212205646111791465056733438285393367754585052991076631696140669884384676693226693791434596401668014694011823602484287090368863296079154607793929218086795310022728031178434548513882909541668680069229104955244132194029196891849965782273357589
n= 85727473305545653447808079210618243755608471863792992171396768139703519284776826565159685035542577584485964108550078191335468847145300913886481048062801304524021242407675493302783019253912127439252772393431533857654128073208678027945554558319866096431675861939482542499339069772092888573070105917491017426299
a0= 9258913181661530918742635495443953035742795143905324057951823942319649598855774377635643743597167186161050684365640332709405353605768272605622477358719082
a1= 9258913181661530918742634745288912680596662661021506088139076157908383249960356364839651537235383678810400723341378148819628103544366819978284243753200182
b0= 42915799843775492921042849752381809791532781265400578518092836975695368224449477009762606251800581675105098420248057044335
b1= 213787302482413175545111447355422661984444503473122071005677522836057175203098934672699337171319743669140250265475479604305

p = GCD(a1*b0 + a0*b1,n)
q = n//p
e = ( n - pow(a0,2) )//pow(b0,2)
phi = (p-1)*(q-1)
d = inverse(e,phi)
m = pow(c,d,n)
flag = long_to_bytes(m)
print(flag)