W'Blog

Wbuildings的自勉小屋

0%

“近期的一些比赛”

发表于 分类于 Valine：
本文字数： 45k 阅读时长 ≈ 41 分钟

近期的一些比赛的一些题目，VMCTF2024，SEKAICTF2024，京津冀长城杯2024，ByteCTF-2024

2024VMCTF

RSA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.Util.number import *
from secrets import flag
m = bytes_to_long(flag)
p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 0x10001

M = matrix(Zmod(n), [
    [m, -m-p-q, -m-2*p, 2*q-m],
    [m+p+q,  m, 2*q-m,  m+2*p],
    [m+2*p,  m-2*q,  m, -m-p-q],
    [m-2*q, -m-2*p,  m+p+q,  m]
])

enc = M**e

print(f"n = {n}")
print(f"e = {e}")
print(list(enc))
n=13228298199631335610499409465400552275305629934024756614227830931136508640681372951453757994834844498763877490566164031828108583453919741685657210448857955666192855872103622943922893572765718705893238315297600050789804418329650168680719372191579207505092037294294875908952803670819999025123209403251314588474192758376162806705064430837428828805477906627599506069017651159117664246131790529354533675662936081996490294431369820750274303028529977278828959613343997326534446148884333619071935180484450320323844737055406889458275298296950269660857078186043669204168045730995355857013530919638304423700701901063780318208789
e=65537
enc=[(1491873293560323909465836471682585391496137454962536255211620436893391549603126009345148985699013899435764986980919290827837440218992944453711597495517127038406936254470963878149611067609857046502282994346483454884781103538081677117421537728730737422899739818406539050745938770868537148564365984825217449546939297237128543198112642950063626687602582556615437626388875069902892432216468378684299365817407995725759407957747215159745600867120912008194130121350313833434901083388223410629737737418961006112893999319596217781130922876695397872007871395908185274519733474161410964601075476672137735633842608230612826681061, 4956025543963860548224153175168493318238985854531591968596322951867101383038318092494673400475554880419342014784571362229741642826660412082585292197764604908450405263330703286845800303018092222139976907126517882830745820723998293430203137128739850924103620078289772876248014239067659155995114953314111131752812515097213052728067061893768763077056914111566820414025280534046400995356712414837449121046062079911435309295464490263283769221830037029108374974495201782045992874653920211537537724643230986981824349266978767367402293999209162694369772760075107747609491264902786041130826876918123202134703658442941891830242, 7710011511933273600956066580006667228795766247206337007278271463871915295714373557766306241838812677910529618690854981247073325175370147283360553440166198511565970962496527743224575526922830794861623489204146092991883999208502150565496732100104360091815826333424313805145648110936043125983239009895903602879010609096750963186952687545255588633288528372363096307287365891027749166227382683937570696463897150461450791183251190323380329123556440876127657763835466077899344290052877228945633508945118354870143193111572860186690380517929737934424809644493802524411423150714171313957036859668776471063633076408076909640002, 11534398990341303260469847611439061098979668999994719829731530111550470410818410249398161750557290507614569764189238005873703309686837109506327355518339608092717603460229057410906842405901627607535605010996612762231101162949308540690378638599362997229992351236008016988744038581908756449465377928987817065146363195497304246692426541055618255515479438494976345916998240594200316617809496338857712977577830501882906692816143225556486899297950715922558009978599642835535619697869607264637171021550028689009097951803276399427016025503188133689654404551377724037837852806988185689913776323215325531565269517783734339408476), (8272272655667475062275256290232058957066644079493164645631507979269407257643054858959084594359289618344535475781592669598366940627259329603071918251093350757742450608772919657077093269747626483753261408171082167959058597605651875250516235062839356580988417216005103032704789431752339869128094449937203456721380243278949753976997368943660065728420992516032685654992370625071263250775078114517084554616874002085054985135905330486990533806699940249720584638848795544488453274230413407534397455841219333342020387788428122090873004297741106966487305425968561456558554466092569815882704042720181221565998242620838426378547, 1491873293560323909465836471682585391496137454962536255211620436893391549603126009345148985699013899435764986980919290827837440218992944453711597495517127038406936254470963878149611067609857046502282994346483454884781103538081677117421537728730737422899739818406539050745938770868537148564365984825217449546939297237128543198112642950063626687602582556615437626388875069902892432216468378684299365817407995725759407957747215159745600867120912008194130121350313833434901083388223410629737737418961006112893999319596217781130922876695397872007871395908185274519733474161410964601075476672137735633842608230612826681061, 11534398990341303260469847611439061098979668999994719829731530111550470410818410249398161750557290507614569764189238005873703309686837109506327355518339608092717603460229057410906842405901627607535605010996612762231101162949308540690378638599362997229992351236008016988744038581908756449465377928987817065146363195497304246692426541055618255515479438494976345916998240594200316617809496338857712977577830501882906692816143225556486899297950715922558009978599642835535619697869607264637171021550028689009097951803276399427016025503188133689654404551377724037837852806988185689913776323215325531565269517783734339408476, 5518286687698062009543342885393885046509863686818419606949559467264593344966999393687451752996031820853347871875309050581035258278549594402296657008691757154626884909607095200698318045842887911031614826093453957797920419121148018115222640091474847413276210960870562103807155559883955899139970393355410985595182149279411843518111743292173240172189378255236409761730285268089915079904407845416962979199038931535039503248118630426893973904973536402701301849508531248635101858831456390126301671539331965453701543943834029271584917779020531726432268541549866679756622580281184543056494059969527952637068824655703408568787), (5518286687698062009543342885393885046509863686818419606949559467264593344966999393687451752996031820853347871875309050581035258278549594402296657008691757154626884909607095200698318045842887911031614826093453957797920419121148018115222640091474847413276210960870562103807155559883955899139970393355410985595182149279411843518111743292173240172189378255236409761730285268089915079904407845416962979199038931535039503248118630426893973904973536402701301849508531248635101858831456390126301671539331965453701543943834029271584917779020531726432268541549866679756622580281184543056494059969527952637068824655703408568787, 1693899209290032350029561853961491176325960934030036784496300819586038229862962702055596244277553991149307726376926025954405273767082632179329854930518347573475252411874565533016051166864091098357633304300987288558703255380341627990340733592216210275099686058286858920208765088911242575657831474263497523327829562878858560012637889781810573289998468132623160152019410564917347628322294190496820698085105580113583601615226595193787403730579261356270949634744354490998826451014726354434764158934421631314746785252130490031259272793762135971202673634665945166330192924007170167099754596422978892135432383280045978800313, 1491873293560323909465836471682585391496137454962536255211620436893391549603126009345148985699013899435764986980919290827837440218992944453711597495517127038406936254470963878149611067609857046502282994346483454884781103538081677117421537728730737422899739818406539050745938770868537148564365984825217449546939297237128543198112642950063626687602582556615437626388875069902892432216468378684299365817407995725759407957747215159745600867120912008194130121350313833434901083388223410629737737418961006112893999319596217781130922876695397872007871395908185274519733474161410964601075476672137735633842608230612826681061, 4956025543963860548224153175168493318238985854531591968596322951867101383038318092494673400475554880419342014784571362229741642826660412082585292197764604908450405263330703286845800303018092222139976907126517882830745820723998293430203137128739850924103620078289772876248014239067659155995114953314111131752812515097213052728067061893768763077056914111566820414025280534046400995356712414837449121046062079911435309295464490263283769221830037029108374974495201782045992874653920211537537724643230986981824349266978767367402293999209162694369772760075107747609491264902786041130826876918123202134703658442941891830242), (1693899209290032350029561853961491176325960934030036784496300819586038229862962702055596244277553991149307726376926025954405273767082632179329854930518347573475252411874565533016051166864091098357633304300987288558703255380341627990340733592216210275099686058286858920208765088911242575657831474263497523327829562878858560012637889781810573289998468132623160152019410564917347628322294190496820698085105580113583601615226595193787403730579261356270949634744354490998826451014726354434764158934421631314746785252130490031259272793762135971202673634665945166330192924007170167099754596422978892135432383280045978800313, 7710011511933273600956066580006667228795766247206337007278271463871915295714373557766306241838812677910529618690854981247073325175370147283360553440166198511565970962496527743224575526922830794861623489204146092991883999208502150565496732100104360091815826333424313805145648110936043125983239009895903602879010609096750963186952687545255588633288528372363096307287365891027749166227382683937570696463897150461450791183251190323380329123556440876127657763835466077899344290052877228945633508945118354870143193111572860186690380517929737934424809644493802524411423150714171313957036859668776471063633076408076909640002, 8272272655667475062275256290232058957066644079493164645631507979269407257643054858959084594359289618344535475781592669598366940627259329603071918251093350757742450608772919657077093269747626483753261408171082167959058597605651875250516235062839356580988417216005103032704789431752339869128094449937203456721380243278949753976997368943660065728420992516032685654992370625071263250775078114517084554616874002085054985135905330486990533806699940249720584638848795544488453274230413407534397455841219333342020387788428122090873004297741106966487305425968561456558554466092569815882704042720181221565998242620838426378547, 1491873293560323909465836471682585391496137454962536255211620436893391549603126009345148985699013899435764986980919290827837440218992944453711597495517127038406936254470963878149611067609857046502282994346483454884781103538081677117421537728730737422899739818406539050745938770868537148564365984825217449546939297237128543198112642950063626687602582556615437626388875069902892432216468378684299365817407995725759407957747215159745600867120912008194130121350313833434901083388223410629737737418961006112893999319596217781130922876695397872007871395908185274519733474161410964601075476672137735633842608230612826681061)]

