2025GHCTF新生赛-Crypto-WP
新申赛说是...
babysign
题目: 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19from 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\)为偶数，与\(\phi(n)\)是不互素的，所以没办法求出\(d\)，这里实际上是需在模素数的情况下开4次方根，开根可以直接用sagemath的roots方法，由于是在模p，q的情况下分别开根的，所以要用CRT将p，q合并。
exp: 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15# 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
题目: 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21from 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
"""
exp: 1
2
3
4
5
6
7
8
9
10
11
12
13# 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
题目: 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32from 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
'''
这题看题目就知道要用费马小定理: \[ p为素数，对任意的整数a，有:\\ a^p \equiv a \mod p \] 这里要用到费马小定理的一个推论: \[ a^{p^i} \equiv a \mod p \] 通过反复使用费马小定理可以得到这个推论。
对于题目所给的\(w\)，有: \[ w \equiv 2^{f(p)} \equiv 2^{\sum^{332}_0a_ip^i} \equiv \prod^{332}_02^{a_ip^i} \equiv \prod^{332}_02^{a_i} \mod p \]
所以: \[ p \mid w - \prod^{332}_02^{a_i} \]
所以\(w - \prod^{332}_02^{a_i}\)与\(n\)的最大公因数就是\(p\)，成功分解\(n\)后就是常规的RSA解密了。
exp: 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15# 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
题目： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32from 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)\phi(n) + r(q)} \equiv 2^{r(q)} \mod n \]
然后采取和EZ_Fermat一样的做法就行。
exp: 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25# 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
题目： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23from 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: 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34# 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
题目： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27from 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_1k_2\)，这里我们可以猜测\(k_1,k_2\)是比较接近的，也就是\(k_1 \approx k_2 \approx \sqrt{\text{KEY}}\) 我们已知: \[ ck \equiv \text{KEY}^e \equiv k_1^ek_2^e \mod n \] 稍加变形得: \[ ck \cdot k_1^{-e} \equiv k_2^e \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_1k_2)\)要快不少。最后实测下来其中一个因子的大小是17bits。
exp: 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30# 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
题目： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28from 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 * key + z \mod p \] 即: \[ g_i = t_i * key + z - k_ip \]
注意到\(z\)是比较小的，可以构造如下的格： \[ \begin{pmatrix} g_1 & g_2 & \cdots & g_{30} & 1 & \\ t_1 & t_2 & \cdots & t_{30} & & 1\\ p \\ &p\\ &&\ddots\\ &&&p \end{pmatrix} \] 这个格具有如下的小向量: \[ (1, -key, k_1, k_2, \cdots, k_{30}) \begin{pmatrix} g_1 & g_2 & \cdots & g_{30} & 1 & \\ t_1 & t_2 & \cdots & t_{30} & & 1\\ p \\ &p\\ &&\ddots\\ &&&p \end{pmatrix} = (z_1, z_2, \cdots, z_{30}, 1, -key) \] \(z_i\)是比较小的，所以对格使用格基规约算法可能可以得到这个短向量。这里我们还需要稍微调整一下，让这个向量的各分量都比较接近，这样更容易得到我们想要的答案，最终我们构造一个如下的格，具有如下的短向量: \[ (1, -key, k_1, k_2, \cdots, k_{30}) \begin{pmatrix} 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{pmatrix} = (2^{112}z_1, 2^{112}z_2, \cdots, 2^{112}z_{30}, 2^{512}, -key) \]
因为\(key\)与\(p\)的大小相近，所以最后格出来的实际上是\(key-p\)
exp:
1 | # exp.sage |
RSA_and_DSA
题目： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67from 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{aligned} k*s_1 \equiv h + xr_1 \mod q \\ (k+ink)*s_2 \equiv h + xr_2 \mod q \end{aligned} \] 刚好2个未知量，联立解出x即可。
exp: 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69# 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: 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25# 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
题目： 1
2
3
4
5
6from 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{aligned} c&=2\sin(m) - 2\sin(m)\cos(2m)\\ &=2\sin(m)(1-\cos(2m))\\ &=4\sin^3(m) \end{aligned} \] 所以: \[ \arcsin((\frac{c}{4})^{\frac{1}{3}}) = m + k\pi \] 其中\(m,k\)是整数。 为了方便，这里记\(\arcsin((\frac{c}{4})^{\frac{1}{3}})为m_{fake}\)
实数域上这个等式是成立的。但在计算机上不一定，假设我们对\(m_{fake}, \pi\)都只取1024比特的精度，那么实际上是会存在一个非常小的误差\(\epsilon\): \[ m_{fake} = m + k\pi + \epsilon \] 即： \[ \epsilon = m_{fake} - m - k\pi \]
所以我们可以构造一个如下的格: \[ (-m, 1, -k) \begin{pmatrix} 1&1&0\\ m_{fake}&0&1\\ \pi&0&0\\ \end{pmatrix} = (\epsilon, -m, 1) \] 这里为了让目标向量的各个分量比较均衡，所以对格稍微调整一下： \[ (-m, 1, -k) \begin{pmatrix} 2^{1024}&1&0\\ 2^{1024}m_{fake}&0&2^{256}\\ 2^{1024}\pi&0&0\\ \end{pmatrix} = (2^{1024}\epsilon, -m, 2^{256}) \]
exp: 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19exp.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
题目： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42from 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位：
- 如果output的第k+1位等于\(\mathbf{a}\)的第i位，说明lfsr可能没有更新，prefix后面就应该再加上0，即dfs(index, prefix[:] + [0], output)
- 如果output的第k+1位等于\(\mathbf{a}\)的第i位且output的第k+1等于\(\mathbf{a}\)的第i+1位，说明lfsr可能更新了，prefix后面应该再加上1，即dfs(index+1, prefix[:] + [1], output)
- 如果output的第k+1位不等于\(\mathbf{a}\)的第i位且output的第k+1位不等于\(\mathbf{a}\)的第i+1位，说明这是矛盾的。
- 如果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}^{'} = ( s_2, s_3, \cdots, s_{63}, \mathbf{state} \cdot \mathbf{mask}^T ) \] 我们可以把它写作矩阵形式： \[ \mathbf{state}^{'} = \mathbf{state} \begin{pmatrix} &&&&m_1\\ 1&&&&m_2\\ &1&&&m_3\\ &&\ddots&&\vdots\\ &&&1&m_{64} \end{pmatrix} \] 将这个矩阵作用64次后得到的状态，就是lfsr的连续64比特的输出，即： \[ \mathbf{a} = \mathbf{state} \begin{pmatrix} &&&&m_1\\ 1&&&&m_2\\ &1&&&m_3\\ &&\ddots&&\vdots\\ &&&1&m_{64} \end{pmatrix}^{64} \] 所以有了\(\mathbf{a}\)后，只需要右乘一个矩阵逆原就可以恢复初始状态，从而得到seed。
exp: 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86# 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}