2025 GHCTF（校赛） Writeup

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

题目给了如下的等式

2^{f(p)} \equiv w \ (mod\ n)

我们带入多项式并展开，有

2^{2*x^{332}} * 2^{-x^{331}} + \dots +2^{-x^2}+ 2^{-1} \equiv w\ (mod\ n)

其实要是对应因式分解熟悉一点的，都知道考点可能是费马小定理

我们简单测试一下

x = var('x')
for i in range(1, 334):
    f = x ^ i - 1
    print(f.factor())

    
'''
这边就简单放几组
x - 1
(x + 1)*(x - 1)
(x^2 + x + 1)*(x - 1)
(x^2 + 1)*(x + 1)*(x - 1)
(x^4 + x^3 + x^2 + x + 1)*(x - 1)
(x^2 + x + 1)*(x^2 - x + 1)*(x + 1)*(x - 1)
(x^6 + x^5 + x^4 + x^3 + x^2 + x + 1)*(x - 1)
(x^4 + 1)*(x^2 + 1)*(x + 1)*(x - 1)
(x^6 + x^3 + 1)*(x^2 + x + 1)*(x - 1)
(x^4 + x^3 + x^2 + x + 1)*(x^4 - x^3 + x^2 - x + 1)*(x + 1)*(x - 1)

'''

可以看到每个因式分解都带 $x-1$ ，然后 $x$ 又等于p，那么很明显就是费马小定理了

那现在我们就要构造出 $x^i - 1$ ，这边的 $i$ 就是每个多项式对应的系数

也就是我们可以构造出如下的等式

2^{2*(x^{332} - 1)} * 2^{-(x^{331} - 1)} * \dots * 2^{-(x^2-1)} * 2^{-1} \equiv w*2^{-2} * 2 * \dots * 2\ (mod\ n)

然后转为模p意义下，在依据费马小定理，有

2^{-1} \equiv w*2^{-2} * 2 * \dots * 2\ (mod\ p)

也就是

\begin{array}{l} 2* w*2^{-2} * 2 * \dots * 2\ \equiv 1 (mod\ p)\\ 2* w*2^{-2} * 2 * \dots * 2\ -1 \equiv 0 (mod\ p) \end{array}

和 $n$ 进行 $gcd$ 即可求得 $p$

exp：

from Crypto.Util.number import long_to_bytes, inverse
from gmpy2 import gcd

x = var('x')
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
for i in f.list()[1::]:
    w *= 2 ^ (-ZZ(i))
    w %= n

p = gcd(w * 2 - 1,  n)
q = n // p
print(long_to_bytes(pow(c, inverse(e, (p - 1) * (q - 1)), n)))  #b'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
e = 65537
c = 32384071331939239285992149489589967884022349189352515487950255250160126611084915524664364190130039873461090810189570222748422757594726643684332100753373557666031160718150203596579825955216919802911458293840557069152132506518827761626306871971480050052005979083878379439210757328323337697175682026549870910934
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

这次是有p又有q了，但是思路其实差不多的，考点都是费马

一个等式中，如果同时含有p和q的话，我们是没办法提取公因子，所以我们要想办法消掉其中一个

观察多项式，可知我们只要给原版的多项式乘上 $p^{32}$ ，就可以消掉全部的 $q$ ，然后再根据乘完后对应的系数，使用原先的做法即可

推导如下：

\begin{array}{l} 2^{f(p)} \equiv w\ (mod\ n)\\ 2^{f(p) * p^{32}} \equiv w^{p^{32}}\ (mod\ n) \end{array}

转到模 $p$ ，根据费马小定理，有：

2^{f(p) * p^{32}} \equiv w\ (mod\ p)

然后和上一题一样的推导即可

题目的第二部分，实际上只要造个简单的格就可以解决，有代码我们可以知道， $flag$ 的所有字符（去掉头和尾）都是由 $0-9$ 构成的，并且长度为 $80$ ，我们假设 $m_a$ 表示NSSCTF{， $m_b$ 表示为}，中间八十个都是数字的字符表示为 $m_1-m_{80}$ （从右往左看），转为整数的值设为 $m$ ，那么显然我们有如下的等式

\begin{array}{l} c \equiv 256^{81} * m_a + 256 *m + m_b \ (mod\ p)\\ m \equiv (c - 256 ^ {81} * m_a - m_b) * 256^{-1}\ (mod\ p)\\ m \equiv c_0\ (mod\ p)\\ \end{array}

也就是

\sum_{i=1}^{80}m_i * 256^{i-1} \equiv c_0\ (mod\ p)

因为 $m_i$ 实际上可以表示为 $48 + t_i$ ，这时候的 $t_i$ 的值就是 $0-9$ ，相对来说更短，可以增加规约的成功率

可以构造如下的格

\begin{bmatrix} 1 & & & & & & 256^{0}\\ & 1 & & & & & 256^{1}\\ & & \ddots & & & & \vdots \\ & & & 1 & & & 256^{78} \\ & & & & 1 & & 256^{79}\\ & & & & & 1 & -c_0 \\ & & & & & & p \end{bmatrix}

该格满足

(t_1,\ t_2,\ \cdots,\ t_{79},\ t_{80},\ 1,\ k)\begin{bmatrix} 1 & & & & & & 256^{0}\\ & 1 & & & & & 256^{1}\\ & & \ddots & & & & \vdots \\ & & & 1 & & & 256^{78} \\ & & & & 1 & & 256^{79}\\ & & & & & 1 & -c_0 \\ & & & & & & p \end{bmatrix}(t_1,\ t_2,\ \cdots,\ t_{79},\ t_{80},\ 1,\ 0)

简单

下面是中间处理过程的一些代码：

p, q = var('p q')
P.<x,y> = PolynomialRing(ZZ)
x, y = P.gens()
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
f = x ^ 32 * f
print(f.subs(x = p, y = q))