分析

enc = M**e，矩阵的e次方

这类题目之前见过

多维矩阵下的线性群阶

查：GL(n,Fp)群阶的研究 | Tover’s Blog

正常做法：

1
2
3
4
5
6
7
8
C = Matrix(Zmod(n),c)

order_p = p*(p-1)*(p+1)*(p^2+p+1)
order_q = q*(q-1)*(q+1)*(q^2+q+1)
order = order_p * order_q

d = gmpy2.invert(e,order)
M = C ** d

这里我们并不能分解n，所以并不能这样解

1
2
3
4
5
6
M = matrix(Zmod(n), [
    [m, -m-p-q, -m-2*p, 2*q-m],
    [m+p+q,  m, 2*q-m,  m+2*p],
    [m+2*p,  m-2*q,  m, -m-p-q],
    [m-2*q, -m-2*p,  m+p+q,  m]
])

将矩阵M拆成一个反对称矩阵和单位矩阵的和形式：

M = A+mE

1
2
3
4
5
6
A = matrix([
    [0, -m-p-q, -m-2*p, 2*q-m],
    [m+p+q,  0, 2*q-m,  m+2*p],
    [m+2*p,  m-2*q,  0, -m-p-q],
    [m-2*q, -m-2*p,  m+p+q,  0]
])

就有 $C=M^e=(A+mE)^e$

按二项式定理展开：

测试发现 A的偶次幂是个对角矩阵，所以说C的非对角线元素都是A的奇次幂贡献的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
PR.<m,p,q> = PolynomialRing(ZZ)
M = matrix([
    [m, -m-p-q, -m-2*p, 2*q-m],
    [m+p+q,  m, 2*q-m,  m+2*p],
    [m+2*p,  m-2*q,  m, -m-p-q],
    [m-2*q, -m-2*p,  m+p+q,  m]
])

A = matrix([
    [0, -m-p-q, -m-2*p, 2*q-m],
    [m+p+q,  0, 2*q-m,  m+2*p],
    [m+2*p,  m-2*q,  0, -m-p-q],
    [m-2*q, -m-2*p,  m+p+q,  0]
])

E = Matrix(ZZ, identity_matrix(4))	# 对角矩阵

print(A^2)
[-3*m^2 - 6*m*p - 5*p^2 + 2*m*q - 2*p*q - 5*q^2                                              0                                              0                                              0]
[                                             0 -3*m^2 - 6*m*p - 5*p^2 + 2*m*q - 2*p*q - 5*q^2                                              0                                              0]
[                                             0                                              0 -3*m^2 - 6*m*p - 5*p^2 + 2*m*q - 2*p*q - 5*q^2                                              0]
[                                             0                                              0                                              0 -3*m^2 - 6*m*p - 5*p^2 + 2*m*q - 2*p*q - 5*q^2]

用A的小数次幂去factor一下非对角线元素的因子，会发现这些和式均有共同因子：

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
PR.<m,p,q> = PolynomialRing(ZZ)
M = matrix([
    [m, -m-p-q, -m-2*p, 2*q-m],
    [m+p+q,  m, 2*q-m,  m+2*p],
    [m+2*p,  m-2*q,  m, -m-p-q],
    [m-2*q, -m-2*p,  m+p+q,  m]
])

A = matrix([
    [0, -m-p-q, -m-2*p, 2*q-m],
    [m+p+q,  0, 2*q-m,  m+2*p],
    [m+2*p,  m-2*q,  0, -m-p-q],
    [m-2*q, -m-2*p,  m+p+q,  0]
])

E = Matrix(ZZ, identity_matrix(4))

print(factor((A^1)[1,0]))
print(factor((A^3)[1,0]))
print(factor((A^5)[1,0]))
print(factor((A^7)[1,0]))
m + p + q
(-1) * (m + p + q) * (3*m^2 + 6*m*p + 5*p^2 - 2*m*q + 2*p*q + 5*q^2)
(m + p + q) * (3*m^2 + 6*m*p + 5*p^2 - 2*m*q + 2*p*q + 5*q^2)^2
(-1) * (m + p + q) * (3*m^2 + 6*m*p + 5*p^2 - 2*m*q + 2*p*q + 5*q^2)^3

我们再看非对角线元素其他位置上的关系：

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
PR.<m,p,q> = PolynomialRing(ZZ)
M = matrix([
    [m, -m-p-q, -m-2*p, 2*q-m],
    [m+p+q,  m, 2*q-m,  m+2*p],
    [m+2*p,  m-2*q,  m, -m-p-q],
    [m-2*q, -m-2*p,  m+p+q,  m]
])

A = matrix([
    [0, -m-p-q, -m-2*p, 2*q-m],
    [m+p+q,  0, 2*q-m,  m+2*p],
    [m+2*p,  m-2*q,  0, -m-p-q],
    [m-2*q, -m-2*p,  m+p+q,  0]
])

E = Matrix(ZZ, identity_matrix(4))


print(factor((A^3)[1,0]))
print(factor((A^3)[2,0]))
print(factor((A^3)[3,0]))
print()
print(factor((A^5)[1,0]))
print(factor((A^5)[2,0]))
print(factor((A^5)[3,0]))

