2025miniLCTF

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

owo

题目质量感觉还蛮高。学到了一些东西。只是可惜知道的时候已经快结束了，没啥时间打。现在来复现一下

1，babaisiginsigin

z3一把梭XD，顺便学了一下z3的使用，之前没咋用过。

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
import random
import socket
import threading
import os

def calculate_level1(m, x, y):
    return (m | x) + (m | y)

def calculate_level2(m, x, y):
    return (m | x) + (m ^ y)

def level(conn, calculate, x, y, guess, description, test_times):
    for _ in range(test_times):
        conn.sendall(b"Enter your number: ")
        
        # 设置 5 秒超时
        conn.settimeout(5)
        
        try:
            data = conn.recv(1024)
            if not data:
                return False
            try:
                test = int(data.strip())
            except:
                conn.sendall(b"Invalid input. Bye.\n")
                return False
            result = calculate(test, x, y)
            conn.sendall(f"Calculation result: {result}\n".encode())
        except socket.timeout:
            conn.sendall(b"Time out! Respond in 5 seconds.\n")
            return False

    conn.sendall(f"\nNow, guess the result of {description} for m = {guess}:\n".encode())
    
    # 设置 5 秒超时
    conn.settimeout(5)
    
    try:
        data = conn.recv(1024)
        if not data:
            return False
        try:
            user_guess = int(data.strip())
        except:
            conn.sendall(b"Invalid input. Bye.\n")
            return False

        correct_result = calculate(guess, x, y)
        if user_guess == correct_result:
            conn.sendall(b"Correct! Proceeding to next level...\n\n")
            return True
        else:
            conn.sendall(b"Wrong guess! Exiting...\n")
            return False
    except socket.timeout:
        conn.sendall(b"Time out! You took too long to respond.\n")
        return False

def handle_client(conn, addr, flag):
    conn.sendall(b"Welcome to Puzzle!\n\n")
    try:
        # Level 1
        x = random.getrandbits(30)
        y = random.getrandbits(30)
        guess = random.getrandbits(30)
        conn.sendall(b"Level 1:\n")
        if not level(conn, calculate_level1, x, y, guess, "(m | x) + (m | y)", test_times=2):
            conn.close()
            return

        # Level 2
        x = random.getrandbits(30)
        y = random.getrandbits(30)
        guess = random.getrandbits(30)
        conn.sendall(b"Level 2:\n")
        if not level(conn, calculate_level2, x, y, guess, "(m | x) + (m ^ y)", test_times=2):
            conn.close()
            return

        # 通关，发flag
        conn.sendall(f"Congratulations! You've passed all levels!\nHere is your flag: {flag}\n".encode())
    except Exception as e:
        conn.sendall(b"An error occurred. Bye.\n")
    finally:
        conn.close()

def main():
    host = "0.0.0.0"
    port = 2227

    flag = os.getenv('FLAG', 'flag{testflag}')

    s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    s.bind((host, port))
    s.listen(5)
    print(f"[+] Listening on {host}:{port}")

    while True:
        conn, addr = s.accept()
        threading.Thread(target=handle_client, args=(conn, addr, flag)).start()

if __name__ == "__main__":
    main()

题目流程很简单。给出level1和level2，对于每个level有两次尝试机会。用户可自定义输入，交互会返回计算值，而通关条件是计算出给定m的结果。那很明显我们需要得到x，y的某种关系或者直接算出x，y才能计算。我一开始推了很久结果发现可以z3一把梭(z3神力！),脚本写的详细一点顺便再复习一下z3的使用。

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
from pwn import *
from z3 import *


def calculate_level1(m, x, y):
    return (m | x) + (m | y)

def calculate_level2(m, x, y):
    return (m | x) + (m ^ y)


m1 = 15*"10"
m1 = int(m1, 2)
m2 = 15*"01"
m2 = int(m2, 2)
io = remote("127.0.0.1", 28434)

# level 1
io.recv()
io.send(f"{m1}".encode())
#io.recv()
# print(io.recv())
io.recvuntil(b"Calculation result: ")
# r1 = eval(io.recv().split(b"Calculation result: ")[1])
r1 = int(io.recvuntil(b'\n')[:-1])
print(r1)

print(io.recv())
#print(io.recv())
io.send(f"{m2}".encode())
io.recvuntil(b"Calculation result: ")
r2 = int(io.recvuntil(b'\n')[:-1])
m = eval(io.recv().split(b"m = ")[-1][:-2])
x = BitVec('x', 30)
y = BitVec('y', 30)
s = Solver()
s.add((m1 | x) + (m1 | y)==r1)
s.add((m2 | x) + (m2 | y)==r2)
if s.check() != sat:
    print("false")
else:
    print(s.model())
    x = s.model().eval(x).py_value()
    y = s.model().eval(y).py_value()
    res = calculate_level1(m, x, y)
    io.send(f"{res}".encode())
print(io.recv())

# level 2

io.send(f"{m1}".encode())
io.recvuntil(b"Calculation result: ")
# r1 = eval(io.recv().split(b"Calculation result: ")[1])
r1 = int(io.recvuntil(b'\n')[:-1])
print(r1)
print(io.recv())
io.send(f"{m2}".encode())
io.recvuntil(b"Calculation result: ")
r2 = int(io.recvuntil(b'\n')[:-1])
m = eval(io.recv().split(b"m = ")[-1][:-2])
x = BitVec('x', 30)
y = BitVec('y', 30)
s = Solver()
s.add((m1 | x) + (m1 ^ y)==r1)
s.add((m2 | x) + (m2 ^ y)==r2)
if s.check() != sat:
    print("false")
else:
    print(s.model())
    x = s.model().eval(x).py_value()
    y = s.model().eval(y).py_value()
    res = calculate_level2(m, x, y)
    io.send(f"{res}".encode())
print(io.recv())

官方wp里有句话感觉很有意义“用最合适的工具解决最合适的问题，Gurobi 解决线性优化最快，SAT 求解器解决布尔逻辑最快，Z3 处理复杂混合逻辑最灵活。”确实选择了合适的工具效率会大大提升。