'''
p^63 - p^62*q - 2*p^61*q^2 + 7*p^60*q^3 + 2*p^59*q^4 - 4*p^56*q^7 + 3*p^55*q^8 - p^52*q^11 - 4*p^51*q^12 + p^50*q^13 - 5*p^49*q^14 - 4*p^48*q^15 - p^47*q^16 + p^46*q^17 + p^45*q^18 + p^44*q^19 - 2*p^43*q^20 - 3*p^41*q^22 + 5*p^39*q^24 + p^38*q^25 + 6*p^36*q^27 + p^35*q^28 + 2*p^33*q^30 + p^32*q^31 - 2*p^62 - 3*p^61*q + 2*p^60*q^2 + 2*p^59*q^3 - p^58*q^4 - p^57*q^5 - 2*p^56*q^6 - 3*p^55*q^7 - 3*p^54*q^8 - 3*p^52*q^10 - 4*p^51*q^11 + 2*p^50*q^12 + p^47*q^15 - p^46*q^16 - 2*p^44*q^18 - 3*p^43*q^19 - p^42*q^20 + p^41*q^21 + 2*p^40*q^22 + p^39*q^23 + p^37*q^25 - p^36*q^26 - 2*p^35*q^27 - 2*p^34*q^28 - p^32*q^30 - 2*p^61 - p^60*q + 3*p^58*q^3 - p^57*q^4 - 2*p^56*q^5 + p^55*q^6 - p^54*q^7 - p^52*q^9 + 2*p^51*q^10 + 2*p^50*q^11 + p^48*q^13 + p^47*q^14 + p^46*q^15 + p^45*q^16 + p^44*q^17 + 5*p^43*q^18 - p^41*q^20 - 2*p^40*q^21 - 5*p^39*q^22 - 2*p^38*q^23 + 3*p^37*q^24 - 5*p^35*q^26 - p^34*q^27 + 2*p^33*q^28 - p^32*q^29 + 3*p^60 + 3*p^59*q - 2*p^58*q^2 + p^57*q^3 + 2*p^56*q^4 - p^55*q^5 - 2*p^54*q^6 - 3*p^52*q^8 - 3*p^51*q^9 + 4*p^49*q^11 - p^48*q^12 - 3*p^47*q^13 - 2*p^46*q^14 + p^45*q^15 + 2*p^44*q^16 - 2*p^43*q^17 + p^42*q^18 - 2*p^41*q^19 + p^40*q^20 - 2*p^39*q^21 - p^38*q^22 + p^37*q^23 - p^36*q^24 + p^35*q^25 + p^34*q^26 - p^33*q^27 - p^32*q^28 + p^59 + p^58*q - 2*p^56*q^3 + p^55*q^4 - 3*p^54*q^5 - 2*p^53*q^6 - 2*p^52*q^7 - 5*p^51*q^8 + 2*p^50*q^9 - 5*p^49*q^10 + p^48*q^11 - 3*p^47*q^12 - 4*p^46*q^13 - p^45*q^14 + p^44*q^15 + 3*p^43*q^16 + 2*p^42*q^17 - 4*p^41*q^18 - 2*p^38*q^21 + p^37*q^22 + 4*p^35*q^24 + 2*p^34*q^25 + 2*p^33*q^26 - 2*p^32*q^27 + p^57*q + p^56*q^2 + p^55*q^3 + 5*p^54*q^4 + p^52*q^6 - 3*p^51*q^7 + p^50*q^8 - p^49*q^9 + 2*p^47*q^11 - p^46*q^12 + 2*p^45*q^13 - p^44*q^14 + 4*p^43*q^15 - p^42*q^16 - 2*p^38*q^20 - p^37*q^21 + 3*p^35*q^23 + p^34*q^24 - 3*p^33*q^25 - 3*p^32*q^26 + 3*p^57 - 2*p^55*q^2 - p^53*q^4 + p^49*q^8 + 2*p^48*q^9 - p^47*q^10 - 2*p^46*q^11 - p^45*q^12 + 2*p^44*q^13 - 2*p^43*q^14 - p^41*q^16 - p^40*q^17 - p^38*q^19 - p^37*q^20 + p^36*q^21 + p^35*q^22 + 5*p^33*q^24 - 2*p^32*q^25 - p^56 + 2*p^55*q + p^54*q^2 - p^53*q^3 - p^51*q^5 + p^50*q^6 - p^49*q^7 + 2*p^48*q^8 - 4*p^47*q^9 - p^46*q^10 - p^45*q^11 - p^44*q^12 + 4*p^42*q^14 + 2*p^41*q^15 - p^40*q^16 - 2*p^39*q^17 - 2*p^38*q^18 + 4*p^37*q^19 + p^36*q^20 + 2*p^34*q^22 - 5*p^33*q^23 - p^32*q^24 + p^55 - p^54*q + 2*p^53*q^2 - p^52*q^3 - p^50*q^5 - p^49*q^6 - 5*p^47*q^8 + p^46*q^9 - 3*p^45*q^10 + 3*p^44*q^11 + 2*p^43*q^12 - 2*p^42*q^13 - 2*p^41*q^14 - p^40*q^15 + 2*p^39*q^16 - 2*p^38*q^17 - 4*p^37*q^18 - 5*p^35*q^20 - p^34*q^21 - p^33*q^22 - 4*p^32*q^23 - p^54 + 2*p^53*q - 2*p^52*q^2 - 2*p^51*q^3 - 3*p^49*q^5 - p^48*q^6 - p^47*q^7 + 4*p^45*q^9 + 2*p^44*q^10 + 3*p^43*q^11 + 2*p^42*q^12 - p^41*q^13 - p^39*q^15 + 2*p^38*q^16 + p^35*q^19 + 2*p^34*q^20 + 2*p^33*q^21 + 3*p^32*q^22 - 3*p^53 - p^52*q - p^51*q^2 + 2*p^49*q^4 - p^48*q^5 - p^47*q^6 + p^46*q^7 - 5*p^44*q^9 - 2*p^43*q^10 + p^42*q^11 + p^38*q^15 + p^37*q^16 + p^36*q^17 - 3*p^34*q^19 - 2*p^33*q^20 - 2*p^32*q^21 + p^52 + 2*p^51*q - 2*p^49*q^3 + 2*p^48*q^4 - 3*p^47*q^5 + 4*p^46*q^6 + 2*p^45*q^7 - p^44*q^8 - 2*p^43*q^9 + p^42*q^10 + 6*p^41*q^11 + p^40*q^12 + p^39*q^13 + 2*p^37*q^15 + 4*p^36*q^16 + p^35*q^17 - p^34*q^18 + 3*p^33*q^19 - p^49*q^2 + 2*p^48*q^3 + 3*p^46*q^5 - p^45*q^6 + 2*p^43*q^8 + p^42*q^9 + 3*p^41*q^10 - p^39*q^12 - p^38*q^13 + 3*p^37*q^14 - 4*p^36*q^15 + p^34*q^17 + 2*p^32*q^19 - p^50 - p^48*q^2 - 2*p^46*q^4 - 2*p^45*q^5 - 2*p^44*q^6 + 2*p^43*q^7 + 3*p^41*q^9 + 3*p^40*q^10 + p^38*q^12 - p^36*q^14 + 2*p^35*q^15 + 2*p^34*q^16 - 2*p^33*q^17 - p^49 - 4*p^48*q - 2*p^47*q^2 + 2*p^46*q^3 - p^45*q^4 + p^44*q^5 - 2*p^43*q^6 - 3*p^42*q^7 - p^41*q^8 - 5*p^40*q^9 + 2*p^39*q^10 + 2*p^38*q^11 - p^37*q^12 + p^36*q^13 - 3*p^34*q^15 + p^33*q^16 - 3*p^48 + p^47*q - 3*p^46*q^2 - p^45*q^3 - p^44*q^4 + 2*p^43*q^5 - p^42*q^6 + 5*p^40*q^8 + 3*p^39*q^9 + 3*p^38*q^10 + 2*p^37*q^11 + 4*p^36*q^12 + 2*p^35*q^13 + p^34*q^14 - 3*p^33*q^15 - p^47 + 3*p^46*q + p^45*q^2 - p^44*q^3 - 3*p^43*q^4 + p^42*q^5 - p^41*q^6 + 2*p^40*q^7 - p^39*q^8 + 4*p^37*q^10 - 2*p^36*q^11 + p^35*q^12 - p^46 + p^45*q + 2*p^44*q^2 + p^43*q^3 - 5*p^42*q^4 - p^41*q^5 - 3*p^40*q^6 - 2*p^39*q^7 + p^38*q^8 + 3*p^37*q^9 + p^36*q^10 + 2*p^35*q^11 - p^34*q^12 - 4*p^33*q^13 + 3*p^32*q^14 + p^44*q - 2*p^43*q^2 - p^41*q^4 - p^40*q^5 + 5*p^39*q^6 - 4*p^38*q^7 + 3*p^37*q^8 + 4*p^36*q^9 - 3*p^35*q^10 - p^34*q^11 - 2*p^33*q^12 - 3*p^32*q^13 + 3*p^44 + p^43*q + p^42*q^2 + p^41*q^3 + p^40*q^4 - p^38*q^6 - p^37*q^7 - 4*p^35*q^9 - p^34*q^10 - 3*p^33*q^11 - 2*p^32*q^12 + p^42*q + 5*p^41*q^2 + p^40*q^3 + 3*p^37*q^6 + p^36*q^7 + 2*p^35*q^8 - 4*p^34*q^9 + 2*p^33*q^10 + 3*p^32*q^11 - p^42 - 2*p^41*q - 2*p^39*q^3 - p^38*q^4 + p^37*q^5 + 3*p^36*q^6 - 2*p^34*q^8 - p^33*q^9 + 4*p^41 - 3*p^40*q - 3*p^38*q^3 + p^37*q^4 - p^36*q^5 - 2*p^35*q^6 - 2*p^34*q^7 + p^33*q^8 + 4*p^32*q^9 + 2*p^40 - p^39*q - 2*p^37*q^3 - 4*p^36*q^4 + 3*p^35*q^5 + 4*p^34*q^6 + 2*p^33*q^7 - 2*p^32*q^8 + 2*p^39 + 3*p^37*q^2 + 3*p^34*q^5 - p^33*q^6 - 4*p^38 + 6*p^35*q^3 + 2*p^34*q^4 - 2*p^33*q^5 - 3*p^32*q^6 + p^37 - 3*p^36*q + p^35*q^2 + p^34*q^3 - 2*p^33*q^4 + 2*p^36 - 2*p^35*q + 6*p^34*q^2 - 3*p^33*q^3 - 2*p^32*q^4 - 5*p^35 - 2*p^34*q - 2*p^33*q^2 + 3*p^32*q^3 + 2*p^34 - p^33*q + p^32*q^2 - 2*p^33 + 2*p^32*q - 2*p^32
'''