# (-1) * (m + p + q) * (3*m^2 + 6*m*p + 5*p^2 - 2*m*q + 2*p*q + 5*q^2)
# (-1) * (m + 2*p) * (3*m^2 + 6*m*p + 5*p^2 - 2*m*q + 2*p*q + 5*q^2)
# (-1) * (m - 2*q) * (3*m^2 + 6*m*p + 5*p^2 - 2*m*q + 2*p*q + 5*q^2)

# (m + p + q) * (3*m^2 + 6*m*p + 5*p^2 - 2*m*q + 2*p*q + 5*q^2)^2
# (m + 2*p) * (3*m^2 + 6*m*p + 5*p^2 - 2*m*q + 2*p*q + 5*q^2)^2
# (m - 2*q) * (3*m^2 + 6*m*p + 5*p^2 - 2*m*q + 2*p*q + 5*q^2)^2

所以可以从中提取几组代数关系求解：

1
2
3
(m + 2*p)*enc[1,0] == (m + p + q)*enc[2,0]
(m - 2*q)*enc[1,0] == (m + p + q)*enc[3,0]
p*q == n

模n下用 Groebner解方程

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
from Crypto.Util.number import *

n = 13228298199631335610499409465400552275305629934024756614227830931136508640681372951453757994834844498763877490566164031828108583453919741685657210448857955666192855872103622943922893572765718705893238315297600050789804418329650168680719372191579207505092037294294875908952803670819999025123209403251314588474192758376162806705064430837428828805477906627599506069017651159117664246131790529354533675662936081996490294431369820750274303028529977278828959613343997326534446148884333619071935180484450320323844737055406889458275298296950269660857078186043669204168045730995355857013530919638304423700701901063780318208789
e = 65537
enc = [(1491873293560323909465836471682585391496137454962536255211620436893391549603126009345148985699013899435764986980919290827837440218992944453711597495517127038406936254470963878149611067609857046502282994346483454884781103538081677117421537728730737422899739818406539050745938770868537148564365984825217449546939297237128543198112642950063626687602582556615437626388875069902892432216468378684299365817407995725759407957747215159745600867120912008194130121350313833434901083388223410629737737418961006112893999319596217781130922876695397872007871395908185274519733474161410964601075476672137735633842608230612826681061, 4956025543963860548224153175168493318238985854531591968596322951867101383038318092494673400475554880419342014784571362229741642826660412082585292197764604908450405263330703286845800303018092222139976907126517882830745820723998293430203137128739850924103620078289772876248014239067659155995114953314111131752812515097213052728067061893768763077056914111566820414025280534046400995356712414837449121046062079911435309295464490263283769221830037029108374974495201782045992874653920211537537724643230986981824349266978767367402293999209162694369772760075107747609491264902786041130826876918123202134703658442941891830242, 7710011511933273600956066580006667228795766247206337007278271463871915295714373557766306241838812677910529618690854981247073325175370147283360553440166198511565970962496527743224575526922830794861623489204146092991883999208502150565496732100104360091815826333424313805145648110936043125983239009895903602879010609096750963186952687545255588633288528372363096307287365891027749166227382683937570696463897150461450791183251190323380329123556440876127657763835466077899344290052877228945633508945118354870143193111572860186690380517929737934424809644493802524411423150714171313957036859668776471063633076408076909640002, 11534398990341303260469847611439061098979668999994719829731530111550470410818410249398161750557290507614569764189238005873703309686837109506327355518339608092717603460229057410906842405901627607535605010996612762231101162949308540690378638599362997229992351236008016988744038581908756449465377928987817065146363195497304246692426541055618255515479438494976345916998240594200316617809496338857712977577830501882906692816143225556486899297950715922558009978599642835535619697869607264637171021550028689009097951803276399427016025503188133689654404551377724037837852806988185689913776323215325531565269517783734339408476), (8272272655667475062275256290232058957066644079493164645631507979269407257643054858959084594359289618344535475781592669598366940627259329603071918251093350757742450608772919657077093269747626483753261408171082167959058597605651875250516235062839356580988417216005103032704789431752339869128094449937203456721380243278949753976997368943660065728420992516032685654992370625071263250775078114517084554616874002085054985135905330486990533806699940249720584638848795544488453274230413407534397455841219333342020387788428122090873004297741106966487305425968561456558554466092569815882704042720181221565998242620838426378547, 1491873293560323909465836471682585391496137454962536255211620436893391549603126009345148985699013899435764986980919290827837440218992944453711597495517127038406936254470963878149611067609857046502282994346483454884781103538081677117421537728730737422899739818406539050745938770868537148564365984825217449546939297237128543198112642950063626687602582556615437626388875069902892432216468378684299365817407995725759407957747215159745600867120912008194130121350313833434901083388223410629737737418961006112893999319596217781130922876695397872007871395908185274519733474161410964601075476672137735633842608230612826681061, 11534398990341303260469847611439061098979668999994719829731530111550470410818410249398161750557290507614569764189238005873703309686837109506327355518339608092717603460229057410906842405901627607535605010996612762231101162949308540690378638599362997229992351236008016988744038581908756449465377928987817065146363195497304246692426541055618255515479438494976345916998240594200316617809496338857712977577830501882906692816143225556486899297950715922558009978599642835535619697869607264637171021550028689009097951803276399427016025503188133689654404551377724037837852806988185689913776323215325531565269517783734339408476, 5518286687698062009543342885393885046509863686818419606949559467264593344966999393687451752996031820853347871875309050581035258278549594402296657008691757154626884909607095200698318045842887911031614826093453957797920419121148018115222640091474847413276210960870562103807155559883955899139970393355410985595182149279411843518111743292173240172189378255236409761730285268089915079904407845416962979199038931535039503248118630426893973904973536402701301849508531248635101858831456390126301671539331965453701543943834029271584917779020531726432268541549866679756622580281184543056494059969527952637068824655703408568787), (5518286687698062009543342885393885046509863686818419606949559467264593344966999393687451752996031820853347871875309050581035258278549594402296657008691757154626884909607095200698318045842887911031614826093453957797920419121148018115222640091474847413276210960870562103807155559883955899139970393355410985595182149279411843518111743292173240172189378255236409761730285268089915079904407845416962979199038931535039503248118630426893973904973536402701301849508531248635101858831456390126301671539331965453701543943834029271584917779020531726432268541549866679756622580281184543056494059969527952637068824655703408568787, 1693899209290032350029561853961491176325960934030036784496300819586038229862962702055596244277553991149307726376926025954405273767082632179329854930518347573475252411874565533016051166864091098357633304300987288558703255380341627990340733592216210275099686058286858920208765088911242575657831474263497523327829562878858560012637889781810573289998468132623160152019410564917347628322294190496820698085105580113583601615226595193787403730579261356270949634744354490998826451014726354434764158934421631314746785252130490031259272793762135971202673634665945166330192924007170167099754596422978892135432383280045978800313, 1491873293560323909465836471682585391496137454962536255211620436893391549603126009345148985699013899435764986980919290827837440218992944453711597495517127038406936254470963878149611067609857046502282994346483454884781103538081677117421537728730737422899739818406539050745938770868537148564365984825217449546939297237128543198112642950063626687602582556615437626388875069902892432216468378684299365817407995725759407957747215159745600867120912008194130121350313833434901083388223410629737737418961006112893999319596217781130922876695397872007871395908185274519733474161410964601075476672137735633842608230612826681061, 4956025543963860548224153175168493318238985854531591968596322951867101383038318092494673400475554880419342014784571362229741642826660412082585292197764604908450405263330703286845800303018092222139976907126517882830745820723998293430203137128739850924103620078289772876248014239067659155995114953314111131752812515097213052728067061893768763077056914111566820414025280534046400995356712414837449121046062079911435309295464490263283769221830037029108374974495201782045992874653920211537537724643230986981824349266978767367402293999209162694369772760075107747609491264902786041130826876918123202134703658442941891830242), (1693899209290032350029561853961491176325960934030036784496300819586038229862962702055596244277553991149307726376926025954405273767082632179329854930518347573475252411874565533016051166864091098357633304300987288558703255380341627990340733592216210275099686058286858920208765088911242575657831474263497523327829562878858560012637889781810573289998468132623160152019410564917347628322294190496820698085105580113583601615226595193787403730579261356270949634744354490998826451014726354434764158934421631314746785252130490031259272793762135971202673634665945166330192924007170167099754596422978892135432383280045978800313, 7710011511933273600956066580006667228795766247206337007278271463871915295714373557766306241838812677910529618690854981247073325175370147283360553440166198511565970962496527743224575526922830794861623489204146092991883999208502150565496732100104360091815826333424313805145648110936043125983239009895903602879010609096750963186952687545255588633288528372363096307287365891027749166227382683937570696463897150461450791183251190323380329123556440876127657763835466077899344290052877228945633508945118354870143193111572860186690380517929737934424809644493802524411423150714171313957036859668776471063633076408076909640002, 8272272655667475062275256290232058957066644079493164645631507979269407257643054858959084594359289618344535475781592669598366940627259329603071918251093350757742450608772919657077093269747626483753261408171082167959058597605651875250516235062839356580988417216005103032704789431752339869128094449937203456721380243278949753976997368943660065728420992516032685654992370625071263250775078114517084554616874002085054985135905330486990533806699940249720584638848795544488453274230413407534397455841219333342020387788428122090873004297741106966487305425968561456558554466092569815882704042720181221565998242620838426378547, 1491873293560323909465836471682585391496137454962536255211620436893391549603126009345148985699013899435764986980919290827837440218992944453711597495517127038406936254470963878149611067609857046502282994346483454884781103538081677117421537728730737422899739818406539050745938770868537148564365984825217449546939297237128543198112642950063626687602582556615437626388875069902892432216468378684299365817407995725759407957747215159745600867120912008194130121350313833434901083388223410629737737418961006112893999319596217781130922876695397872007871395908185274519733474161410964601075476672137735633842608230612826681061)]
enc = Matrix(Zmod(n), enc)

