[GWCTF 2019]BabyRSA1

1.题目代码：

# import hashlib
# import sympy
# from Crypto.Util.number import *
#
# N=636585149594574746909030160182690866222909256464847291783000651837227921337237899651287943597773270944384034858925295744880727101606841413640006527614873110651410155893776548737823152943797884729130149758279127430044739254000426610922834573094957082589539445610828279428814524313491262061930512829074466232633130599104490893572093943832740301809630847541592548921200288222432789208650949937638303429456468889100192613859073752923812454212239908948930178355331390933536771065791817643978763045030833712326162883810638120029378337092938662174119747687899484603628344079493556601422498405360731958162719296160584042671057160241284852522913676264596201906163
# m1=90009974341452243216986938028371257528604943208941176518717463554774967878152694586469377765296113165659498726012712288670458884373971419842750929287658640266219686646956929872115782173093979742958745121671928568709468526098715927189829600497283118051641107305128852697032053368115181216069626606165503465125725204875578701237789292966211824002761481815276666236869005129138862782476859103086726091860497614883282949955023222414333243193268564781621699870412557822404381213804026685831221430728290755597819259339616650158674713248841654338515199405532003173732520457813901170264713085107077001478083341339002069870585378257051150217511755761491021553239
# m2=487443985757405173426628188375657117604235507936967522993257972108872283698305238454465723214226871414276788912058186197039821242912736742824080627680971802511206914394672159240206910735850651999316100014691067295708138639363203596244693995562780286637116394738250774129759021080197323724805414668042318806010652814405078769738548913675466181551005527065309515364950610137206393257148357659666687091662749848560225453826362271704292692847596339533229088038820532086109421158575841077601268713175097874083536249006018948789413238783922845633494023608865256071962856581229890043896939025613600564283391329331452199062858930374565991634191495137939574539546
#
# flag = 'GWHT{******}'
# secret = '******'
#
# assert(len(flag) == 38)
#
# half = len(flag) / 2
#
# flag1 = flag[:half]
# flag2 = flag[half:]
#
# secret_num = getPrime(1024) * bytes_to_long(secret)
#
# p = sympy.nextprime(secret_num)
# q = sympy.nextprime(p)
#
# N = p * q
#
# e = 0x10001
#
# F1 = bytes_to_long(flag1)
# F2 = bytes_to_long(flag2)
#
# c1 = F1 + F2
# c2 = pow(F1, 3) + pow(F2, 3)
# assert(c2 < N)
#
# m1 = pow(c1, e, N)
# m2 = pow(c2, e, N)

2.复现

直接分解n，发现可以分解。

 直接看代码吧，懒得解释了，大概就是flag被分成了2部分，F1,F2 。

题目给出了一个方程组F1+F2=c1,F1^3+F3^3=c2.

p,q知道了,c1,c2就可以算出来了，就解上面这个方程求出F1和F2。

主要是(x+y)(x²-xy+y²)，所以可以化解为2次方程求解，用sympy的Symbol解方程。

import sympy
import gmpy2
import libnum
n=636585149594574746909030160182690866222909256464847291783000651837227921337237899651287943597773270944384034858925295744880727101606841413640006527614873110651410155893776548737823152943797884729130149758279127430044739254000426610922834573094957082589539445610828279428814524313491262061930512829074466232633130599104490893572093943832740301809630847541592548921200288222432789208650949937638303429456468889100192613859073752923812454212239908948930178355331390933536771065791817643978763045030833712326162883810638120029378337092938662174119747687899484603628344079493556601422498405360731958162719296160584042671057160241284852522913676264596201906163
m1=90009974341452243216986938028371257528604943208941176518717463554774967878152694586469377765296113165659498726012712288670458884373971419842750929287658640266219686646956929872115782173093979742958745121671928568709468526098715927189829600497283118051641107305128852697032053368115181216069626606165503465125725204875578701237789292966211824002761481815276666236869005129138862782476859103086726091860497614883282949955023222414333243193268564781621699870412557822404381213804026685831221430728290755597819259339616650158674713248841654338515199405532003173732520457813901170264713085107077001478083341339002069870585378257051150217511755761491021553239
m2=487443985757405173426628188375657117604235507936967522993257972108872283698305238454465723214226871414276788912058186197039821242912736742824080627680971802511206914394672159240206910735850651999316100014691067295708138639363203596244693995562780286637116394738250774129759021080197323724805414668042318806010652814405078769738548913675466181551005527065309515364950610137206393257148357659666687091662749848560225453826362271704292692847596339533229088038820532086109421158575841077601268713175097874083536249006018948789413238783922845633494023608865256071962856581229890043896939025613600564283391329331452199062858930374565991634191495137939574539546
# e = int(0x10001)
# print(e)
e=65537
p=797862863902421984951231350430312260517773269684958456342860983236184129602390919026048496119757187702076499551310794177917920137646835888862706126924088411570997141257159563952725882214181185531209186972351469946269508511312863779123205322378452194261217016552527754513215520329499967108196968833163329724620251096080377747699
q=797862863902421984951231350430312260517773269684958456342860983236184129602390919026048496119757187702076499551310794177917920137646835888862706126924088411570997141257159563952725882214181185531209186972351469946269508511312863779123205322378452194261217016552527754513215520329499967108196968833163329724620251096080377748737
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
c1=pow(m1,d,n)
c2=pow(m2,d,n)
# print(c1)
# print(c2)
# 2732509502629189160482346120094198557857912754
# 5514544075236012543362261483183657422998274674127032311399076783844902086865451355210243586349132992563718009577051164928513093068525554
# (x+y)(x²-xy+y²)
c=c2//c1#F1^2-F1*F2+F2^2
# 二元二次方程组
x = sympy.Symbol('x')
y= sympy.Symbol('y')
solved_value=sympy.solve([x**2-x*y+y**2-c,x+y-c1], [x,y])
# print(solved_value)
# [(1141553212031156130619789508463772513350070909, 1590956290598033029862556611630426044507841845), (1590956290598033029862556611630426044507841845, 1141553212031156130619789508463772513350070909)]
flag1=libnum.n2s(1141553212031156130619789508463772513350070909)
flag2=libnum.n2s(1590956290598033029862556611630426044507841845)
print(flag1,flag2)
# b'30ca8972959a1033b2}' b'GWHT{f709e0e2cfe7e5'
# GMHT{f709e0e2cfe7e530ca8972959a1033b2}