2，rsasign

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
from Crypto.Util.number import bytes_to_long, getPrime, inverse
from secret import flag


def genKeys(nbits):
    e = 0x10001
    p = getPrime(nbits // 2)
    q = getPrime(nbits // 2)
    n = p * q
    phi = n - (p + q) + 1
    d = inverse(e, phi)
    pubkey = (n, e)
    prikey = (d, p, q)
    
    return pubkey, prikey


def encrypt(msg, pubkey):
    m = bytes_to_long(msg)
    n, e = pubkey
    c = pow(m, e, n)
    return c


def get_gift(prikey):
    a = bytes_to_long(b'miniL')
    b = bytes_to_long(b'mini7')
    p, q = prikey[1:]
    phi = (p - 1)*(q - 1)
    giftp = p + a
    giftq = q + b
    gift = pow((giftp + giftq + a*b), 2, phi)
    return gift >> 740


if __name__ == "__main__":
    nbits = 1024
    pubkey, prikey = genKeys(nbits)
    c = encrypt(flag, pubkey)
    gift = get_gift(prikey)
    with open('output.txt', 'a') as f:
        f.write('pubkey = ' + str(pubkey) + '\n')
        f.write('c = ' + str(c) + '\n')
        f.write('gift = ' + str(gift) + '\n')

关键函数为

1
2
3
4
5
6
7
8
9
def get_gift(prikey):
    a = bytes_to_long(b'miniL')
    b = bytes_to_long(b'mini7')
    p, q = prikey[1:]
    phi = (p - 1)*(q - 1)
    giftp = p + a
    giftq = q + b
    gift = pow((giftp + giftq + a*b), 2, phi)
    return gift >> 740

因为a和b都只有30位，把gift展开一下，约等于是(p+q)$^2$+kphi,我们自己生成几组数据不难发现k为4，用结式联立一下p*q=n就能得到p，q之一的高位(这里尝试过grobner基不过没出，看来对于未知量少的还是结式比较nb)。然后用普通的p高位泄露去打就行啦。

打结式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from Crypto.Util.number import *
from gmpy2 import gmpy2

#from sage.matrix.matrix2 import Matrix

def resultant(f1, f2, var):
    return Matrix.determinant(f1.sylvester_matrix(f2, var))
n=103894244981844985537754880154957043605938484102562158690722531081787219519424572416881754672377601851964416424759136080204870893054485062449999897173374210892603308440838199225926262799093152616430249061743215665167990978654674200171059005559869946978592535720766431524243942662028069102576083861914106412399
gift =2391232579794490071131297275577300947901582900418236846514147804369797358429972790212
gift=gift<<740
p, q = QQ['x, y'].gens()
f =n-p*q
g = (p+q)**2-4*(n-(p+q)+1) - gift
h = f.resultant(g, q)
print([f, g])
print([h, factor(h)])
PR.<x> = PolynomialRing(RealField(1000))
h = PR(h)
print(h)
res =h.monic().roots()
print(res)

经过测试发现得到的p的高229位是准确的，太有心机了刚好卡在epsilon的界上。

（以512bit的p为例)

当beta=0.4时，在未知位数少于等于227bit时，可以恢复p

当beta=0.4,epsilon=0.01时，在未知位数少于等于248bit时，可以恢复p

加一下epsilon的参数直接打即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
e=65537
c=50810871938251627005285090837280618434273429940089654925377752488011128518767341675465435906094867261596016363149398900195250354993172711611856393548098646094748785774924511077105061611095328649875874203921275281780733446616807977350320544877201182003521199057295967111877565671671198186635360508565083698058
n=103894244981844985537754880154957043605938484102562158690722531081787219519424572416881754672377601851964416424759136080204870893054485062449999897173374210892603308440838199225926262799093152616430249061743215665167990978654674200171059005559869946978592535720766431524243942662028069102576083861914106412399
gift =2391232579794490071131297275577300947901582900418236846514147804369797358429972790212
print(int(8.50163959012197759505352373881837525967941479473010602057836865805627052910871914284361623987618060959240804297171916281996509283848634874980052464884478767329803877247851607313541184922319727944953935066659961095394358139432989452855479778189020778762947568782629837455544564537937538688849538209838e153))
ph=8501639590121977595053523738818375259679414794730106020578368658056270529108719142843616239876180609592408042971719162819965092838486348749800524648844787
p_high=ph>>229<<229
print(p_high)
print(p_high.bit_length())
R.<x> = PolynomialRing(Zmod(n))
f = p_high + x
res = f.small_roots(X = 2^229,beta=0.4,epsilon=0.01)
if res != []:
    p = p_high + int(res[0])
    q = n // p
    print(p*q-n)
    d = gmpy2.invert(e,(p-1)*(q-1))
    m = pow(c,d,n)
    print(long_to_bytes(int(m)))

3，ezhash？！

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
from Crypto.Util.number import*
import random
import string
from secret import flag,key

def shash(value,key):
    assert type(value) == str
    assert type(key) == int
    length = len(value)

    if length == 0:
        return 0
    mask = 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
    x = (ord(value[0]) << 7) & mask
    for c in value:
        x = (key * x) & mask ^ ord(c)

    x ^= length & mask

    return x

def get_test(key):

    testvalue = []
    testhash = []

    for i in range(64):
        a = ''.join(random.choices(string.ascii_letters + string.digits, k=32)) 
        testvalue.append(a)
        testhash.append(shash(a,key))

    return testvalue,testhash

if __name__ == "__main__":
    assert len(flag) == 32
    assert type(flag) == str
    key = getRandomInteger(128)
    testvalue,testhash = get_test(key)
    shash = shash(flag,key)
    with open('output.txt', 'a') as f:
        f.write('testvalue = ' + str(testvalue) + '\n')
        f.write('testhash = ' + str(testhash) + '\n')
        f.write('shash = ' + str(shash) + '\n')

刚看到题目就想到了去年国赛的那道hash，去翻了翻发现还真是差不多，唯一的一点差别是这道题没给出key。那么我们咋求key呢。我们来看看shash和gettest函数

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
def shash(value,key):
    assert type(value) == str
    assert type(key) == int
    length = len(value)

    if length == 0:
        return 0
    mask = 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
    x = (ord(value[0]) << 7) & mask
    for c in value:
        x = (key * x) & mask ^ ord(c)

    x ^= length & mask

    return x
def get_test(key):

    testvalue = []
    testhash = []

    for i in range(64):
        a = ''.join(random.choices(string.ascii_letters + string.digits, k=32)) 
        testvalue.append(a)
        testhash.append(shash(a,key))

    return testvalue,testhash

我们可以发现testhash是key和 testvalue经过shash运算得到的结果。那么很明显啦，z3神力！使用一组test就能得到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
from z3 import *
from Crypto.Util.number import *
from gmpy2 import *
import hashlib, binascii
from tqdm import *


# 输入数据（替换为实际数据）
testvalue = ['tx4QYfj3lCTABrCoMsh3PPvQIM7dmIIw', 'jKLrKVRVpjjyrchL41IjMVkQMgSkyyig', 'fdbfg4185rfRJyhwCwc2flhmsCDuVOe8', 'ZL8h1XOKVNXkVh1ZcCHhDUvF4FO96139', 'HcDKLC1iMwoiWoGxaC5VNC78VHLt5JOI', 'GzGJsONsN8GSZxh6C89w0nzRiTaR3tkj', 'Qcc9vqEBGXYd8sZ3E94Ode6ChC3U53x7', 'kABKm4mE7AttOzac3eBXvIxKE9Ve0viT', 'IkxnSW31AuUGpVldXGopAxfzr5eTXc2u', 'rJ2LZ0uDPCWEwJzaGGalaWWHBbxrLH4h', 'bOlXdB5xVb2RQO0MAhLvzgOZpEo2hIdP', 'gRhoDgyxFFV5kBLwZxexhoHNd5BD81UE', 'Ij86fy7zhVOaapV76xI71IUC8utF6Ct6', 'T055KPGIWKhNIEPxAKW4MLMbmWDvEnLb', 'SQSSYTFryov8Bp1ckfjbUTTV8H3Z3Dr7', 'AzfvT7z8NXJ9u8ID6vgJ8Zml58F2k0iF', 'o3nEYw9XaNzgetmmwypTU7oePU04Tkhc', 'B44YjfhqOrlPg8XQJq2fhWEoGaCijfsc', 'b7cvfUfjvorVjDBW6DiXrZc3eBqx98Ro', '9MwfbmLtdmRRt0TONZ4zmd6NN7z7V8Eg', '2f7I0f65nopjOpIZzErAoqYSGl0tMo0x', 'PqvrJ3FmEuJh1ASIQ06RyYCXbe6426CY', 'c3C60OTDrIs5ZChP2hTAYvViDw43ARCK', 'D6a0NJ2JpwtTBCRJdw1DcXntMgRRyj2A', 'gJ0rEL4zyy8A6aKZ1H3N46rsQnY6UGGx', 'CD19v37d2jHu9YZMp20h70sm1Q3t1yOm', '7vt0C1SCNvPBqBm0YrJffbeLG8vS8388', 'o2KRrZQJLD7CMuLzlPJoJHXwVOHEanBi', 'Lm8I9m5ikXVrguEUFKw6yIc9QWnLwisx', 'kt9H0IDCsjCfqkR83aHD8D23jXq55q5K', 'HsXBVD2dMVTScHfgwAeNsqHkLCWuuaVn', 'QnkXRLGjzfh16icAVidcW4kVx1LEOv0j', '29dQWe0QWOxNAhv48Lfnv8II4IZqeUh1', 'E9Hj5zUhGXUfrNJRmhxF0KfBq0wSjX0i', 'mEc57IdmvliXneKStFzb3pAnNNm4UHbh', 'TvRZb6btVQeKXsO5iVuRCdz3A4ORZ5yQ', 'yOfrPTw9Vkd0P7kiijnGVYL4SogWF7cY', 'GNI7o11w4RyXYY2hnxdq1mAeVPrppkRc', 'YCMxUi7OcB5xozjTg09xXbJvwM6U4apy', '0g6ItBFoe3174e7wpEaEgoid0rixLHBs', 'bsyXlUGPUnQjoNwQLROwrA2SCkbDR1k5', 'CMNSNW3fU14ibZgL0ifWrA0xbbq7Yrks', 'VHfbRmzF9mzGCbYySdljWWo08IVCmAMZ', 'SLfmmSZ5TjDc4ZfKIB2gOVf9KIH2jDUi', 'YKTagkUhZjI0gMyaE1YjVJdCYtPGPZge', 'kCVhCGvjedxC44BlTqQryGdMliYqYrIz', 'HflxuwlJZ2rByOnv995gpXz03ZK6MLW2', '8Yy45IMlpMhDO3CFVhr5f0iRBnNuj3ut', 'Ydae2l7kt1O6mCIBRwjr6TWn6fLRHXjf', '3cLGeEXfyLnrL0ZkvgSEAbDBYgaFNFxB', '97xOFim3lkwqrWM1BqQ7c8mYo5S5TxkC', 'U1EgvNhZz3M8Hg38FsuBVG0PvuWiCfez', '1elLy7dgdfEtb2XyZMxaU6h8dGjfokjv', 'FlSHFSs2SeKNOUVAprkHdtD2FrIPUGIR', 'Bu1pVMZ5QqMmvBTdUt4IwsTpkclqwQKF', 'BPzJvHHDTAu23xBS1wVButTF7lU0JGoo', '6xje2blSl3QwGeV9D4pUmxMKJDqpyXpt', 'F2DkyxkRcHotO6i5MVUKzzDsxV2F69wh', 'kvSYBqmZNppDfweere2A8co50Tv85c4m', '9k5gxX8oz1WmVLtCcN4SdFIse2FizYDU', 'BJ2PCD5KgukjFWntZ3VSjcHJzIZprno2', 'Lyw9EacIjF6j6de3e5wFRQLdzrOfQoAR', 'egf9LJLJrWDIrtnsHZ4XRgoPTXNsz91a', 'Y3ptIW83Rwtny4kng2lCEAYQyPrSIXWl']
testhash = [139452903649273495774796570198749847935154848275416989998236609393670079561796026566, 1898315960650462382992557075551445244853390783794354772475023552166352399126801574913, 1548283380348601157365276865178627465508293067676981633220766480841355279423253644108, 923519463377078549688929962730292019193308698763374121309865664233390770048594933085, 1756902502089018688726236312608077708484907801835749190713532913735823397112051091188, 485883566823442644293538461674550566921074196968613685770142417532151624958507107972, 1173292014155884160226339046019271687659068020981556335907768031140876583959335792191, 1497598230931219654402725391331476099708291441530945577907300933091011484442911623559, 405254852716971084666570344588562007424273706832802434925282540786042396564117859893, 1394088214004563872208003758992014976825245306078851263986862009024422531466462221196, 1763510459716348629512798257958014024443432479861579028783119470126357343664438877507, 27569271776233701581922903599984775754217802504994237075390721310066121958700422257, 358721799072196562200934505713368644637409165736588969777736471282788507457480492393, 393768200956019495628870433474843666326783653588854234548113046584760291662872350533, 1807499005738194381232046747643492968233097104171420081977957810644000450496758434126, 1128375044917910760907836056160281710737671148936596789317429758098492329675588054412, 190801904376187850882600897701548299608718300961575858190394579710450430805489346060, 696235869802737571933351613461601576350495964954926712734858661433694663819119664403, 144629031178782625524039663692148786536912021223673544659451459599242746855791775856, 401144481698447351083363386545760097487182143265029898145794033656496473914256697335, 1009618288798575771577716476700225261222418219966898563557126734083036472365735018549, 1652157599124169823165290864340613818899678030477803381010155627950330279311151902666, 1870720516435595720338243705356357230346778004770545711499635272857342051185669675206, 1487151272734883591621339384743729579702945226647848932314811332859011211687393769612, 1479191883622650407012568261078896124452298448888937784127270669623167501587692263629, 780856915459110484827869192135025240964695263399685896704373351690074659693517658597, 1272702898194178848480618231703540760239057875392727193937165056708655804663623414520, 1275195323347307250910668562396243097983325652451465111552014287378408554253858874273, 1698673537783777278793781484130287999078310462163146951845044095951885080758156044986, 1116043791065172596267818286071095315966453133595258493434104767743854595678117184595, 1348107024738703857635485943338711096444282613588540975344171990396347335813147110414, 674079263421647723071324170291511267338891718494055820365382788749002205059725239586, 295061829951102865059369162125524442985720861319812067484094160955682413284464056261, 1538215242227433291697344636690665676070219615083515667029553094023114463154050936814, 721505087135717334627356208457079819823654955152265437431617001188458058923464437209, 1829121734506718678607427505722187801463532440435031915402835074237985549711879794153, 641638098138302116745154827833695010970508819483215023447636503844550651793330508318, 578773085269354102367810984562000052879291442293349350198300750627238557013515250567, 1037095172573176620769108515135124799537948207093565906631598569276504664097088051993, 1135701773556587743998667090148858666225101588783019121910187176364233349468967967460, 558240645642302963325581107204211662019896908316831899444935081810819489268610165950, 1058477746525469710567689847282850794170250650192794892415352733735415750154044535539, 1078948952548590509616082107408254715684287170445966544383750373684441181406075608800, 1125503915235599245173592373330463888468814720113318696411329986853859005519154551245, 620937641933659718470519231175003762666892925875327642171561741417944681106496958467, 1606192912497675735832389346699475593863960301930109653069662356606234973780336341534, 1080665036256326887412273484626209788664633047255179233142423471463514811554155351816, 983009583253660084055702843297933007090244160053834934015802835528599935867335658914, 483554778736863191047830758397092863562079726548422384268968936073701177390747179894, 1448392838363784830874780455853191313920717249664981009097361707739423512768919183176, 1485175804980546607220269493098915446350406205462077528986751407380405658199537322034, 645127338301455578293193215328875283422934699182904112612610112081929081505533458304, 1809012351380435986646710932772127842855528298763939575266488725018536037784342688529, 1204732789391044629328843397205785308919820285525150764490536624969971871178313643864, 577072907834194443039001358264806817627199891744275024388326836994220595931009773412, 4850110449540994875278068624822977611188629104877448016749725577673217396499782282, 1431458221917644050146055837804453915809781510516096707298405324221753990760039183190, 997966793625232984798176686099411790420209217223783698909939651134351713786805317998, 1663286211430268448119727051818073243067649643181675027323547282932628837598336996456, 1864894557154744961308146774304105483911867578158330607820790060568575114233028842003, 345822843952211153189889023070066136116424104740167243049994988868945364800740535124, 803699468991667968627856232995969437316168483382073633967569490433608395707635458855, 1700532832517222239684444041937412551935144886911006116260771516969538181780787023704, 351624945474123146509460066647337532150453362002844376810733781394757015795554947704]
enc = 463802484547898091835999726502006552543022358314700124374789687370275467670717610329
mask = 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
mask_bits = 280


def shash(value,key):
    assert type(value) == str
    #assert type(key) == int
    length = len(value)

    if length == 0:
        return 0
    mask = 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
    x = (ord(value[0]) << 7) & mask
    for c in value:
        x = (key * x) & mask ^^ ord(c)

    x ^^= length & mask

    return x
# 提取测试样本
s = testvalue[0]
h = testhash[0]
# 初始化Z3求解器
solver = Solver()
key = BitVec('key', 128)

# 提取测试样本
solver.add(shash(s,key) == h)
# 求解密钥
if solver.check() == sat:
    model = solver.model()
    print(model)
    key = model.eval(key).py_value()
    print(f"Recovered Key (hex): {key}")

造格的重点是把异或看作加或者是减去一个值，并且这个值在-255到255之间。详细的造格说明可以参考CISCN2024-Crypto - Shin’s Blog，这里不再过多赘述。

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
from Crypto.Util.number import *
from gmpy2 import *
import hashlib, binascii
from tqdm import *
# 输入数据（替换为实际数据）
testvalue = ['tx4QYfj3lCTABrCoMsh3PPvQIM7dmIIw', 'jKLrKVRVpjjyrchL41IjMVkQMgSkyyig', 'fdbfg4185rfRJyhwCwc2flhmsCDuVOe8', 'ZL8h1XOKVNXkVh1ZcCHhDUvF4FO96139', 'HcDKLC1iMwoiWoGxaC5VNC78VHLt5JOI', 'GzGJsONsN8GSZxh6C89w0nzRiTaR3tkj', 'Qcc9vqEBGXYd8sZ3E94Ode6ChC3U53x7', 'kABKm4mE7AttOzac3eBXvIxKE9Ve0viT', 'IkxnSW31AuUGpVldXGopAxfzr5eTXc2u', 'rJ2LZ0uDPCWEwJzaGGalaWWHBbxrLH4h', 'bOlXdB5xVb2RQO0MAhLvzgOZpEo2hIdP', 'gRhoDgyxFFV5kBLwZxexhoHNd5BD81UE', 'Ij86fy7zhVOaapV76xI71IUC8utF6Ct6', 'T055KPGIWKhNIEPxAKW4MLMbmWDvEnLb', 'SQSSYTFryov8Bp1ckfjbUTTV8H3Z3Dr7', 'AzfvT7z8NXJ9u8ID6vgJ8Zml58F2k0iF', 'o3nEYw9XaNzgetmmwypTU7oePU04Tkhc', 'B44YjfhqOrlPg8XQJq2fhWEoGaCijfsc', 'b7cvfUfjvorVjDBW6DiXrZc3eBqx98Ro', '9MwfbmLtdmRRt0TONZ4zmd6NN7z7V8Eg', '2f7I0f65nopjOpIZzErAoqYSGl0tMo0x', 'PqvrJ3FmEuJh1ASIQ06RyYCXbe6426CY', 'c3C60OTDrIs5ZChP2hTAYvViDw43ARCK', 'D6a0NJ2JpwtTBCRJdw1DcXntMgRRyj2A', 'gJ0rEL4zyy8A6aKZ1H3N46rsQnY6UGGx', 'CD19v37d2jHu9YZMp20h70sm1Q3t1yOm', '7vt0C1SCNvPBqBm0YrJffbeLG8vS8388', 'o2KRrZQJLD7CMuLzlPJoJHXwVOHEanBi', 'Lm8I9m5ikXVrguEUFKw6yIc9QWnLwisx', 'kt9H0IDCsjCfqkR83aHD8D23jXq55q5K', 'HsXBVD2dMVTScHfgwAeNsqHkLCWuuaVn', 'QnkXRLGjzfh16icAVidcW4kVx1LEOv0j', '29dQWe0QWOxNAhv48Lfnv8II4IZqeUh1', 'E9Hj5zUhGXUfrNJRmhxF0KfBq0wSjX0i', 'mEc57IdmvliXneKStFzb3pAnNNm4UHbh', 'TvRZb6btVQeKXsO5iVuRCdz3A4ORZ5yQ', 'yOfrPTw9Vkd0P7kiijnGVYL4SogWF7cY', 'GNI7o11w4RyXYY2hnxdq1mAeVPrppkRc', 'YCMxUi7OcB5xozjTg09xXbJvwM6U4apy', '0g6ItBFoe3174e7wpEaEgoid0rixLHBs', 'bsyXlUGPUnQjoNwQLROwrA2SCkbDR1k5', 'CMNSNW3fU14ibZgL0ifWrA0xbbq7Yrks', 'VHfbRmzF9mzGCbYySdljWWo08IVCmAMZ', 'SLfmmSZ5TjDc4ZfKIB2gOVf9KIH2jDUi', 'YKTagkUhZjI0gMyaE1YjVJdCYtPGPZge', 'kCVhCGvjedxC44BlTqQryGdMliYqYrIz', 'HflxuwlJZ2rByOnv995gpXz03ZK6MLW2', '8Yy45IMlpMhDO3CFVhr5f0iRBnNuj3ut', 'Ydae2l7kt1O6mCIBRwjr6TWn6fLRHXjf', '3cLGeEXfyLnrL0ZkvgSEAbDBYgaFNFxB', '97xOFim3lkwqrWM1BqQ7c8mYo5S5TxkC', 'U1EgvNhZz3M8Hg38FsuBVG0PvuWiCfez', '1elLy7dgdfEtb2XyZMxaU6h8dGjfokjv', 'FlSHFSs2SeKNOUVAprkHdtD2FrIPUGIR', 'Bu1pVMZ5QqMmvBTdUt4IwsTpkclqwQKF', 'BPzJvHHDTAu23xBS1wVButTF7lU0JGoo', '6xje2blSl3QwGeV9D4pUmxMKJDqpyXpt', 'F2DkyxkRcHotO6i5MVUKzzDsxV2F69wh', 'kvSYBqmZNppDfweere2A8co50Tv85c4m', '9k5gxX8oz1WmVLtCcN4SdFIse2FizYDU', 'BJ2PCD5KgukjFWntZ3VSjcHJzIZprno2', 'Lyw9EacIjF6j6de3e5wFRQLdzrOfQoAR', 'egf9LJLJrWDIrtnsHZ4XRgoPTXNsz91a', 'Y3ptIW83Rwtny4kng2lCEAYQyPrSIXWl']
testhash = [139452903649273495774796570198749847935154848275416989998236609393670079561796026566, 1898315960650462382992557075551445244853390783794354772475023552166352399126801574913, 1548283380348601157365276865178627465508293067676981633220766480841355279423253644108, 923519463377078549688929962730292019193308698763374121309865664233390770048594933085, 1756902502089018688726236312608077708484907801835749190713532913735823397112051091188, 485883566823442644293538461674550566921074196968613685770142417532151624958507107972, 1173292014155884160226339046019271687659068020981556335907768031140876583959335792191, 1497598230931219654402725391331476099708291441530945577907300933091011484442911623559, 405254852716971084666570344588562007424273706832802434925282540786042396564117859893, 1394088214004563872208003758992014976825245306078851263986862009024422531466462221196, 1763510459716348629512798257958014024443432479861579028783119470126357343664438877507, 27569271776233701581922903599984775754217802504994237075390721310066121958700422257, 358721799072196562200934505713368644637409165736588969777736471282788507457480492393, 393768200956019495628870433474843666326783653588854234548113046584760291662872350533, 1807499005738194381232046747643492968233097104171420081977957810644000450496758434126, 1128375044917910760907836056160281710737671148936596789317429758098492329675588054412, 190801904376187850882600897701548299608718300961575858190394579710450430805489346060, 696235869802737571933351613461601576350495964954926712734858661433694663819119664403, 144629031178782625524039663692148786536912021223673544659451459599242746855791775856, 401144481698447351083363386545760097487182143265029898145794033656496473914256697335, 1009618288798575771577716476700225261222418219966898563557126734083036472365735018549, 1652157599124169823165290864340613818899678030477803381010155627950330279311151902666, 1870720516435595720338243705356357230346778004770545711499635272857342051185669675206, 1487151272734883591621339384743729579702945226647848932314811332859011211687393769612, 1479191883622650407012568261078896124452298448888937784127270669623167501587692263629, 780856915459110484827869192135025240964695263399685896704373351690074659693517658597, 1272702898194178848480618231703540760239057875392727193937165056708655804663623414520, 1275195323347307250910668562396243097983325652451465111552014287378408554253858874273, 1698673537783777278793781484130287999078310462163146951845044095951885080758156044986, 1116043791065172596267818286071095315966453133595258493434104767743854595678117184595, 1348107024738703857635485943338711096444282613588540975344171990396347335813147110414, 674079263421647723071324170291511267338891718494055820365382788749002205059725239586, 295061829951102865059369162125524442985720861319812067484094160955682413284464056261, 1538215242227433291697344636690665676070219615083515667029553094023114463154050936814, 721505087135717334627356208457079819823654955152265437431617001188458058923464437209, 1829121734506718678607427505722187801463532440435031915402835074237985549711879794153, 641638098138302116745154827833695010970508819483215023447636503844550651793330508318, 578773085269354102367810984562000052879291442293349350198300750627238557013515250567, 1037095172573176620769108515135124799537948207093565906631598569276504664097088051993, 1135701773556587743998667090148858666225101588783019121910187176364233349468967967460, 558240645642302963325581107204211662019896908316831899444935081810819489268610165950, 1058477746525469710567689847282850794170250650192794892415352733735415750154044535539, 1078948952548590509616082107408254715684287170445966544383750373684441181406075608800, 1125503915235599245173592373330463888468814720113318696411329986853859005519154551245, 620937641933659718470519231175003762666892925875327642171561741417944681106496958467, 1606192912497675735832389346699475593863960301930109653069662356606234973780336341534, 1080665036256326887412273484626209788664633047255179233142423471463514811554155351816, 983009583253660084055702843297933007090244160053834934015802835528599935867335658914, 483554778736863191047830758397092863562079726548422384268968936073701177390747179894, 1448392838363784830874780455853191313920717249664981009097361707739423512768919183176, 1485175804980546607220269493098915446350406205462077528986751407380405658199537322034, 645127338301455578293193215328875283422934699182904112612610112081929081505533458304, 1809012351380435986646710932772127842855528298763939575266488725018536037784342688529, 1204732789391044629328843397205785308919820285525150764490536624969971871178313643864, 577072907834194443039001358264806817627199891744275024388326836994220595931009773412, 4850110449540994875278068624822977611188629104877448016749725577673217396499782282, 1431458221917644050146055837804453915809781510516096707298405324221753990760039183190, 997966793625232984798176686099411790420209217223783698909939651134351713786805317998, 1663286211430268448119727051818073243067649643181675027323547282932628837598336996456, 1864894557154744961308146774304105483911867578158330607820790060568575114233028842003, 345822843952211153189889023070066136116424104740167243049994988868945364800740535124, 803699468991667968627856232995969437316168483382073633967569490433608395707635458855, 1700532832517222239684444041937412551935144886911006116260771516969538181780787023704, 351624945474123146509460066647337532150453362002844376810733781394757015795554947704]
enc = 463802484547898091835999726502006552543022358314700124374789687370275467670717610329

mask = 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
mask_bits = 280
key=1000001
var_names = ['v' + str(i) for i in range(1, 33)]

    # 创建多项式环（32个变量，系数为整数）
R = PolynomialRing(ZZ, var_names)

    # 获取所有变量（按顺序）
variables = R.gens()
x = variables[0] * 128
for c in tqdm(variables):
    x = key * x + c
coe = x.coefficients()

# 造格
t = (enc ^^ 32) & mask
M = identity_matrix(ZZ, 32 + 2)
bel = 2 ^ 500
for i in range(32):
    M[i, -1] = coe[i] * bel
M[-2, -2] = 1
M[-1, -1] = 2 ** 280 * bel
M[-2, -1] = -t * bel
res = M.LLL()[:-1]
for i in res:
    if i[-1] == 0 and i[-2] == 1:
        res = i[:-2]
print(res)
# 还原key
a1 = invert(key, 2 ** 280)
flag = b''
for i in res[::-1]:
    xa = (t - i) % (2 ^ 280)
    x = t ^^ xa
    flag += long_to_bytes(x)
    t = (xa * a1) % (2 ** 280)
print(flag[::-1])

4，Noisy

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
from Crypto.Util.number import getPrime
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from random import getrandbits, randint
from hashlib import md5


class Noisy_cipher:
    def __init__(self, params):
        self.nbits = params["nbits"]
        self.pbits = params["nbits"]//2
        self.Mbits = params["Mbits"]
        self.k0bits = params["k0bits"]
        self.k1bits = params["k1bits"]
        self.samples = params["samples"]
        self.p = getPrime(self.pbits)
        self.q = getPrime(self.nbits)
        self.n = self.p * self.q
        self.s = randint(0, self.n)
        self.M = getrandbits(self.Mbits)
        self.pubKey = [self.n]
        self.priKey = [self.s, self.p, self.M]
    
    
    def encrypt(self,msg):
        res = []
        for i in range(self.samples):
            k0 = getrandbits(self.k0bits)
            k1 = getrandbits(self.k1bits)
            ci = self.s * (msg[i] + k0*self.M)*(1 + k1*self.p) % self.n
            res.append(ci)
        
        return res


if __name__ == '__main__':
    params = {
        "nbits":1024,
        "Mbits":30,
        "k0bits":30,
        "k1bits":512,
        "samples":20,
    }
    mbits = 24
    Noise = Noisy_cipher(params)
    n = Noise.n
    msg = [getrandbits(mbits) for _ in range(params["samples"])]
    cipher = Noise.encrypt(msg)
    with open('secret.txt', 'r') as file:
        flag = file.readlines()[0].encode()
    file.close()
    key = md5(str(msg).encode()).digest()
    aes = AES.new(key, AES.MODE_ECB)
    encrypted_flag = aes.encrypt(pad(flag, 16)).hex()
    with open('output.txt', 'a') as file:
        file.write('n = ' + str(n) + '\n')
        file.write('c = ' + str(cipher) + '\n')
        file.write('encrypted_flag = "' + encrypted_flag + '"\n')
    file.close()

大概看一眼题目代码不难发现重点是这一行

1
ci = self.s * (msg[i] + k0*self.M)*(1 + k1*self.p) % self.n

展开改写一下得到

令x=m+k$_0$·M.可以写成x+k$_1$x · p mod n，并且我们已知n=pq，这就转化成了一个PACD问题，可以使用正交格的方法求解，可以参考格密码分析：正交格攻击 | tl2cents blog，值得注意的是正交格规约出来是与原向量垂直的向量，所以要求我们想得到的结果需要对造出的格求一个right_kernel()。然后就能得到x，且x=m+k$_0$·M，那就是一个AGCD了，也是正交格去打。

那么就可以写出代码啦

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
from Crypto.Util.number import *
from Crypto.Cipher import AES
from gmpy2 import *
from subprocess import check_output
from hashlib import md5

def flatter(M):
    # compile https://github.com/keeganryan/flatter and put it in $PATH
    z = "[[" + "]\n[".join(" ".join(map(str, row)) for row in M) + "]]"
    ret = check_output(["flatter"], input=z.encode())
    from re import findall
    return matrix(M.nrows(), M.ncols(), map(int, findall(b"-?\\d+", ret)))

n = 931345196654137409294197135173149859904800504387235031569844050477816805471659477549867345780405716254835453866134323419945309131852465776955243829422305657434938224724478007837188982154686395040152421927773513751675951117273164534599361707388401754689467232293524773873081390900445460751849312463853674644147032417729111218144080786016585938118028106088150701390374246123227343653724932824469200315405886227541178516859510470438102946063729298109789753400535413
c = [44393461469135749552341687573367202324883191440583805973792574295302702852134846481849103946409919792057095346990009804033846370311582900685718559323930567746395228471258159648661807580463697803841730176308557755645476991733346247396500365688994367463153020886602899611038036228481769117396526392280614311463280399494133571801648415803508402241721480392296346279553729911935412665319929139397699629742042460689944378768977129239396836317204774266638191562623642, 539920802606578584210996520924579291346905910518135607177245745820517711828351507337959361269794979842233434156795677265464942949246448433197513954168602625494100194699716593500051960783605835250817713574311904996510832420400834091420622842541472830357072621740148258698642873008987856098015262213586418636597458173855887200534596678693164065907611865092804827249866719338749882553240206311618656611195747325612206359345586978029288254676405381961327252078121227, 912969253027180152302008239757950557255143999987684345824704782128308837709443475359601738962500473197792984510949472765652709449576511551753476192189067928236825729802081544313577905638454269321307806960030818401241547153518148752380077970852835890206560157651154083006318242420498917321741946345422908249723406759064990622534934300768889856495669567881646449061735911544207219295421775183342850849511318455169459802392153404840292256588462238484017184070439058, 704129339391476902834623647545050360055052560918471812433439198050896702771009034197961257854439637856923149427107485450685758012059915229254711158222062274633832027255279885472858093979886344455603364752039574393763740089052781056817698204632985382283135005709245118795006715288914374917267774490980643965855806763792705970367942842066301900528153149411886703069237980512017698620265259775250207231454943195707701376131205089963780783194378880892920761769396376, 75233039998980230184893215882867932908211138581464925469465529257051933026745951594054393764107823684556757549941976687507867860435869332829256074033281246343192963839759052028459631662209667578023008295444423181997621348563199183346960455353232990885813330466287295547759326363405275137501042528970911270222207659932659495447106007866559948214804837910916964981447827647966841595069719238014777879036315306528393822101416510360429475270780316967314977212062479, 461423095526820857155507142909810859741993739691637425310258711373657533005997947691887212668647744754708998545032230990008781169413674049824069040664094391313692719411542897396557436563635856225821281279781008700827315066631377604685721697875513442045633625509355719320731049790871449432502165309335238486557551797017798444889669487248744419599481849250280233778118639348019549912963106101292147155681429237126220845262529135044627852020816746814659384780280973, 367364572148059002452458378431919918417128457895918835895792042718588658184890998070524174563741131829770068017761303942083521976211260357518337046963857857923796113599655185025979061513594565985351757490979954268209182516032134979103468620018163916908405334869466018019365868158827852395987531538640537494591839876488794094867513081526454002977847709327257947076683213914991119173347188654815917923371430774772220979039309203396300178280207360538444565566020299, 904463452273264226577027020039531313648975201538158946181894446099560257332044693934142997946585244486522386003568254369400502693137880071694551015943027552207478494112177186465294633752846739107117260820777505887557669953162522289988781935162572334120761828958346938610998284198883207252030818244320266796588782628679469599573621141532731189668347726613589688599907757436810708578278511123476853464661969249807190793933642629049121152594554138741064353908267527, 905416992071609918194286515398185039717046426602235967032724042039427878441223712019928849846046512156035414203668484273724435007867326197142639578134394106888412651336818885397451910937280467497797130716216468206865920691694792412526665587970431309296769222651386297077280003604436310714741049806737139142445245569932908914027744645513522958423615830744399292707462525246610072828618152626530619477149886211241901531983934546033687698719922827074723162112877139, 452643031792027333761138831146502956340724720315042375737589105675038921336234007024472026194106213621694017814735826360779159432111610885222090540082603623837117068711452615521100137223909708233119331357716789686350547309821120723790772118708237069207516678406654282702496219667506339320212014846049065105749599898166761195573717057859137983450296304872572871751663468743347535459305514224218500703387571202207027664726341715849324032699940941905839302766827499, 212673278087605343276071433314325651822590138814583835769266435297532085609513722222971062796758536350174937826257599823800561305906518757901728127745886814862639273759236069230910033612691903488587337500974112537248366383295461678533905165374092697347321036155866150099809018499951162533765210416850725766195148466913723342201317273777814265581791043948667692208912085197333559714555752788986641645892112079484237438406289333978097134665465890869117192499040078, 618885378867829225574384501430248365944801981788397398087382860821512631127016396693744705104921139258471344898496683075139334050462054819762115919159392842707178868016697534175927650393416588623170936742373077805758963002568768267797843281721972800997172099222722029886235184148160770288591312377965422085410302286242604988405174145979590045724258072059745959840087044435085850665653201438615483013012669624865477331056502564666781619316693156013842919938163321, 247541522606162447639301360070006352189819939226525086556447182525813620932850763368793482733250887839896454988833382645818017844366921462117689698250456542373028553792898964827039839763697407818465152532046980456227414222696647288759140238333732153522322593390570208339332394637394873323773760730999003953875961526476008886559596300228049432970064036768172196837050887080432644677813778844185851969703026669069770482802366425198959039311171290582323970136971886, 908018178869624877463246006010850998859189967677977854520359272664016848400825720425780329121594793126516838777613620596508996703936445567812415853284383999097120944182957514958755630252556706588567697742822534195073018061427160931816814733075736791598346359735687960831673101184689094229555577585585923791489244865110884570860216605752334625663191443649941759569007973564548438436441428870306894238322372831477776218474307399183417368990004923389659543747195296, 366523156922156965821828874107564478788643127754015557590598074555449309032008658382486713007501973690333305257733148972529467963882646318977084677556747090610737208466813471179929722614677159741828176112063648755272191520333104369216677948221832614065957220855992127171151122742679465992969209100579420456272759494150603308918209213782654566120728303606840200883548862818260127217153333990531566636412609141292951607073854516504587688328356290301197508841143741, 639406992161231079019948085936226229300789127373562729169611827945671359155688049810884857367876003831554226874585473740231752445953638246901220714046836671336883740086166378134402994243966696885331702926066667688733147620400909589757552630021877907871711728497089853311096298440658356847718920978470275256185444145070691778883308538596800581292775537884030859076294618094092471841198971413069838393993348287099841406516752971246902464209608259286659436366564130, 174788516082730477653159546514041816772418089789276014413831566132969570738198961172185399940444613359439932847237594496731166190833395423296555364488106067480663357216325505878919022799798056746312098513235963582560821318135335749507326788293491822146649158662575138071628748364257596420485792422257187406205492351506462873966550421052920225650910969287505948086603766444926390024169074853316825113026820782720738096044454079119560396182767773276067915935620838, 692122366621668667934219623781427243412441522160495343734761009370335228032983188772200711284859681304604759206913240934049495316525633233831165309292048163807009060066877565588518825399293683925724650068090938676695109266471854850233584663313868765863440164620682884162805086273022432479339558553205180790661279541212760937139848506839349409774335221610460173306469631751320521446368124215699897055036629272579050909508624189106164372746898653884579369739300732, 655458433272866580956847752295203248320777879825112389989922084544791554484471603499617539316146184842569741790211263945397678411830636036184289378485001841639074371604764089931122272819428308907402735409020487920248536050013994567271676166709669489791796881195493234306692941286104370305393726294538393465256528119230161794643693614527801553094915478577302812822235536872500554436063474907280123259938377500419679054323084985978824524145718399076476333347704243, 469953808456651804146000233164086224981688489612248280585566256224965907341271421402496612389906809620564044789407968371121708170572023237144917029355521900919148351696528608187440824844352038236393593068104904053288525955999815309158295080405407971397111278262543364815818529357051823886830084476645557683307203866337081517030832639815424599514896405759257146192241829045108758822206019067643000025217245916174241352087766812082643533881822356002925358883319804]
encrypted_flag = "3627c955f73257f3253e1ab1d0d9489da506d71bf670776a005fb44bab85fa2d"
cipher = bytes.fromhex(encrypted_flag)


################################################################### step1 PACD
l = len(c)
c_vec = vector([(-c[i] * invert(c[-1], n)) % n for i in range(l-1)])
L = identity_matrix(l - 1).augment(c_vec)
L = L.stack(vector([0] * (l - 1) + [n]))
u = L.LLL()[:-2]
r = Matrix(u).right_kernel().matrix()[0].list()
#p = GCD(c[1] * r[1] - c[2] * r[0], n)

################################################################### step2 GACD
l = len(r)
alpha = int(2 ** 24)
A = vector(r)
L = identity_matrix(l).augment(Matrix(alpha * A).T)
t = L.LLL()
V = [x[:-1] for x in t[:-2]]
t = Matrix(V).right_kernel().matrix()
r = t.LLL()[0]

################################################################### step3 get flag
msg = r.list()
key = md5(str(msg).encode()).digest()
aes = AES.new(key, AES.MODE_ECB)
flag = aes.decrypt(cipher)
print(flag)

(不过不知道为什么flatter犯病了，明明其他用flatter的脚本都能跑偏偏这个跑不出，只能改成正常的LLL了qaq)

(还有两道先咕咕)