# Groebner
PR.<m,p,q> = PolynomialRing(Zmod(n))
f1 = (m + 2 * p) - (inverse(enc[1,0],n)*enc[2,0])*(m + p + q)
f2 = (m - 2 * q) - (inverse(enc[1,0],n)*enc[3,0])*(m + p + q)
f3 = p*q
res = Ideal([f1,f2,f3]).groebner_basis()
for i in res:
    print(i)
# test
q = 98199204383444167136509999317652307746300154257439691314026803510437035509888229764173492052858804263577571331383214859652229706329210472593337809065208882042178413249493877596701444929209070708258353144837330382092255133776768117120874000890494449018234172972678168219613884207547781528635959091301251971281
p = n // q
assert p*q == n

PR.<m> = PolynomialRing(Zmod(n))
f = (m + 2 * p) - (inverse(enc[1,0],n)*enc[2,0])*(m + p + q)
# print(f)		##记录一下
a = 3297056809289327500256202079127136134187438944961708132751779704042134248345975436322191479293257096389543469387818190390952261259850867719244868774056284786555129809594382750795637970645528822198427409878547718771238431341613753773735778866319889665322786887273473714741059398430312523411707495791556075878244637630480194633873896328931631465317325085583101546945701547571540285337915330695525854299979138422312974757786532911019780366620715999126086808046470039825598115253747158220517041862628277627457873544852999345612018379688444091864667014856637790925604130983328623143861756949881991846056060324187971651968
b = 1498891588977545370451304005269054204989297955532246655702497171972634294190353786886109979315712227670838063747138944971165078237866699516737057265958406033545290094866918511445027202221306581865115556251808822409761737528633460237914954126481851519653767357154958076960906373574059921391655491951867500826108554012342761055413189807372591262833424798009944360120455674246600349563624996782442874590028504156102295527090123626799675614654662807183634567377812300847810842883813710868799454486184658344859843573551816770639242317817513006458632518373823719039586807296528828652532914106040726579904539566401034957917

flag = inverse(a,n) * (-b) %n
print(long_to_bytes(int(flag)))

#WMCTF{QU4t3rni0n_4nd_Matr1x_4r3_4un}

K-Cessation

描述：

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
K-Cessation
ChllengeInfo
misc/crypto 进入无界之界
## 背景：
K-Cessation 密码是一种使用 K 位轮从明文位中挑选下一个密文位的古典密码。
当加密开始时，从轮子的最后一位开始。
当轮子到达终点时，它会从头开始循环。
对于每个明文位，轮子会旋转到轮子中与明文位匹配的下一个位，并将旋转的距离附加到密文中。

因此，如果不知道轮子，就不可能解密密文。
是这样吗？


## 例子：
要使用轮子 1100011011100011100110100011110110010110010100001011111011111010 将“youtu.be/dQw4w9WgXcQ”编码为 64-Cessation：
1. 将明文转换为比特： 01111001 01101111 01110101 01110100 01110101 00101110 01100010 01100101 00101111 01100100 01010001 01110111 0011 0100 01110111 00111001 01010111 01100111 01011000 01100011 01010001
2.从wheel[-1]到轮子中的下一个“0”位，距离为3，当前轮位置为wheel[2]
3.从wheel[2]到轮子中的下一个“1”位，距离为3，当前轮子位置为wheel[5]
4. 重复步骤直到所有位都被编码
5.结果为3312121232111411211311221152515233123332223411313221112161142123243321244111111311111112111131113211132412111212112112321122115251142114213312132313311222111112


## 挑战：
一个野生Flag使用 64-Cessation 密码进行编码。
轮子内容是未知的，它是 64 位长。
密文在 ciphertext.txt 中给出。
该Flag已知是长度超过 64 个字符的 ASCII 字符串。
除此之外，该Flag的任何部分都是未知的，这意味着该Flag不是 WMCTF{} 或 FLAG{} 格式。
提交时，请将Flag改为WMCTF{}格式。
请注意，每个ASCII字节的最高有效位被随机翻转。
您需要从密文中提取Flag并提交。
为了您的方便，flag_hash.txt 中给出了该Flag的盐焗 SHA-256 哈希值。

ChllengeInfo-EN
misc/crypto Enter the realm of no realm
## Background:
K-Cessation cipher is a cipher that uses a K bit wheel to pick the next cipher bit from plaintext bit.
When encryption starts, the wheel starts at the last bit of the wheel.
The wheel loops around when it reaches the end.
For every plaintext bit, the wheel is rotated to the next bit in the wheel that matches the plaintext bit, and the distance rotated is appended to the ciphertext.

Therefore, if the wheel is not known, it is not possible to decrypt the ciphertext.
Or is it?


## Example:
To encode "youtu.be/dQw4w9WgXcQ" in 64-Cessation with the wheel 1100011011100011100110100011110110010110010100001011111011111010:
1. convert the plaintext to bits: 01111001 01101111 01110101 01110100 01110101 00101110 01100010 01100101 00101111 01100100 01010001 01110111 00110100 01110111 00111001 01010111 01100111 01011000 01100011 01010001
2. from wheel[-1] to the next "0" bit in the wheel, distance is 3, the current wheel position is wheel[2]
3. from wheel[2] to the next "1" bit in the wheel, distance is 3, the current wheel position is wheel[5]
4. repeat the steps until all bits is encoded
5. the result is 3312121232111411211311221152515233123332223411313221112161142123243321244111111311111112111131113211132412111212112112321122115251142114213312132313311222111112