把里面的 $p*q$ 替换为 $n$

替换后为

n**31*p + 2*n**30*p**3 - n**30*p**2 - n**29*p**3 + n**28*p**7 - 2*n**28*p**6 + 2*n**28*p**5 - n**28*p**4 + 6*n**27*p**9 - 2*n**27*p**8 - n**27*p**7 - n**27*p**6 - 2*n**27*p**5 - n**26*p**10 - 5*n**26*p**9 + n**26*p**8 + 2*n**26*p**7 - 3*n**26*p**6 + n**25*p**13 + n**25*p**12 + n**25*p**10 + 2*n**25*p**9 - 3*n**25*p**8 - 2*n**25*p**7 + 5*n**24*p**15 + 3*n**24*p**13 - n**24*p**12 + 4*n**24*p**11 + n**24*p**10 + 5*n**24*p**9 - n**24*p**8 + n**23*p**16 - 2*n**23*p**15 + n**23*p**14 + 3*n**23*p**12 - 5*n**23*p**10 - 4*n**23*p**9 - 3*n**22*p**19 + 2*n**22*p**18 - 5*n**22*p**17 - n**22*p**16 + n**22*p**15 + n**22*p**13 + 2*n**22*p**12 - n**22*p**11 + 3*n**22*p**10 + n**21*p**20 - 2*n**21*p**19 - 2*n**21*p**18 - 2*n**21*p**17 - n**21*p**16 + n**21*p**15 - n**21*p**13 + 2*n**21*p**12 - 2*n**21*p**11 - 2*n**20*p**23 - n**20*p**22 - n**20*p**21 + n**20*p**20 - 2*n**20*p**18 - n**20*p**17 + n**20*p**16 - 5*n**20*p**15 + 2*n**20*p**14 - 2*n**20*p**13 + n**19*p**25 - 3*n**19*p**24 - 2*n**19*p**22 - n**19*p**19 + 4*n**19*p**18 + n**19*p**16 - 3*n**19*p**15 + 3*n**19*p**14 + 2*n**19*p**13 + n**18*p**27 - 2*n**18*p**26 + 5*n**18*p**25 + n**18*p**24 - 4*n**18*p**23 - 2*n**18*p**20 - 4*n**18*p**19 - n**18*p**16 + n**17*p**29 + n**17*p**27 - 2*n**17*p**26 + 2*n**17*p**25 - n**17*p**23 - 2*n**17*p**22 - 2*n**17*p**21 + n**17*p**19 + n**17*p**18 + n**17*p**17 - 2*n**17*p**16 - n**16*p**31 - n**16*p**30 + n**16*p**29 + 2*n**16*p**28 + 3*n**16*p**27 - n**16*p**26 - n**16*p**25 - n**16*p**24 + 2*n**16*p**23 + 2*n**16*p**22 + n**16*p**21 + 4*n**16*p**20 + 2*n**16*p**18 + n**16*p**17 - 4*n**15*p**33 + n**15*p**32 + n**15*p**31 + n**15*p**30 + n**15*p**29 + 4*n**15*p**28 + 2*n**15*p**26 - n**15*p**25 - n**15*p**24 + n**15*p**23 + 2*n**15*p**22 - 4*n**15*p**21 + 2*n**15*p**20 - 3*n**15*p**19 - 3*n**15*p**18 - 5*n**14*p**35 + n**14*p**33 - 2*n**14*p**32 - n**14*p**31 - n**14*p**30 - 2*n**14*p**29 + 4*n**14*p**28 - 2*n**14*p**27 + 3*n**14*p**23 - n**14*p**22 + n**14*p**20 + 3*n**14*p**18 + n**13*p**37 + n**13*p**35 - 3*n**13*p**34 - 4*n**13*p**33 + 2*n**13*p**32 + 2*n**13*p**31 - 2*n**13*p**29 - n**13*p**28 + n**13*p**26 - n**13*p**25 + n**13*p**23 + 2*n**13*p**22 - 4*n**13*p**20 - 3*n**13*p**19 - 4*n**12*p**39 + 2*n**12*p**38 - n**12*p**36 - 3*n**12*p**35 - n**12*p**34 - n**12*p**33 - n**12*p**32 + 2*n**12*p**31 + 2*n**12*p**30 + n**12*p**28 - n**12*p**27 + n**12*p**26 - n**12*p**25 + 4*n**12*p**24 + n**12*p**23 - n**12*p**22 - 2*n**12*p**21 - 2*n**12*p**20 - n**11*p**41 - 4*n**11*p**40 + 2*n**11*p**39 + 4*n**11*p**38 + n**11*p**37 + 2*n**11*p**36 - 2*n**11*p**35 - n**11*p**34 + 3*n**11*p**33 + 3*n**11*p**32 + n**11*p**31 + 6*n**11*p**30 + 2*n**11*p**27 + 2*n**11*p**26 - 2*n**11*p**25 + 2*n**11*p**24 - n**11*p**23 - 3*n**11*p**22 + 3*n**11*p**21 - 3*n**10*p**42 + 2*n**10*p**41 - 5*n**10*p**39 - n**10*p**37 - n**10*p**36 - 3*n**10*p**35 + 2*n**10*p**34 - 2*n**10*p**33 + n**10*p**32 + 3*n**10*p**31 + 3*n**10*p**30 + 2*n**10*p**29 + 3*n**10*p**28 + 4*n**10*p**27 + n**10*p**26 - 3*n**10*p**25 - n**10*p**24 + 2*n**10*p**23 - n**9*p**43 - 3*n**9*p**42 + 2*n**9*p**41 - n**9*p**40 + 2*n**9*p**39 - 4*n**9*p**38 + n**9*p**37 + 4*n**9*p**36 - 5*n**9*p**35 - 2*n**9*p**34 + n**9*p**33 + 3*n**9*p**32 - 5*n**9*p**31 + 3*n**9*p**30 + 3*n**9*p**28 + 4*n**9*p**27 - 4*n**9*p**26 - 4*n**9*p**25 - n**9*p**24 + 4*n**9*p**23 + 3*n**8*p**47 - 3*n**8*p**46 - 3*n**8*p**44 - 5*n**8*p**43 + n**8*p**42 + n**8*p**41 + 2*n**8*p**40 - 5*n**8*p**39 - n**8*p**36 + 2*n**8*p**35 - n**8*p**33 + 5*n**8*p**32 - n**8*p**31 + n**8*p**30 + 3*n**8*p**29 + 2*n**8*p**27 - 2*n**8*p**26 + n**8*p**25 - 2*n**8*p**24 - 4*n**7*p**49 - 3*n**7*p**48 - n**7*p**47 - 2*n**7*p**45 - 3*n**7*p**44 - n**7*p**42 - n**7*p**40 + n**7*p**39 + 2*n**7*p**38 + 2*n**7*p**36 - 3*n**7*p**35 + 2*n**7*p**33 - 2*n**7*p**32 - 4*n**7*p**31 - n**7*p**30 + n**7*p**29 - 2*n**7*p**27 + 2*n**7*p**26 - 2*n**6*p**50 + n**6*p**49 - 2*n**6*p**48 - 2*n**6*p**47 + n**6*p**46 + n**6*p**44 - n**6*p**43 - n**6*p**42 - n**6*p**41 + 4*n**6*p**40 - n**6*p**39 - 2*n**6*p**38 - 2*n**6*p**37 - n**6*p**36 - n**6*p**35 - 3*n**6*p**34 + 5*n**6*p**33 - n**6*p**32 + 3*n**6*p**31 + 3*n**6*p**30 - 2*n**6*p**29 + 4*n**6*p**28 - n**6*p**27 - 3*n**6*p**26 - n**5*p**52 - 2*n**5*p**51 - n**5*p**50 - 3*n**5*p**49 - n**5*p**46 - n**5*p**45 - 3*n**5*p**44 - n**5*p**43 - 3*n**5*p**42 + 3*n**5*p**41 - 2*n**5*p**40 + n**5*p**39 + 2*n**5*p**38 + n**5*p**37 - n**5*p**36 - n**5*p**35 + n**5*p**32 - n**5*p**31 + 3*n**5*p**30 + 3*n**5*p**29 - 2*n**5*p**28 + 2*n**4*p**55 - n**4*p**54 - n**4*p**53 + 2*n**4*p**52 + n**4*p**51 + 5*n**4*p**50 - n**4*p**49 + 2*n**4*p**45 + 2*n**4*p**44 - 2*n**4*p**42 - n**4*p**41 - n**4*p**40 - 3*n**4*p**39 - 5*n**4*p**38 - n**4*p**37 + n**4*p**36 - n**4*p**34 + n**4*p**33 - 4*n**4*p**32 + 2*n**4*p**30 - 2*n**4*p**29 - 2*n**4*p**28 + 7*n**3*p**57 + 2*n**3*p**56 + 3*n**3*p**55 + n**3*p**54 - 2*n**3*p**53 + n**3*p**52 - n**3*p**50 - n**3*p**49 - 2*n**3*p**48 - 2*n**3*p**46 + 2*n**3*p**45 + 2*n**3*p**43 - n**3*p**42 - n**3*p**41 + n**3*p**40 + n**3*p**38 + n**3*p**37 - 2*n**3*p**36 - 3*n**3*p**35 - 2*n**3*p**34 + 6*n**3*p**32 + n**3*p**31 - 3*n**3*p**30 + 3*n**3*p**29 - 2*n**2*p**59 + 2*n**2*p**58 - 2*n**2*p**56 + n**2*p**54 - 2*n**2*p**53 + n**2*p**52 + 2*n**2*p**51 - 2*n**2*p**50 - n**2*p**49 - n**2*p**47 - n**2*p**46 - 2*n**2*p**45 - 3*n**2*p**44 + n**2*p**43 + 2*n**2*p**42 - 2*n**2*p**41 + n**2*p**40 + 5*n**2*p**39 + 3*n**2*p**35 + n**2*p**33 + 6*n**2*p**32 - 2*n**2*p**31 + n**2*p**30 - n*p**61 - 3*n*p**60 - n*p**59 + 3*n*p**58 + n*p**57 + n*p**56 + 2*n*p**54 - n*p**53 + 2*n*p**52 - n*p**51 + 2*n*p**50 - 4*n*p**47 + n*p**46 + 3*n*p**45 + n*p**44 + n*p**43 + n*p**42 + n*p**41 - 2*n*p**40 - 3*n*p**39 - n*p**38 - 3*n*p**35 - 2*n*p**34 - 2*n*p**33 - n*p**32 + 2*n*p**31 + p**63 - 2*p**62 - 2*p**61 + 3*p**60 + p**59 + 3*p**57 - p**56 + p**55 - p**54 - 3*p**53 + p**52 - p**50 - p**49 - 3*p**48 - p**47 - p**46 + 3*p**44 - p**42 + 4*p**41 + 2*p**40 + 2*p**39 - 4*p**38 + p**37 + 2*p**36 - 5*p**35 + 2*p**34 - 2*p**33 - 2*p**32

