GHCTF2025-Crypto-WP
baby_signintask:由于gcd(e,(p-1)*(q-1)) 最大公因数为4，有限域开方即可（baby_factor普通的rsa解密（exp:EZ_Fermattask:先把x=1代入方程得到f(1) 然后费马即可baby_factor_revengetask:很经典的已知phi分解n ，分解出三个因子，然后都遍历一遍得到flag，类似于NKCTF2023的ezRSA的part1exp
baby_signin
task:
from Crypto.Util.number import getPrime, bytes_to_long
p=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
'''由于gcd(e,(p-1)*(q-1)) 最大公因数为4，有限域开方即可（
#sage
from Crypto.Util.number import *
p= 182756071972245688517047475576147877841
q= 305364532854935080710443995362714630091
c= 14745090428909283741632702934793176175157287000845660394920203837824364163635
n= 55807222544207698804941555841826949089076269327839468775219849408812970713531
e=4
P.<a>=PolynomialRing(Zmod(p),implementation='NTL')
f=a^e-c
mps=f.monic().roots()
P.<a>=PolynomialRing(Zmod(q),implementation='NTL')
g=a^e-c
mqs=g.monic().roots()
flag=[]
for mpp in mps:
x=mpp[0]
for mqq in mqs:
y=mqq[0]
solution = CRT_list([int(x), int(y)], [p, q])
flag.append(solution)
for i in flag:
m=long_to_bytes(i)
if b'NSSCTF'in m:
print(m)
#b'NSSCTF{4MM_1s_so_e4s7!}'baby_factor
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{xxx}'
p,q,r = pl[0],pl[1],pl[2]
e = 65537
n = p*q*r
phi = (p-1)*(q-1)*(r-1)
c=pow(bytes_to_long(m),e,n)
print(f'n={n}')
print(f'phi={phi}')
print(f'c={c}')
"""
n=2741832985459799195551463586200496171706401045582705736390510500694289553647578857170635209048629428396407631873312962021354740290808869502374444435394061448767702908255197762575345798570340246369827688321483639197634802985398882606068294663625992927239602442735647762662536456784313240499437659967114509197846086151042512153782486075793224874304872205720564733574010669935992016367832666397263951446340260962650378484847385424893514879629196181114844346169851383460163815147712907264437435463059397586675769959094397311450861780912636566993749356097243760640620004707428340786147078475120876426087835327094386842765660642186546472260607586011343238080538092580452700406255443887820337778505999803772196923996033929998741437250238302626841957729397241851219567703420968177784088484002831289722211924810899441563382481216744212304879717297444824808184727136770899310815544776369231934774967139834384853322157766059825736075553
phi=2741832985459799195551463586200496171706401045582705736390510500694289553647578857170635209048629428396407631873312962021354740290808869502374444435394061448767702908255197762575345798570340246369827688321483639197634802985398882606068294663625992927239602442735647762662536456784313240499437659967114509197784246608456057052779643060628984335578973450260519106769911425793594847759982583376628098472390090331415895352869275325656949958242181688663465437185437198392460569653734315961071709533645370007008616755547195108861900432818710027794402838336405197750190466425895582236209479543326147804766393022786785337752319686125574507066082357748118175068545756301823381723776525427724798780890160482013759497102382173931716030992837059880049832065500252713739288235410544982532170147652055063681116147027591678349638753796122845041417275362394757384204924094885233281257928031484806977974575497621444483701792085077113227851520
c=2675023626005191241628571734421094007494866451142251352071850033504791090546156004348738217761733467156596330653396106482342801412567035848069931148880296036606611571818493841795682186933874790388789734748415540102210757974884805905578650801916130709273985096229857987312816790471330181166965876955546627327549473645830218664078284830699777113214559053294592015697007540297033755845037866295098660371843447432672454589238297647906075964139778749351627739005675106752803394387612753005638224496040203274119150075266870378506841838513636541340104864561937527329845541975189814018246183215952285198950920021711141273569490277643382722047159198943471946774301837440950402563578645113393610924438585345876355654972759318203702572517614743063464534582417760958462550905093489838646250677941813170355212088529993225869303917882372480469839803533981671743959732373159808299457374754090436951368378994871937358645247263240789585351233
"""普通的rsa解密（
exp:
from Crypto.Util.number import *
n=2741832985459799195551463586200496171706401045582705736390510500694289553647578857170635209048629428396407631873312962021354740290808869502374444435394061448767702908255197762575345798570340246369827688321483639197634802985398882606068294663625992927239602442735647762662536456784313240499437659967114509197846086151042512153782486075793224874304872205720564733574010669935992016367832666397263951446340260962650378484847385424893514879629196181114844346169851383460163815147712907264437435463059397586675769959094397311450861780912636566993749356097243760640620004707428340786147078475120876426087835327094386842765660642186546472260607586011343238080538092580452700406255443887820337778505999803772196923996033929998741437250238302626841957729397241851219567703420968177784088484002831289722211924810899441563382481216744212304879717297444824808184727136770899310815544776369231934774967139834384853322157766059825736075553
phi=2741832985459799195551463586200496171706401045582705736390510500694289553647578857170635209048629428396407631873312962021354740290808869502374444435394061448767702908255197762575345798570340246369827688321483639197634802985398882606068294663625992927239602442735647762662536456784313240499437659967114509197784246608456057052779643060628984335578973450260519106769911425793594847759982583376628098472390090331415895352869275325656949958242181688663465437185437198392460569653734315961071709533645370007008616755547195108861900432818710027794402838336405197750190466425895582236209479543326147804766393022786785337752319686125574507066082357748118175068545756301823381723776525427724798780890160482013759497102382173931716030992837059880049832065500252713739288235410544982532170147652055063681116147027591678349638753796122845041417275362394757384204924094885233281257928031484806977974575497621444483701792085077113227851520
c=2675023626005191241628571734421094007494866451142251352071850033504791090546156004348738217761733467156596330653396106482342801412567035848069931148880296036606611571818493841795682186933874790388789734748415540102210757974884805905578650801916130709273985096229857987312816790471330181166965876955546627327549473645830218664078284830699777113214559053294592015697007540297033755845037866295098660371843447432672454589238297647906075964139778749351627739005675106752803394387612753005638224496040203274119150075266870378506841838513636541340104864561937527329845541975189814018246183215952285198950920021711141273569490277643382722047159198943471946774301837440950402563578645113393610924438585345876355654972759318203702572517614743063464534582417760958462550905093489838646250677941813170355212088529993225869303917882372480469839803533981671743959732373159808299457374754090436951368378994871937358645247263240789585351233
d = inverse(65537, phi)
m_int = pow(c, d, n)
flag = long_to_bytes(m_int)
print(flag)
#b'NSSCTF{W0W!!_Y0u_4r3_g00d_G03!!!}'EZ_Fermat
task:
from Crypto.Util.number import getPrime, bytes_to_long
from secret import f
flag = 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
'''先把x=1代入方程得到f(1) 然后费马即可
根据题目中 w = 2^(f(p)) mod n，并利用费马小定理有 2^(f(p)) ≡ 2^(f(1)) (mod p)
所以 p 整除 (2^(f(1)) - w)from Crypto.Util.number import long_to_bytes, inverse, GCD
from sympy import sympify, symbols
n = 101780569941880865465631942473186578520071435753163950944409148606282910806650879176280021512435190682009749926285674412651435782567149633130455645157688819845748439487113261739503325065997835517112163014056297017874761742768297646567397770742374004940360061700285170103292360590891188591132054903101398360047
e = 65537
c = 77538275949900942020886849496162539665323546686749270705418870515132296087721218282974435210763225488530925782158331269160555819622551413648073293857866671421886753377970220838141826468831099375757481041897142546760492813343115244448184595644585857978116766199800311200819967057790401213156560742779242511746
w = 32824596080441735190523997982799829197530203904568086251690542244969244071312854874746142497647579310192994177896837383837384405062036521829088599595750902976191010000575697075792720479387771945760107268598283406893094243282498381006464103080551366587157561686900620059394693185990788592220509670478190685244
f_str = """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"""
x = symbols('x')
f_poly = sympify(f_str)
f1 = int(f_poly.subs(x, 1))
#print("f(1) =", f1)
v = pow(2, f1, n)
p = GCD(n, v - w)
q = n // p
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m = pow(c, d, n)
flag = long_to_bytes(m)
print(flag)
b'NSSCTF{8d1e3405044a79b23a44a43084bd994b}'baby_factor_revenge
task:
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
"""很经典的已知phi分解n ，分解出三个因子，然后都遍历一遍得到flag，类似于NKCTF2023的ezRSA的part1
exp:
from math import gcd
from math import isqrt
from random import randrange
from gmpy2 import is_prime
def 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:
# Element to factorize.
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:
# We can remove the element to factorize now, because we have a factorization.
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)
# Continue in the outer loop
break
i += 1
return tuple(prime_factors)
if __name__ == '__main__':
n = 3191868707489083296976422171754481125088448532695639929013026951283334085716937496519972309690132954050242378974370025245594553866043111294840209514577676946872746793700126873931085112786381515154186105142460622301297252278473097650013016482539838576476763183025029834004241446095147665598581368214114851984460699747964946764645986828307675081596907634022110868102739948513844625534865764252668312850364286204872187001344218083941399088833989233474318289529103178632284291007694811574023047207470113594082533713524606268388742119103653587354956091145288566437795469230667897089543048576812362251576281067933183713438502813206542834734983616378764909202774603304124497453696792428111112644362307853143219890039129054302905340695668256116233515323529918746264727874817221051242387145263342018617858562987223211598238069486447049955021864781104312134816578626968386395835285074116149472750100154961405785440009296096563521430833
phi = 3191868707489083296976422171754481125088448532695639929013026951283334085716937496519972309690132954050242378974370025245594553866043111294840209514577676946872746793700126873931085112786381515154186105142460622301297252278473097650013016482539838576476763183025029834004241446095147665598581368214114851984394758254181484105857103844940487787404078873566779953101987404891507588290232992132681729619718279684673827347612899406697514777723904351697638562060304399923174376216080338949397741477013367831377040866937433520175862575061413321076151761545984886547872427147498175814451096795344136954743868643889768901204954902708679102384061694877757565486240670882343628571424084461972849147495569088820011108794930593172573959423278140327579049114196086428504291102619820322231225943837444001821535593671764186251713714593498207219093585758479440828038119079608764008747539277397742897542501803218788455452391287578171880267200
c = 8847973599594272436100870059187158819529199340583461915617467299706215012295598155778224026186157290320191983062022702191439286020733625396165573681688842631368993650799220713225485752608650482408353598320160571916055498330875851476520668973214124194890108144336715482373743731578734960096351460142579903010557821654345995923836938260379746304222820835040419844947019844885128550552066290798665884099701340641403329066058638137944934073185448687990744852400616823426082588916251127609191094346267837812018236673478691437630461425526779014305216914035039981685211625653600564431704400207095883904994772993227506462664
e=65537
fac = factorize_multi_prime(n, phi)
#print(fac)
for p in fac:
for q in fac:
n=p*q
d=gmpy2.invert(e,(p-1)*(q-1))
m=pow(c,d,n)
if b'NSSCTF{' in long_to_bytes(m):
print(long_to_bytes(m))
break
#b'NSSCTF{D0_Y0u_knnn0www_p71!!!}'baby_lattice
task:
from Crypto.Util.number import *
from Crypto.Cipher import AES
import os
from Crypto.Util.Padding import pad
from secret import flag
miku = 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}')
'''
p = 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'
'''很经典的hnp问题,解出key,再求aes,构格方式类似:https://dexterjie.github.io/2023/08/25/%E6%A0%BC%E5%AF%86%E7%A0%81%E8%BF%9B%E9%98%B6/#BabyHNP：
#sage
q = 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]
A=ts
B=gs
K = 2^400
ge=matrix(QQ,32,32)
for i in range(30):
ge[i,i]=q
ge[-2,i]=A[i]
ge[-1,i]=-B[i]
ge[-2,-2]=K/q
ge[-1,-1]=K
l=ge.LLL()
key=l[1][-2]/(K/q)%q
print(key)
#8822339647694935089915197969905863773289879929485897803998091330537213988642290800374856766322959957004685197416863851570012301749195861223023504873219753
#python
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
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'
key=8822339647694935089915197969905863773289879929485897803998091330537213988642290800374856766322959957004685197416863851570012301749195861223023504873219753
print(key.bit_length())
key_bytes = str(key).encode()[:16]
cipher = AES.new(key_bytes, AES.MODE_CBC, iv)
decrypted = cipher.decrypt(ciphertext)
flag = unpad(decrypted, 16)
print(flag)
#b'NSSCTF{F@@@un7_L4444t1c3333!!}'MIMT_RSA
task:
from Crypto.Util.number import *
from hashlib import md5
from 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
'''一个中间相遇问题，key为36位的话，其实就是把ck=key^e mod n拆成ck=A^ e* B^e modn，两个值的位数可能一个17位，一个19位，或者是16位和20位，这时候不断去爆破逼近即可（
exp:
from Crypto.Util.number import *
from hashlib import *
from tqdm import tqdm
n = 26563847822899403123579768059987758748518109506340688366937229057385768563897579939399589878779201509595131302887212371556759550226965583832707699167542469352676806103999861576255689028708092007726895892953065618536676788020023461249303717579266840903337614272894749021562443472322941868357046500507962652585875038973455411548683247853955371839865042918531636085668780924020410159272977805762814306445393524647460775620243065858710021030314398928537847762167177417552351157872682037902372485985979513934517709478252552309280270916202653365726591219198063597536812483568301622917160509027075508471349507817295226801011
e = 65537
ck = 8371316287078036479056771367631991220353236851470185127168826270131149168993253524332451231708758763231051593801540258044681874144589595532078353953294719353350061853623495168005196486200144643168051115479293775329183635187974365652867387949378467702492757863040766745765841802577850659614528558282832995416523310220159445712674390202765601817050315773584214422244200409445854102170875265289152628311393710624256106528871400593480435083264403949059237446948467480548680533474642869718029551240453665446328781616706968352290100705279838871524562305806920722372815812982124238074246044446213460443693473663239594932076
precomputed = {}
for A in range(2**16,2**18):
precomputed[pow(A, e, n)] = A
print('done')
for B in range(2**18,2**20):
B_inv_e = inverse(pow(B, e, n), n)
target = (ck * B_inv_e) % n
if target in precomputed:
A = precomputed[target]
KEY = A * B
print(f"Found KEY: {KEY}")
break
flag=b'NSSCTF{' + md5(str(KEY).encode()).hexdigest().encode() + b'}'
print(flag)
EZ_Fermat_bag_PRO
task:
from Crypto.Util.number import getPrime, bytes_to_long
from random import *
from secret import f, flag
assert 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
'''这题的目的是求出p,可以把y写成n//x，然后x=1代入多项式方程组，然后就是费马解了 和上面那个费马差不多，就可以求出p来（
exp:
from sympy import symbols, sympify
from Crypto.Util.number import *
n = 95656952327201449381426394713246214670537600365883923624876350719801926817916514429721785287844335184715049179879891389941974481490433975689601829920289485889138252888029716516069912637121531561601839948367426922036690701168975937162280451323099126372019216020898338909808577022618554997063496690156977790629
w = 12796020294902567574981427270787776254781813995526831579805652479456168245098217943847166109912113827479436654134179666391771173421469188197935460525521295192736123648410762964187396897298542198935971755852754544978564521188423737649175136194386664628304164316905741781089536713701674793641345344818309314224
c = 10266913434526071998707605266130137733134248608585146234981245806763995653822203763396430876254213500327272952979577138542487120755771047170064775346450942
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'''
x, y = symbols('x y')
f_expr = sympify(f)
f_substituted = f_expr.subs(y, n // x)
f1 = int(f_substituted.subs(x, 1))
#print("f(1) =", f1)
v = pow(2, f1, n)
p = GCD(n, v - w)
print(p)
#12887845651556262230127533819087214645114299622757184262163859030601366568025020416006528177186367994745018858915213064803349065489849643880676026721892753
然后就是求flag,其中flag大于p，且大于的较多所以没办法爆破求解,同时flag具有一定特殊性
因为
assert all(chr(i) in ''.join(list(set(str(p)))) for i in flag[7:-1:])这句代码意思是 flag的组成都是p的数字，也就是说flag都是0-9的数字组成。
这里参考easy_mod系列：https://tangcuxiaojikuai.xyz/post/94c7e291.html
exp:
from Crypto.Util.number import *
p = 12887845651556262230127533819087214645114299622757184262163859030601366568025020416006528177186367994745018858915213064803349065489849643880676026721892753
c = 10266913434526071998707605266130137733134248608585146234981245806763995653822203763396430876254213500327272952979577138542487120755771047170064775346450942
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] = 5
L[-2,-1] = -c
L[-1,-1] = p
L[:,-1:] *= p
res = L.BKZ()
flag = ""
for i in res[:-1]:
if(abs(i[-2]) == 5 and all(abs(j) < 10 for j in i[:-2])):
for j in i[:-2][::-1]:
flag += chr(48 + abs(j))
print(flag)
#38886172735077060750460332815973614272222523052135584902884007925985948919714862所以flag为：NSSCTF{38886172735077060750460332815973614272222523052135584902884007925985948919714862}
RSA_and_DSA
task:
from random import getrandbits, randint
from secrets import randbelow
from Crypto.Util.number import*
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
import hashlib
import random
import gmpy2
ink=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的线性关系
先维纳攻击求出d1来 然后求ink即可，后是线性K的DSA签名,类似于NSSRound#1 Basic的number_by_number
exp:
from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from RSAwienerHacker import *
import hashlib
c_ink= 75517502692097831363443739147565176367247985201143975453326891807623085586665800338505194812511215986799510259417486636115714543892322380908775898968005967267154089356401466517827082639942650711458196552847137272733225451581167527549711435805194039361007506436462393605949663173972848316802086005675594122447
e= 97127528017076464922170978933159739328499830874876612140194720448608536284451056980759925228574802703400503852897647806707933102198339936307176078592550748707182506634151382952065240918923594664309561466538540752851827183955776181255541306419282376724578231110985180090748520497985751591062886932254909959583
N= 131342286566556880877092331187418465653855813425966929864425381510875531237549624989644814104311810243468058174748867544024292263674725375273146689145421426693384862215460097683187892351130513429928063652701077721570140977719823754701988835199434602294597102748436781125528389125846980183998136743830655746063
d=hack_RSA(e,N)
ink=pow(c_ink,d,N)
#print(ink)
(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'
h = int(hashlib.sha256(b'GHCTF-2025').digest().hex(),16)
a = s2*r1-r2*s1
b = (r1-r2)*h-ink*s2*r1
k = (b%q*inverse(a,q))%q
x = ((k*s1-h)%q*inverse(r1,q))%q
pri=x
key = hashlib.sha1(str(pri).encode()).digest()[:16]
cipher = AES.new(key, AES.MODE_ECB)
decrypted = unpad(cipher.decrypt(ciphertext), 16)
print(decrypted)
#b'NSSCTF{n0_RRRrs4_or_DDDS4????}'Sin
task:
from Crypto.Util.number import bytes_to_long; print((2 * sin((m := bytes_to_long(b'NSSCTF{test_flag}'))) - 2 * sin(m) * cos(2 * m)).n(1024))
'''
m的值即为flag
0.002127416739298073705574696200593072466561264659902471755875472082922378713642526659977748539883974700909790177123989603377522367935117269828845667662846262538383970611125421928502514023071134249606638896732927126986577684281168953404180429353050907281796771238578083386883803332963268109308622153680934466412
'''三角函数等式为：2*sin(m)-2sin(m)cos(2m)，化简一下得到4sin(m)^3 。所以先除以4然后再开三次根得到sin(m),再造格得到满足的预期即可（
exp
from Crypto.Util.number import *
c = RealField(1024)(0.002127416739298073705574696200593072466561264659902471755875472082922378713642526659977748539883974700909790177123989603377522367935117269828845667662846262538383970611125421928502514023071134249606638896732927126986577684281168953404180429353050907281796771238578083386883803332963268109308622153680934466412)
data = (c / 4) ** (1/3)
c=data.n(1024)
#print(c)
asin = arcsin(c)
RR = RealField(1024)
pi = RR(pi)
Ge = Matrix(QQ,[
[1, 0, 2^800],
[0, 2^400, 2^800*asin],
[0, 0, 2^800*2*pi]
])
m = Ge.LLL()
for i in m:
if abs(i[1])==2^400:
mm=long_to_bytes(int(abs(i[0])))
print(mm)
#b'NSSCTF{just_make_a_latter_and_LLL_is_OK_padpad}'END