2025GHCTF新生赛-Crypto-WP

遇到了几个有意思的题记录一下

babysign

题目:

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
'''

可以发现这里$e$为偶数，与$\varphi (n)$是不互素的，所以没办法求出$d$，这里实际上是需在模素数的情况下开4次方根，开根可以直接用sagemath的roots方法，由于是在模p，q的情况下分别开根的，所以要用CRT将p，q合并。

exp:

# exp.sage
from Crypto.Util.number import *
p= 182756071972245688517047475576147877841
q= 305364532854935080710443995362714630091
c= 14745090428909283741632702934793176175157287000845660394920203837824364163635
n= 55807222544207698804941555841826949089076269327839468775219849408812970713531
PR.<x> = ZZ[]
f = x^4 - c
mp = [int(i[0]) for i in f.change_ring(GF(p)).roots()]
mq = [int(i[0]) for i in f.change_ring(GF(q)).roots()]
for m1 in mp:
    for m2 in mq:
        m = crt([m1, m2], [p, q])
        print(long_to_bytes(m))
# 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，由于给了$\varphi (n)$，所以和常规的RSA一样，可以直接求出解密指数$d$。

exp:

# exp.py
from Crypto.Util.number import *

n=2741832985459799195551463586200496171706401045582705736390510500694289553647578857170635209048629428396407631873312962021354740290808869502374444435394061448767702908255197762575345798570340246369827688321483639197634802985398882606068294663625992927239602442735647762662536456784313240499437659967114509197846086151042512153782486075793224874304872205720564733574010669935992016367832666397263951446340260962650378484847385424893514879629196181114844346169851383460163815147712907264437435463059397586675769959094397311450861780912636566993749356097243760640620004707428340786147078475120876426087835327094386842765660642186546472260607586011343238080538092580452700406255443887820337778505999803772196923996033929998741437250238302626841957729397241851219567703420968177784088484002831289722211924810899441563382481216744212304879717297444824808184727136770899310815544776369231934774967139834384853322157766059825736075553
phi=2741832985459799195551463586200496171706401045582705736390510500694289553647578857170635209048629428396407631873312962021354740290808869502374444435394061448767702908255197762575345798570340246369827688321483639197634802985398882606068294663625992927239602442735647762662536456784313240499437659967114509197784246608456057052779643060628984335578973450260519106769911425793594847759982583376628098472390090331415895352869275325656949958242181688663465437185437198392460569653734315961071709533645370007008616755547195108861900432818710027794402838336405197750190466425895582236209479543326147804766393022786785337752319686125574507066082357748118175068545756301823381723776525427724798780890160482013759497102382173931716030992837059880049832065500252713739288235410544982532170147652055063681116147027591678349638753796122845041417275362394757384204924094885233281257928031484806977974575497621444483701792085077113227851520
c=2675023626005191241628571734421094007494866451142251352071850033504791090546156004348738217761733467156596330653396106482342801412567035848069931148880296036606611571818493841795682186933874790388789734748415540102210757974884805905578650801916130709273985096229857987312816790471330181166965876955546627327549473645830218664078284830699777113214559053294592015697007540297033755845037866295098660371843447432672454589238297647906075964139778749351627739005675106752803394387612753005638224496040203274119150075266870378506841838513636541340104864561937527329845541975189814018246183215952285198950920021711141273569490277643382722047159198943471946774301837440950402563578645113393610924438585345876355654972759318203702572517614743063464534582417760958462550905093489838646250677941813170355212088529993225869303917882372480469839803533981671743959732373159808299457374754090436951368378994871937358645247263240789585351233
e = 65537

d = pow(e, -1, phi)
m = pow(c, d, n)
print(long_to_bytes(m))

# NSSCTF{W0W!!_Y0u_4r3_g00d_G03!!!}

EZ_Fermat

题目:

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
'''

这题看题目就知道要用费马小定理: $$\begin{gathered} p\mathrm{为}\mathrm{素}\mathrm{数}，\mathrm{对}\mathrm{任}\mathrm{意}\mathrm{的}\mathrm{整}\mathrm{数}a，\mathrm{有}: \\ {a}^p\equiv a\mathrm{mod}p \end{gathered}$$ 这里要用到费马小定理的一个推论: $$a^{p^i}\equiv a\mathrm{mod}p$$ 通过反复使用费马小定理可以得到这个推论。

