XYCTF2025

发表于 更新于 阅读次数： 本文字数： 53k 阅读时长 ≈ 1:36

OWO

梦开始的地方。

1,Complex_signin

题目

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
from Crypto.Util.number import *
from Crypto.Cipher import ChaCha20
import hashlib
from secret import flag


class Complex:
    def __init__(self, re, im):
        self.re = re
        self.im = im

    def __mul__(self, c):
        re_ = self.re * c.re - self.im * c.im
        im_ = self.re * c.im + self.im * c.re
        return Complex(re_, im_)

    def __eq__(self, c):
        return self.re == c.re and self.im == c.im

    def __rshift__(self, m):
        return Complex(self.re >> m, self.im >> m)

    def __lshift__(self, m):
        return Complex(self.re << m, self.im << m)

    def __str__(self):
        if self.im == 0:
            return str(self.re)
        elif self.re == 0:
            if abs(self.im) == 1:
                return f"{'-' if self.im < 0 else ''}i"
            else:
                return f"{self.im}i"
        else:
            return f"{self.re} {'+' if self.im > 0 else '-'} {abs(self.im)}i"

    def tolist(self):
        return [self.re, self.im]


def complex_pow(c, exp, n):
    result = Complex(1, 0)
    while exp > 0:
        if exp & 1:
            result = result * c
            result.re = result.re % n
            result.im = result.im % n
        c = c * c
        c.re = c.re % n
        c.im = c.im % n
        exp >>= 1
    return result

bits = 128
p = getPrime(1024)
q = getPrime(1024)
n = p * q
m = Complex(getRandomRange(1, n), getRandomRange(1, n))
e = 3
c = complex_pow(m, e, n)
print(f"n = {n}")
print(f"mh = {(m >> bits << bits).tolist()}")
print(f"C = {c.tolist()}")
print(f"enc = {ChaCha20.new(key=hashlib.sha256(str(m.re + m.im).encode()).digest(), nonce=b'Pr3d1ctmyxjj').encrypt(flag)}")

'''
n = 24240993137357567658677097076762157882987659874601064738608971893024559525024581362454897599976003248892339463673241756118600994494150721789525924054960470762499808771760690211841936903839232109208099640507210141111314563007924046946402216384360405445595854947145800754365717704762310092558089455516189533635318084532202438477871458797287721022389909953190113597425964395222426700352859740293834121123138183367554858896124509695602915312917886769066254219381427385100688110915129283949340133524365403188753735534290512113201932620106585043122707355381551006014647469884010069878477179147719913280272028376706421104753
mh = [3960604425233637243960750976884707892473356737965752732899783806146911898367312949419828751012380013933993271701949681295313483782313836179989146607655230162315784541236731368582965456428944524621026385297377746108440938677401125816586119588080150103855075450874206012903009942468340296995700270449643148025957527925452034647677446705198250167222150181312718642480834399766134519333316989347221448685711220842032010517045985044813674426104295710015607450682205211098779229647334749706043180512861889295899050427257721209370423421046811102682648967375219936664246584194224745761842962418864084904820764122207293014016, 15053801146135239412812153100772352976861411085516247673065559201085791622602365389885455357620354025972053252939439247746724492130435830816513505615952791448705492885525709421224584364037704802923497222819113629874137050874966691886390837364018702981146413066712287361010611405028353728676772998972695270707666289161746024725705731676511793934556785324668045957177856807914741189938780850108643929261692799397326838812262009873072175627051209104209229233754715491428364039564130435227582042666464866336424773552304555244949976525797616679252470574006820212465924134763386213550360175810288209936288398862565142167552]
C = [5300743174999795329371527870190100703154639960450575575101738225528814331152637733729613419201898994386548816504858409726318742419169717222702404409496156167283354163362729304279553214510160589336672463972767842604886866159600567533436626931810981418193227593758688610512556391129176234307448758534506432755113432411099690991453452199653214054901093242337700880661006486138424743085527911347931571730473582051987520447237586885119205422668971876488684708196255266536680083835972668749902212285032756286424244284136941767752754078598830317271949981378674176685159516777247305970365843616105513456452993199192823148760, 21112179095014976702043514329117175747825140730885731533311755299178008997398851800028751416090265195760178867626233456642594578588007570838933135396672730765007160135908314028300141127837769297682479678972455077606519053977383739500664851033908924293990399261838079993207621314584108891814038236135637105408310569002463379136544773406496600396931819980400197333039720344346032547489037834427091233045574086625061748398991041014394602237400713218611015436866842699640680804906008370869021545517947588322083793581852529192500912579560094015867120212711242523672548392160514345774299568940390940653232489808850407256752]
enc = b'\x9c\xc4n\x8dF\xd9\x9e\xf4\x05\x82!\xde\xfe\x012$\xd0\x8c\xaf\xfb\rEb(\x04)\xa1\xa6\xbaI2J\xd2\xb2\x898\x11\xe6x\xa9\x19\x00pn\xf6rs- \xd2\xd1\xbe\xc7\xf51.\xd4\xd2 \xe7\xc6\xca\xe5\x19\xbe'
'''

熟悉的复数，熟悉的味道（还记得去年的两道复数.泪目了

前半部分就是定义了一下复数的运算，后半部分是一个已知m高位的RSA。已知m高位很明显要打copper，那这道题是复数域，咋办呢。那就分别对实部和虚部打copper，也就是二元cooper啦。

先贴个二元copper的板子

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
def Small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()
    R = f.base_ring()
    N = R.cardinality()
    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)
    G = Sequence([], f.parent())
    for i in range(m + 1):
        base = N ^ (m - i) * f ^ i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)
    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)
    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)
    B = B.dense_matrix().LLL()
    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1 / factor)
    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B * monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots
    return []

众所周知，我们打copper需要一个式子，这里我们就根据complex_pow(c, exp, n)这个对应的式子来打。(顺带一提.tolist()会返回包含该复数实部和虚部的一个列表)

1
2
3
4
5
6
7
8
9
H1, H2 = mh
R.<a, b> = PolynomialRing(Zmod(n))
m = Complex(H1+a, H2+b)
e = 3
c0, c1 = complex_pow(m, e, n).tolist()
f = c0+c1-C[0]-C[1]
a, b = Small_roots(f, bounds=(2**128, 2**128), m=1, d=4)[0]
m = Complex(H1+a, H2+b)

其实就是普通的m高位的思路，对实部虚部分别打就行。

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
# Sage 10.5
from Crypto.Util.number import *
from Crypto.Cipher import ChaCha20
import itertools
import hashlib

class Complex:
    def __init__(self, re, im):
        self.re = re
        self.im = im

    def __mul__(self, c):
        re_ = self.re * c.re - self.im * c.im
        im_ = self.re * c.im + self.im * c.re
        return Complex(re_, im_)

    def __eq__(self, c):
        return self.re == c.re and self.im == c.im

    def __rshift__(self, m):
        return Complex(self.re >> m, self.im >> m)

    def __lshift__(self, m):
        return Complex(self.re << m, self.im << m)

    def __str__(self):
        if self.im == 0:
            return str(self.re)
        elif self.re == 0:
            if abs(self.im) == 1:
                return f"{'-' if self.im < 0 else ''}i"
            else:
                return f"{self.im}i"
        else:
            return f"{self.re} {'+' if self.im > 0 else '-'} {abs(self.im)}i"

    def tolist(self):
        return [self.re, self.im]

def complex_pow(c, exp, n):
    result = Complex(1, 0)
    while exp > 0:
        if exp & 1:
            result = result * c
            result.re = result.re % n
            result.im = result.im % n
        c = c * c
        c.re = c.re % n
        c.im = c.im % n
        exp >>= 1
    return result

def Small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()
    R = f.base_ring()
    N = R.cardinality()
    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)
    G = Sequence([], f.parent())
    for i in range(m + 1):
        base = N ^ (m - i) * f ^ i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)
    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)
    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)
    B = B.dense_matrix().LLL()
    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1 / factor)
    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B * monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots
    return []

n = 24240993137357567658677097076762157882987659874601064738608971893024559525024581362454897599976003248892339463673241756118600994494150721789525924054960470762499808771760690211841936903839232109208099640507210141111314563007924046946402216384360405445595854947145800754365717704762310092558089455516189533635318084532202438477871458797287721022389909953190113597425964395222426700352859740293834121123138183367554858896124509695602915312917886769066254219381427385100688110915129283949340133524365403188753735534290512113201932620106585043122707355381551006014647469884010069878477179147719913280272028376706421104753
mh = [3960604425233637243960750976884707892473356737965752732899783806146911898367312949419828751012380013933993271701949681295313483782313836179989146607655230162315784541236731368582965456428944524621026385297377746108440938677401125816586119588080150103855075450874206012903009942468340296995700270449643148025957527925452034647677446705198250167222150181312718642480834399766134519333316989347221448685711220842032010517045985044813674426104295710015607450682205211098779229647334749706043180512861889295899050427257721209370423421046811102682648967375219936664246584194224745761842962418864084904820764122207293014016, 15053801146135239412812153100772352976861411085516247673065559201085791622602365389885455357620354025972053252939439247746724492130435830816513505615952791448705492885525709421224584364037704802923497222819113629874137050874966691886390837364018702981146413066712287361010611405028353728676772998972695270707666289161746024725705731676511793934556785324668045957177856807914741189938780850108643929261692799397326838812262009873072175627051209104209229233754715491428364039564130435227582042666464866336424773552304555244949976525797616679252470574006820212465924134763386213550360175810288209936288398862565142167552]
C = [5300743174999795329371527870190100703154639960450575575101738225528814331152637733729613419201898994386548816504858409726318742419169717222702404409496156167283354163362729304279553214510160589336672463972767842604886866159600567533436626931810981418193227593758688610512556391129176234307448758534506432755113432411099690991453452199653214054901093242337700880661006486138424743085527911347931571730473582051987520447237586885119205422668971876488684708196255266536680083835972668749902212285032756286424244284136941767752754078598830317271949981378674176685159516777247305970365843616105513456452993199192823148760, 21112179095014976702043514329117175747825140730885731533311755299178008997398851800028751416090265195760178867626233456642594578588007570838933135396672730765007160135908314028300141127837769297682479678972455077606519053977383739500664851033908924293990399261838079993207621314584108891814038236135637105408310569002463379136544773406496600396931819980400197333039720344346032547489037834427091233045574086625061748398991041014394602237400713218611015436866842699640680804906008370869021545517947588322083793581852529192500912579560094015867120212711242523672548392160514345774299568940390940653232489808850407256752]
enc = b'\x9c\xc4n\x8dF\xd9\x9e\xf4\x05\x82!\xde\xfe\x012$\xd0\x8c\xaf\xfb\rEb(\x04)\xa1\xa6\xbaI2J\xd2\xb2\x898\x11\xe6x\xa9\x19\x00pn\xf6rs- \xd2\xd1\xbe\xc7\xf51.\xd4\xd2 \xe7\xc6\xca\xe5\x19\xbe'
H1, H2 = mh
R.<a, b> = PolynomialRing(Zmod(n))
m = Complex(H1+a, H2+b)
e = 3
c0, c1 = complex_pow(m, e, n).tolist()
print(c0)
print(c1)
f = c0+c1-C[0]-C[1]
a, b = Small_roots(f, bounds=(2**128, 2**128), m=1, d=4)[0]
m = Complex(H1+a, H2+b)
print(ChaCha20.new(key=hashlib.sha256(str(m.re + m.im).encode()).digest(), nonce=b'Pr3d1ctmyxjj').decrypt(enc))
# XYCTF{Welcome_to_XYCTF_Now_let_us_together_play_Crypto_challenge}