## Challenge:
A flag is encoded with 64-Cessation cipher.
The wheel is not known except that it is 64 bits long.
The ciphertext is given in ciphertext.txt.
The flag is only known to be an ASCII string that is longer than 64 characters.
No part of the flag is known, which means the flag is NOT in WMCTF{} or FLAG{} format.
When submitting, please make the flag in WMCTF{} format.
Note that, The most significant bit of each ASCII byte is flipped with a random bit.
You need to extract the flag from the ciphertext and submit it.
For your convenience, a salted sha256 hash of the flag is given in flag_hash.txt.

附件

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
from typing import List,Union,Literal
from Crypto.Util.number import long_to_bytes
import secrets
import random,string,re

class K_Cessation:
    '''
    ## Background:
    K-Cessation cipher is a cipher that uses a K bit wheel to pick the next cipher bit from plaintext bit.
    When encryption starts, the wheel starts at the last bit of the wheel.
    The wheel loops around when it reaches the end.
    For every plaintext bit, the wheel is rotated to the next bit in the wheel that matches the plaintext bit, and the distance rotated is appended to the ciphertext.

    Therefore, if the wheel is not known, it is not possible to decrypt the ciphertext. 
    Or is it?

    
    ## Example:
    To encode "youtu.be/dQw4w9WgXcQ" in 64-Cessation with the wheel 1100011011100011100110100011110110010110010100001011111011111010:
    1. convert the plaintext to bits: 01111001 01101111 01110101 01110100 01110101 00101110 01100010 01100101 00101111 01100100 01010001 01110111 00110100 01110111 00111001 01010111 01100111 01011000 01100011 01010001
    2. from wheel[-1] to the next "0" bit in the wheel, distance is 3, the current wheel position is wheel[2]
    3. from wheel[2] to the next "1" bit in the wheel, distance is 3, the current wheel position is wheel[5]
    4. repeat the steps until all bits is encoded
    5. the result is 3312121232111411211311221152515233123332223411313221112161142123243321244111111311111112111131113211132412111212112112321122115251142114213312132313311222111112


    ## Challenge:
    A flag is encoded with 64-Cessation cipher. 
    The wheel is not known. 
    The ciphertext is given in ciphertext.txt.
    The flag is only known to be an ascii string that is longer than 64 characters. 
    No part of the flag is known, which means the flag is NOT in WMCTF{} or FLAG{} format.
    When submitting, please make the flag in WMCTF{} format.
    The most significant bit of each byte is flipped with a random bit.
    You need to extract the flag from the ciphertext and submit it.
    For your convenience, a salted sha256 hash of the flag is given in flag_hash.txt.

    '''

    def __is_valid_wheel(self):
        hasZero = False
        hasOne = False
        for i in self.wheel:
            if not isinstance(i,int):
                raise ValueError("Wheel must be a list of int")
            if i == 0:
                hasZero = True
            elif i == 1:
                hasOne = True
            if i > 1 or i < 0:
                raise ValueError("Wheel must be a list of 0s and 1s")
        if not hasZero or not hasOne:
            raise ValueError("Wheel must contain at least one 0 and one 1")

    def __init__(self,wheel:List[int]):
        self.wheel = wheel
        self.__is_valid_wheel()
        self.state = -1
        self.finalized = False
    def __find_next_in_wheel(self,target:Literal[1,0]) -> List[int]:
        result = 1
        while True:
            ptr = self.state + result
            ptr = ptr % len(self.wheel)
            v = self.wheel[ptr]
            if v == target:
                self.state = ptr
                return [result]
            result+=1
    def __iter_bits(self,data:bytes):
        for b in data:
            for i in range(7,-1,-1):
                yield (b >> i) & 1
    def __check_finalized(self):
        if self.finalized:
            raise ValueError("This instance has already been finalized")
        self.finalized = True
    def encrypt(self,data:Union[str,bytes]) -> List[int]:
        self.__check_finalized()
        if isinstance(data,str):
            data = data.encode()
        out = []
        for bit in self.__iter_bits(data):
            rs = self.__find_next_in_wheel(bit)
            # print(f"bit={bit},rs={rs},state={self.state}")
            out.extend(rs)
        return out
    
    def decrypt(self,data:List[int]) -> bytes:
        self.__check_finalized()
        out = []
        for i in data:
            assert type(i) == int
            self.state = self.state + i
            self.state %= len(self.wheel)
            out.append(self.wheel[self.state])
        long = "".join(map(str,out))
        return long_to_bytes(int(long,2))

# generate a random wheel with k bits.
def random_wheel(k=64) -> List[int]:
    return [secrets.randbelow(2) for _ in range(k)]

# the most significant bit of each byte is flipped with a random bit.
def encode_ascii_with_random_msb(data:bytes) -> bytes:
    out = bytearray()
    for b in data:
        assert b < 128, "not ascii"
        b = b ^ (0b10000000 * secrets.randbelow(2))
        out.append(b)
    return bytes(out)

# for your convenience, here is the decoding function.
def decode_ascii_with_random_msb(data:bytes) -> bytes:
    out = bytearray()
    for b in data:
        b = b & 0b01111111
        out.append(b)
    return bytes(out)


if __name__ == "__main__":
    try:
        from flag import flag
        from flag import wheel
    except ImportError:
        print("flag.py not found, using test flag")
        flag = "THIS_IS_TEST_FLAG_WHEN_YOU_HEAR_THE_BUZZER_LOOK_AT_THE_FLAG_BEEEP"
        wheel = random_wheel(64)

    # wheel is wheel and 64 bits
    assert type(wheel) == list and len(wheel) == 64 and all((i in [0,1] for i in wheel))
    # flag is flag and string
    assert type(flag) == str
    # flag is ascii
    assert all((ord(c) < 128 for c in flag))
    # flag is long
    assert len(flag) > 64
    # flag does not start with wmctf{ nor does it end with }
    assert not flag.lower().startswith("wmctf{") and not flag.endswith("}")
    # flag also does not start with flag{
    assert not flag.lower().startswith("flag{")

    # the most significant bit of each byte is flipped with a random bit.
    plaintext = encode_ascii_with_random_msb(flag.encode())

    c = K_Cessation(wheel)
    ct = c.encrypt(plaintext)
    with open("ciphertext.txt","w") as f:
        f.write(str(ct))

    import hashlib
    # for you can verify the correctness of your decryption.
    # or you can brute force the flag hash, it is just a >64 length string :)
    with open("flag_hash.txt","w") as f:
        salt = secrets.token_bytes(16).hex()
        h = hashlib.sha256((salt + flag).encode()).hexdigest()
        f.write(h + ":" + salt)

    # demostration that decryption works
    c = K_Cessation(wheel)
    pt = c.decrypt(ct)
    pt = decode_ascii_with_random_msb(pt)
    print(pt)
    assert flag.encode() in pt
    