对于题目所给的$w$，有: $$w\equiv 2^{f(p)}\equiv 2^{\sum _0^{332}{a}_i{p}^i}\equiv \prod _0^{332}{2}^{a_i{p}^i}\equiv \prod _0^{332}{2}^{a_i}\mathrm{mod}p$$

所以: $$p\mid w-\prod _0^{332}{2}^{a_i}$$

所以$w-\prod _0^{332}{2}^{a_i}$与$n$的最大公因数就是$p$，成功分解$n$后就是常规的RSA解密了。

exp:

# exp.sage
from Crypto.Util.number import long_to_bytes
R.<x> = ZZ[]
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
p = gcd(w - pow(2, sum(f.coefficients()), n), n)
q = n // p
d = pow(e, -1, (p-1)*(q-1))
m = pow(c, d, n)
print(long_to_bytes(ZZ(m)))

# NSSCTF{8d1e3405044a79b23a44a43084bd994b}

EZ_Fermat_bag_PRO

题目：

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
'''

这题难点在于$f$是一个二元多项式，如果还直接采取模p的方法的话，指数上会剩余q，这题的做法是用$f(x,y)$对$(n-x-y+1)$做带余除法： $$f(x,y)=k(x,y)(n-x-y+1)+r(y)$$ 由于除式是个一次项，所以余式$r(y)$只含变量$y$，然后就可以得到: $$w\equiv 2^{f(p,q)}\equiv 2^{k(p,q)(n-p-q+1)+r(q)}\equiv 2^{k(p,q)\varphi (n)+r(q)}\equiv 2^{r(q)}\mathrm{mod}n$$

然后采取和EZ_Fermat一样的做法就行。

exp:

# exp.sage
from Crypto.Util.number import *
P.<x,y> = ZZ[]
PR.<z> = ZZ[]
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
n = 95656952327201449381426394713246214670537600365883923624876350719801926817916514429721785287844335184715049179879891389941974481490433975689601829920289485889138252888029716516069912637121531561601839948367426922036690701168975937162280451323099126372019216020898338909808577022618554997063496690156977790629
w = 12796020294902567574981427270787776254781813995526831579805652479456168245098217943847166109912113827479436654134179666391771173421469188197935460525521295192736123648410762964187396897298542198935971755852754544978564521188423737649175136194386664628304164316905741781089536713701674793641345344818309314224
c = 10266913434526071998707605266130137733134248608585146234981245806763995653822203763396430876254213500327272952979577138542487120755771047170064775346450942
g = f % (n - x - y + 1)
g = g(0, z)
q = GCD(pow(2, g(1), n) - w, n)
p = n // q

diff = b"NSSCTF{" + b"0"*80 + b"}"
diff = bytes_to_long(diff)
M = column_matrix([2**(8*(80 - i)) for i in range(80)] + [diff-c] + [p])
M = M.augment(identity_matrix(81).stack(zero_vector(81)))
MLLL = M.LLL()
v = MLLL[0]
v = v[-1]*v
print("NSSCTF{", end="")
for i in v[1:-1]:
    print(str(i), end="")
print("}")
# NSSCTF{38886172735077060750460332815973614272222523052135584902884007925985948919714862}

baby_factor_revenge

题目：

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
"""

这题与baby_factor的区别是需要我们必须分解$n$，题目给了$n,phi$，那么我们就得到了两个关于$p,q,r$的两个等式，由于变量多了一个，所以没办法利用解方程来分解$n$。这里用到的分解技巧可以看我写的这篇文章: [多素数RSA]利用phi(n)分解n

exp:

# exp.py
from Crypto.Util.number import *
n=3191868707489083296976422171754481125088448532695639929013026951283334085716937496519972309690132954050242378974370025245594553866043111294840209514577676946872746793700126873931085112786381515154186105142460622301297252278473097650013016482539838576476763183025029834004241446095147665598581368214114851984460699747964946764645986828307675081596907634022110868102739948513844625534865764252668312850364286204872187001344218083941399088833989233474318289529103178632284291007694811574023047207470113594082533713524606268388742119103653587354956091145288566437795469230667897089543048576812362251576281067933183713438502813206542834734983616378764909202774603304124497453696792428111112644362307853143219890039129054302905340695668256116233515323529918746264727874817221051242387145263342018617858562987223211598238069486447049955021864781104312134816578626968386395835285074116149472750100154961405785440009296096563521430833
phi=3191868707489083296976422171754481125088448532695639929013026951283334085716937496519972309690132954050242378974370025245594553866043111294840209514577676946872746793700126873931085112786381515154186105142460622301297252278473097650013016482539838576476763183025029834004241446095147665598581368214114851984394758254181484105857103844940487787404078873566779953101987404891507588290232992132681729619718279684673827347612899406697514777723904351697638562060304399923174376216080338949397741477013367831377040866937433520175862575061413321076151761545984886547872427147498175814451096795344136954743868643889768901204954902708679102384061694877757565486240670882343628571424084461972849147495569088820011108794930593172573959423278140327579049114196086428504291102619820322231225943837444001821535593671764186251713714593498207219093585758479440828038119079608764008747539277397742897542501803218788455452391287578171880267200
c=8847973599594272436100870059187158819529199340583461915617467299706215012295598155778224026186157290320191983062022702191439286020733625396165573681688842631368993650799220713225485752608650482408353598320160571916055498330875851476520668973214124194890108144336715482373743731578734960096351460142579903010557821654345995923836938260379746304222820835040419844947019844885128550552066290798665884099701340641403329066058638137944934073185448687990744852400616823426082588916251127609191094346267837812018236673478691437630461425526779014305216914035039981685211625653600564431704400207095883904994772993227506462664
t = 0
s = phi
while (s % 2 == 0):
    s //= 2
    t += 1
factor = set()
for a in range(2, 10):
    p = GCD(pow(a, s, n) - 1, n)
    if 1 < p < n:
            factor.add(p)

    for i in range(t):
        p = GCD(pow(a, 2**t*s, n) + 1, n)
        if 1 < p < n:
            factor.add(p)
factor = list(factor)

pqr = []
pqr.append(GCD(factor[0], factor[1]))
pqr.append(factor[0]//pqr[0])
pqr.append(factor[1]//pqr[0])
pqr = sorted(pqr)

p, q, r = pqr
e = 65537
d = pow(e, -1, (p-1)*(q-1))
m = pow(c, d, p*q)
print(long_to_bytes(m))
# NSSCTF{D0_Y0u_knnn0www_p71!!!}

MIMT_RSA

题目：

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
'''