2,Reed

题目

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
import string
import random
from secret import flag

assert flag.startswith('XYCTF{') and flag.endswith('}')
flag = flag.rstrip('}').lstrip('XYCTF{')

table = string.ascii_letters + string.digits
assert all(i in table for i in flag)
r = random.Random()

class PRNG:
    def __init__(self, seed):
        self.a = 1145140
        self.b = 19198100
        random.seed(seed)

    def next(self):
        x = random.randint(self.a, self.b)
        random.seed(x ** 2 + 1)
        return x
    
    def round(self, k):
        for _ in range(k):
            x = self.next()
        return x

def encrypt(msg, a, b):
    c = [(a * table.index(m) + b) % 19198111 for m in msg]
    return c

seed = int(input('give me seed: '))
prng = PRNG(seed)
a = prng.round(r.randrange(2**16))
b = prng.round(r.randrange(2**16))
enc = encrypt(flag, a, b)
print(enc)

AI一把梭XD

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
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
class ComComplex:
    def __init__(self, value=[0,0,0,0]):
        self.value = value
    def __str__(self):
        s = str(self.value[0])
        for k,i in enumerate(self.value[1:]):
            if i >= 0:
                s += '+'
            s += str(i) +'ijk'[k]
        return s
    def __add__(self,x):
        return ComComplex([i+j for i,j in zip(self.value,x.value)])
    def __mul__(self,x):
        a = self.value[0]*x.value[0]-self.value[1]*x.value[1]-self.value[2]*x.value[2]-self.value[3]*x.value[3]
        b = self.value[0]*x.value[1]+self.value[1]*x.value[0]+self.value[2]*x.value[3]-self.value[3]*x.value[2]
        c = self.value[0]*x.value[2]-self.value[1]*x.value[3]+self.value[2]*x.value[0]+self.value[3]*x.value[1]
        d = self.value[0]*x.value[3]+self.value[1]*x.value[2]-self.value[2]*x.value[1]+self.value[3]*x.value[0]
        return ComComplex([a,b,c,d])
    def __mod__(self,x):
        return ComComplex([i % x for i in self.value])
    def __pow__(self, x, n=None):
        tmp = ComComplex(self.value)
        a = ComComplex([1,0,0,0])
        while x:
            if x & 1:
                a *= tmp
            tmp *= tmp
            if n:
                a %= n
                tmp %= n
            x >>= 1
        return a

from Crypto.Util.number import *
from secret import flag, hint

p = getPrime(256)
q = getPrime(256)
r = getPrime(256)
n = p * q * r

P = getPrime(512)
assert len(hint) == 20
hints = ComComplex([bytes_to_long(hint[i:i+5]) for i in range(0,20,5)])
keys = ComComplex([0, p, q, r])
print('hint =',hints)
print('gift =',hints*keys%P)
print('P =',P)