# d650078ae91d82ebd1d586110960a789c1a15e2cbc053b9daf8d8a4905950720:b840089ce93581869e9c02a7b5aefa7b
# [2, 1, 1, 3, 1, 1, 3, 2, 1, 4, 1, 2, 3, 1, 1, 1, 2, 1, 1, 2, 2, 2, 1, 3, 1, 6, 1, 1, 4, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 3, 3, 2, 1, 1, 3, 1, 1, 1, 3, 4, 1, 3, 1, 2, 2, 4, 2, 5, 1, 1, 1, 3, 2, 1, 4, 2, 2, 1, 2, 1, 3, 1, 1, 1, 1, 1, 2, 3, 1, 2, 1, 1, 1, 1, 3, 4, 1, 2, 2, 4, 2, 5, 1, 2, 1, 2, 2, 1, 4, 1, 2, 1, 2, 1, 1, 1, 1, 1, 1, 2, 2, 1, 4, 3, 1, 2, 1, 3, 1, 3, 3, 2, 1, 3, 1, 6, 2, 1, 1, 2, 1, 2, 1, 3, 1, 1, 2, 1, 2, 1, 1, 2, 1, 2, 2, 2, 3, 1, 1, 4, 1, 3, 1, 1, 1, 2, 1, 1, 2, 4, 1, 1, 5, 2, 4, 2, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 3, 3, 1, 1, 1, 1, 1, 2, 1, 2, 3, 1, 1, 2, 1, 1, 2, 1, 2, 1, 2, 1, 1, 1, 2, 5, 1, 1, 1, 3, 1, 1, 2, 3, 1, 2, 2, 2, 1, 3, 3, 1, 1, 2, 1, 1, 4, 3, 1, 3, 4, 1, 1, 1, 2, 1, 3, 1, 6, 1, 2, 1, 1, 3, 2, 3, 1, 2, 2, 1, 3, 2, 1, 2, 2, 2, 3, 3, 3, 1, 1, 2, 4, 1, 1, 1, 1, 1, 4, 2, 1, 4, 1, 2, 3, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 3, 2, 1, 2, 1, 1, 1, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 2, 4, 2, 1, 4, 2, 4, 2, 2, 3, 1, 2, 2, 2, 1, 3, 3, 1, 2, 1, 1, 1, 1, 3, 3, 1, 3, 1, 1, 1, 1, 3, 1, 1, 4, 2, 5, 2, 1, 3, 1, 1, 2, 3, 1, 2, 2, 1, 1, 1, 1, 1, 1, 3, 1, 2, 1, 3, 1, 2, 3, 4, 4, 3, 2, 4, 2, 1, 4, 2, 4, 1, 2, 1, 3, 1, 2, 1, 1, 1, 3, 2, 1, 2, 2, 2, 3, 3, 1, 2, 1, 3, 1, 1, 1, 2, 1, 3, 4, 2, 1, 4, 1, 2, 1, 2, 2, 2, 1, 1, 2, 1, 1, 2, 2, 2, 1, 4, 2, 1, 4, 1, 1, 1, 1, 2, 4, 4, 3, 2, 4, 2, 1, 1, 1, 1, 1, 1, 1, 4, 2, 2, 3, 1, 1, 1, 2, 1, 3, 1, 4, 1, 2, 4, 1, 2, 3, 4, 1, 3, 1, 1, 1, 2, 4, 1, 1, 1, 4, 1, 1, 4, 2, 1, 4, 2, 2, 1, 1, 1, 1, 1, 2, 3, 2, 1, 4, 3, 3, 4, 4, 3, 2, 4, 2, 1, 1, 3, 2, 4, 1, 1, 2, 3, 1, 1, 1, 2, 2, 1, 1, 1, 1, 3, 1, 1, 1, 4, 3, 3, 1, 1, 2, 1, 1, 1, 1, 3, 1, 1, 4, 2, 5, 1, 1, 4, 2, 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 2, 1, 2, 1, 2, 4, 3, 1, 1, 1, 1, 3, 4, 3, 1, 1, 4, 1, 6, 2, 1, 1, 1, 3, 1, 1, 3, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 4, 3, 1, 1, 5, 4, 1, 2, 2, 4, 1, 6, 1, 2, 1, 1, 3, 1, 4, 1, 2, 1, 2, 1, 1, 1, 1, 4, 2, 2, 3, 1, 2, 3, 1, 3, 4, 1, 1, 3, 4, 2, 5, 1, 1, 1, 3, 2, 2, 3, 2, 1, 2, 2, 2, 2, 3, 1, 2, 1, 3, 3, 3, 1, 1, 2, 1, 3, 3, 1, 1, 4, 2, 5, 2, 4, 1, 2, 4, 1, 2, 1, 2, 1, 1, 1, 2, 3, 1, 2, 4, 1, 1, 4, 4, 1, 1, 2, 3, 2, 4, 2, 5, 1, 2, 1, 2, 1, 1, 2, 3, 1, 2, 1, 2, 1, 1, 3, 1, 1, 2, 1, 2, 3, 1, 1, 1, 3, 4, 1, 1, 2, 1, 1, 1, 2, 4, 2, 1, 1, 3, 1, 2, 1, 2, 2, 2, 1, 2, 2, 1, 1, 1, 2, 1, 3, 1, 1, 2, 1, 2, 3, 1, 1, 1, 3, 4, 1, 1, 2, 3, 1, 2, 3, 1, 6, 2, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 4, 2, 1, 4, 1, 2, 3, 1, 1, 2, 1]

加密的原理我们并不难理解，但需要我们找到细节规律