这题题目已经告诉了我们是MIMT攻击，这里说一下它的原理，对于本题而言，漏洞点在于$\text{KEY}$不是素数，所以$\text{KEY}=k_1{k}_2$，这里我们可以猜测$k_1,k_2$是比较接近的，也就是$k_1\approx k_2\approx \sqrt{\text{KEY}}$ 我们已知: $$ck\equiv {\text{KEY}}^e\equiv k_1^e{k}_2^e\mathrm{mod}n$$ 稍加变形得: $$ck\cdot k_1^{-e}\equiv k_2^e\mathrm{mod}n$$

这里$\text{KEY}$是36bits，所以$k_1,k_2$大概18bits，我们可以先枚举$k_1$，求出$ck\cdot k_1^{-e}$的所有可能值放到集合中$S$中，然后枚举$k_2$，看看$k_2^e$是否存在于$S$中，如果存在，就说明我们找到了$k_1,k_2$。可以发现，由于查找的时间复杂度是$O(lg(k_2))$，所以总的时间复杂度是$O(\sqrt{k_1}\text{log}(k_2))$，相比直接枚举$\text{KEY}$的时间复杂度$O(k_1{k}_2)$要快不少。最后实测下来其中一个因子的大小是17bits。 exp:

# exp.py
from Crypto.Util.number import *
from hashlib import md5
from tqdm import trange

n = 26563847822899403123579768059987758748518109506340688366937229057385768563897579939399589878779201509595131302887212371556759550226965583832707699167542469352676806103999861576255689028708092007726895892953065618536676788020023461249303717579266840903337614272894749021562443472322941868357046500507962652585875038973455411548683247853955371839865042918531636085668780924020410159272977805762814306445393524647460775620243065858710021030314398928537847762167177417552351157872682037902372485985979513934517709478252552309280270916202653365726591219198063597536812483568301622917160509027075508471349507817295226801011
e = 65537
ck = 8371316287078036479056771367631991220353236851470185127168826270131149168993253524332451231708758763231051593801540258044681874144589595532078353953294719353350061853623495168005196486200144643168051115479293775329183635187974365652867387949378467702492757863040766745765841802577850659614528558282832995416523310220159445712674390202765601817050315773584214422244200409445854102170875265289152628311393710624256106528871400593480435083264403949059237446948467480548680533474642869718029551240453665446328781616706968352290100705279838871524562305806920722372815812982124238074246044446213460443693473663239594932076