e = 65547
m = ComComplex([bytes_to_long(flag[i:i+len(flag)//4+1]) for i in range(0,len(flag),len(flag)//4+1)])
c = pow(m, e, n)
print('n =', n)
print('c =', c)

'''
hint = 375413371936+452903063925i+418564633198j+452841062207k
gift = 8123312244520119413231609191866976836916616973013918670932199631084038015924368317077919454611785179950870055560079987034735836668109705445946887481003729+20508867471664499348708768798854433383217801696267611753941328714877299161068885700412171i+22802458968832151777449744120185122420871929971817937643641589637402679927558503881707868j+40224499597522456323122179021760594618350780974297095023316834212332206526399536884102863k
P = 8123312244520119413231609191866976836916616973013918670932199631182724263362174895104545305364960781233690810077210539091362134310623408173268475389315109
n = 408713495380933615345467409596399184629824932933932227692519320046890365817329617301604051766392980053993030281090124694858194866782889226223493799859404283664530068697313752856923001112586828837146686963124061670340088332769524367
c = 212391106108596254648968182832931369624606731443797421732310126161911908195602305474921714075911012622738456373731638115041135121458776339519085497285769160263024788009541257401354037620169924991531279387552806754098200127027800103+24398526281840329222660628769015610312084745844610670698920371305353888694519135578269023873988641161449924124665731242993290561874625654977013162008430854786349580090169988458393820787665342793716311005178101342140536536153873825i+45426319565874516841189981758358042952736832934179778483602503215353130229731883231784466068253520728052302138781204883495827539943655851877172681021818282251414044916889460602783324944030929987991059211909160860125047647337380125j+96704582331728201332157222706704482771142627223521415975953255983058954606417974983056516338287792260492498273014507582247155218239742778886055575426154960475637748339582574453542182586573424942835640846567809581805953259331957385k
'''

是复数，但不是一般的复数，看一下前面的class部分发现是一个四元复数，这点其实解hint也能得到。

1
2
3
4
5
6
7
8
9
10
11
numbers = [375413371936, 452903063925, 418564633198, 452841062207]
byte_arrays = []
for number in numbers:
    byte_array = number.to_bytes(5, 'big')
    byte_arrays.append(byte_array)
result = b''.join(byte_arrays)
print(result)



b'What is Quaternion??'

然后就可以先把p，q，r分别算出来。这里的重点是四元数的乘法，也就是这一段

1
2
3
4
5
def __mul__(self,x):
        a = self.value[0]*x.value[0]-self.value[1]*x.value[1]-self.value[2]*x.value[2]-self.value[3]*x.value[3]
        b = self.value[0]*x.value[1]+self.value[1]*x.value[0]+self.value[2]*x.value[3]-self.value[3]*x.value[2]
        c = self.value[0]*x.value[2]-self.value[1]*x.value[3]+self.value[2]*x.value[0]+self.value[3]*x.value[1]
        d = self.value[0]*x.value[3]+self.value[1]*x.value[2]-self.value[2]*x.value[1]+self.value[3]*x.value[0]

a = h00 - h1p - h2q - h3r

b = h0p + h10 + h2r - h3q

c = h0q - h1r + h20 + h3p

d = h0r + h1q - h2p + h30

对每个分量模p就得到gift，gift = (hints * keys) % P。因此，如果我们能找到hints的逆四元数H_inv，使得H_inv * hints ≡ 1 mod P（这里的1是四元数[1,0,0,0]），那么就可以通过gift * H_inv mod P来得到keys。因为gift ≡ hints * keys mod P。

这里需要补充一个知识点，四元数的逆为其共轭除以模长平方。

O047o1.png

将H_inv与gift进行四元数乘法，结果模P后得到keys：

1
2
3
4
b0 = (a0 * g0 - a1 * g1 - a2 * g2 - a3 * g3) % P
b1 = (a0 * g1 + a1 * g0 + a2 * g3 - a3 * g2) % P
b2 = (a0 * g2 - a1 * g3 + a2 * g0 + a3 * g1) % P
b3 = (a0 * g3 + a1 * g2 - a2 * g1 + a3 * g0) % P

解得p=b1,q=b2,r=b3.

四元数的欧拉函数为phi(pqr) = (p−1)p(p+1)(q −1)q(q +1)(r −1)r(r +1)。

但是本题的e为65547，gcd(e,phi)=27。出题人给出的wp里说是gcd是9，要两次AMM的开立方根，感觉有点问题。自己试了一下。直接phi//27就行，但是没太懂是为啥。

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
from Cryptodome.Util.number import inverse, long_to_bytes
from gmpy2 import gcd, invert
class ComComplex:
    def __init__(self, value=[0,0,0,0]):
        self.value = value
    def __str__(self):
        s = str(self.value[0])
        for k,i in enumerate(self.value[1:]):
            if i >= 0:
                s += '+'
            s += str(i) +'ijk'[k]
        return s
    def __add__(self,x):
        return ComComplex([i+j for i,j in zip(self.value,x.value)])
    def __mul__(self,x):
        a = self.value[0]*x.value[0]-self.value[1]*x.value[1]-self.value[2]*x.value[2]-self.value[3]*x.value[3]
        b = self.value[0]*x.value[1]+self.value[1]*x.value[0]+self.value[2]*x.value[3]-self.value[3]*x.value[2]
        c = self.value[0]*x.value[2]-self.value[1]*x.value[3]+self.value[2]*x.value[0]+self.value[3]*x.value[1]
        d = self.value[0]*x.value[3]+self.value[1]*x.value[2]-self.value[2]*x.value[1]+self.value[3]*x.value[0]
        return ComComplex([a,b,c,d])
    def __mod__(self,x):
        return ComComplex([i % x for i in self.value])
    def __pow__(self, x, n=None):
        tmp = ComComplex(self.value)
        a = ComComplex([1,0,0,0])
        while x:
            if x & 1:
                a *= tmp
            tmp *= tmp
            if n:
                a %= n
                tmp %= n
            x >>= 1
        return a

hints = [375413371936, 452903063925, 418564633198, 452841062207]
gift = [
    8123312244520119413231609191866976836916616973013918670932199631084038015924368317077919454611785179950870055560079987034735836668109705445946887481003729,
    20508867471664499348708768798854433383217801696267611753941328714877299161068885700412171,
    22802458968832151777449744120185122420871929971817937643641589637402679927558503881707868,
    40224499597522456323122179021760594618350780974297095023316834212332206526399536884102863
]
P = 8123312244520119413231609191866976836916616973013918670932199631182724263362174895104545305364960781233690810077210539091362134310623408173268475389315109
n = 408713495380933615345467409596399184629824932933932227692519320046890365817329617301604051766392980053993030281090124694858194866782889226223493799859404283664530068697313752856923001112586828837146686963124061670340088332769524367

h0, h1, h2, h3 = hints
g0, g1, g2, g3 = gift

# 计算norm_H
norm_H = (pow(h0, 2, P) + pow(h1, 2, P) + pow(h2, 2, P) + pow(h3, 2, P)) % P
inv_norm_H = inverse(norm_H, P)

# 构造H_inv
a0 = (h0 * inv_norm_H) % P
a1 = (-h1 * inv_norm_H) % P
a2 = (-h2 * inv_norm_H) % P
a3 = (-h3 * inv_norm_H) % P

# 四元数乘法 H_inv * gift
b0 = (a0 * g0 - a1 * g1 - a2 * g2 - a3 * g3) % P
b1 = (a0 * g1 + a1 * g0 + a2 * g3 - a3 * g2) % P
b2 = (a0 * g2 - a1 * g3 + a2 * g0 + a3 * g1) % P
b3 = (a0 * g3 + a1 * g2 - a2 * g1 + a3 * g0) % P

p, q, r = b1, b2, b3

# 验证乘积
assert (p * q * r) == n, "p*q*r != n"
print(f"p = {p}\nq = {q}\nr = {r}")
n=p*q*r
phi=(p-1)*p*(p+1)*(q-1)*q*(q +1)*(r-1)*r*(r+1)//27
e=65547
print(gcd(e,phi))
d=invert(e,phi)
cc= ComComplex([212391106108596254648968182832931369624606731443797421732310126161911908195602305474921714075911012622738456373731638115041135121458776339519085497285769160263024788009541257401354037620169924991531279387552806754098200127027800103,24398526281840329222660628769015610312084745844610670698920371305353888694519135578269023873988641161449924124665731242993290561874625654977013162008430854786349580090169988458393820787665342793716311005178101342140536536153873825,45426319565874516841189981758358042952736832934179778483602503215353130229731883231784466068253520728052302138781204883495827539943655851877172681021818282251414044916889460602783324944030929987991059211909160860125047647337380125,96704582331728201332157222706704482771142627223521415975953255983058954606417974983056516338287792260492498273014507582247155218239742778886055575426154960475637748339582574453542182586573424942835640846567809581805953259331957385])
m=pow(cc,d,n)
print(b"".join([long_to_bytes(i) for i in m.value]))

4,新勒索病毒

赛中非预期做的，还是按正常做法做做吧。

首先我们看到给了一个enc文件和exe文件，exe文件打不开。那么思路首先是尝试反编译这个exe文件从而得到python加密源码。这里使用的是pyinstxtractor，值得一提的是必须在python3.8版本才能使用（重新配环境花了蛮久时间XD），然后在终端运行

1
python pyinstxtractor.py task.exe

O04v2b.png

此时在同一个目录下就会出现task.exe_extracted文件夹。打开后需要找到和原文件同名的文件，并加上pyc文件后缀。即task.pyc,此时我们用16进制编辑器打开就能看到加密代码。

O04gWl.png

然后直接bytes.fromhex()即可。

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
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
import re
import base64
import os
import sys
from gmssl import sm4
from Crypto.Util.Padding import pad
import binascii
from random import shuffle, randrange

N = 49
p = 3
q = 128
d = 3
assert q > (6 * d + 1) * p
R. < x > = ZZ[]


def generate_T(d1, d2):
    assert N >= d1 + d2
    s = [1] * d1 + [-1] * d2 + [0] * (N - d1 - d2)
    shuffle(s)
    return R(s)


def invert_mod_prime(f, p):
    Rp = R.change_ring(Integers(p)).quotient(x ^ N - 1)
    return R(lift(1 / Rp(f)))


def convolution(f, g):
    return (f * g) % (x ^ N - 1)


def lift_mod(f, q):
    return R([((f[i] + q // 2) % q) - q // 2 for i in range(N)])


def poly_mod(f, q):
    return R([f[i] % q for i in range(N)])


def invert_mod_pow2(f, q):
    assert q.is_power_of(2)
    g = invert_mod_prime(f, 2)
    while True:
        r = lift_mod(convolution(g, f), q)
        if r == 1:
            return g
        g = lift_mod(convolution(g, 2 - r), q)


def generate_message():
    return R([randrange(p) - 1 for _ in range(N)])


def generate_key():
    while True:
        try:
            f = generate_T(d + 1, d)
            g = generate_T(d, d)
            Fp = poly_mod(invert_mod_prime(f, p), p)
            Fq = poly_mod(invert_mod_pow2(f, q), q)
            break
        except:
            continue
    h = poly_mod(convolution(Fq, g), q)
    return h, (f, g)


def encrypt_message(m, h):
    e = lift_mod(p * convolution(h, generate_T(d, d)) + m, q)
    return e


def save_ntru_keys():
    h, secret = generate_key()
    with open("pub_key.txt", "w") as f:
        f.write(str(h))
    m = generate_message()
    with open("priv_key.txt", "w") as f:
        f.write(str(m))
    e = encrypt_message(m, h)
    with open("enc.txt", "w") as f:
        f.write(str(e))


def terms(poly_str):
    terms = []
    pattern = r'([+-]?\s*x\^?\d*|[-+]?\s*\d+)'
    matches = re.finditer(pattern, poly_str.replace(' ', ''))

    for match in matches:
        term = match.group()
        if term == '+x' or term == 'x':
            terms.append(1)
        elif term == '-x':
            terms.append(-1)
        elif 'x^' in term:
            coeff_part = term.split('x^')[0]
            exponent = int(term.split('x^')[1])
            if not coeff_part or coeff_part == '+':
                coeff = 1
            elif coeff_part == '-':
                coeff = -1
            else:
                coeff = int(coeff_part)
            terms.append(coeff * exponent)
        elif 'x' in term:
            coeff_part = term.split('x')[0]
            if not coeff_part or coeff_part == '+':
                terms.append(1)
            elif coeff_part == '-':
                terms.append(-1)
            else:
                terms.append(int(coeff_part))
        else:
            if term == '+1' or term == '1':
                terms.append(0)
                terms.append(-0)
    return terms


def gen_key(poly_terms):
    binary = [0] * 128
    for term in poly_terms:
        exponent = abs(term)
        if term > 0 and exponent <= 127:
            binary[127 - exponent] = 1
    binary_str = ''.join(map(str, binary))
    hex_key = hex(int(binary_str, 2))[2:].upper().zfill(32)
    return hex_key


def read_polynomial_from_file(filename):
    with open(filename, 'r') as file:
        return file.read().strip()


def sm4_encrypt(key, plaintext):
    assert len(key) == 16, "SM4 key must be 16 bytes"
    cipher = sm4.CryptSM4()
    cipher.set_key(key, sm4.SM4_ENCRYPT)
    padded_plaintext = pad(plaintext, 16)
    return cipher.crypt_ecb(padded_plaintext)


def sm4_encrypt_file(input_path, output_path, key):
    with open(input_path, 'rb') as f:
        plaintext = f.read()

    ciphertext = sm4_encrypt(key, plaintext)

    with open(output_path, 'wb') as f:
        f.write(ciphertext)


def resource_path(relative_path):
    if getattr(sys, 'frozen', False):
        base_path = sys._MEIPASS
    else:
        base_path = os.path.abspath(".")
    return os.path.join(base_path, relative_path)


def encrypt_directory(directory, sm4_key, extensions=[".txt"]):
    if not os.path.exists(directory):
        print(f"Directory does not exist: {directory}")
        return

    for root, _, files in os.walk(directory):
        for file in files:
            if any(file.endswith(ext) for ext in extensions):
                input_path = os.path.join(root, file)
                output_path = input_path + ".enc"

                try:
                    sm4_encrypt_file(input_path, output_path, sm4_key)
                    os.remove(input_path)
                    print(f"Encrypted: {input_path} -> {output_path}")
                except Exception as e:
                    print(f"Error encrypting {input_path}: {str(e)}")


def main():
    try:
        save_ntru_keys()
        poly_str = read_polynomial_from_file("priv_key.txt")
        poly_terms = terms(poly_str)
        sm4_key = binascii.unhexlify(poly_terms)
        user_name = os.getlogin()
        target_dir = os.path.join("C:\Users", user_name, "Desktop", "test_files")

        if not os.path.exists(target_dir):
            os.makedirs(target_dir, exist_ok=True)
            print(f"Created directory: {target_dir}")
            return

        txt_files = [f for f in os.listdir(target_dir)
                     if f.endswith('.txt') and os.path.isfile(os.path.join(target_dir, f))]

        if not txt_files:
            print("No .txt files found in directory")
            return

        for txt_file in txt_files:
            file_path = os.path.join(target_dir, txt_file)
            try:
                with open(file_path, 'rb') as f:
                    test_data = f.read()

                ciphertext = sm4_encrypt(sm4_key, test_data)
                encrypted_path = file_path + '.enc'

                with open(encrypted_path, 'wb') as f:
                    f.write(ciphertext)
            except Exception as e:
                print(f"Error processing {txt_file}: {str(e)}")

    except Exception as e:
        print(f"Fatal error: {str(e)}")


if __name__ == "__main__":
    main()

首先根据

1
2
3
def encrypt_message(m, h):
    e = lift_mod(p * convolution(h, generate_T(d, d)) + m, q)
    return e

NTRU解密得到priv_key.

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
import random
from Crypto.Util.number import *
Zx = PolynomialRing(ZZ, 'x')
x = Zx.gen()
def center_polynomial_coefficients(f, q):
    return Zx([((f[i] + q//2) % q) - q//2 for i in range(len(f.coefficients()))])
def compute_cyclic_convolution(f, g):
    return (f * g) % (x**n - 1)
def invert_polynomial_prime_modulus(f, p):
    T = Zx.change_ring(Integers(p)).quotient(x**n - 1)
    return Zx(lift(1 / T(f)))
def invert_polynomial_power_of_two(f, q):
    assert q.is_power_of(2)
    g = invert_polynomial_prime_modulus(f, 2)
    while True:
        r = center_polynomial_coefficients(compute_cyclic_convolution(g, f), q)
        if r == 1:
            return g
        g = center_polynomial_coefficients(compute_cyclic_convolution(g, 2 - r), q)
def generate_random_polynomial():
    return Zx([random.randint(-d, d) for _ in range(n)])

def encrypt_message(message, public_key):
    r = generate_random_polynomial()
    return center_polynomial_coefficients(
        compute_cyclic_convolution(public_key, r) + message, q)

def decrypt_ciphertext(ciphertext, private_key, private_key_inverse):
    a = center_polynomial_coefficients(
        compute_cyclic_convolution(private_key, ciphertext), q)
    return center_polynomial_coefficients(
        compute_cyclic_convolution(private_key_inverse, a), p)

def perform_ntru_attack(public_key):
    recip3 = lift(1/Integers(q)(3))
    public_key_over_3 = center_polynomial_coefficients(recip3 * public_key, q)
    M = matrix(2 * n)
    for i in range(n):
        M[i, i] = q
    for i in range(n):
        M[i+n, i+n] = 1
        c = compute_cyclic_convolution(x**i, public_key_over_3)
        for j in range(n):
            M[i+n, j] = c[j]
    M = M.LLL()
    for j in range(2 * n):
        try:
            f = Zx(list(M[j][n:]))
            f3 = invert_polynomial_prime_modulus(f, 3)
            return (f, f3)
        except:
            pass
    return (f, f)

# 参数设置
n = 49
p = 3
q = 128
d = 3
assert q > (6*d + 1)*p

# 公钥定义
public_key = 8*x^48 + 58*x^47 + 18*x^46 + 61*x^45 + 33*x^44 + 21*x^43 + 58*x^42 + 21*x^41 + 5*x^40 + 32*x^39 + 15*x^38 + 40*x^37 + 24*x^36 + 14*x^35 + 40*x^34 + 5*x^33 + x^32 + 48*x^31 + 21*x^30 + 36*x^29 + 42*x^28 + 8*x^27 + 17*x^26 + 54*x^25 + 39*x^24 + 38*x^23 + 14*x^22 + 22*x^21 + 26*x^20 + 22*x^18 + 7*x^17 + 29*x^16 + 53*x^15 + 50*x^14 + 49*x^13 + 21*x^12 + 47*x^11 + 50*x^10 + 32*x^9 + 14*x^8 + 50*x^7 + 18*x^6 + 9*x^5 + 61*x^4 + 10*x^3 + 9*x^2 + 11*x + 47
# 加密消息
encrypted_message = 31*x^48 - 14*x^47 + x^46 + 8*x^45 - 9*x^44 - 18*x^43 - 30*x^41 + 14*x^40 + 3*x^39 - 17*x^38 + 22*x^37 + 7*x^36 + 31*x^34 - 30*x^33 - 22*x^32 - 25*x^31 + 31*x^30 - 28*x^29 + 7*x^28 + 23*x^27 - 6*x^26 + 12*x^25 - 6*x^24 + 5*x^23 - 13*x^22 - 10*x^20 + 4*x^19 + 15*x^18 + 23*x^17 + 24*x^16 - 2*x^15 - 8*x^14 - 20*x^13 + 24*x^12 - 23*x^11 - 4*x^10 - 26*x^9 - 14*x^8 + 10*x^7 + 4*x^6 - 4*x^5 - 32*x^4 - 5*x^3 - 31*x^2 + 16*x + 11
# 攻击并解密
recovered_keys = perform_ntru_attack(public_key)
decrypted_message = decrypt_ciphertext(encrypted_message, recovered_keys[0], recovered_keys[1])
print(decrypted_message)


因为是多项式，所以一些像求逆这种运算需要重新定义一下。

然后正常sm4解密就行

这里加密代码好像有点问题，在sm4_key = binascii.unhexlify(poly_terms)之前应该还要调用一下gen_key()才能用。

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
import binascii
import re
from binascii import unhexlify
from gmssl import sm4
from Cryptodome.Util.Padding import pad, unpad
def terms(poly_str):
    terms = []
    pattern = r'([+-]?\s*x\^?\d*|[-+]?\s*\d+)'
    matches = re.finditer(pattern, poly_str.replace(' ', ''))

    for match in matches:
        term = match.group()
        if term == '+x' or term == 'x':
            terms.append(1)
        elif term == '-x':
            terms.append(-1)
        elif 'x^' in term:
            coeff_part = term.split('x^')[0]
            exponent = int(term.split('x^')[1])
            if not coeff_part or coeff_part == '+':
                coeff = 1
            elif coeff_part == '-':
                coeff = -1
            else:
                coeff = int(coeff_part)
            terms.append(coeff * exponent)
        elif 'x' in term:
            coeff_part = term.split('x')[0]
            if not coeff_part or coeff_part == '+':
                terms.append(1)
            elif coeff_part == '-':
                terms.append(-1)
            else:
                terms.append(int(coeff_part))
        else:
            if term == '+1' or term == '1':
                terms.append(0)
                terms.append(-0)
    return terms
def read_polynomial_from_file(filename):
    with open(filename, 'r') as file:
        return file.read().strip()
def gen_key(poly_terms):
    binary = [0] * 128
    for term in poly_terms:
        exponent = abs(term)
        if term > 0 and exponent <= 127:
            binary[127 - exponent] = 1
    binary_str = ''.join(map(str, binary))
    hex_key = hex(int(binary_str, 2))[2:].upper().zfill(32)
    return hex_key


poly_str = read_polynomial_from_file("123.txt")
poly_terms = terms(poly_str)
print(poly_terms)
pol_terms=gen_key(poly_terms)
sm4_key = binascii.unhexlify(pol_terms)
print(sm4_key)
key=sm4_key.hex().upper()
print(key)



'000000000000000000002B15203C0208'

网站解一下

O0GcEs.png

最后转一下就行

1
2
3
4
5
print(bytes.fromhex("58594354467B43727970746F305F63616E5F6E30745F536F3176655F69747D01"))



b'XYCTF{Crypto0_can_n0t_So1ve_it}\x01'

5,Choice

给了三个py文件，首先看给出的random.py,其中定义了choice函数如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def _randbelow_with_getrandbits(self, n):
    "Return a random int in the range [0,n).  Defined for n > 0."

    getrandbits = self.getrandbits
    k = n.bit_length() - 1
    r = getrandbits(k)  # 0 <= r < 2**k
    while r >= n:
        r = getrandbits(k)
    return r

def choice(self, seq):
    """Choose a random element from a non-empty sequence."""

    # As an accommodation for NumPy, we don't use "if not seq"
    # because bool(numpy.array()) raises a ValueError.
    if not len(seq):
        raise IndexError('Cannot choose from an empty sequence')
    return seq[self._randbelow(len(seq))]

题目

1
2
3
4
5
6
7
8
9
10
11
from Crypto.Util.number import bytes_to_long
from random import Random
from secret import flag
 
assert flag.startswith(b'XYCTF{') and flag.endswith(b'}')
flag = flag[6:-1]
 
msg = bytes_to_long(flag)
rand = Random()
test = bytes([i for i in range(255, -1, -1)])
open('output.py', 'w').write(f'enc = {msg ^ rand.getrandbits(msg.bit_length())}\nr = {[rand.choice(test) for _ in range(2496)]}')

_randbelow 方法确保生成的随机数在 [0, len(test)) 范围内。由于 test 的长度是 256，_randbelow(256) 会生成一个 8 位的随机整数（因为 256 是 2^8），而且并不会进入while循环，因为 k = n.bit_length() - 1，r = getrandbits(k)所以r一定是小于len(test)的。

而题目给了我们2496*8=19968个bit，所以还是MT19937，直接板子打就行。还有一点要注意的是此时我们的随机数随机的是数的位置而不是数本身，所以需要提取题目给出数据的位置去打MT。这里我们用.index去提取

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
# sage 10.6
from Crypto.Util.number import *
from random import *
from tqdm import *


# 1, get data
x,c=[],[]
enc = 5042764371819053176884777909105310461303359296255297
test = [i for i in range(255, -1, -1)]
cc = [224, 55, 218, 253, 150, 84, 208, 134, 18, 177, 244, 54, 122, 193, 249, 5, 121, 80, 230, 21, 236, 33, 226, 3, 120, 141, 212, 33, 69, 195, 78, 112, 0, 62, 64, 197, 10, 224, 64, 191, 17, 112, 196, 143, 209, 92, 10, 198, 174, 181, 96, 118, 175, 145, 111, 41, 113, 206, 137, 37, 56, 227, 252, 84, 18, 145, 81, 124, 202, 14, 255, 144, 200, 13, 230, 218, 208, 210, 222, 101, 211, 114, 222, 12, 190, 226, 62, 118, 87, 152, 118, 245, 196, 4, 92, 251, 238, 142, 114, 13, 113, 247, 171, 8, 138, 20, 169, 192, 221, 223, 60, 56, 188, 70, 184, 202, 195, 246, 71, 235, 152, 255, 73, 128, 140, 159, 119, 79, 1, 223, 239, 242, 60, 228, 205, 90, 210, 5, 165, 35, 176, 75, 21, 182, 220, 212, 240, 212, 77, 124, 52, 140, 85, 200, 207, 31, 177, 82, 76, 152, 128, 124, 205, 216, 252, 34, 27, 198, 186, 61, 161, 192, 158, 226, 40, 127, 69, 162, 24, 46, 208, 183, 99, 165, 1, 221, 184, 40, 147, 136, 236, 245, 228, 197, 86, 15, 201, 95, 115, 18, 131, 79, 86, 12, 122, 63, 200, 192, 244, 205, 229, 36, 86, 217, 249, 170, 5, 134, 99, 33, 214, 10, 120, 105, 233, 115, 230, 114, 105, 84, 39, 167, 18, 10, 77, 236, 104, 225, 196, 181, 105, 180, 159, 24, 4, 147, 131, 143, 64, 201, 212, 175, 203, 200, 19, 99, 24, 112, 180, 75, 222, 204, 204, 13, 210, 165, 135, 175, 132, 205, 247, 28, 178, 76, 240, 196, 240, 121, 132, 21, 8, 45, 203, 143, 206, 6, 11, 51, 47, 87, 88, 35, 63, 168, 251, 11, 254, 11, 46, 72, 210, 230, 184, 114, 88, 194, 99, 229, 144, 1, 226, 44, 133, 10, 42, 234, 112, 100, 248, 247, 66, 221, 72, 229, 236, 4, 65, 203, 65, 61, 23, 181, 190, 87, 1, 76, 113, 48, 178, 42, 175, 49, 78, 159, 104, 229, 213, 223, 13, 249, 216, 60, 144, 203, 156, 23, 129, 148, 87, 37, 79, 227, 141, 202, 210, 245, 236, 121, 129, 78, 7, 121, 42, 82, 184, 222, 96, 100, 189, 62, 102, 176, 198, 1, 153, 242, 23, 191, 197, 176, 115, 206, 122, 50, 104, 70, 170, 29, 52, 189, 157, 99, 82, 187, 201, 78, 25, 75, 126, 118, 160, 250, 53, 112, 143, 161, 251, 221, 44, 255, 232, 115, 182, 77, 31, 217, 228, 97, 112, 236, 21, 160, 127, 9, 220, 22, 97, 159, 239, 25, 140, 206, 210, 148, 105, 184, 41, 56, 92, 141, 3, 200, 165, 14, 161, 219, 177, 40, 189, 75, 48, 146, 130, 151, 100, 144, 239, 22, 19, 246, 166, 231, 228, 68, 254, 16, 99, 95, 32, 177, 216, 170, 125, 211, 100, 142, 251, 16, 64, 83, 161, 184, 242, 248, 239, 141, 171, 135, 48, 20, 34, 250, 13, 70, 236, 172, 22, 241, 171, 25, 18, 204, 36, 248, 253, 203, 138, 10, 130, 249, 15, 157, 244, 154, 41, 4, 231, 64, 20, 212, 126, 160, 48, 154, 171, 250, 199, 113, 32, 186, 126, 217, 3, 236, 115, 37, 174, 75, 222, 125, 55, 86, 65, 96, 56, 254, 226, 213, 244, 36, 199, 164, 160, 126, 191, 29, 50, 135, 234, 165, 122, 132, 68, 133, 129, 0, 220, 72, 87, 172, 93, 15, 131, 37, 119, 240, 43, 239, 105, 45, 244, 6, 34, 111, 151, 144, 54, 46, 159, 6, 5, 160, 32, 4, 180, 246, 39, 220, 85, 209, 145, 41, 88, 137, 110, 101, 113, 115, 204, 11, 53, 152, 177, 240, 193, 220, 136, 84, 221, 12, 43, 74, 122, 251, 236, 53, 175, 36, 46, 246, 181, 137, 246, 53, 189, 171, 240, 104, 8, 126, 56, 122, 245, 155, 130, 31, 16, 20, 212, 147, 33, 165, 82, 117, 244, 167, 235, 115, 244, 94, 173, 195, 34, 36, 33, 218, 39, 13, 90, 196, 172, 207, 105, 73, 255, 187, 221, 162, 242, 186, 122, 140, 241, 120, 98, 44, 81, 172, 201, 150, 238, 111, 147, 24, 214, 192, 125, 102, 157, 53, 219, 172, 123, 218, 222, 71, 138, 117, 188, 32, 104, 10, 188, 118, 58, 254, 36, 104, 212, 76, 209, 15, 6, 33, 149, 15, 225, 76, 8, 157, 48, 70, 127, 19, 126, 77, 216, 133, 132, 30, 33, 113, 117, 134, 238, 57, 20, 121, 26, 184, 229, 202, 90, 28, 42, 230, 42, 159, 19, 191, 162, 205, 241, 67, 177, 216, 191, 164, 146, 90, 228, 232, 149, 163, 135, 130, 193, 196, 178, 215, 216, 155, 238, 20, 36, 196, 153, 207, 177, 149, 40, 172, 139, 12, 134, 142, 154, 225, 179, 95, 248, 190, 8, 154, 246, 229, 102, 121, 197, 116, 135, 163, 128, 109, 112, 114, 143, 164, 134, 233, 45, 244, 22, 141, 211, 214, 122, 14, 93, 49, 251, 85, 95, 95, 191, 210, 245, 181, 142, 125, 110, 33, 195, 150, 197, 173, 86, 50, 127, 187, 129, 67, 119, 58, 134, 119, 36, 151, 136, 122, 157, 22, 171, 195, 48, 178, 232, 228, 177, 6, 124, 50, 163, 161, 32, 49, 197, 157, 188, 86, 208, 226, 208, 63, 173, 21, 192, 148, 194, 208, 251, 95, 117, 34, 116, 217, 130, 150, 97, 206, 101, 201, 88, 137, 163, 90, 104, 129, 4, 191, 99, 50, 115, 8, 145, 116, 250, 180, 193, 229, 128, 92, 55, 26, 6, 154, 68, 0, 66, 77, 126, 192, 170, 218, 252, 127, 192, 29, 107, 152, 231, 190, 202, 130, 116, 229, 193, 63, 13, 48, 220, 238, 126, 74, 232, 19, 242, 71, 159, 9, 196, 187, 111, 243, 81, 244, 193, 95, 166, 85, 22, 240, 32, 1, 114, 11, 64, 114, 149, 217, 207, 194, 1, 33, 245, 14, 101, 119, 32, 233, 214, 139, 71, 103, 125, 54, 17, 86, 140, 132, 221, 45, 227, 136, 203, 156, 223, 73, 43, 82, 190, 119, 22, 14, 115, 0, 192, 105, 147, 210, 146, 47, 89, 210, 18, 225, 126, 210, 240, 55, 219, 247, 106, 190, 50, 35, 13, 255, 236, 253, 82, 244, 117, 139, 1, 72, 182, 19, 170, 173, 59, 175, 10, 95, 66, 253, 178, 139, 45, 5, 24, 59, 9, 222, 58, 46, 79, 48, 39, 175, 196, 249, 249, 70, 126, 118, 69, 165, 155, 119, 67, 221, 20, 133, 16, 99, 41, 132, 11, 12, 35, 70, 87, 43, 197, 103, 33, 201, 3, 195, 142, 128, 135, 121, 26, 185, 2, 73, 235, 70, 219, 49, 227, 133, 241, 34, 6, 9, 109, 66, 50, 177, 114, 119, 101, 91, 144, 41, 246, 40, 81, 113, 203, 226, 87, 8, 0, 73, 212, 5, 95, 112, 230, 4, 28, 206, 93, 252, 30, 195, 197, 226, 165, 120, 3, 124, 169, 66, 227, 113, 55, 101, 135, 141, 71, 84, 202, 19, 145, 25, 92, 50, 80, 53, 63, 85, 184, 196, 93, 254, 47, 252, 182, 150, 115, 20, 181, 178, 87, 162, 50, 190, 228, 125, 240, 134, 10, 142, 173, 206, 250, 49, 186, 201, 118, 146, 246, 244, 199, 9, 55, 253, 123, 103, 200, 206, 79, 168, 216, 99, 192, 191, 236, 214, 248, 111, 115, 74, 155, 165, 150, 40, 86, 224, 240, 133, 69, 34, 52, 13, 63, 61, 116, 182, 144, 177, 101, 164, 77, 217, 65, 218, 150, 142, 249, 165, 160, 220, 120, 25, 36, 157, 134, 223, 11, 46, 121, 75, 182, 126, 104, 91, 204, 45, 49, 175, 10, 48, 83, 150, 96, 244, 10, 149, 76, 124, 189, 149, 200, 252, 175, 124, 146, 126, 230, 70, 194, 243, 63, 204, 224, 115, 140, 115, 110, 86, 22, 193, 5, 11, 18, 177, 159, 94, 160, 38, 188, 139, 89, 1, 200, 163, 138, 8, 140, 169, 54, 29, 225, 22, 5, 99, 144, 247, 239, 106, 77, 29, 141, 206, 89, 236, 4, 32, 104, 115, 206, 204, 15, 100, 66, 199, 15, 89, 24, 246, 99, 224, 207, 7, 205, 142, 203, 28, 87, 16, 110, 93, 72, 73, 206, 48, 59, 170, 152, 224, 2, 74, 9, 125, 140, 82, 206, 159, 0, 117, 237, 252, 47, 200, 75, 133, 68, 239, 109, 169, 25, 168, 202, 240, 5, 67, 125, 173, 233, 6, 148, 38, 182, 13, 141, 149, 39, 119, 189, 122, 49, 173, 153, 78, 103, 211, 65, 224, 52, 10, 35, 233, 88, 66, 43, 120, 255, 71, 169, 215, 250, 218, 205, 163, 164, 226, 46, 178, 25, 88, 59, 98, 199, 167, 134, 244, 167, 210, 20, 246, 159, 163, 252, 114, 5, 168, 52, 47, 177, 159, 255, 236, 166, 49, 36, 61, 10, 130, 135, 220, 101, 202, 69, 150, 100, 217, 98, 203, 217, 166, 33, 169, 203, 230, 194, 224, 15, 249, 205, 52, 41, 124, 191, 223, 148, 251, 147, 133, 85, 149, 214, 198, 5, 134, 91, 201, 191, 204, 152, 240, 37, 34, 236, 211, 182, 142, 207, 1, 188, 67, 87, 222, 220, 7, 78, 49, 129, 236, 98, 120, 217, 204, 77, 106, 89, 250, 182, 15, 18, 27, 143, 13, 27, 61, 223, 213, 196, 190, 24, 35, 104, 100, 220, 60, 194, 174, 169, 20, 167, 75, 162, 26, 253, 213, 59, 219, 187, 253, 160, 249, 61, 122, 113, 223, 55, 57, 198, 53, 138, 94, 154, 18, 132, 233, 183, 71, 7, 22, 50, 196, 181, 202, 103, 86, 31, 119, 83, 130, 165, 242, 170, 31, 35, 175, 117, 95, 89, 247, 221, 186, 47, 236, 241, 77, 194, 111, 148, 45, 101, 88, 41, 0, 33, 139, 15, 127, 156, 72, 234, 217, 170, 218, 216, 31, 4, 73, 150, 78, 49, 178, 13, 178, 46, 102, 93, 184, 110, 205, 132, 190, 43, 87, 194, 35, 188, 166, 9, 97, 184, 202, 113, 45, 150, 62, 106, 108, 19, 162, 85, 212, 188, 131, 38, 67, 23, 136, 208, 87, 63, 69, 6, 209, 242, 45, 13, 228, 14, 233, 8, 71, 43, 51, 89, 46, 195, 101, 132, 254, 154, 183, 220, 115, 221, 255, 174, 150, 65, 141, 176, 57, 144, 16, 115, 252, 144, 139, 52, 205, 224, 75, 190, 192, 2, 231, 30, 238, 149, 22, 200, 137, 244, 239, 185, 212, 145, 230, 200, 8, 249, 109, 26, 226, 195, 133, 140, 103, 50, 230, 180, 47, 196, 226, 105, 13, 239, 135, 20, 214, 152, 211, 208, 81, 213, 48, 187, 232, 77, 139, 16, 79, 204, 216, 56, 41, 41, 58, 192, 245, 1, 104, 85, 42, 107, 94, 142, 12, 247, 90, 254, 116, 72, 193, 219, 54, 247, 5, 28, 60, 140, 10, 185, 86, 148, 101, 198, 96, 181, 245, 61, 25, 186, 29, 57, 176, 188, 9, 239, 93, 198, 110, 248, 23, 87, 193, 161, 107, 40, 38, 186, 205, 148, 197, 127, 144, 69, 19, 47, 132, 82, 23, 170, 83, 224, 235, 49, 190, 44, 145, 65, 66, 141, 78, 1, 254, 24, 157, 7, 23, 227, 28, 81, 176, 22, 92, 139, 188, 48, 183, 229, 139, 205, 174, 131, 189, 241, 21, 146, 204, 58, 249, 167, 217, 174, 43, 41, 56, 181, 212, 42, 188, 6, 117, 93, 178, 160, 129, 15, 76, 150, 207, 245, 227, 247, 130, 171, 114, 204, 101, 176, 55, 43, 138, 149, 90, 124, 45, 96, 181, 221, 16, 121, 210, 51, 210, 164, 68, 64, 154, 167, 91, 69, 35, 153, 212, 10, 125, 235, 203, 166, 145, 9, 174, 86, 65, 70, 112, 194, 140, 92, 170, 49, 191, 157, 218, 199, 152, 151, 247, 208, 182, 209, 34, 245, 5, 173, 105, 175, 159, 71, 251, 198, 246, 214, 99, 58, 70, 154, 52, 39, 88, 149, 179, 202, 86, 240, 108, 200, 83, 250, 62, 213, 113, 138, 73, 106, 141, 192, 204, 90, 251, 208, 28, 124, 30, 134, 119, 144, 68, 23, 204, 181, 186, 76, 156, 71, 8, 104, 186, 87, 221, 134, 122, 72, 244, 203, 121, 181, 65, 90, 185, 131, 230, 133, 54, 158, 186, 168, 201, 178, 155, 172, 164, 22, 130, 111, 90, 209, 2, 167, 23, 176, 63, 139, 89, 63, 15, 238, 110, 204, 85, 36, 127, 68, 240, 177, 31, 2, 81, 147, 205, 192, 214, 173, 103, 130, 10, 100, 232, 125, 216, 163, 209, 171, 168, 243, 145, 6, 170, 41, 142, 250, 145, 57, 139, 224, 221, 189, 48, 141, 232, 146, 92, 216, 154, 126, 223, 8, 90, 82, 138, 221, 240, 223, 87, 209, 165, 17, 52, 154, 91, 12, 121, 212, 238, 46, 215, 217, 147, 136, 139, 251, 91, 39, 188, 244, 251, 52, 110, 22, 126, 200, 231, 153, 103, 203, 120, 219, 118, 172, 53, 141, 203, 75, 163, 150, 194, 27, 208, 9, 186, 6, 85, 46, 243, 135, 66, 40, 79, 206, 250, 20, 85, 123, 35, 164, 44, 85, 104, 66, 51, 177, 125, 189, 165, 226, 13, 75, 78, 225, 252, 226, 138, 81, 171, 172, 175, 122, 145, 68, 254, 37, 153, 39, 113, 237, 232, 220, 80, 193, 181, 21, 197, 186, 56, 202, 239, 213, 135, 41, 6, 85, 54, 135, 214, 95, 102, 23, 192, 153, 235, 110, 26, 14, 84, 220, 142, 236, 192, 8, 117, 205, 249, 92, 148, 149, 77, 235, 205, 232, 21, 48, 14, 84, 187, 124, 218, 166, 155, 183, 62, 10, 123, 53, 63, 79, 101, 193, 3, 61, 29, 39, 99, 22, 197, 75, 10, 165, 44, 215, 210, 181, 74, 235, 200, 247, 158, 187, 200, 102, 22, 150, 73, 42, 131, 28, 17, 180, 133, 205, 23, 228, 226, 219, 175, 207, 81, 53, 141, 114, 140, 59, 218, 169, 7, 219, 139, 75, 210, 97, 236, 157, 21, 109, 195, 128, 54, 5, 55, 217, 127, 49, 62, 59, 101, 95, 86, 255, 22, 186, 94, 151, 114, 93, 19, 198, 159, 174, 142, 132, 195, 157, 206, 161, 107, 255, 106, 196, 250, 191, 86, 221, 196, 36, 29, 37, 50, 224, 42, 20, 89, 212, 252, 191, 157, 237, 10, 157, 80, 42, 234, 180, 1, 183, 186, 239, 129, 14, 125, 114, 66, 203, 120, 114, 37, 214, 37, 73, 153, 182, 165, 87, 177, 75, 220, 210, 105, 154, 149, 114, 13, 202, 128, 55, 128, 96, 158, 150, 57, 86, 106, 127, 160, 57, 80, 255, 107, 241, 95, 121, 14, 110, 160, 119, 211, 150, 156, 185, 158, 221, 110, 76, 255, 119, 15, 245, 1, 238, 139, 100, 250, 220, 147, 193, 51, 144, 123, 139, 13, 26, 158, 95, 148, 251, 82, 227, 119, 92, 132, 219, 248, 239, 217, 101, 88, 121, 10, 148, 203, 156, 156]
c = [test.index(k) for k in cc]

# 2, recover MT and get random bytes of (f_inf, f_len)
RNG = Random()
length = 19968
def construct_a_row(RNG):
    # 这里是关键, 一定要跟你已知数据的生成方式一致
    row = []
    RNG.getrandbits(171)
    for i in range(2496):
        row+=list(map(int, (bin(RNG.getrandbits(8))[2:].zfill(8))))
    return row

L = []
for i in trange(length):
    state = [0]*624
    temp = "0"*i + "1"*1 + "0"*(length-1-i)
    for j in range(624):
        state[j] = int(temp[32*j:32*j+32],2)
    RNG.setstate((3,tuple(state+[624]),None))
    L.append(construct_a_row(RNG))
L = Matrix(GF(2),L)

known = []
for i in tqdm(c):
    known+=list(map(int, (bin(i)[2:].zfill(8))))
print("solve_left")
s = L.solve_left(vector(GF(2),known))
print("ok")
init = "".join(list(map(str,s)))
print("init")
state = []
for i in range(624):
    state.append(int(init[32*i:32*i+32],2))
print("state")

prng = Random()
prng.setstate(tuple([3, tuple(state+[624]), None]))
print(long_to_bytes(enc^^prng.getrandbits(172)))



b'___0h_51mple_r@nd0m___'

又因为enc.bit_length()是172，所以明文的长度应该也是172附近，都试试就行了。

也可以用gf2bv这个库打(不过要加一个[mt[0] ^ 0x80000000])，加了之后需要的数据个数会少一点。此时我们用ans.append(255-r[i])还原位置。

refer:[XYCTF2025 wp&复现 | Lst4r’s Blog](https://lst4r-max.github.io/2025/04/08/XYCTF2025 wp&复现/)

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
from gf2bv import LinearSystem
from gf2bv.crypto.mt import MT19937
from tqdm import *
import random
from Crypto.Util.number import *
enc = 5042764371819053176884777909105310461303359296255297
r = [224, 55, 218, 253, 150, 84, 208, 134, 18, 177, 244, 54, 122, 193, 249, 5, 121, 80, 230, 21, 236, 33, 226, 3, 120, 141, 212, 33, 69, 195, 78, 112, 0, 62, 64, 197, 10, 224, 64, 191, 17, 112, 196, 143, 209, 92, 10, 198, 174, 181, 96, 118, 175, 145, 111, 41, 113, 206, 137, 37, 56, 227, 252, 84, 18, 145, 81, 124, 202, 14, 255, 144, 200, 13, 230, 218, 208, 210, 222, 101, 211, 114, 222, 12, 190, 226, 62, 118, 87, 152, 118, 245, 196, 4, 92, 251, 238, 142, 114, 13, 113, 247, 171, 8, 138, 20, 169, 192, 221, 223, 60, 56, 188, 70, 184, 202, 195, 246, 71, 235, 152, 255, 73, 128, 140, 159, 119, 79, 1, 223, 239, 242, 60, 228, 205, 90, 210, 5, 165, 35, 176, 75, 21, 182, 220, 212, 240, 212, 77, 124, 52, 140, 85, 200, 207, 31, 177, 82, 76, 152, 128, 124, 205, 216, 252, 34, 27, 198, 186, 61, 161, 192, 158, 226, 40, 127, 69, 162, 24, 46, 208, 183, 99, 165, 1, 221, 184, 40, 147, 136, 236, 245, 228, 197, 86, 15, 201, 95, 115, 18, 131, 79, 86, 12, 122, 63, 200, 192, 244, 205, 229, 36, 86, 217, 249, 170, 5, 134, 99, 33, 214, 10, 120, 105, 233, 115, 230, 114, 105, 84, 39, 167, 18, 10, 77, 236, 104, 225, 196, 181, 105, 180, 159, 24, 4, 147, 131, 143, 64, 201, 212, 175, 203, 200, 19, 99, 24, 112, 180, 75, 222, 204, 204, 13, 210, 165, 135, 175, 132, 205, 247, 28, 178, 76, 240, 196, 240, 121, 132, 21, 8, 45, 203, 143, 206, 6, 11, 51, 47, 87, 88, 35, 63, 168, 251, 11, 254, 11, 46, 72, 210, 230, 184, 114, 88, 194, 99, 229, 144, 1, 226, 44, 133, 10, 42, 234, 112, 100, 248, 247, 66, 221, 72, 229, 236, 4, 65, 203, 65, 61, 23, 181, 190, 87, 1, 76, 113, 48, 178, 42, 175, 49, 78, 159, 104, 229, 213, 223, 13, 249, 216, 60, 144, 203, 156, 23, 129, 148, 87, 37, 79, 227, 141, 202, 210, 245, 236, 121, 129, 78, 7, 121, 42, 82, 184, 222, 96, 100, 189, 62, 102, 176, 198, 1, 153, 242, 23, 191, 197, 176, 115, 206, 122, 50, 104, 70, 170, 29, 52, 189, 157, 99, 82, 187, 201, 78, 25, 75, 126, 118, 160, 250, 53, 112, 143, 161, 251, 221, 44, 255, 232, 115, 182, 77, 31, 217, 228, 97, 112, 236, 21, 160, 127, 9, 220, 22, 97, 159, 239, 25, 140, 206, 210, 148, 105, 184, 41, 56, 92, 141, 3, 200, 165, 14, 161, 219, 177, 40, 189, 75, 48, 146, 130, 151, 100, 144, 239, 22, 19, 246, 166, 231, 228, 68, 254, 16, 99, 95, 32, 177, 216, 170, 125, 211, 100, 142, 251, 16, 64, 83, 161, 184, 242, 248, 239, 141, 171, 135, 48, 20, 34, 250, 13, 70, 236, 172, 22, 241, 171, 25, 18, 204, 36, 248, 253, 203, 138, 10, 130, 249, 15, 157, 244, 154, 41, 4, 231, 64, 20, 212, 126, 160, 48, 154, 171, 250, 199, 113, 32, 186, 126, 217, 3, 236, 115, 37, 174, 75, 222, 125, 55, 86, 65, 96, 56, 254, 226, 213, 244, 36, 199, 164, 160, 126, 191, 29, 50, 135, 234, 165, 122, 132, 68, 133, 129, 0, 220, 72, 87, 172, 93, 15, 131, 37, 119, 240, 43, 239, 105, 45, 244, 6, 34, 111, 151, 144, 54, 46, 159, 6, 5, 160, 32, 4, 180, 246, 39, 220, 85, 209, 145, 41, 88, 137, 110, 101, 113, 115, 204, 11, 53, 152, 177, 240, 193, 220, 136, 84, 221, 12, 43, 74, 122, 251, 236, 53, 175, 36, 46, 246, 181, 137, 246, 53, 189, 171, 240, 104, 8, 126, 56, 122, 245, 155, 130, 31, 16, 20, 212, 147, 33, 165, 82, 117, 244, 167, 235, 115, 244, 94, 173, 195, 34, 36, 33, 218, 39, 13, 90, 196, 172, 207, 105, 73, 255, 187, 221, 162, 242, 186, 122, 140, 241, 120, 98, 44, 81, 172, 201, 150, 238, 111, 147, 24, 214, 192, 125, 102, 157, 53, 219, 172, 123, 218, 222, 71, 138, 117, 188, 32, 104, 10, 188, 118, 58, 254, 36, 104, 212, 76, 209, 15, 6, 33, 149, 15, 225, 76, 8, 157, 48, 70, 127, 19, 126, 77, 216, 133, 132, 30, 33, 113, 117, 134, 238, 57, 20, 121, 26, 184, 229, 202, 90, 28, 42, 230, 42, 159, 19, 191, 162, 205, 241, 67, 177, 216, 191, 164, 146, 90, 228, 232, 149, 163, 135, 130, 193, 196, 178, 215, 216, 155, 238, 20, 36, 196, 153, 207, 177, 149, 40, 172, 139, 12, 134, 142, 154, 225, 179, 95, 248, 190, 8, 154, 246, 229, 102, 121, 197, 116, 135, 163, 128, 109, 112, 114, 143, 164, 134, 233, 45, 244, 22, 141, 211, 214, 122, 14, 93, 49, 251, 85, 95, 95, 191, 210, 245, 181, 142, 125, 110, 33, 195, 150, 197, 173, 86, 50, 127, 187, 129, 67, 119, 58, 134, 119, 36, 151, 136, 122, 157, 22, 171, 195, 48, 178, 232, 228, 177, 6, 124, 50, 163, 161, 32, 49, 197, 157, 188, 86, 208, 226, 208, 63, 173, 21, 192, 148, 194, 208, 251, 95, 117, 34, 116, 217, 130, 150, 97, 206, 101, 201, 88, 137, 163, 90, 104, 129, 4, 191, 99, 50, 115, 8, 145, 116, 250, 180, 193, 229, 128, 92, 55, 26, 6, 154, 68, 0, 66, 77, 126, 192, 170, 218, 252, 127, 192, 29, 107, 152, 231, 190, 202, 130, 116, 229, 193, 63, 13, 48, 220, 238, 126, 74, 232, 19, 242, 71, 159, 9, 196, 187, 111, 243, 81, 244, 193, 95, 166, 85, 22, 240, 32, 1, 114, 11, 64, 114, 149, 217, 207, 194, 1, 33, 245, 14, 101, 119, 32, 233, 214, 139, 71, 103, 125, 54, 17, 86, 140, 132, 221, 45, 227, 136, 203, 156, 223, 73, 43, 82, 190, 119, 22, 14, 115, 0, 192, 105, 147, 210, 146, 47, 89, 210, 18, 225, 126, 210, 240, 55, 219, 247, 106, 190, 50, 35, 13, 255, 236, 253, 82, 244, 117, 139, 1, 72, 182, 19, 170, 173, 59, 175, 10, 95, 66, 253, 178, 139, 45, 5, 24, 59, 9, 222, 58, 46, 79, 48, 39, 175, 196, 249, 249, 70, 126, 118, 69, 165, 155, 119, 67, 221, 20, 133, 16, 99, 41, 132, 11, 12, 35, 70, 87, 43, 197, 103, 33, 201, 3, 195, 142, 128, 135, 121, 26, 185, 2, 73, 235, 70, 219, 49, 227, 133, 241, 34, 6, 9, 109, 66, 50, 177, 114, 119, 101, 91, 144, 41, 246, 40, 81, 113, 203, 226, 87, 8, 0, 73, 212, 5, 95, 112, 230, 4, 28, 206, 93, 252, 30, 195, 197, 226, 165, 120, 3, 124, 169, 66, 227, 113, 55, 101, 135, 141, 71, 84, 202, 19, 145, 25, 92, 50, 80, 53, 63, 85, 184, 196, 93, 254, 47, 252, 182, 150, 115, 20, 181, 178, 87, 162, 50, 190, 228, 125, 240, 134, 10, 142, 173, 206, 250, 49, 186, 201, 118, 146, 246, 244, 199, 9, 55, 253, 123, 103, 200, 206, 79, 168, 216, 99, 192, 191, 236, 214, 248, 111, 115, 74, 155, 165, 150, 40, 86, 224, 240, 133, 69, 34, 52, 13, 63, 61, 116, 182, 144, 177, 101, 164, 77, 217, 65, 218, 150, 142, 249, 165, 160, 220, 120, 25, 36, 157, 134, 223, 11, 46, 121, 75, 182, 126, 104, 91, 204, 45, 49, 175, 10, 48, 83, 150, 96, 244, 10, 149, 76, 124, 189, 149, 200, 252, 175, 124, 146, 126, 230, 70, 194, 243, 63, 204, 224, 115, 140, 115, 110, 86, 22, 193, 5, 11, 18, 177, 159, 94, 160, 38, 188, 139, 89, 1, 200, 163, 138, 8, 140, 169, 54, 29, 225, 22, 5, 99, 144, 247, 239, 106, 77, 29, 141, 206, 89, 236, 4, 32, 104, 115, 206, 204, 15, 100, 66, 199, 15, 89, 24, 246, 99, 224, 207, 7, 205, 142, 203, 28, 87, 16, 110, 93, 72, 73, 206, 48, 59, 170, 152, 224, 2, 74, 9, 125, 140, 82, 206, 159, 0, 117, 237, 252, 47, 200, 75, 133, 68, 239, 109, 169, 25, 168, 202, 240, 5, 67, 125, 173, 233, 6, 148, 38, 182, 13, 141, 149, 39, 119, 189, 122, 49, 173, 153, 78, 103, 211, 65, 224, 52, 10, 35, 233, 88, 66, 43, 120, 255, 71, 169, 215, 250, 218, 205, 163, 164, 226, 46, 178, 25, 88, 59, 98, 199, 167, 134, 244, 167, 210, 20, 246, 159, 163, 252, 114, 5, 168, 52, 47, 177, 159, 255, 236, 166, 49, 36, 61, 10, 130, 135, 220, 101, 202, 69, 150, 100, 217, 98, 203, 217, 166, 33, 169, 203, 230, 194, 224, 15, 249, 205, 52, 41, 124, 191, 223, 148, 251, 147, 133, 85, 149, 214, 198, 5, 134, 91, 201, 191, 204, 152, 240, 37, 34, 236, 211, 182, 142, 207, 1, 188, 67, 87, 222, 220, 7, 78, 49, 129, 236, 98, 120, 217, 204, 77, 106, 89, 250, 182, 15, 18, 27, 143, 13, 27, 61, 223, 213, 196, 190, 24, 35, 104, 100, 220, 60, 194, 174, 169, 20, 167, 75, 162, 26, 253, 213, 59, 219, 187, 253, 160, 249, 61, 122, 113, 223, 55, 57, 198, 53, 138, 94, 154, 18, 132, 233, 183, 71, 7, 22, 50, 196, 181, 202, 103, 86, 31, 119, 83, 130, 165, 242, 170, 31, 35, 175, 117, 95, 89, 247, 221, 186, 47, 236, 241, 77, 194, 111, 148, 45, 101, 88, 41, 0, 33, 139, 15, 127, 156, 72, 234, 217, 170, 218, 216, 31, 4, 73, 150, 78, 49, 178, 13, 178, 46, 102, 93, 184, 110, 205, 132, 190, 43, 87, 194, 35, 188, 166, 9, 97, 184, 202, 113, 45, 150, 62, 106, 108, 19, 162, 85, 212, 188, 131, 38, 67, 23, 136, 208, 87, 63, 69, 6, 209, 242, 45, 13, 228, 14, 233, 8, 71, 43, 51, 89, 46, 195, 101, 132, 254, 154, 183, 220, 115, 221, 255, 174, 150, 65, 141, 176, 57, 144, 16, 115, 252, 144, 139, 52, 205, 224, 75, 190, 192, 2, 231, 30, 238, 149, 22, 200, 137, 244, 239, 185, 212, 145, 230, 200, 8, 249, 109, 26, 226, 195, 133, 140, 103, 50, 230, 180, 47, 196, 226, 105, 13, 239, 135, 20, 214, 152, 211, 208, 81, 213, 48, 187, 232, 77, 139, 16, 79, 204, 216, 56, 41, 41, 58, 192, 245, 1, 104, 85, 42, 107, 94, 142, 12, 247, 90, 254, 116, 72, 193, 219, 54, 247, 5, 28, 60, 140, 10, 185, 86, 148, 101, 198, 96, 181, 245, 61, 25, 186, 29, 57, 176, 188, 9, 239, 93, 198, 110, 248, 23, 87, 193, 161, 107, 40, 38, 186, 205, 148, 197, 127, 144, 69, 19, 47, 132, 82, 23, 170, 83, 224, 235, 49, 190, 44, 145, 65, 66, 141, 78, 1, 254, 24, 157, 7, 23, 227, 28, 81, 176, 22, 92, 139, 188, 48, 183, 229, 139, 205, 174, 131, 189, 241, 21, 146, 204, 58, 249, 167, 217, 174, 43, 41, 56, 181, 212, 42, 188, 6, 117, 93, 178, 160, 129, 15, 76, 150, 207, 245, 227, 247, 130, 171, 114, 204, 101, 176, 55, 43, 138, 149, 90, 124, 45, 96, 181, 221, 16, 121, 210, 51, 210, 164, 68, 64, 154, 167, 91, 69, 35, 153, 212, 10, 125, 235, 203, 166, 145, 9, 174, 86, 65, 70, 112, 194, 140, 92, 170, 49, 191, 157, 218, 199, 152, 151, 247, 208, 182, 209, 34, 245, 5, 173, 105, 175, 159, 71, 251, 198, 246, 214, 99, 58, 70, 154, 52, 39, 88, 149, 179, 202, 86, 240, 108, 200, 83, 250, 62, 213, 113, 138, 73, 106, 141, 192, 204, 90, 251, 208, 28, 124, 30, 134, 119, 144, 68, 23, 204, 181, 186, 76, 156, 71, 8, 104, 186, 87, 221, 134, 122, 72, 244, 203, 121, 181, 65, 90, 185, 131, 230, 133, 54, 158, 186, 168, 201, 178, 155, 172, 164, 22, 130, 111, 90, 209, 2, 167, 23, 176, 63, 139, 89, 63, 15, 238, 110, 204, 85, 36, 127, 68, 240, 177, 31, 2, 81, 147, 205, 192, 214, 173, 103, 130, 10, 100, 232, 125, 216, 163, 209, 171, 168, 243, 145, 6, 170, 41, 142, 250, 145, 57, 139, 224, 221, 189, 48, 141, 232, 146, 92, 216, 154, 126, 223, 8, 90, 82, 138, 221, 240, 223, 87, 209, 165, 17, 52, 154, 91, 12, 121, 212, 238, 46, 215, 217, 147, 136, 139, 251, 91, 39, 188, 244, 251, 52, 110, 22, 126, 200, 231, 153, 103, 203, 120, 219, 118, 172, 53, 141, 203, 75, 163, 150, 194, 27, 208, 9, 186, 6, 85, 46, 243, 135, 66, 40, 79, 206, 250, 20, 85, 123, 35, 164, 44, 85, 104, 66, 51, 177, 125, 189, 165, 226, 13, 75, 78, 225, 252, 226, 138, 81, 171, 172, 175, 122, 145, 68, 254, 37, 153, 39, 113, 237, 232, 220, 80, 193, 181, 21, 197, 186, 56, 202, 239, 213, 135, 41, 6, 85, 54, 135, 214, 95, 102, 23, 192, 153, 235, 110, 26, 14, 84, 220, 142, 236, 192, 8, 117, 205, 249, 92, 148, 149, 77, 235, 205, 232, 21, 48, 14, 84, 187, 124, 218, 166, 155, 183, 62, 10, 123, 53, 63, 79, 101, 193, 3, 61, 29, 39, 99, 22, 197, 75, 10, 165, 44, 215, 210, 181, 74, 235, 200, 247, 158, 187, 200, 102, 22, 150, 73, 42, 131, 28, 17, 180, 133, 205, 23, 228, 226, 219, 175, 207, 81, 53, 141, 114, 140, 59, 218, 169, 7, 219, 139, 75, 210, 97, 236, 157, 21, 109, 195, 128, 54, 5, 55, 217, 127, 49, 62, 59, 101, 95, 86, 255, 22, 186, 94, 151, 114, 93, 19, 198, 159, 174, 142, 132, 195, 157, 206, 161, 107, 255, 106, 196, 250, 191, 86, 221, 196, 36, 29, 37, 50, 224, 42, 20, 89, 212, 252, 191, 157, 237, 10, 157, 80, 42, 234, 180, 1, 183, 186, 239, 129, 14, 125, 114, 66, 203, 120, 114, 37, 214, 37, 73, 153, 182, 165, 87, 177, 75, 220, 210, 105, 154, 149, 114, 13, 202, 128, 55, 128, 96, 158, 150, 57, 86, 106, 127, 160, 57, 80, 255, 107, 241, 95, 121, 14, 110, 160, 119, 211, 150, 156, 185, 158, 221, 110, 76, 255, 119, 15, 245, 1, 238, 139, 100, 250, 220, 147, 193, 51, 144, 123, 139, 13, 26, 158, 95, 148, 251, 82, 227, 119, 92, 132, 219, 248, 239, 217, 101, 88, 121, 10, 148, 203, 156, 156]
def mt19937(bs, out):

    lin = LinearSystem([32] * 624)
    mt = lin.gens()

    rng = MT19937(mt)
    rng.getrandbits(175)
    zeros = [rng.getrandbits(bs) ^ o for o in out] + [mt[0] ^ 0x80000000]
    print("solving...")
    
    sol = lin.solve_one(zeros)

    rng = MT19937(sol)
    pyrand = rng.to_python_random()
    print("solved")
    print(long_to_bytes(pyrand.getrandbits(175)^enc))
test = bytes([i for i in range(255, -1, -1)])

ans=[]
for i in trange(len(r)):
    ans.append(255-r[i])
out=[]
assert len(ans)==624*4
print(type(ans[0]))  
for i in range(624*4):
    out.append(random.getrandbits(8))
print(type(out[0]))
mt19937(8,ans)

6,prng_xxxx

咕咕