密文第一个是3，说明wheel里面1，2是相同的，且与3相反，密文第二个是5，说明wheel里面 4，5，6，7是相同的，且与8相反，不是0就是1，我们只需足够多的密文来确定足够多的相同的位置，就能确定wheel

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
ct = [2, 1, 1, 3, 1, 1, 3, 2, 1, 4, 1, 2, 3, 1, 1, 1, 2, 1, 1, 2, 2, 2, 1, 3, 1, 6, 1, 1, 4, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 3, 3, 2, 1, 1, 3, 1, 1, 1, 3, 4, 1, 3, 1, 2, 2, 4, 2, 5, 1, 1, 1, 3, 2, 1, 4, 2, 2, 1, 2, 1, 3, 1, 1, 1, 1, 1, 2, 3, 1, 2, 1, 1, 1, 1, 3, 4, 1, 2, 2, 4, 2, 5, 1, 2, 1, 2, 2, 1, 4, 1, 2, 1, 2, 1, 1, 1, 1, 1, 1, 2, 2, 1, 4, 3, 1, 2, 1, 3, 1, 3, 3, 2, 1, 3, 1, 6, 2, 1, 1, 2, 1, 2, 1, 3, 1, 1, 2, 1, 2, 1, 1, 2, 1, 2, 2, 2, 3, 1, 1, 4, 1, 3, 1, 1, 1, 2, 1, 1, 2, 4, 1, 1, 5, 2, 4, 2, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 3, 3, 1, 1, 1, 1, 1, 2, 1, 2, 3, 1, 1, 2, 1, 1, 2, 1, 2, 1, 2, 1, 1, 1, 2, 5, 1, 1, 1, 3, 1, 1, 2, 3, 1, 2, 2, 2, 1, 3, 3, 1, 1, 2, 1, 1, 4, 3, 1, 3, 4, 1, 1, 1, 2, 1, 3, 1, 6, 1, 2, 1, 1, 3, 2, 3, 1, 2, 2, 1, 3, 2, 1, 2, 2, 2, 3, 3, 3, 1, 1, 2, 4, 1, 1, 1, 1, 1, 4, 2, 1, 4, 1, 2, 3, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 3, 2, 1, 2, 1, 1, 1, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 2, 4, 2, 1, 4, 2, 4, 2, 2, 3, 1, 2, 2, 2, 1, 3, 3, 1, 2, 1, 1, 1, 1, 3, 3, 1, 3, 1, 1, 1, 1, 3, 1, 1, 4, 2, 5, 2, 1, 3, 1, 1, 2, 3, 1, 2, 2, 1, 1, 1, 1, 1, 1, 3, 1, 2, 1, 3, 1, 2, 3, 4, 4, 3, 2, 4, 2, 1, 4, 2, 4, 1, 2, 1, 3, 1, 2, 1, 1, 1, 3, 2, 1, 2, 2, 2, 3, 3, 1, 2, 1, 3, 1, 1, 1, 2, 1, 3, 4, 2, 1, 4, 1, 2, 1, 2, 2, 2, 1, 1, 2, 1, 1, 2, 2, 2, 1, 4, 2, 1, 4, 1, 1, 1, 1, 2, 4, 4, 3, 2, 4, 2, 1, 1, 1, 1, 1, 1, 1, 4, 2, 2, 3, 1, 1, 1, 2, 1, 3, 1, 4, 1, 2, 4, 1, 2, 3, 4, 1, 3, 1, 1, 1, 2, 4, 1, 1, 1, 4, 1, 1, 4, 2, 1, 4, 2, 2, 1, 1, 1, 1, 1, 2, 3, 2, 1, 4, 3, 3, 4, 4, 3, 2, 4, 2, 1, 1, 3, 2, 4, 1, 1, 2, 3, 1, 1, 1, 2, 2, 1, 1, 1, 1, 3, 1, 1, 1, 4, 3, 3, 1, 1, 2, 1, 1, 1, 1, 3, 1, 1, 4, 2, 5, 1, 1, 4, 2, 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 2, 1, 2, 1, 2, 4, 3, 1, 1, 1, 1, 3, 4, 3, 1, 1, 4, 1, 6, 2, 1, 1, 1, 3, 1, 1, 3, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 4, 3, 1, 1, 5, 4, 1, 2, 2, 4, 1, 6, 1, 2, 1, 1, 3, 1, 4, 1, 2, 1, 2, 1, 1, 1, 1, 4, 2, 2, 3, 1, 2, 3, 1, 3, 4, 1, 1, 3, 4, 2, 5, 1, 1, 1, 3, 2, 2, 3, 2, 1, 2, 2, 2, 2, 3, 1, 2, 1, 3, 3, 3, 1, 1, 2, 1, 3, 3, 1, 1, 4, 2, 5, 2, 4, 1, 2, 4, 1, 2, 1, 2, 1, 1, 1, 2, 3, 1, 2, 4, 1, 1, 4, 4, 1, 1, 2, 3, 2, 4, 2, 5, 1, 2, 1, 2, 1, 1, 2, 3, 1, 2, 1, 2, 1, 1, 3, 1, 1, 2, 1, 2, 3, 1, 1, 1, 3, 4, 1, 1, 2, 1, 1, 1, 2, 4, 2, 1, 1, 3, 1, 2, 1, 2, 2, 2, 1, 2, 2, 1, 1, 1, 2, 1, 3, 1, 1, 2, 1, 2, 3, 1, 1, 1, 3, 4, 1, 1, 2, 3, 1, 2, 3, 1, 6, 2, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 4, 2, 1, 4, 1, 2, 3, 1, 1, 2, 1]
X_64 = BooleanPolynomialRing(64, [f"x{i}" for i in range(64)])  #设64个布尔值的未知数
Xs = list(X_64.gens())
eqs = []
begin = 0
for i in ct:
    for j in range(i - 1):
        if j == i-2:	# 判断相邻两个是否相同
            eq = Xs[(begin + j) % 64] + Xs[(begin + j + 1) % 64] + 1
            eqs.append(eq)
        else:
            eq = Xs[(begin + j) % 64] + Xs[(begin + j + 1) % 64]
            eqs.append(eq)
    begin += i

m = []
B = []
for i in eqs:
    s = []
    for x in range(len(Xs)):
        if Xs[x] in i:
            s.append(1)
        else:
            s.append(0)
    if "+ 1" in str(i):
        B.append(1)
    else:
        B.append(0)
    m.append(s)
m = matrix(GF(2), m)	# 矩阵
B = vector(GF(2), B)	# 系数

wheel = m.solve_right(B)

print(wheel)
# [(1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0)]

佩服，转换成了一个多项式矩阵解

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
from typing import List,Union,Literal
from Crypto.Util.number import long_to_bytes
import secrets
import random,string,re

class K_Cessation:
    '''
    ## Background:
    K-Cessation cipher is a cipher that uses a K bit wheel to pick the next cipher bit from plaintext bit.
    When encryption starts, the wheel starts at the last bit of the wheel.
    The wheel loops around when it reaches the end.
    For every plaintext bit, the wheel is rotated to the next bit in the wheel that matches the plaintext bit, and the distance rotated is appended to the ciphertext.

    Therefore, if the wheel is not known, it is not possible to decrypt the ciphertext. 
    Or is it?

    
    ## Example:
    To encode "youtu.be/dQw4w9WgXcQ" in 64-Cessation with the wheel 1100011011100011100110100011110110010110010100001011111011111010:
    1. convert the plaintext to bits: 01111001 01101111 01110101 01110100 01110101 00101110 01100010 01100101 00101111 01100100 01010001 01110111 00110100 01110111 00111001 01010111 01100111 01011000 01100011 01010001
    2. from wheel[-1] to the next "0" bit in the wheel, distance is 3, the current wheel position is wheel[2]
    3. from wheel[2] to the next "1" bit in the wheel, distance is 3, the current wheel position is wheel[5]
    4. repeat the steps until all bits is encoded
    5. the result is 3312121232111411211311221152515233123332223411313221112161142123243321244111111311111112111131113211132412111212112112321122115251142114213312132313311222111112


    ## Challenge:
    A flag is encoded with 64-Cessation cipher. 
    The wheel is not known. 
    The ciphertext is given in ciphertext.txt.
    The flag is only known to be an ascii string that is longer than 64 characters. 
    No part of the flag is known, which means the flag is NOT in WMCTF{} or FLAG{} format.
    When submitting, please make the flag in WMCTF{} format.
    The most significant bit of each byte is flipped with a random bit.
    You need to extract the flag from the ciphertext and submit it.
    For your convenience, a salted sha256 hash of the flag is given in flag_hash.txt.

    '''

    def __is_valid_wheel(self):
        hasZero = False
        hasOne = False
        for i in self.wheel:
            if not isinstance(i,int):
                raise ValueError("Wheel must be a list of int")
            if i == 0:
                hasZero = True
            elif i == 1:
                hasOne = True
            if i > 1 or i < 0:
                raise ValueError("Wheel must be a list of 0s and 1s")
        if not hasZero or not hasOne:
            raise ValueError("Wheel must contain at least one 0 and one 1")

    def __init__(self,wheel:List[int]):
        self.wheel = wheel
        self.__is_valid_wheel()
        self.state = -1
        self.finalized = False
    def __find_next_in_wheel(self,target:Literal[1,0]) -> List[int]:
        result = 1
        while True:
            ptr = self.state + result
            ptr = ptr % len(self.wheel)
            v = self.wheel[ptr]
            if v == target:
                self.state = ptr
                return [result]
            result+=1
    def __iter_bits(self,data:bytes):
        for b in data:
            for i in range(7,-1,-1):
                yield (b >> i) & 1
    def __check_finalized(self):
        if self.finalized:
            raise ValueError("This instance has already been finalized")
        self.finalized = True
    def encrypt(self,data:Union[str,bytes]) -> List[int]:
        self.__check_finalized()
        if isinstance(data,str):
            data = data.encode()
        out = []
        for bit in self.__iter_bits(data):
            rs = self.__find_next_in_wheel(bit)
            # print(f"bit={bit},rs={rs},state={self.state}")
            out.extend(rs)
        return out
    
    def decrypt(self,data:List[int]) -> bytes:
        self.__check_finalized()
        out = []
        for i in data:
            assert type(i) == int
            self.state = self.state + i
            self.state %= len(self.wheel)
            out.append(self.wheel[self.state])
        long = "".join(map(str,out))
        return long_to_bytes(int(long,2))