def get_KEY():
    l = []
    begin, end = 2**16, 2**17
    for k2 in trange(begin, end):
        l.append(ck*pow(k2, -e, n) % n)

    begin, end = 2**36 // end, 2**36 // begin
    for k1 in trange(begin, end):
        tmp = pow(k1, e, n)
        if tmp in l:
            k1, k2 = k1, l.index(tmp)
            return k1, k2

k1, k2 = get_KEY()
KEY = k1 * (k2 + 2**16)
assert ck == pow(KEY, e, n)
flag = b'NSSCTF{' + md5(str(KEY).encode()).hexdigest().encode() + b'}'
print(flag)

# NSSCTF{14369380f677abec84ed8b6d0e3a0ba9}

baby_lattice

题目：

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}')

题目给了30组如下的等式: $$g_i\equiv t_i\ast key+z\mathrm{mod}p$$ 即: $$g_i=t_i\ast key+z-k_{i}p$$

注意到$z$是比较小的，可以构造如下的格： $$\left(\begin{array}{cccccc}{g}_1& g_2& \cdots & g_{30}& 1& \\ t_1& t_2& \cdots & t_{30}& & 1\\ p\\ & p\\ & & \ddots \\ & & & p\end{array}\right)$$ 这个格具有如下的小向量: $$(1,-key,k_1,k_2,\cdots ,k_{30})\left(\begin{array}{cccccc}{g}_1& g_2& \cdots & g_{30}& 1& \\ t_1& t_2& \cdots & t_{30}& & 1\\ p\\ & p\\ & & \ddots \\ & & & p\end{array}\right)=(z_1,z_2,\cdots ,z_{30},1,-key)$$ $z_i$是比较小的，所以对格使用格基规约算法可能可以得到这个短向量。这里我们还需要稍微调整一下，让这个向量的各分量都比较接近，这样更容易得到我们想要的答案，最终我们构造一个如下的格，具有如下的短向量: $$(1,-key,k_1,k_2,\cdots ,k_{30})\left(\begin{array}{cccccc}{2}^{112}{g}_1& 2^{112}{g}_2& \cdots & 2^{112}{g}_{30}& 2^{512}& \\ 2^{112}{t}_1& 2^{112}{t}_2& \cdots & 2^{112}{t}_{30}& & 1\\ 2^{112}p\\ & 2^{112}p\\ & & \ddots \\ & & & 2^{112}p\end{array}\right)=(2^{112}{z}_1,2^{112}{z}_2,\cdots ,2^{112}{z}_{30},2^{512},-key)$$

因为$key$与$p$的大小相近，所以最后格出来的实际上是$key-p$

exp:

# exp.sage
from Crypto.Util.number import *
from Crypto.Cipher import AES
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'

num = 30
M = matrix([gs[:num], ts[:num]])
M = M.stack(p * identity_matrix(num))

M = 2**112 * M
I = matrix([[2**512, 0],
            [0,      1]])
M = M.augment(I.stack(zero_matrix(30, 2)))
MLLL = M.LLL()
key = MLLL[1][-1] + p
cipher = AES.new(str(key).encode()[:16], AES.MODE_CBC,iv)
flag=cipher.decrypt(ciphertext)
print(flag)
# NSSCTF{F@@@un7_L4444t1c3333!!}

RSA_and_DSA

题目：

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{xxxxxxxxx}"
ciphertext = cipher.encrypt(pad(flag.encode(), 16))
print(f"{ciphertext = }")
'''
c_ink= 84329531596553394336538987023357227935440127545924398750500007122949822951975451942488164538560925222694222413022235832336439700420379598454619959178424907616592885325169668838139433265501326382467741883799799897305247164532663683724926267222341485376684034461780316163663624769479766276645610470850267093664
e= 100797590979191597676081881632112443200677974501832055481332601002844223186483558337099380805371010917502984674789369037985572270571944684404114475915036053451756526659905789324413633016308331745100752282051937597697581233757669107763643041665187533373053952694612521031477624363476981177214961821456672635823
N= 133020919573254586736009662994351483197630110046444622015176359062686053521475990861985101412597512894313048001198942449066636145265799205815566892581351543233960812384316942438814742826123037762680960898927252792974233266551853930274479435403549161383103059746381782668941421906340168652870371226382805032027
(r1,s1)= (105538622724986198173818280402723234123231812870, 165871242333491991006684781121637801537623792920)
(r2,s2)= (895673018852361693797535983771888430717799939767, 511956887428148277909616673338517730698888202223)
g= 97444164915108666817264719918456841236668149777715575246719562319277238318814584882880249446488655758781498681349330709135670188875982069778879957837454582916193915374305422049064769688749957611500682447936476425649642359105731049262259786188565867271216015835626264543593116387612078934710741467063982007499
q= 974306102330898613562307019447798934376234044213
p= 113996945917185663452903189185812083054654586038361814576057637684218572059191009152754335053396974825607186512631652893899380922217026759410880236546966561476761050482902589270845489570126254333374605973087540746242818447451510386137109253463070487353845675998098620056687507969012229115435439218407426962991
y= 8015503667614219250943034151839311927430676423719991507127801373333532219335171760992873121586820712328636972152697436159934583810723294897449200937370031784164230148453787378834760102389031574149857480339843366568164403131143385627621208571673677878768568991050568882099039880976450795530322753270408770484
ciphertext = b'\xb0\ra\x9c\xeb9y\xd5k\xfde\xdfJ\xba\n\xce^u\xae\x81J8\xe4\x8da\xdf;H@WV5'
'''

