LilCTF2025-crypto个人wp
Crypto
Liner
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$方程的x，官方wp的思路是，找到Ax的左核，Ax的左核就是b的左核，就是$ker(Ax)=ker(b)$,$ker(b)Ax=O$,这样x就是ker(b)A的右核，使用LLL算法规约最短向量就是
举个例子比如：
找到所有$y=(y_1,y_2)$,$y_11+y_24=0$,比如y=(4,-1)
找出A的左核空间$y^T$,并计算$y^TA=4(2,3)-1(5,7)=(8,12)-(5,7)=(3,5)$,
$(3,5)x=0$,$3x_1+5x_2=0$,然后使用LLL向量找到最短的x=(5,-3)或(-5,3)
exp
from pwn import *
from sage.all import *
conn = process(["python3", "task.py"])
A = eval(conn.recvline().decode().strip())
b = eval(conn.recvline().decode().strip())
A = Matrix(ZZ, A)
b = Matrix(ZZ, b).T
ker_b = b.kernel().basis_matrix()
A = ker_b*A
ker_A = A.transpose().kernel().basis_matrix()
ker_A = ker_A.LLL()
solution = [abs(int(i)) for i in ker_A[0]]
conn.sendline(' '.join(map(str, solution)).encode())
conn.recvline()
flag = conn.recvline().decode('utf-8').strip()
print(flag)
conn.close()
我自己解的思路是这样的，
采用增广矩阵解线性方程,引入s表示b的系数，那么式子将会是
增广矩阵的右零空间是
存在等式
所以我们要求的解$x=-\frac{x}{s}$,所以要求我们在零空间找到一个向量满足s不等于0，并且x/-s 在[1,114514]区间
我们对右零空间BKZ规约找到范数小的右零空间，得到短向量就可以求解了
exp
from sage.all import *
from Pwn4Sage.pwn import remote
import ast
import time
def solve_problem():
# 建立网络连接
try:
connection_str = f"[+] 连接到服务器: challenge.xinshi.fun:43767"
print(connection_str)
network_io = remote("challenge.xinshi.fun", 43767)
except Exception as connection_error:
print(f"[-] 连接错误: {connection_error}")
return
# 获取输入数据
try:
recv_data = network_io.recvuntil(b"Enter your solution:").decode().split('\n')
print("[+] 接收数据完成:")
print(recv_data)
except Exception as recv_error:
print(f"[-] 数据接收异常: {recv_error}")
network_io.close()
return
# 矩阵向量解析
try:
coefficient_matrix = matrix(ZZ, ast.literal_eval(recv_data[0].strip()))
target_vector = vector(ZZ, ast.literal_eval(recv_data[1].strip()))
print("[+] 系数矩阵和向量解析成功")
print(f"[+] 系数矩阵: {coefficient_matrix}")
print(f"[+] 目标向量: {target_vector}")
except Exception as parse_error:
print(f"[-] 解析错误: {parse_error}")
network_io.close()
return
# 构造增广矩阵
augmented_mat = coefficient_matrix.augment(target_vector, subdivide=True)
# 计算零空间
start_timer = time.time()
nullspace = augmented_mat.right_kernel()
print(f"[+] 零空间维度: {nullspace.dimension()}")
print(f"[+] 零空间计算耗时: {time.time() - start_timer} 秒")
if nullspace.dimension() == 0:
print("[-] 零空间为空")
network_io.close()
return
# 基约简过程
base_vectors = matrix(ZZ, nullspace.basis())
start_timer = time.time()
reduced_base = base_vectors.BKZ(block_size=30) # BKZ参数设置
print(f"[+] 基约简耗时: {time.time() - start_timer} 秒")
# 搜索最优解向量
best_norm_value = None
optimal_vector = None
for current_vec in reduced_base:
constant_term = current_vec[-1] # 最后一项是常数项
if constant_term == 0:
continue
norm_value = current_vec.norm()
print(f"[+] 向量检查: {current_vec}, 范数: {norm_value}, 常数项: {constant_term}")
if best_norm_value is None or norm_value < best_norm_value:
best_norm_value = norm_value
optimal_vector = current_vec
if optimal_vector is None:
print("[-] 未发现有效解向量")
network_io.close()
return
# 计算特解
scalar = optimal_vector[-1]
solution_vector = (-vector(optimal_vector[:-1])).apply_map(lambda element: element / scalar)
# 验证解
print(f"[+] 计算解: {solution_vector}")
if coefficient_matrix * solution_vector == target_vector:
print("[+] 解验证通过")
# 检查范围约束
int_solution = [int(num) for num in solution_vector]
if all(1 <= val <= 114514 for val in int_solution):
print("[+] 解满足约束条件")
# 格式化输出
solution_str = " ".join(map(str, int_solution))
print(f"[+] 提交解: {solution_str}")
try:
network_io.sendline(solution_str.encode())
# 获取响应
server_response = ""
response_timer = time.time()
while time.time() - response_timer < 5:
data_chunk = network_io.recv(4096).decode()
if not data_chunk:
break
server_response += data_chunk
print("[+] 服务端响应:", server_response)
except Exception as io_error:
print(f"[-] 通信错误: {io_error}")
else:
print("[-] 解超出允许范围")
else:
print("[-] 解验证失败")
network_io.close()
if __name__ == "__main__":
solve_problem()
#LILCTF{9344030e-7ce1-4f31-bf82-5627b4fe8765}
还有一种方法，就是LilCTF 2025 - SeanDictionary | 折腾日记用背包密码解法
from fpylll import IntegerMatrix, LLL, FPLLL
from Crypto.Util.number import *
import random
from pwn import *
import ast
# import re
def process_matrices(matrix1, matrix2):
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)]
A = matrix1
b = matrix2
K = 1000000
# print(f"A = {A}")
# print(f"b = {b}")
# print(f"x = {x}")
dim = nrows + ncols
M = IntegerMatrix(dim, dim)
for i in range(ncols):
M[i, i] = 1
for j in range(nrows):
M[i, ncols + j] = A[j][i] * K
for j in range(nrows):
M[ncols, ncols + j] = -b[j] * K
L = LLL.reduction(M)
for line in M:
line = list(line)
if all(x == 0 for x in line[ncols:]) and all(x != 0 for x in line[:ncols]):
# print(f"x = {line[:ncols]}")
return line[:ncols]
def parse_matrix(matrix_str):
"""将字符串形式的矩阵解析为二维列表"""
# 去除空行并分割每行
lines = [line.strip() for line in matrix_str.strip().split("\n") if line.strip()]
# 分割每行元素并转换为整数
return [list(map(int, line.split())) for line in lines]
def format_matrix(matrix):
"""将二维列表格式化为字符串形式的矩阵"""
return "\n".join([" ".join(map(str, row)) for row in matrix]) + "\n"
def main():
# 配置连接信息
host = "challenge.xinshi.fun" # 替换为目标主机地址
port = 42749 # 替换为目标端口
# 建立连接
try:
io = remote(host, port)
print(f"成功连接到 {host}:{port}")
except Exception as e:
print(f"连接失败: {e}")
return
try:
# io.interactive()
# 接收第一个矩阵
print("接收第一个矩阵...")
matrix1_str = io.recvline().decode().strip()
matrix1 = ast.literal_eval(matrix1_str)
# 接收第二个矩阵
print("接收第二个矩阵...")
matrix2_str = io.recvline().decode().strip()
matrix2 = ast.literal_eval(matrix2_str)
# 等待服务器提示
print(io.recvuntil(":").decode().strip())
# 处理矩阵
print("处理矩阵中...")
result_matrix = process_matrices(matrix1, matrix2)
print(result_matrix)
# 发送结果矩阵
print("发送结果矩阵...")
result_str = " ".join(map(str, result_matrix))
io.sendline(result_str.encode())
# 等待服务器提示
print(io.recvline())
io.interactive()
# 可以根据需要接收服务器的响应
# response = p.recvall().decode()
# print(f"服务器响应: {response}")
except Exception as e:
print(f"处理过程中出错: {e}")
finally:
# 关闭连接
io.close()
print("\n连接已关闭")
if __name__ == "__main__":
main()
mid_math
from sage.all import *
from Crypto.Util.number import *
flag = b'LILCTF{test_flag}'[7:-1]
lambda1 = bytes_to_long(flag[:len(flag)//2])
lambda2 = bytes_to_long(flag[len(flag)//2:])
p = getPrime(512)
def mul(vector, c):
return [vector[0]*c, vector[1]*c]
v1 = [getPrime(128), getPrime(128)]
v2 = [getPrime(128), getPrime(128)]
A = matrix(GF(p), [v1, v2])
B = matrix(GF(p), [mul(v1,lambda1), mul(v2,lambda2)])
C = A.inverse() * B
print(f'p = {p}')
print(f'C = {str(C).replace(" ", ",").replace("\n", ",").replace("[,", "[")}')
所以C和D相似，所以它们的特征值相等，所以求C的特征值就是flag
mid_math
task.py
from sage.all import *
from Crypto.Util.number import *
from tqdm import tqdm
from random import randint
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
flag = b'LILCTF{test_flag}'
p = getPrime(64)
P = GF(p)
key = randint(2**62, p)
def mul(vector, c):
return [vector[0]*c, vector[1]*c, vector[2]*c, vector[3]*c, vector[4]*c]
v1 = [getPrime(64), getPrime(64), getPrime(64), getPrime(64), getPrime(64)]
v2 = [getPrime(64), getPrime(64), getPrime(64), getPrime(64), getPrime(64)]
v3 = [getPrime(64), getPrime(64), getPrime(64), getPrime(64), getPrime(64)]
v4 = [getPrime(64), getPrime(64), getPrime(64), getPrime(64), getPrime(64)]
v5 = [getPrime(64), getPrime(64), getPrime(64), getPrime(64), getPrime(64)]
a, b, c, d, e = getPrime(64), getPrime(64), getPrime(64), getPrime(64), 0
A = matrix(P, [v1, v2, v3, v4, v5])
B = matrix(P, [mul(v1,a), mul(v2,b), mul(v3, c), mul(v4, d), mul(v5, e)])
C = A.inverse() * B
D = C**key
key = pad(long_to_bytes(key), 16)
aes = AES.new(key,AES.MODE_ECB)
msg = aes.encrypt(pad(flag, 64))
print(f"p = {p}")
print(f'C = {[i for i in C]}'.replace('(', '[').replace(')', ']'))
print(f'D = {[i for i in D]}'.replace('(', '[').replace(')', ']'))
print(f"msg = {msg}")
#p = 14668080038311483271
#C = [[11315841881544731102, 2283439871732792326, 6800685968958241983, 6426158106328779372, 9681186993951502212], [4729583429936371197, 9934441408437898498, 12454838789798706101, 1137624354220162514, 8961427323294527914], [12212265161975165517, 8264257544674837561, 10531819068765930248, 4088354401871232602, 14653951889442072670], [6045978019175462652, 11202714988272207073, 13562937263226951112, 6648446245634067896, 13902820281072641413], [1046075193917103481, 3617988773170202613, 3590111338369894405, 2646640112163975771, 5966864698750134707]]
#D = [[1785348659555163021, 3612773974290420260, 8587341808081935796, 4393730037042586815, 10490463205723658044], [10457678631610076741, 1645527195687648140, 13013316081830726847, 12925223531522879912, 5478687620744215372], [9878636900393157276, 13274969755872629366, 3231582918568068174, 7045188483430589163, 5126509884591016427], [4914941908205759200, 7480989013464904670, 5860406622199128154, 8016615177615097542, 13266674393818320551], [3005316032591310201, 6624508725257625760, 7972954954270186094, 5331046349070112118, 6127026494304272395]]
#msg = b"\xcc]B:\xe8\xbc\x91\xe2\x93\xaa\x88\x17\xc4\xe5\x97\x87@\x0fd\xb5p\x81\x1e\x98,Z\xe1n`\xaf\xe0%:\xb7\x8aD\x03\xd2Wu5\xcd\xc4#m'\xa7\xa4\x80\x0b\xf7\xda8\x1b\x82k#\xc1gP\xbd/\xb5j"
和ez_math一样，只不过这里增加了$D=C^{key}$，也就是矩阵的离散对数问题
exp
# 文件名: calculate_keys.sage
# 运行方式: sage calculate_keys.sage
from sage.all import *
# --- 已知信息 ---
p = 14668080038311483271
C_list = [[11315841881544731102, 2283439871732792326, 6800685968958241983, 6426158106328779372, 9681186993951502212], [4729583429936371197, 9934441408437898498, 12454838789798706101, 1137624354220162514, 8961427323294527914], [12212265161975165517, 8264257544674837561, 10531819068765930248, 4088354401871232602, 14653951889442072670], [6045978019175462652, 11202714988272207073, 13562937263226951112, 6648446245634067896, 13902820281072641413], [1046075193917103481, 3617988773170202613, 3590111338369894405, 2646640112163975771, 5966864698750134707]]
D_list = [[1785348659555163021, 3612773974290420260, 8587341808081935796, 4393730037042586815, 10490463205723658044], [10457678631610076741, 1645527195687648140, 13013316081830726847, 12925223531522879912, 5478687620744215372], [9878636900393157276, 13274969755872629366, 3231582918568068174, 7045188483430589163, 5126509884591016427], [4914941908205759200, 7480989013464904670, 5860406622199128154, 8016615177615097542, 13266674393818320551], [3005316032591310201, 6624508725257625760, 7972954954270186094, 5331046349070112118, 6127026494304272395]]
# 1. 设置 SageMath 的有限域和矩阵
P = GF(p)
C_mat = matrix(P, C_list)
D_mat = matrix(P, D_list)
print("[SAGE] 正在计算矩阵 C 和 D 的特征值...")
# 2. 计算特征值并过滤掉 0
C_eigenvalues = [v for v in C_mat.eigenvalues() if v != 0]
D_eigenvalues = [v for v in D_mat.eigenvalues() if v != 0]
print(f"[SAGE] C 的非零特征值: {C_eigenvalues}")
print(f"[SAGE] D 的非零特征值: {D_eigenvalues}")
# 3. 遍历所有可能的特征值配对，求解离散对数
potential_keys = set() # 使用集合来自动去重
for c_eig in C_eigenvalues:
for d_eig in D_eigenvalues:
try:
# 求解离散对数: d_eig = c_eig ^ key
key_candidate = d_eig.log(c_eig)
potential_keys.add(int(key_candidate))
except (ValueError, TypeError):
# 如果配对不正确，log 会失败
continue
# 文件名: decrypt_flag.py
# 运行方式: python decrypt_flag.py
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from Crypto.Util.number import long_to_bytes
# --- 已知信息 ---
msg = b"\xcc]B:\xe8\xbc\x91\xe2\x93\xaa\x88\x17\xc4\xe5\x97\x87@\x0fd\xb5p\x81\x1e\x98,Z\xe1n`\xaf\xe0%:\xb7\x8aD\x03\xd2Wu5\xcd\xc4#m'\xa7\xa4\x80\x0b\xf7\xda8\x1b\x82k#\xc1gP\xbd/\xb5j"
# --- 开始解密 ---
print("[PYTHON] 开始尝试使用候选 Key 进行解密...")
found = False
for key_int in potential_keys:
try:
print(f"\n[*] 正在尝试 Key: {key_int}")
# 1. 准备 AES 密钥
aes_key = pad(long_to_bytes(key_int), 16)
# 2. 创建解密器并解密
cipher = AES.new(aes_key, AES.MODE_ECB)
decrypted_padded = cipher.decrypt(msg)
# 3. 反填充
# 原始脚本使用 pad(flag, 64)，所以 unpad 时 block_size 也是 64
decrypted = unpad(decrypted_padded, 64)
# 4. 验证解密结果
if decrypted.startswith(b'LILCTF{'):
print("\n" + "="*50)
print(f"[SUCCESS] 找到正确的 Key: {key_int}")
print(f"[SUCCESS] 解密成功! Flag 是: {decrypted.decode()}")
print("="*50)
found = True
break
else:
print(f"[-] 解密内容不正确: {decrypted}")
except Exception as e:
# 可能是 unpad 错误，说明 key 不正确
print(f"[-] 解密或反填充失败: {e}")
continue
if not found:
print("\n[FAIL] 遍历了所有候选 Key，但未能解密 Flag。")
后面发现还是做麻烦了
直接使用矩阵DLP板子
from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
p = 14668080038311483271
C = [[11315841881544731102, 2283439871732792326, 6800685968958241983, 6426158106328779372, 9681186993951502212], [4729583429936371197, 9934441408437898498, 12454838789798706101, 1137624354220162514, 8961427323294527914], [12212265161975165517, 8264257544674837561, 10531819068765930248, 4088354401871232602, 14653951889442072670], [6045978019175462652, 11202714988272207073, 13562937263226951112, 6648446245634067896, 13902820281072641413], [1046075193917103481, 3617988773170202613, 3590111338369894405, 2646640112163975771, 5966864698750134707]]
D = [[1785348659555163021, 3612773974290420260, 8587341808081935796, 4393730037042586815, 10490463205723658044], [10457678631610076741, 1645527195687648140, 13013316081830726847, 12925223531522879912, 5478687620744215372], [9878636900393157276, 13274969755872629366, 3231582918568068174, 7045188483430589163, 5126509884591016427], [4914941908205759200, 7480989013464904670, 5860406622199128154, 8016615177615097542, 13266674393818320551], [3005316032591310201, 6624508725257625760, 7972954954270186094, 5331046349070112118, 6127026494304272395]]
msg = b"\xcc]B:\xe8\xbc\x91\xe2\x93\xaa\x88\x17\xc4\xe5\x97\x87@\x0fd\xb5p\x81\x1e\x98,Z\xe1n`\xaf\xe0%:\xb7\x8aD\x03\xd2Wu5\xcd\xc4#m'\xa7\xa4\x80\x0b\xf7\xda8\x1b\x82k#\xc1gP\xbd/\xb5j"
n = 5
G = matrix(GF(p), n, n, C)
H = matrix(GF(p), n, n, D)
G_Jor, P = G.jordan_form(transformation=True)
H_Jor = ~P * H * P
print(G_Jor, H_Jor)
key = discrete_log(H_Jor[1][1], G_Jor[1][1], p-1)
key = pad(long_to_bytes(key), 16)
aes = AES.new(key,AES.MODE_ECB)
flag = aes.decrypt(pad(msg, 64))
print(flag)
# b'LILCTF{Are_y0u_5till_4wake_que5t1on_m4ker!}\x15\x15\x15\x15\x15\x15\x15\x15\x15\x15\x15\x15\x15\x15\x15\x15\x15\x15\x15\x15\x15\xd5\x98\x0f\xd7\xa1\x05\xe8%b:\xb7\x96\xc6\xaf\x05\x1b\xd5\x98\x0f\xd7\xa1\x05\xe8%b:\xb7\x96\xc6\xaf\x05\x1b\xd5\x98\x0f\xd7\xa1\x05\xe8%b:\xb7\x96\xc6\xaf\x05\x1b\xd5\x98\x0f\xd7\xa1\x05\xe8%b:\xb7\x96\xc6\xaf\x05\x1b'
Space Travel
task.py
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()))
还没弄懂..