# generate a random wheel with k bits.
def random_wheel(k=64) -> List[int]:
    return [secrets.randbelow(2) for _ in range(k)]

# the most significant bit of each byte is flipped with a random bit.
def encode_ascii_with_random_msb(data:bytes) -> bytes:
    out = bytearray()
    for b in data:
        assert b < 128, "not ascii"
        b = b ^ (0b10000000 * secrets.randbelow(2))
        out.append(b)
    return bytes(out)

# for your convenience, here is the decoding function.
def decode_ascii_with_random_msb(data:bytes) -> bytes:
    out = bytearray()
    for b in data:
        b = b & 0b01111111
        out.append(b)
    return bytes(out)

ct = [2, 1, 1, 3, 1, 1, 3, 2, 1, 4, 1, 2, 3, 1, 1, 1, 2, 1, 1, 2, 2, 2, 1, 3, 1, 6, 1, 1, 4, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 3, 3, 2, 1, 1, 3, 1, 1, 1, 3, 4, 1, 3, 1, 2, 2, 4, 2, 5, 1, 1, 1, 3, 2, 1, 4, 2, 2, 1, 2, 1, 3, 1, 1, 1, 1, 1, 2, 3, 1, 2, 1, 1, 1, 1, 3, 4, 1, 2, 2, 4, 2, 5, 1, 2, 1, 2, 2, 1, 4, 1, 2, 1, 2, 1, 1, 1, 1, 1, 1, 2, 2, 1, 4, 3, 1, 2, 1, 3, 1, 3, 3, 2, 1, 3, 1, 6, 2, 1, 1, 2, 1, 2, 1, 3, 1, 1, 2, 1, 2, 1, 1, 2, 1, 2, 2, 2, 3, 1, 1, 4, 1, 3, 1, 1, 1, 2, 1, 1, 2, 4, 1, 1, 5, 2, 4, 2, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 3, 3, 1, 1, 1, 1, 1, 2, 1, 2, 3, 1, 1, 2, 1, 1, 2, 1, 2, 1, 2, 1, 1, 1, 2, 5, 1, 1, 1, 3, 1, 1, 2, 3, 1, 2, 2, 2, 1, 3, 3, 1, 1, 2, 1, 1, 4, 3, 1, 3, 4, 1, 1, 1, 2, 1, 3, 1, 6, 1, 2, 1, 1, 3, 2, 3, 1, 2, 2, 1, 3, 2, 1, 2, 2, 2, 3, 3, 3, 1, 1, 2, 4, 1, 1, 1, 1, 1, 4, 2, 1, 4, 1, 2, 3, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 3, 2, 1, 2, 1, 1, 1, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 2, 4, 2, 1, 4, 2, 4, 2, 2, 3, 1, 2, 2, 2, 1, 3, 3, 1, 2, 1, 1, 1, 1, 3, 3, 1, 3, 1, 1, 1, 1, 3, 1, 1, 4, 2, 5, 2, 1, 3, 1, 1, 2, 3, 1, 2, 2, 1, 1, 1, 1, 1, 1, 3, 1, 2, 1, 3, 1, 2, 3, 4, 4, 3, 2, 4, 2, 1, 4, 2, 4, 1, 2, 1, 3, 1, 2, 1, 1, 1, 3, 2, 1, 2, 2, 2, 3, 3, 1, 2, 1, 3, 1, 1, 1, 2, 1, 3, 4, 2, 1, 4, 1, 2, 1, 2, 2, 2, 1, 1, 2, 1, 1, 2, 2, 2, 1, 4, 2, 1, 4, 1, 1, 1, 1, 2, 4, 4, 3, 2, 4, 2, 1, 1, 1, 1, 1, 1, 1, 4, 2, 2, 3, 1, 1, 1, 2, 1, 3, 1, 4, 1, 2, 4, 1, 2, 3, 4, 1, 3, 1, 1, 1, 2, 4, 1, 1, 1, 4, 1, 1, 4, 2, 1, 4, 2, 2, 1, 1, 1, 1, 1, 2, 3, 2, 1, 4, 3, 3, 4, 4, 3, 2, 4, 2, 1, 1, 3, 2, 4, 1, 1, 2, 3, 1, 1, 1, 2, 2, 1, 1, 1, 1, 3, 1, 1, 1, 4, 3, 3, 1, 1, 2, 1, 1, 1, 1, 3, 1, 1, 4, 2, 5, 1, 1, 4, 2, 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 2, 1, 2, 1, 2, 4, 3, 1, 1, 1, 1, 3, 4, 3, 1, 1, 4, 1, 6, 2, 1, 1, 1, 3, 1, 1, 3, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 4, 3, 1, 1, 5, 4, 1, 2, 2, 4, 1, 6, 1, 2, 1, 1, 3, 1, 4, 1, 2, 1, 2, 1, 1, 1, 1, 4, 2, 2, 3, 1, 2, 3, 1, 3, 4, 1, 1, 3, 4, 2, 5, 1, 1, 1, 3, 2, 2, 3, 2, 1, 2, 2, 2, 2, 3, 1, 2, 1, 3, 3, 3, 1, 1, 2, 1, 3, 3, 1, 1, 4, 2, 5, 2, 4, 1, 2, 4, 1, 2, 1, 2, 1, 1, 1, 2, 3, 1, 2, 4, 1, 1, 4, 4, 1, 1, 2, 3, 2, 4, 2, 5, 1, 2, 1, 2, 1, 1, 2, 3, 1, 2, 1, 2, 1, 1, 3, 1, 1, 2, 1, 2, 3, 1, 1, 1, 3, 4, 1, 1, 2, 1, 1, 1, 2, 4, 2, 1, 1, 3, 1, 2, 1, 2, 2, 2, 1, 2, 2, 1, 1, 1, 2, 1, 3, 1, 1, 2, 1, 2, 3, 1, 1, 1, 3, 4, 1, 1, 2, 3, 1, 2, 3, 1, 6, 2, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 4, 2, 1, 4, 1, 2, 3, 1, 1, 2, 1]
wheels = [(1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0)]

for wheel in wheels:
    c = K_Cessation(wheel)
    pt = c.decrypt(ct)
    pt = decode_ascii_with_random_msb(pt)
    print(pt)

# b'DoubleUmCtF[S33K1NG_tru7h-7h3_w1s3-f1nd_1n57e4d-17s_pr0f0und-4b5ence_n0w-g0_s0lv3-th3_3y3s-1n_N0ita]'

reference：

2024-WMCTF-wp-crypto | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz)

2024WMCTF | DexterJie’Blog

SEKAICTF2024

京津冀长城杯2024

ByteCTF-2024

-------------　　　　本文结束　　感谢阅读　　　　-------------