RSA部分

这里发现d只有200bits，符合weiner攻击的条件： $$d<\frac{1}{3}{N}^{0.25}$$ 通过weiner攻击，我们就可以获得获取私钥d，解密得到ink。

DAS部分

DAS方案中，每次签名都应该使用两个不同的随机数，而这里进行的两次签名使用的随机数是k，k+ink，这样根据签名的等式，我们就有如下两组方程:

$$\begin{array}{r}k\ast s_1\equiv h+x{r}_1\mathrm{mod}q\\ (k+ink)\ast s_2\equiv h+x{r}_2\mathrm{mod}q\end{array}$$ 刚好2个未知量，联立解出x即可。

exp:

# exp.py
from Crypto.Util.number import *
from gmpy2 import iroot
import hashlib
from Crypto.Cipher import AES

# RSA
c_ink= 84329531596553394336538987023357227935440127545924398750500007122949822951975451942488164538560925222694222413022235832336439700420379598454619959178424907616592885325169668838139433265501326382467741883799799897305247164532663683724926267222341485376684034461780316163663624769479766276645610470850267093664
e= 100797590979191597676081881632112443200677974501832055481332601002844223186483558337099380805371010917502984674789369037985572270571944684404114475915036053451756526659905789324413633016308331745100752282051937597697581233757669107763643041665187533373053952694612521031477624363476981177214961821456672635823
N= 133020919573254586736009662994351483197630110046444622015176359062686053521475990861985101412597512894313048001198942449066636145265799205815566892581351543233960812384316942438814742826123037762680960898927252792974233266551853930274479435403549161383103059746381782668941421906340168652870371226382805032027

class ContinuedFraction():
    def __init__(self, numerator, denumerator):
        self.numberlist = []  # number in continued fraction
        self.fractionlist = []  # the near fraction list
        self.GenerateNumberList(numerator, denumerator)
        self.GenerateFractionList()

    def GenerateNumberList(self, numerator, denumerator):
        while numerator != 1:
            quotient = numerator // denumerator
            remainder = numerator % denumerator
            self.numberlist.append(quotient)
            numerator = denumerator
            denumerator = remainder

    def GenerateFractionList(self):
        self.fractionlist.append([self.numberlist[0], 1])
        for i in range(1, len(self.numberlist)):
            numerator = self.numberlist[i]
            denumerator = 1
            for j in range(i):
                temp = numerator
                numerator = denumerator + numerator * self.numberlist[i - j - 1]
                denumerator = temp
            self.fractionlist.append([numerator, denumerator])


a = ContinuedFraction(e, N)
for k, d in a.fractionlist:
    if d.bit_length() == 200:
        phi = (e*d - 1) // k
        delta = iroot((phi - N - 1)**2 - 4*N, 2)
        if delta[1]:
            delta = int(delta[0])
            p, q = (delta - phi + N + 1) // 2, (-delta - phi + N + 1) // 2
            break
assert p*q == N
d = pow(e, -1, (p-1)*(q-1))
ink = pow(c_ink, d, N)
print(f"{ink = }")