最终exp：

N = 95656952327201449381426394713246214670537600365883923624876350719801926817916514429721785287844335184715049179879891389941974481490433975689601829920289485889138252888029716516069912637121531561601839948367426922036690701168975937162280451323099126372019216020898338909808577022618554997063496690156977790629
e = 65537
c = 32384071331939239285992149489589967884022349189352515487950255250160126611084915524664364190130039873461090810189570222748422757594726643684332100753373557666031160718150203596579825955216919802911458293840557069152132506518827761626306871971480050052005979083878379439210757328323337697175682026549870910934
w = 12796020294902567574981427270787776254781813995526831579805652479456168245098217943847166109912113827479436654134179666391771173421469188197935460525521295192736123648410762964187396897298542198935971755852754544978564521188423737649175136194386664628304164316905741781089536713701674793641345344818309314224

P.<n,p> = PolynomialRing(ZZ)
n, p = P.gens()
f = n**31*p + 2*n**30*p**3 - n**30*p**2 - n**29*p**3 + n**28*p**7 - 2*n**28*p**6 + 2*n**28*p**5 - n**28*p**4 + 6*n**27*p**9 - 2*n**27*p**8 - n**27*p**7 - n**27*p**6 - 2*n**27*p**5 - n**26*p**10 - 5*n**26*p**9 + n**26*p**8 + 2*n**26*p**7 - 3*n**26*p**6 + n**25*p**13 + n**25*p**12 + n**25*p**10 + 2*n**25*p**9 - 3*n**25*p**8 - 2*n**25*p**7 + 5*n**24*p**15 + 3*n**24*p**13 - n**24*p**12 + 4*n**24*p**11 + n**24*p**10 + 5*n**24*p**9 - n**24*p**8 + n**23*p**16 - 2*n**23*p**15 + n**23*p**14 + 3*n**23*p**12 - 5*n**23*p**10 - 4*n**23*p**9 - 3*n**22*p**19 + 2*n**22*p**18 - 5*n**22*p**17 - n**22*p**16 + n**22*p**15 + n**22*p**13 + 2*n**22*p**12 - n**22*p**11 + 3*n**22*p**10 + n**21*p**20 - 2*n**21*p**19 - 2*n**21*p**18 - 2*n**21*p**17 - n**21*p**16 + n**21*p**15 - n**21*p**13 + 2*n**21*p**12 - 2*n**21*p**11 - 2*n**20*p**23 - n**20*p**22 - n**20*p**21 + n**20*p**20 - 2*n**20*p**18 - n**20*p**17 + n**20*p**16 - 5*n**20*p**15 + 2*n**20*p**14 - 2*n**20*p**13 + n**19*p**25 - 3*n**19*p**24 - 2*n**19*p**22 - n**19*p**19 + 4*n**19*p**18 + n**19*p**16 - 3*n**19*p**15 + 3*n**19*p**14 + 2*n**19*p**13 + n**18*p**27 - 2*n**18*p**26 + 5*n**18*p**25 + n**18*p**24 - 4*n**18*p**23 - 2*n**18*p**20 - 4*n**18*p**19 - n**18*p**16 + n**17*p**29 + n**17*p**27 - 2*n**17*p**26 + 2*n**17*p**25 - n**17*p**23 - 2*n**17*p**22 - 2*n**17*p**21 + n**17*p**19 + n**17*p**18 + n**17*p**17 - 2*n**17*p**16 - n**16*p**31 - n**16*p**30 + n**16*p**29 + 2*n**16*p**28 + 3*n**16*p**27 - n**16*p**26 - n**16*p**25 - n**16*p**24 + 2*n**16*p**23 + 2*n**16*p**22 + n**16*p**21 + 4*n**16*p**20 + 2*n**16*p**18 + n**16*p**17 - 4*n**15*p**33 + n**15*p**32 + n**15*p**31 + n**15*p**30 + n**15*p**29 + 4*n**15*p**28 + 2*n**15*p**26 - n**15*p**25 - n**15*p**24 + n**15*p**23 + 2*n**15*p**22 - 4*n**15*p**21 + 2*n**15*p**20 - 3*n**15*p**19 - 3*n**15*p**18 - 5*n**14*p**35 + n**14*p**33 - 2*n**14*p**32 - n**14*p**31 - n**14*p**30 - 2*n**14*p**29 + 4*n**14*p**28 - 2*n**14*p**27 + 3*n**14*p**23 - n**14*p**22 + n**14*p**20 + 3*n**14*p**18 + n**13*p**37 + n**13*p**35 - 3*n**13*p**34 - 4*n**13*p**33 + 2*n**13*p**32 + 2*n**13*p**31 - 2*n**13*p**29 - n**13*p**28 + n**13*p**26 - n**13*p**25 + n**13*p**23 + 2*n**13*p**22 - 4*n**13*p**20 - 3*n**13*p**19 - 4*n**12*p**39 + 2*n**12*p**38 - n**12*p**36 - 3*n**12*p**35 - n**12*p**34 - n**12*p**33 - n**12*p**32 + 2*n**12*p**31 + 2*n**12*p**30 + n**12*p**28 - n**12*p**27 + n**12*p**26 - n**12*p**25 + 4*n**12*p**24 + n**12*p**23 - n**12*p**22 - 2*n**12*p**21 - 2*n**12*p**20 - n**11*p**41 - 4*n**11*p**40 + 2*n**11*p**39 + 4*n**11*p**38 + n**11*p**37 + 2*n**11*p**36 - 2*n**11*p**35 - n**11*p**34 + 3*n**11*p**33 + 3*n**11*p**32 + n**11*p**31 + 6*n**11*p**30 + 2*n**11*p**27 + 2*n**11*p**26 - 2*n**11*p**25 + 2*n**11*p**24 - n**11*p**23 - 3*n**11*p**22 + 3*n**11*p**21 - 3*n**10*p**42 + 2*n**10*p**41 - 5*n**10*p**39 - n**10*p**37 - n**10*p**36 - 3*n**10*p**35 + 2*n**10*p**34 - 2*n**10*p**33 + n**10*p**32 + 3*n**10*p**31 + 3*n**10*p**30 + 2*n**10*p**29 + 3*n**10*p**28 + 4*n**10*p**27 + n**10*p**26 - 3*n**10*p**25 - n**10*p**24 + 2*n**10*p**23 - n**9*p**43 - 3*n**9*p**42 + 2*n**9*p**41 - n**9*p**40 + 2*n**9*p**39 - 4*n**9*p**38 + n**9*p**37 + 4*n**9*p**36 - 5*n**9*p**35 - 2*n**9*p**34 + n**9*p**33 + 3*n**9*p**32 - 5*n**9*p**31 + 3*n**9*p**30 + 3*n**9*p**28 + 4*n**9*p**27 - 4*n**9*p**26 - 4*n**9*p**25 - n**9*p**24 + 4*n**9*p**23 + 3*n**8*p**47 - 3*n**8*p**46 - 3*n**8*p**44 - 5*n**8*p**43 + n**8*p**42 + n**8*p**41 + 2*n**8*p**40 - 5*n**8*p**39 - n**8*p**36 + 2*n**8*p**35 - n**8*p**33 + 5*n**8*p**32 - n**8*p**31 + n**8*p**30 + 3*n**8*p**29 + 2*n**8*p**27 - 2*n**8*p**26 + n**8*p**25 - 2*n**8*p**24 - 4*n**7*p**49 - 3*n**7*p**48 - n**7*p**47 - 2*n**7*p**45 - 3*n**7*p**44 - n**7*p**42 - n**7*p**40 + n**7*p**39 + 2*n**7*p**38 + 2*n**7*p**36 - 3*n**7*p**35 + 2*n**7*p**33 - 2*n**7*p**32 - 4*n**7*p**31 - n**7*p**30 + n**7*p**29 - 2*n**7*p**27 + 2*n**7*p**26 - 2*n**6*p**50 + n**6*p**49 - 2*n**6*p**48 - 2*n**6*p**47 + n**6*p**46 + n**6*p**44 - n**6*p**43 - n**6*p**42 - n**6*p**41 + 4*n**6*p**40 - n**6*p**39 - 2*n**6*p**38 - 2*n**6*p**37 - n**6*p**36 - n**6*p**35 - 3*n**6*p**34 + 5*n**6*p**33 - n**6*p**32 + 3*n**6*p**31 + 3*n**6*p**30 - 2*n**6*p**29 + 4*n**6*p**28 - n**6*p**27 - 3*n**6*p**26 - n**5*p**52 - 2*n**5*p**51 - n**5*p**50 - 3*n**5*p**49 - n**5*p**46 - n**5*p**45 - 3*n**5*p**44 - n**5*p**43 - 3*n**5*p**42 + 3*n**5*p**41 - 2*n**5*p**40 + n**5*p**39 + 2*n**5*p**38 + n**5*p**37 - n**5*p**36 - n**5*p**35 + n**5*p**32 - n**5*p**31 + 3*n**5*p**30 + 3*n**5*p**29 - 2*n**5*p**28 + 2*n**4*p**55 - n**4*p**54 - n**4*p**53 + 2*n**4*p**52 + n**4*p**51 + 5*n**4*p**50 - n**4*p**49 + 2*n**4*p**45 + 2*n**4*p**44 - 2*n**4*p**42 - n**4*p**41 - n**4*p**40 - 3*n**4*p**39 - 5*n**4*p**38 - n**4*p**37 + n**4*p**36 - n**4*p**34 + n**4*p**33 - 4*n**4*p**32 + 2*n**4*p**30 - 2*n**4*p**29 - 2*n**4*p**28 + 7*n**3*p**57 + 2*n**3*p**56 + 3*n**3*p**55 + n**3*p**54 - 2*n**3*p**53 + n**3*p**52 - n**3*p**50 - n**3*p**49 - 2*n**3*p**48 - 2*n**3*p**46 + 2*n**3*p**45 + 2*n**3*p**43 - n**3*p**42 - n**3*p**41 + n**3*p**40 + n**3*p**38 + n**3*p**37 - 2*n**3*p**36 - 3*n**3*p**35 - 2*n**3*p**34 + 6*n**3*p**32 + n**3*p**31 - 3*n**3*p**30 + 3*n**3*p**29 - 2*n**2*p**59 + 2*n**2*p**58 - 2*n**2*p**56 + n**2*p**54 - 2*n**2*p**53 + n**2*p**52 + 2*n**2*p**51 - 2*n**2*p**50 - n**2*p**49 - n**2*p**47 - n**2*p**46 - 2*n**2*p**45 - 3*n**2*p**44 + n**2*p**43 + 2*n**2*p**42 - 2*n**2*p**41 + n**2*p**40 + 5*n**2*p**39 + 3*n**2*p**35 + n**2*p**33 + 6*n**2*p**32 - 2*n**2*p**31 + n**2*p**30 - n*p**61 - 3*n*p**60 - n*p**59 + 3*n*p**58 + n*p**57 + n*p**56 + 2*n*p**54 - n*p**53 + 2*n*p**52 - n*p**51 + 2*n*p**50 - 4*n*p**47 + n*p**46 + 3*n*p**45 + n*p**44 + n*p**43 + n*p**42 + n*p**41 - 2*n*p**40 - 3*n*p**39 - n*p**38 - 3*n*p**35 - 2*n*p**34 - 2*n*p**33 - n*p**32 + 2*n*p**31 + p**63 - 2*p**62 - 2*p**61 + 3*p**60 + p**59 + 3*p**57 - p**56 + p**55 - p**54 - 3*p**53 + p**52 - p**50 - p**49 - 3*p**48 - p**47 - p**46 + 3*p**44 - p**42 + 4*p**41 + 2*p**40 + 2*p**39 - 4*p**38 + p**37 + 2*p**36 - 5*p**35 + 2*p**34 - 2*p**33 - 2*p**32
for i, j in zip(f.monomials(), f.coefficients()):
    w *= pow(2, -ZZ(j) * i.subs(p = 1, n = N), N)
    w %= N
    

