CrewCTF2025

约 1219 字大约 4 分钟

2025-09-24

GFLCG

chal.py:

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad

class LCG:
    def __init__(self, nbits):
        self.nbits = nbits
        R = GF(2)['x']
        mod = 0
        while True:
            mod = R.random_element(degree=nbits)
            if mod.is_irreducible():
                break
        assert mod.degree() == nbits
        self.F = GF(2 ** nbits, 'x', modulus=mod)
        self.a = self.F.random_element()
        self.b = self.F.random_element()
        self.m = mod
        self.state = self.F.random_element()

    def __next__(self):
        self.state *= self.a
        self.state += self.b
        return self.state.to_integer() >> ((self.nbits * 2) // 3)


L = LCG(64 * 3)

values = [next(L) for _ in range(200)]
print(f'{values = }')

v1 = next(L)
v2 = next(L)
key = v1 + v2 * pow(2, 64)
key = int.to_bytes(int(key), 16)

flag = 'crew{*** REDACTED ***}'
cipher = AES.new(key, AES.MODE_ECB)

msg = cipher.encrypt(pad(flag.encode(), 16))
print(f'{msg = }')

output.txt

values = [14841917648858837769, 9575471537143015742, 15844238770919434615, 5212260032608174747, 9233247444323572291, 10459091850700078324, 6348171461039085016, 11275083358377081726, 15851907641654315174, 5642462723638664555, 12166934227670445515, 16652002833255337213, 1100331227495018541, 17310052757528676070, 10647848709476991180, 7381860977210638817, 14749898712454789023, 9867793747622460486, 1616048454543341186, 8104578690941366513, 4083347094007115737, 11760837183986471162, 16862797396993697119, 1174637638031988756, 1804745826465075031, 16276632568687926630, 5043494920323747028, 11409272895120917919, 16265611200345769799, 14970614558261079002, 2250516726687967919, 1197248850350389243, 14603131310865530726, 16548361948476584779, 13353652992939482174, 13336486704510937571, 10441893770111811970, 4107764688249514273, 11772797255441774916, 12518165417933617541, 7010550077174075010, 14001355721098446832, 437777177382829002, 1722164767628433760, 6559647342847449596, 7938756427230732045, 13281366260429048930, 13092183655381323106, 11806529132310996843, 13947964017447178113, 4621312151518731422, 12501874612357040563, 10826458102042992364, 2159902472703790642, 13882393964322032422, 6529148921315953891, 10134887505878190392, 10419951393751420634, 10135848342454860542, 14313363158598253532, 8934368669847669830, 5124101360181491049, 14913219354552074425, 10908282099950928722, 4253964689299281724, 7407726974875151040, 14219905121435863470, 4181337490774743589, 4184184504223738823, 16936150976212002434, 14433936574129760038, 15520881989251542597, 11194070033146759221, 18174433602168311426, 13020442067015339358, 4382990166888652495, 10254297534043164279, 3817100944212579597, 5331877218604250458, 7185825545642354761, 338711531771068892, 10250264203376128253, 7359215208260510617, 14277514750873457414, 3460304295915392143, 3818816217224032441, 4483483566282319717, 2866544513807354462, 12135646457812113066, 8778669990047144231, 12989768322575258896, 8988116933722638298, 15692389573895602242, 4456647617936315332, 6039845569195475247, 14311304340715617600, 17295981409675358596, 11427453308135142971, 9052862849088317754, 6137397312278782739, 9544766266324391091, 16447228426027058890, 13803636818363488657, 16670480602864962535, 3351397243085772246, 5665702184993835815, 16424003006508152011, 13976194469704404585, 401185194999070420, 5699512823604259627, 17357160984615588720, 3670786096561696620, 4323747368693388297, 10876978042181159325, 7883125366518538304, 2344284687610109741, 12391759147373797536, 12590053927293200960, 8879156692797105548, 8461065756503570819, 17573320578141302871, 15642604376730203427, 12749133263385207476, 4133105186664632492, 18028280465459656846, 3067339009189147778, 15204862189705497345, 18132974384436241649, 8091492506662448517, 18147014166549437993, 5201643316892664569, 3104017212583314140, 3368545846626480386, 14752755621090773653, 9816609813405607817, 10989512726787524104, 17941375633925480992, 5969536734982737360, 3324460409144811670, 14364167734200742327, 10841885411537515505, 12033027733536926218, 13019115357341976440, 13723571084095846113, 14963449044276506843, 9241404467774916626, 1173475476199930336, 10007814422905689012, 880823326108631285, 2864914879726840475, 12348071585001057949, 6441302746542868688, 4806991077471213319, 8933141648678945175, 11649694907667295433, 8708277013041751508, 11719418456350910218, 16635157254108725579, 2134377351096125475, 10289961173017455600, 7055962786096505116, 21728601024181168, 16456998880597164728, 17216116874066795215, 3380132322173996284, 13114502767808007100, 4207348709474901930, 12916699834279235125, 15877440687400786825, 4585779573201771030, 3370966433634988692, 6413163656213101252, 8735986678159831147, 14813660282203931848, 4336269858741206951, 7680697319476289935, 3057350045239125021, 437484923622226917, 12182392489340614340, 7344380605957273905, 1047582581395548343, 9669150555048976950, 3445073427932842783, 5988003049280873305, 9984210927208328016, 8558400548885959238, 14932071850589169092, 10998241484982990572, 4061032217328993314, 16299495071317926943, 14159713152585339233, 7943955737745599039, 2708719529779063308, 5915795415723872866, 15610632814203455383, 9659638034966636775, 10804220067446596648, 3339259544022408735, 16353934319513835005, 7564345426168321381]
msg = b'\xf9\xb9p\xf1\xa0\xc2\x15-\xa1\x90b\x06\x85\x1e\xa9bH\x15\x02\xcc\xba\x97\xc9.\xd3\xc8#\x1af6N\x96x)\x89\xddrg\xa2\x8b\xdd\x0c\xc9peNzWU\xfc9fJ1\xef\xdd\n\x9c\xa2\tW\x97F\x9a'

题目中LCG类的本质是有限域 $GF(2^{192})$ 上的仿射递归生成器。输出状态只有高64位，少了128位。看似丢失了2/3的状态信息，但由于有限域仿射变换的比特级线性性，高 64 位的每个比特序列仍满足线性递归关系，且题目给出了 200 个输出（远多于递归阶数 192）。

有限域运算的比特投影中，状态更新 $s_{n+1} = a \cdot s_n + b$ 可 “投影” 到每个比特位：对高 64 位的任意一个比特（记为 $t_n^{(i)} = s_n^{(128+i)}$ ， $i=0 \sim 63$ ，即高 64 位的第i个局部比特），其更新满足：

t_{n+1}^{(i)} = \sum_{j=0}^{191} a^{(i,j)} \cdot s_n^{(j)} + b^{(i)} \mod 2

尽管 $t_{n+1}^{(i)}$ 的更新依赖低 128 位（ $s_n^{(0)} \sim s_n^{(127)}$ ），但由于状态序列 $\{s_n\}$ 是192 阶线性递归序列（仿射序列的线性递归阶数不超过有限域维度 192），高 64 位的比特序列 $\{t_n^{(i)}\}$ （ $i=0 \sim 63$ ）会继承这一线性性，形成仅依赖自身历史的线性递归：

t_n^{(i)} = c_0 \cdot t_{n-k}^{(i)} \oplus c_1 \cdot t_{n-k+1}^{(i)} \oplus \dots \oplus c_{k-1} \cdot t_{n-1}^{(i)} \mod 2

c_0 \cdot t_{n-k}^{(i)} \oplus c_1 \cdot t_{n-k+1}^{(i)} \oplus \dots \oplus c_{k-1} \cdot t_{n-1}^{(i)} \oplus 1 \cdot t_n^{(i)} = 0\mod 2

其中 $c_0,c_1,\dots,c_{k-1} \in \{0,1\}$ 是所有比特共享的通用系数（因所有比特来自同一状态更新规则）， $k \leq 192$ （递归阶数不超过有限域维度）。

那么会存在A使得：

A * \begin{pmatrix} s_0^{(0)} & s_0^{(1)} & \cdots & s_0^{(63)} & \cdots\\ s_1^{(0)} & s_1^{(1)} & \cdots & s_1^{(63)} & \cdots\\ \vdots & \vdots & \cdots & \vdots & \cdots \\ \end{pmatrix} = 0

此时A在此比特状态矩阵的左核空间中，只要求出一个唯一确定的，且最后一个系数为1的系数矩阵，就可以用于后续观测矩阵的预测。

"""SageMath version 10.7"""
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad

values = [14841917648858837769, 9575471537143015742, 15844238770919434615, 5212260032608174747, 9233247444323572291, 10459091850700078324, 6348171461039085016, 11275083358377081726, 15851907641654315174, 5642462723638664555, 12166934227670445515, 16652002833255337213, 1100331227495018541, 17310052757528676070, 10647848709476991180, 7381860977210638817, 14749898712454789023, 9867793747622460486, 1616048454543341186, 8104578690941366513, 4083347094007115737, 11760837183986471162, 16862797396993697119, 1174637638031988756, 1804745826465075031, 16276632568687926630, 5043494920323747028, 11409272895120917919, 16265611200345769799, 14970614558261079002, 2250516726687967919, 1197248850350389243, 14603131310865530726, 16548361948476584779, 13353652992939482174, 13336486704510937571, 10441893770111811970, 4107764688249514273, 11772797255441774916, 12518165417933617541, 7010550077174075010, 14001355721098446832, 437777177382829002, 1722164767628433760, 6559647342847449596, 7938756427230732045, 13281366260429048930, 13092183655381323106, 11806529132310996843, 13947964017447178113, 4621312151518731422, 12501874612357040563, 10826458102042992364, 2159902472703790642, 13882393964322032422, 6529148921315953891, 10134887505878190392, 10419951393751420634, 10135848342454860542, 14313363158598253532, 8934368669847669830, 5124101360181491049, 14913219354552074425, 10908282099950928722, 4253964689299281724, 7407726974875151040, 14219905121435863470, 4181337490774743589, 4184184504223738823, 16936150976212002434, 14433936574129760038, 15520881989251542597, 11194070033146759221, 18174433602168311426, 13020442067015339358, 4382990166888652495, 10254297534043164279, 3817100944212579597, 5331877218604250458, 7185825545642354761, 338711531771068892, 10250264203376128253, 7359215208260510617, 14277514750873457414, 3460304295915392143, 3818816217224032441, 4483483566282319717, 2866544513807354462, 12135646457812113066, 8778669990047144231, 12989768322575258896, 8988116933722638298, 15692389573895602242, 4456647617936315332, 6039845569195475247, 14311304340715617600, 17295981409675358596, 11427453308135142971, 9052862849088317754, 6137397312278782739, 9544766266324391091, 16447228426027058890, 13803636818363488657, 16670480602864962535, 3351397243085772246, 5665702184993835815, 16424003006508152011, 13976194469704404585, 401185194999070420, 5699512823604259627, 17357160984615588720, 3670786096561696620, 4323747368693388297, 10876978042181159325, 7883125366518538304, 2344284687610109741, 12391759147373797536, 12590053927293200960, 8879156692797105548, 8461065756503570819, 17573320578141302871, 15642604376730203427, 12749133263385207476, 4133105186664632492, 18028280465459656846, 3067339009189147778, 15204862189705497345, 18132974384436241649, 8091492506662448517, 18147014166549437993, 5201643316892664569, 3104017212583314140, 3368545846626480386, 14752755621090773653, 9816609813405607817, 10989512726787524104, 17941375633925480992, 5969536734982737360, 3324460409144811670, 14364167734200742327, 10841885411537515505, 12033027733536926218, 13019115357341976440, 13723571084095846113, 14963449044276506843, 9241404467774916626, 1173475476199930336, 10007814422905689012, 880823326108631285, 2864914879726840475, 12348071585001057949, 6441302746542868688, 4806991077471213319, 8933141648678945175, 11649694907667295433, 8708277013041751508, 11719418456350910218, 16635157254108725579, 2134377351096125475, 10289961173017455600, 7055962786096505116, 21728601024181168, 16456998880597164728, 17216116874066795215, 3380132322173996284, 13114502767808007100, 4207348709474901930, 12916699834279235125, 15877440687400786825, 4585779573201771030, 3370966433634988692, 6413163656213101252, 8735986678159831147, 14813660282203931848, 4336269858741206951, 7680697319476289935, 3057350045239125021, 437484923622226917, 12182392489340614340, 7344380605957273905, 1047582581395548343, 9669150555048976950, 3445073427932842783, 5988003049280873305, 9984210927208328016, 8558400548885959238, 14932071850589169092, 10998241484982990572, 4061032217328993314, 16299495071317926943, 14159713152585339233, 7943955737745599039, 2708719529779063308, 5915795415723872866, 15610632814203455383, 9659638034966636775, 10804220067446596648, 3339259544022408735, 16353934319513835005, 7564345426168321381]
msg = b'\xf9\xb9p\xf1\xa0\xc2\x15-\xa1\x90b\x06\x85\x1e\xa9bH\x15\x02\xcc\xba\x97\xc9.\xd3\xc8#\x1af6N\x96x)\x89\xddrg\xa2\x8b\xdd\x0c\xc9peNzWU\xfc9fJ1\xef\xdd\n\x9c\xa2\tW\x97F\x9a'


k = 4
c = 64*3 + 2 #194

mat = []

for i in range(c):
    row = []
    for j in range(k):
        U = values[i + j]
        for l in range(64):
            row.append(U & 1)
            U >>= 1
    mat.append(row)

mat = Matrix(GF(2), mat)

pols = mat.left_kernel().basis()
assert len(pols) == 1
pol = pols[0]
assert pol[-1] == 1

for app in range(len(values), len(values) + 2):
    ans = 0
    for i in range(0, len(pol) - 1):
        if pol[i] == 1:
            ans ^^= values[app + i - len(pol) + 1]
    values.append(ans)

key = values[-2] + values[-1] * pow(2, 64)
key = int.to_bytes(int(key), 16)
cipher = AES.new(key,AES.MODE_ECB)
print(unpad(cipher.decrypt(msg), 16).decode())
# crew{Its_34513r_1n_GF2_d1a83b1addeb0ed863b46a85aef9a293}