# DSA
(r1,s1)= (105538622724986198173818280402723234123231812870, 165871242333491991006684781121637801537623792920)
(r2,s2)= (895673018852361693797535983771888430717799939767, 511956887428148277909616673338517730698888202223)
g= 97444164915108666817264719918456841236668149777715575246719562319277238318814584882880249446488655758781498681349330709135670188875982069778879957837454582916193915374305422049064769688749957611500682447936476425649642359105731049262259786188565867271216015835626264543593116387612078934710741467063982007499
q= 974306102330898613562307019447798934376234044213
p= 113996945917185663452903189185812083054654586038361814576057637684218572059191009152754335053396974825607186512631652893899380922217026759410880236546966561476761050482902589270845489570126254333374605973087540746242818447451510386137109253463070487353845675998098620056687507969012229115435439218407426962991
y= 8015503667614219250943034151839311927430676423719991507127801373333532219335171760992873121586820712328636972152697436159934583810723294897449200937370031784164230148453787378834760102389031574149857480339843366568164403131143385627621208571673677878768568991050568882099039880976450795530322753270408770484
ciphertext = b'\xb0\ra\x9c\xeb9y\xd5k\xfde\xdfJ\xba\n\xce^u\xae\x81J8\xe4\x8da\xdf;H@WV5'
msg = b'GHCTF-2025'
h = int(hashlib.sha256(msg).digest().hex(),16)
pri = x = (h*s1 - h*s2 - ink*s1*s2)*pow(r1*s2 - r2*s1, -1, q) % q

key = hashlib.sha1(str(pri).encode()).digest()[:16]
cipher = AES.new(key, AES.MODE_ECB)
flag = cipher.decrypt(ciphertext)
print(f"{flag = }")
# NSSCTF{n0_RRRrs4_or_DDDS4????}

这里其实可以不用管RSA，因为ink只有20bits，直接爆破也行：

exp:

# brute.py
from Crypto.Util.number import *
import hashlib
from Crypto.Cipher import AES
from tqdm import trange

# DSA
(r1,s1)= (105538622724986198173818280402723234123231812870, 165871242333491991006684781121637801537623792920)
(r2,s2)= (895673018852361693797535983771888430717799939767, 511956887428148277909616673338517730698888202223)
g= 97444164915108666817264719918456841236668149777715575246719562319277238318814584882880249446488655758781498681349330709135670188875982069778879957837454582916193915374305422049064769688749957611500682447936476425649642359105731049262259786188565867271216015835626264543593116387612078934710741467063982007499
q= 974306102330898613562307019447798934376234044213
p= 113996945917185663452903189185812083054654586038361814576057637684218572059191009152754335053396974825607186512631652893899380922217026759410880236546966561476761050482902589270845489570126254333374605973087540746242818447451510386137109253463070487353845675998098620056687507969012229115435439218407426962991
y= 8015503667614219250943034151839311927430676423719991507127801373333532219335171760992873121586820712328636972152697436159934583810723294897449200937370031784164230148453787378834760102389031574149857480339843366568164403131143385627621208571673677878768568991050568882099039880976450795530322753270408770484
ciphertext = b'\xb0\ra\x9c\xeb9y\xd5k\xfde\xdfJ\xba\n\xce^u\xae\x81J8\xe4\x8da\xdf;H@WV5'
msg = b'GHCTF-2025'
h = int(hashlib.sha256(msg).digest().hex(),16)
for ink in trange(2**19, 2**20):
    pri = x = (h*s1 - h*s2 - ink*s1*s2)*pow(r1*s2 - r2*s1, -1, q) % q
    key = hashlib.sha1(str(pri).encode()).digest()[:16]
    cipher = AES.new(key, AES.MODE_ECB)
    flag = cipher.decrypt(ciphertext)
    if flag.startswith(b"NSSCTF{"):
        print(flag)
        break
# NSSCTF{n0_RRRrs4_or_DDDS4????}

Sin

