LiLctf2025

(Updated: )

linear

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
import os
import random
import signal

signal.alarm(10)

flag = os.getenv("LILCTF_FLAG", "LILCTF{default}")

nrows = 16
ncols = 32

A = [[random.randint(1, 1919810) for _ in range(ncols)] for _ in range(nrows)]
x = [random.randint(1, 114514) for _ in range(ncols)]

b = [sum(A[i][j] * x[j] for j in range(ncols)) for i in range(nrows)]
print(A)
print(b)

xx = list(map(int, input("Enter your solution: ").strip().split()))
if xx != x:
    print("Oh, your linear algebra needs to be practiced.")
else:
    print("Bravo! Here is your flag:")
    print(flag)

已知线性方程组Ax = b，其中A是一个16 × 32矩阵，x是一个32维向量，b是一个16维向量，要求解出x。 一个欠定方程组问题，这里我们可以将式子变形为$A * x - 1*b=0 ，我们构造格 M = ( A ,-b) ,y=

此时有$ 此时就变成了一个核空间下求解的问题，LLL算法求解这个问题即可

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
#sage
from pwn import *
import json
import re

# --- 1. 连接到远程靶机 ---
HOST = 'challenge.imxbt.cn'
PORT = 32131

# 设置 pwntools 的日志级别
context.log_level = 'info'

# 连接到远程服务器
p = remote(HOST, PORT)

# --- 2. 接收并解析数据 ---
# 接收所有数据，直到 "Enter your solution: " 提示符出现
data = p.recvuntil(b'Enter your solution: ')

# 使用正则表达式从接收到的数据中精确提取矩阵和向量
# re.DOTALL 标志让 '.' 可以匹配包括换行符在内的任意字符
matrix_match = re.search(b'(\\[\\[.*?\\]\\])', data, re.DOTALL)
# re.findall 会找到所有匹配的向量，我们取最后一个
vector_matches = re.findall(b'(\\[[\\d, -]+\\])', data)

if not matrix_match or not vector_matches:
    error("Failed to parse matrix or vector from remote host.")
    exit()

matrix_str = matrix_match.group(1)
vector_str = vector_matches[-1]

# 将字节串解码为字符串，然后用 json 解析
A_list = json.loads(matrix_str.decode())
b_list = json.loads(vector_str.decode())

info(f"Successfully parsed Matrix A with shape {len(A_list)}x{len(A_list[0])}")
info(f"Successfully parsed Vector b with length {len(b_list)}")


# --- 3. 使用 LLL 算法求解 ---
# 将 Python 列表转换为 SageMath 的整数矩阵和向量
A = Matrix(ZZ, A_list)
b = vector(ZZ, b_list)

# 构造增广矩阵 M = (A | -b)，将问题 Ax = b 转换为 My = 0
M = A.augment(-b)
info(f"Constructed augmented matrix M with shape {M.nrows()}x{M.ncols()}")

# 计算 M 的核空间基，它定义了所有整数解构成的格 (Lattice)
kernel_basis = M.right_kernel().basis()
info("Computed the kernel basis of M.")

# 对核空间基进行 LLL 约简，找到一组由短向量组成的新基
lll_basis = Matrix(ZZ, kernel_basis).LLL()
info("Applied LLL algorithm to find short vectors in the lattice.")


# --- 4. 寻找解并发送 ---
solution_found = False
for v in lll_basis:
    # 真正的解 y = (x | 1) 是一个短向量，其最后一个分量为 1 或 -1
    if abs(v[-1]) == 1:
        # 如果最后一个分量是 -1，则整个向量取反，使其标准化
        solution_y = v if v[-1] == 1 else -v
        
        # 解 x 是 y 去掉最后一个分量的部分
        solution_x = solution_y[:-1]
        
        # 将解向量格式化为用空格分隔的字符串
        solution_str = ' '.join(map(str, solution_x))
        info(f"Found solution vector: {[int(i) for i in solution_x[:5]]}...") # 打印前5个元素预览
        
        # 发送解
        p.sendline(solution_str.encode())
        solution_found = True
        break