p = gcd(w - 1, N)
c = 10266913434526071998707605266130137733134248608585146234981245806763995653822203763396430876254213500327272952979577138542487120755771047170064775346450942

ma = bytes_to_long(b'NSSCTF{')
mb = bytes_to_long(b'}')
c0 = (c - 256 ^ 81 * ma - mb) * inverse(256, p) % p

T = []
for i in range(1, 81):
    c0 = c0 - 48 * 256 ^ (i - 1)
    T.append(256 ^ (i - 1))
c1 = c0
T.append(-c1)

T = Matrix(ZZ, 81, 1, T)
L = block_matrix([[identity_matrix(81), T], 
                  [Matrix(ZZ, 1, 81), p]])
Q = diagonal_matrix(ZZ, [1] * 80 + [4] + [p])
L *= Q

res = L.BKZ()
res /= Q
flag = ''
for i in res:
    if abs(i[-2]) == 1 and i[-1] == 0:
        t = i[:80:]
        if all(abs(j) <= 9 for j in t):
            if i[-2] == 1:
                for m in t:
                    flag += chr(48 + m)
            else:
                for m in t:
                    flag += chr(48 - m)
    break
print(flag[::-1])  #38886172735077060750460332815973614272222523052135584902884007925985948919714862

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

'''

我们发现KEY的比特位数并不是很大，似乎可以从爆破入手，但是肯定不是直接爆破

我们知道KEY不是素数，那么KEY肯定是有因子的，我们假设为 $a$ 和 $b$

我们有如下的等式

\begin{array}{l} KEY^e \equiv ck\ (mod\ n)\\ (a*b)^e \equiv ck\ (mod\ n)\\ b^e \equiv ck * a^{-e}\ (mod\ n)\\ \end{array}

我们只要遍历 $a$ 和 $b$ （也就是每组因子，都在20比特以内遍历就行了），就可以找到 $k$ 的值了

exp：

from tqdm import trange


n = 26563847822899403123579768059987758748518109506340688366937229057385768563897579939399589878779201509595131302887212371556759550226965583832707699167542469352676806103999861576255689028708092007726895892953065618536676788020023461249303717579266840903337614272894749021562443472322941868357046500507962652585875038973455411548683247853955371839865042918531636085668780924020410159272977805762814306445393524647460775620243065858710021030314398928537847762167177417552351157872682037902372485985979513934517709478252552309280270916202653365726591219198063597536812483568301622917160509027075508471349507817295226801011
e = 65537
ck = 8371316287078036479056771367631991220353236851470185127168826270131149168993253524332451231708758763231051593801540258044681874144589595532078353953294719353350061853623495168005196486200144643168051115479293775329183635187974365652867387949378467702492757863040766745765841802577850659614528558282832995416523310220159445712674390202765601817050315773584214422244200409445854102170875265289152628311393710624256106528871400593480435083264403949059237446948467480548680533474642869718029551240453665446328781616706968352290100705279838871524562305806920722372815812982124238074246044446213460443693473663239594932076

find1 = {}
find2 = {}
for a in trange(1, 2**20):
    find1[ck * pow(a, -65537, n) % n] = a
for b in trange(1, 2**20):
    find2[pow(b, 65537, n)] = b
inter = set(find1.keys()).intersection(set(find2.keys()))  #求交集
for i in inter:
    a = find1[i]
    b = find2[i]
    k = a*b
    print(k)  #62495925932
    break

Sin

加密代码：

from Crypto.Util.number import bytes_to_long; print((2 * sin((m := bytes_to_long(b'NSSCTF{test_flag}'))) - 2 * ((2 * tan(m / 2)) / (1 + (tan(m / 2)) ^ 2)) * cos(2 * m)).n(1024))

'''
m的值即为flag
0.002127416739298073705574696200593072466561264659902471755875472082922378713642526659977748539883974700909790177123989603377522367935117269828845667662846262538383970611125421928502514023071134249606638896732927126986577684281168953404180429353050907281796771238578083386883803332963268109308622153680934466412
'''

原先的题其实是上面那样的，后面有些原因上错了（实际上都是一样的， $sin(m)$ 用三角函数万能公式搞下就行）

赛中是给了如下的等式

2sin(m) - 2sin(m)cos(2m) = tt

显然后面有 $sin$ 和 $cos$ 的组合，利用积化和差公式转换一下，上式可转换为

2sin(m) - 2sin(m)cos(2m) = 2sin(m) - 2 \cdot \frac{sin(3m) - sin(m)}{2} = 3sin(m) - sin(3m)

注意到这是三倍角公式，有

sin^3(m) =3sin(m) - sin(3m)

那就是题目其实给了 $sin^3(m)$ ，直接在精度环下开三次方就行

其实我原先想直接给 $sin(m)$ 的，但是后面想想太简单了就变了一下☝( ◠‿◠ )☝

一眼造格，给了如下的等式

sin(m)=t

简单变形一下，得到适合造格的等式

\begin{array}{l} m=arcsin(t) + 2 * k * \pi\\ arcsin(t)- m + 2 * k * \pi = 0 \end{array}

构造如下的格

\begin{pmatrix} 2\pi&0&0\\ -1&1&0\\ arctan(t)&0&1 \end{pmatrix}

该格满足

(k,\ m,\ 1) \begin{pmatrix} 2\pi&0&0\\ -1&1&0\\ arctan(t)&0&1 \end{pmatrix}= (0,\ m,\ 1)

配平一下即可，m的长度不确定，但是可以简单爆破一下（其实正常flag也就两三百比特而已）

exp：

from Crypto.Util.number import long_to_bytes, bytes_to_long

R = RealField(1024)  
t = R(0.002127416739298073705574696200593072466561264659902471755875472082922378713642526659977748539883974700909790177123989603377522367935117269828845667662846262538383970611125421928502514023071134249606638896732927126986577684281168953404180429353050907281796771238578083386883803332963268109308622153680934466412)
t /= 4
t = t ^ (1 / 3)

pi = pi.n(1024)


L = Matrix(QQ, [[2 * pi * 2 ^ 1024, 0, 0], 
                [-1 * 2 ^ 1024, 1, 0], 
                [arcsin(t) * 2 ^ 1024, 0, 1 * 2 ^ 423]]) 
res = L.LLL()
for row in res:
    if abs(row[-1]) == 2 ^ 423:
            m = long_to_bytes(abs(ZZ(row[1])))
            if m.isascii():
                print(m)  #b'NSSCTF{just_make_a_latter_and_LLL_is_OK_padpad}'
                break

最后那边 $flag$ 的数量级简单爆一下就行，我这边是出题已经知道了，不知道的就爆一下，反正 $LLL$ 本身挺快的

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

数据：

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'

这个不是我的题，但是感觉也蛮有意思的，记录一下

一眼格，懒得写latex了，这边直接手写

我尝试了两种做法

第一种

构造如上的格，因为模数 $p$ 的数量级只有512比特，和我们要求的 $key$ 是相当的，所以这边要给它缩小一下

规约出来再乘上 $\frac{p}{2^{400}}$ ，然后测看看误差，这边测出来刚刚好，没有误差

值得注意的是规约出来是负数，要在模p下转为正数，不能直接取绝对值

exp：

from Crypto.Util.number import *
from Crypto.Cipher import AES
from tqdm import trange



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'



LL = Matrix(ZZ, 1, 30, ts).stack(identity_matrix(30)).stack(Matrix(ZZ, 1, 30, -vector(gs))).stack(identity_matrix(30) * p)
LR = identity_matrix(32).stack(matrix.zero(30, 32))

L = LL.augment(LR)

Q = diagonal_matrix(QQ, [p] * 30 + [2 ^ 400 / p] + [1] * 30 + [2 ^ 400])
L *= Q
res = L.LLL()

for row in res:
    if abs(row[-1]) == 2 ^ 400:
        key = ZZ(row[30] * (p / t1)) % p  #注意不能取abs，要模p
        dec = AES.new(str(key).encode()[:16], AES.MODE_CBC,iv)
        flag = dec.decrypt(ciphertext)
        if flag.isascii():
            print(flag)
            break

第二种

既然 $key$ 规约不出来，那我们不规约不就行了，先规约出 $z$ 再返回算 $key$

虽然不是方格了，但无伤大雅

exp：

from Crypto.Util.number import *
from Crypto.Cipher import AES
from tqdm import trange
import sys


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'



LL = Matrix(ZZ, 1, 30, ts).stack(identity_matrix(30)).stack(Matrix(ZZ, 1, 30, -vector(gs))).stack(identity_matrix(30) * p)
LR = Matrix(ZZ, 1, 31).stack(identity_matrix(31)).stack(matrix.zero(30, 31))

L = LL.augment(LR).augment(Matrix(ZZ, 62, 1))
Q = diagonal_matrix(ZZ, [p] * 30 + [1] * 30 + [2 ^ 400, 2 ^ 400])
L *= Q
L = L.delete_columns([61])
res = L.LLL()

for row in res:
    if abs(row[-1]) == 2 ^ 400:
        z0 = ZZ(abs(row[30]))
        key = (gs[0] - z0) * inverse(ts[0], p) % p
        dec = AES.new(str(key).encode()[:16], AES.MODE_CBC,iv)
        flag = dec.decrypt(ciphertext)
        if flag.isascii():
            print(flag)
            break

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'

这题的话，预期解是剪枝

既然是剪枝，要剪什么便是关键了，虽然说题目要求的是 $seed$ ，但是如果我们直接去剪seed的话，会发现我们无法去得到 $lsfr1$ 的输出并由 $lsfr2$ 的输出来反向判断，所以这边很明显就是直接剪 $lsfr1$ 的输出了

我们知道 $lsfr2$ 的输出是由 $lsfr1$ 来判断的

当 $lsfr1$ 的输出是1的时候，就更新 $lsfr2$ 的状态
当 $lsfr1$ 的输出是0的时候，就直接拿 $lsfr2$ 的状态的最后一位

我们假设说 $lfsr2$ 的第 $k$ 位来自于 $lsfr1$ 的第 $i$ 位（ $i$ 和 $k$ 实际上是可以相同的，这边例举更一般的例子）

那么对与 $lfsr2$ 的 $k+1$ 位来说（这边懒得写latex了，画个图举个例子给大家理解下，这边试出了三种情况，但是已经足够剪枝了）

第一种

对应 $lsfr2$ 的第 $k+1$ 位等于 $lsfr1$ 的第 $i$ 位，这时候 $lsfr2$ 可能是没有更新的，对应 $find(k, lsfr1 + 0)$

第二种

对应 $lsfr2$ 的第 $k+1$ 位等于 $lsfr1$ 的第 $i$ 位且 $lsfr2$ 的第 $k+1$ 位等于 $lsfr1$ 的第 $i+1$ 位，这时候 $lsfr2$ 肯定是更新的，对应 $find(k+1, lsfr1 + 1)$

第三种

对应 $lsfr2$ 的第 $k+1$ 位不等于 $lsfr1$ 的第 $i$ 位且 $lsfr2$ 的第 $k+1$ 位等于 $lsfr1$ 的第 $i+1$ 位，这时候 $lsfr2$ 肯定是更新的，对应 $find(k+1, lsfr1 + 1)$

如何搜索即可，当 $lsfr1$ 到达64位的时候我们就拿到了一种 $lsfr1$ 的可能，即可还原 $seed$

之后如何还原，参考https://tangcuxiaojikuai.xyz/post/c2c51200.html的做法即可，没什么难度，很容易就能看懂

exp：

from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import md5
from tqdm import tqdm
import sys

mask = 9494051593829874780
output = 13799267741689921474
lsfr2 = bin(output)[2:].zfill(64)
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' 



t_L = block_matrix(Zmod(2), [[Matrix(ZZ, 63, 1).augment(identity_matrix(63))], 
                            [Matrix(ZZ, 1, 64, [int(i) for i in bin(mask)[2::].zfill(64)])]])
L = []
for i in range(1, 64 + 1):
    L.append((t_L ^ i)[-1])
L = Matrix(Zmod(2), 64, 64, L)

def find(lsfr1, k):
    #初始化
    length = len(lsfr1)

    #剪枝
    if length < 64 and lsfr1[k] != lsfr2[length] and lsfr1[k + 1] != lsfr2[length]:
        return

    #搜索和更深层次递归
    if length == 64:
        B = []
        for i in range(1, length + 1):
            B.append(int(lsfr1[i - 1]))
        
        seed = L.solve_right(Matrix(Zmod(2), 64, 1, B))
        seed = int(''.join([str(i[0]) for i in seed]), 2)
        flag = AES.new(key=md5(str(seed).encode()).digest(), mode=AES.MODE_ECB).decrypt(enc)
        if flag.isascii():
            print(flag)  #b'flag{5b322a2b-8d15-43b3-88f0-ee1586f1cf4f}\x06\x06\x06\x06\x06\x06'
            sys.exit()

    elif length < 64:
        if lsfr1[k] == lsfr2[length]:
            find(lsfr1 + '0', k)
    
            if lsfr1[k + 1] == lsfr2[length]:
                find(lsfr1 + '1', k + 1)
    
        if lsfr1[k] != lsfr2[length] and lsfr1[k + 1] == lsfr2[length]:
            find(lsfr1 + '1', k + 1)
find('01', 0)