题目：

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
'''

知乎上有个很像但比这题简单的版本：

设k是一个10位整数，且sqrt（k）的小数点后15位为418400286617716，求k。？

这题老套路了，之前在shctf上有道差不多的，只不过shctf那题是$\cos$。 这里我们先化简: $$\begin{array}{rl}c& =2\sin (m)-2\sin (m)\cos (2m)\\ & =2\sin (m)(1-\cos (2m))\\ & =4{\sin }^3(m)\end{array}$$ 所以: $$\arcsin ((\frac{c}{4}{)}^{\frac{1}{3}})=m+k\pi$$ 其中$m,k$是整数。 为了方便，这里记$\arcsin ((\frac{c}{4}{)}^{\frac{1}{3}})\mathrm{为}{m}_{fake}$

实数域上这个等式是成立的。但在计算机上不一定，假设我们对$m_{fake},\pi$都只取1024比特的精度，那么实际上是会存在一个非常小的误差$ϵ$: $$m_{fake}=m+k\pi +ϵ$$ 即： $$ϵ=m_{fake}-m-k\pi$$

所以我们可以构造一个如下的格: $$(-m,1,-k)\left(\begin{array}{ccc}1& 1& 0\\ m_{fake}& 0& 1\\ \pi & 0& 0\end{array}\right)=(ϵ,-m,1)$$ 这里为了让目标向量的各个分量比较均衡，所以对格稍微调整一下： $$(-m,1,-k)\left(\begin{array}{ccc}{2}^{1024}& 1& 0\\ 2^{1024}{m}_{fake}& 0& 2^{256}\\ 2^{1024}\pi & 0& 0\end{array}\right)=(2^{1024}ϵ,-m,2^{256})$$

exp:

exp.sage
from Crypto.Util.number import *
c = 0.002127416739298073705574696200593072466561264659902471755875472082922378713642526659977748539883974700909790177123989603377522367935117269828845667662846262538383970611125421928502514023071134249606638896732927126986577684281168953404180429353050907281796771238578083386883803332963268109308622153680934466412
sin_m = (c / 4).nth_root(3)
fake_m = arcsin(sin_m)
PI = pi.n(1024)

M = column_matrix([1, QQ(fake_m), QQ(PI)])
M = 2**1024 * M 
I = matrix([[1, 0],
            [0, 2**256]])
M = M.augment(I.stack(vector([0, 0])))
ML = M.LLL()
# print(ML[0])
# for i in ML[0]:
#     print(i.n())
flag = abs(ML[0][1])
print(long_to_bytes(int(flag)))
# NSSCTF{just_make_a_latter_and_LLL_is_OK_padpad}

river

题目：

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from hashlib import md5
from secret import flag, seed, mask


class 踩踩背:
    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 == n
lfsr1 = 奶龙(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))}")
# mask = 9494051593829874780
# output = 13799267741689921474
# enc = b'\x03\xd1#\xb9\xaa5\xff3y\xba\xcb\x91`\x9d4p~9r\xf6i\r\xca\x03dW\xdb\x9a\xd2\xa6\xc6\x85\xfa\x19=b\xb2)5>]\x05,\xeb\xa0\x12\xa9\x1e' 

这题一开始以为就是个简单的lfsr破解，直接把output当成lfsr的连续64bits输出去做了，结果发现output并不是lfsr的连续64bits输出。 但是可以发现output是由lfsr的连续64bits决定的，所以我们先试试能不能从output推出lfsr的连续64bits。

获取lfsr的输出

假设lfsr的前64bits输出如下： $$\mathbf{a}=(a_1,a_2,a_3,\cdots ,a_{64})$$ output第i位的输出逻辑是：

• 如果$\mathbf{a}$的第i位是1，那么更新lfsr的状态，输出当前状态的最后1bits
• 如果$\mathbf{a}$的第i位是0，那么不更新lfsr的状态，输出当前状态的最后1bits

根据这个输出逻辑，我们可以知道output一定是$\mathbf{a}$中的元素，output的第k位一定来自于$\mathbf{a}$的第i位，i不超过a。

output转化为二进制向量如下: $$(1,0,1,1,\cdots ,0,1,0)$$ 我们可以知道$a_2,a_3$一定是1，因为output在第1位到第2位、第2位到3位发生了变化，也就是lfsr的状态一定更新了，而且我们还可以推出$a_1$一定是0，因为如果$a_1$是1的话，我们可以按照output的生成逻辑，得出output的第2位也是1，这与事实矛盾。 这样我们得到了$\mathbf{a}$的前缀是$(0,1,1)$，然后可以利用 递归从前往后求解$\mathbf{a}$。

递归函数为dfs(index, prefix, output)

假设我们已经知道了$\mathbf{a}$的k位前缀(代码中记作prefix)： $$(a_1,a_2,\cdots ,a_k)$$ 假设output的第k位来自于$\mathbf{a}$第i位(代码中记作index) 然后考虑output的第k+1位：

1. 如果output的第k+1位等于$\mathbf{a}$的第i位，说明lfsr可能没有更新，prefix后面就应该再加上0，即dfs(index, prefix[:] + [0], output)
2. 如果output的第k+1位等于$\mathbf{a}$的第i位且output的第k+1等于$\mathbf{a}$的第i+1位，说明lfsr可能更新了，prefix后面应该再加上1，即dfs(index+1, prefix[:] + [1], output)
3. 如果output的第k+1位不等于$\mathbf{a}$的第i位且output的第k+1位不等于$\mathbf{a}$的第i+1位，说明这是矛盾的。
4. 如果output的第k+1位不等于$\mathbf{a}$的第i位且output的第k+1位等于$\mathbf{a}$的第i+1位，说明lfsr只可能是更新了，prefix后面应该再加上1，即dfs(index+1, prefix[:] + [1], output)

就这样往后面递归，直到prefix的长度达到64，就说明已经找到了$\mathbf{a}$的一种情况。

破解lfsr

lfsr在生成随机数的过程中，一直在维护一个状态，这个状态由64个比特构成，我们可以把它记作： $$\mathbf{state}=(s_1,s_2,\cdots ,s_{64})$$ 加密过程还需要一个掩码mask,我们记作： $$\mathbf{mask}=(m_1,m_2,\cdots ,m_{64})$$ 然后将这两个向量作内积，得到的就是输出比特，要注意这里的运算是在$GF(2)$上进行的(可以简单的理解为所有运算都要模2，保证数据只有1比特的大小)。那么新的状态可以表示为： $${\mathbf{state}}^{{}^{\prime }}=(s_2,s_3,\cdots ,s_{64},\mathbf{state}\cdot {\mathbf{mask}}^T)$$ 我们可以把它写作矩阵形式： $${\mathbf{state}}^{{}^{\prime }}=\mathbf{state}\left(\begin{array}{ccccc}& & & & m_1\\ 1& & & & m_2\\ & 1& & & m_3\\ & & \ddots & & ⋮\\ & & & 1& m_{64}\end{array}\right)$$ 将这个矩阵作用64次后得到的状态，就是lfsr的连续64比特的输出，即： $$\mathbf{a}=\mathbf{state}{\left(\begin{array}{ccccc}& & & & m_1\\ 1& & & & m_2\\ & 1& & & m_3\\ & & \ddots & & ⋮\\ & & & 1& m_{64}\end{array}\right)}^{64}$$ 所以有了$\mathbf{a}$后，只需要右乘一个矩阵逆原就可以恢复初始状态，从而得到seed。

exp:

# exp.sage
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from hashlib import md5
from tqdm import trange

mask = 9494051593829874780
output = 13799267741689921474
enc = b'\x03\xd1#\xb9\xaa5\xff3y\xba\xcb\x91`\x9d4p~9r\xf6i\r\xca\x03dW\xdb\x9a\xd2\xa6\xc6\x85\xfa\x19=b\xb2)5>]\x05,\xeb\xa0\x12\xa9\x1e' 
n = int(64)

class 踩踩背:
    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)



def dfs(index, prefix, output):
    all_result = []
    if len(prefix) == 64:
        return [prefix]
    next_num = len(prefix)
    if prefix[index] == output[next_num]:
        result = dfs(index, prefix[:] + [0], output)
        for r in result:
            if r != None:
                all_result.append(r)
        if prefix[index+1] == output[next_num]:
            result = dfs(index + 1, prefix[:] + [1], output)
            for r in result:
                if r != None:
                    all_result.append(r)
    if prefix[index] != output[next_num]:
        if prefix[index + 1] == output[next_num]:
            result = dfs(index + 1, prefix[:] + [1], output)
            for r in result:
                if r != None:
                    all_result.append(r)
        else:
            return [None]
    return all_result
    
mask = matrix(GF(2), [int(b) for b in f"{mask:0{64}b}"])
M = zero_matrix(GF(2), 1, 63).stack(identity_matrix(GF(2), 63)).augment(mask.T)
M = M^64
assert M.rank() == n
M_inv = M^(-1)

index = 1
prefix = [0, 1, 1]
output = [int(i) for i in bin(output)[2:].zfill(64)]
all_result = dfs(index, prefix, output)


for i in trange(len(all_result)):
    v = vector(GF(2), all_result[i])
    fake_s = v*M_inv
    seed = 0
    for i in fake_s.change_ring(ZZ):
        seed <<= 1
        seed ^^= i
    flag = AES.new(key=md5(str(seed).encode()).digest(), mode=AES.MODE_ECB).decrypt(enc)
    if flag[:32].isascii():
        print(flag)
# flag{5b322a2b-8d15-43b3-88f0-ee1586f1cf4f}