if not solution_found:
    error("Could not find the solution vector in the LLL basis.")

# --- 5. 接收 Flag ---
# 接收并打印服务器返回的所有剩余信息，其中应包含 flag
response = p.recvall().decode()
print("\n" + "="*20 + " Server Response " + "="*20)
print(response)
print("="*57)

crypto-baaaaaag

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
from Crypto.Util.number import *
import random
from Crypto.Cipher import AES
import hashlib
from Crypto.Util.Padding import pad
from secret import flag

p = random.getrandbits(72)
assert len(bin(p)[2:]) == 72

a = [getPrime(90) for _ in range(72)]
b = 0
t = p
for i in a:
    temp = t % 2
    b += temp * i
    t = t >> 1

key = hashlib.sha256(str(p).encode()).digest()
cipher = AES.new(key, AES.MODE_ECB)
flag = pad(flag,16)
ciphertext = cipher.encrypt(flag)

print(f'a = {a}')
print(f'b = {b}')
print(f"ciphertext = {ciphertext}")

'''
a = []
b = 
ciphertext = 
'''

背包问题，直接套通解板子 但是这题卡了一个密度，正常的LLL算法是出不来的，预期解似乎是爆破了几位，但实际上换成BKZ调大block_size参数就可以出了。 得到的最短向量中需要判断一下01的位置

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

M = []
S = 
ciphertext = 
ge = Matrix(ZZ,len(M)+1)
for i in range(len(M)):
    ge[i,i] = 2
    ge[i,-1] = M[i]
    ge[-1,i] = 1
ge[-1,-1] = S
Ge = ge.BKZ(block_size=26)
#print(Ge)
ge = Matrix(ZZ,len(M)+1)
for i in range(len(M)):
    ge[i,i] = 2
    ge[i,-1] = M[i]
    ge[-1,i] = 1
ge[-1,-1] = S
Ge = ge.BKZ(block_size=26)
#print(Ge)
for row in Ge:
    m1 = ""
    if row[-1] != 0 or set(row[:-1]) != {-1,1}:#确保求得的最短向量最后位为0并且只包含-1,1两种情况
        continue
    for i in row[:-1]:
        m1 += str((i+1)//2)
    p1=int(m1[::-1],2)
    print(f"p1 = {p1}")
    key = hashlib.sha256(str(p1).encode()).digest()
    cipher = AES.new(key, AES.MODE_ECB)
    msg = cipher.decrypt(ciphertext)
    print(msg)

Space Travel

1
2
3
4
5
6
7
8
9
from Crypto.Cipher import AES
from hashlib import md5
from params import vecs
from os import urandom

key = int("".join([vecs[int.from_bytes(urandom(2)) & 0xfff] for _ in range(50)]), 2)

print("🎁 :", [[nonce := int(urandom(50*2).hex(), 16), (bin(nonce & key).count("1")) % 2] for _ in range(600)])
print("🚩 :", AES.new(key=md5(str(key).encode()).digest(), nonce=b"Tiffany", mode=AES.MODE_CTR).encrypt(open("flag.txt", "rb").read()))

在解决这道问题之前需要了解一些基础的原理

### 仿射变换

仿射变换是指在一个空间内的基于一系列的原子复合变换的运算，其中包括平移，翻转，旋转，剪切等。

变换遵循以下的形式

$$

=

$$

其中，，为偏移量，为对应的变换点的位置。

$$

$$

这个矩阵表示的是一个x, y偏移量为0, 初始位置为(1, 0), (0, 1)两列组成的一个线性空间。

#### 仿射子空间

一个仿射子空间可以被视为一个*线性子空间经过平移*后的的结果

一个向量空间 *V* 一个仿射子空间 *A* 可以被定义为

$$

A = P + U

$$

其中*P*是向量空间 *V* 中的一个特定的点(向量)，U是一个*线性子空间*,它定义了仿射空间的 *形状* 和 *方向*

降维的方法还没看懂看完接着补，咕咕 (x