Misay's blog

LILCTF2025

发表于 分类于
LILCTF2025CryptoWP

题目比较友好适中，成功AK了，鸡块师傅出的Space_Travel很有意思

ez_math

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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("[,", "[")}')

# p = 9620154777088870694266521670168986508003314866222315790126552504304846236696183733266828489404860276326158191906907396234236947215466295418632056113826161
# C = [7062910478232783138765983170626687981202937184255408287607971780139482616525215270216675887321965798418829038273232695370210503086491228434856538620699645,7096268905956462643320137667780334763649635657732499491108171622164208662688609295607684620630301031789132814209784948222802930089030287484015336757787801],[7341430053606172329602911405905754386729224669425325419124733847060694853483825396200841609125574923525535532184467150746385826443392039086079562905059808,2557244298856087555500538499542298526800377681966907502518580724165363620170968463050152602083665991230143669519866828587671059318627542153367879596260872]


模环下两个矩阵给出

给出 也就是 知道 是一定符合要求的 那么可知和是相似矩阵，计算特征值即可还原

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
from Crypto.Util.number import long_to_bytes

p = 9620154777088870694266521670168986508003314866222315790126552504304846236696183733266828489404860276326158191906907396234236947215466295418632056113826161

C_list = [
    [7062910478232783138765983170626687981202937184255408287607971780139482616525215270216675887321965798418829038273232695370210503086491228434856538620699645, 7096268905956462643320137667780334763649635657732499491108171622164208662688609295607684620630301031789132814209784948222802930089030287484015336757787801],
    [7341430053606172329602911405905754386729224669425325419124733847060694853483825396200841609125574923525535532184467150746385826443392039086079562905059808, 2557244298856087555500538499542298526800377681966907502518580724165363620170968463050152602083665991230143669519866828587671059318627542153367879596260872]
]

F = GF(p)

C = matrix(F, C_list)

eigenvalues = C.eigenvalues()

lambda1, lambda2 = eigenvalues

part1 = long_to_bytes(int(lambda1))
part2 = long_to_bytes(int(lambda2))


flag = b'LILCTF{' + part1+part2 + b'}'

print(flag)
# b'LILCTF{It_w4s_the_be5t_of_times_1t_wa5_the_w0rst_of_t1me5}'

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)

生成一个的矩阵,一个列向量 ，然后计算 把告诉你，让你去解

这里因为方程组是缺省的，无法直接求逆解出来，但这边相对是相对小的量，考虑格基归约，我们知道 不难造格子 同时乘上一个大的常数来保证我们的后面基全部取0

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

HOST = 'challenge.xinshi.fun'
PORT = 36459
nrows = 16
ncols = 32
C = 2**20


io = remote(HOST, PORT)

A_str = io.recvline().strip().decode()

b_str = io.recvline().strip().decode()

A_list = ast.literal_eval(A_str)
b_list = ast.literal_eval(b_str)

A = matrix(ZZ, A_list)
b = vector(ZZ, b_list)

M = matrix(ZZ, ncols + 1, ncols + nrows)

for i in range(ncols):
    M[i, i] = 1
    for j in range(nrows):
        M[i, j + ncols] = C * A[j][i]

for i in range(nrows):
    M[-1, i + ncols] = C * (-b[i])


B_reduced = M.LLL()
solution_x = None

for row_vec in B_reduced:
    if all(val == 0 for val in row_vec[ncols:]):
        solution_x = list(row_vec[:ncols])
        break

if solution_x is None:
    io.close()
    exit()


submit_string = " ".join(map(str, solution_x))


io.sendlineafter(b"Enter your solution: ", submit_string.encode())

response = io.recvall(timeout=2).decode()
print(response)

io.close()

# Bravo! Here is your flag:
# LILCTF{1c2b5b26-08eb-4a48-ac29-b4c14fba19d1}

mid_math

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 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类似，给出

同上和 相似，而且满足 再给出 相似矩阵的幂乘是一样算的，直接用即可，也就是说计算的特征矩阵就能得到 然后解离散对数去求即可，而且这里还挺光滑，直接解即可 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
from Crypto.Util.number import long_to_bytes
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad

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]]
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"

P = GF(p)
C = matrix(P, C_list)
D = matrix(P, D_list)

eigenvalues_C = C.eigenvalues()
eigenvalues_D = D.eigenvalues()

c_val = next(val for val in eigenvalues_C if val != 0)

key = None
for d_val in eigenvalues_D:
    if d_val == 0:
        continue
    potential_key = discrete_log(d_val, c_val)

    c_val_2 = next(val for val in eigenvalues_C if val != 0 and val != c_val)
    if c_val_2^potential_key in eigenvalues_D:
        key = potential_key
        print(f"key: {key}")
        break

aes_key_bytes = long_to_bytes(int(key))
aes_key = pad(aes_key_bytes, 16)

cipher = AES.new(aes_key, AES.MODE_ECB)
decrypted_padded_flag = cipher.decrypt(msg)
flag = unpad(decrypted_padded_flag, AES.block_size * 4) 

print(f"\nDecrypted Flag: {flag.decode()}")

# LILCTF{Are_y0u_5till_4wake_que5t1on_m4ker!}

SpaceTravel

1
2
3
4
5
6
7
8
9
10
11
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(len(set(vecs)))

# 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()))

给定一个16位的线性空间vecs,vecs中有组数据，随后我们选50个向量，拼接组合出key，然后题目给你600组800比特的nonce，计算 的01比特和，给出了模2的结果，相当于一组模方程 有600组 肯定没法考虑解方程了，而且维度过高也很难去考虑做格基归约

我们来观察这个线性空间，16位的向量应该有种可能，为什么只有组数据？，这就说明在16位的向量里面不是所有信息都是独立有效的，存在冗余，

我们先尝试找到线性空间的基，比如就取，随后对剩下的组别的,去进行异或回来 直到我们集齐12组线性无关向量即可组成一组基

看上面的构造可能有点诡异，我们从构造来说构造一个的线性01空间，然后按照某种规律去计算后四位的冗余位，造就了我们16位但是个数是的vecs，也就是说，看似是800位，但是实际上200位都是冗余计算出来的，给了我们600组同余方程实际上是刚刚好，我们接下来的工作就是如何从这里的600组方程拓展出剩下的200组

首先我们先准确描述这个冗余拓展的过程 基就是我们这边收集12个向量组成的，收集到这个基之后，我们能利用这个线性空间的延展构造出一个校验方程,那对于所有的vecs中的向量，有 这样就构造出了新的方程，exp思路如下

第一部分 从vecs中获得空间基

第二部分 从基构造出检验矩阵H

第三部分 从检验矩阵中构造出剩下的200个方程

第四部分 解方程 求出密钥key

第五部分 由key解密AES恢复flag

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
from Crypto.Cipher import AES
from hashlib import md5
from typing import List, Set, Tuple, Optional

from params import vecs
gifts =  [...]

encrypted_flag = b'r\x9f\xa5N\x19\xa3\x8b-\xfen\xa7\xc9\xca\x87\x04\x873#ju\xc5\x06\xd0\x85L\x1ab\xa1XEre\xe5\x8c:h'

# --------------------------part1----------------------------------

def verify_linear_code(vecs_int: Set[int]) -> Optional[List[int]]:
    if 0 not in vecs_int: return None
    basis: List[int] = []
    span: Set[int] = {0}
    sorted_vecs = sorted(list(vecs_int))
    for v_int in sorted_vecs:
        if v_int not in span:
            basis.append(v_int)
            new_vectors = {v_int ^ s for s in span}
            span.update(new_vectors)
    if len(span) == len(vecs_int): return basis
    return None

def find_basis_and_shift(vecs_str: List[str]) -> Optional[Tuple[List[int], int]]:
    if not vecs_str: return None
    vecs_int = {int(v, 2) for v in vecs_str}
    shift_vector_c = int(vecs_str[0], 2)
    l_prime = {v ^ shift_vector_c for v in vecs_int}
    basis = verify_linear_code(l_prime)
    if basis: return (basis, shift_vector_c)
    return None

result = find_basis_and_shift(vecs)

basis_vectors_int, shift_vector_c_int = result
num_bits = len(vecs[0])
dimension = len(basis_vectors_int)
print(f"c: {format(shift_vector_c_int, 'b').zfill(num_bits)}")


# --------------------------part2----------------------------------

F = GF(2)
basis_vectors = [vector(F, format(b, 'b').zfill(num_bits)) for b in basis_vectors_int]
G = matrix(F, basis_vectors)
L = LinearCode(G)
H = L.parity_check_matrix()


# --------------------------part3----------------------------------

c_vec = vector(F, format(shift_vector_c_int, 'b').zfill(num_bits))
s = H * c_vec

# --------------------------part4----------------------------------

N_VARS = 800
N_LPN = len(gifts)
N_CODE = H.nrows() * (N_VARS // num_bits) # 4 * 50 = 200

M = matrix(F, N_VARS, N_VARS)
R = vector(F, N_VARS)

for i in range(N_LPN):
    nonce, result = gifts[i]
    nonce_bits = [int(b) for b in format(nonce, 'b').zfill(N_VARS)]
    M[i] = vector(F, nonce_bits)
    R[i] = result


row_offset = N_LPN
for j in range(N_VARS // num_bits):  # 遍历 50 个密钥块
    for i in range(H.nrows()): # 每个块提供 4 个方程
        h_row = H.row(i)
        # 将 h_row 的系数放置到 M 矩阵的正确位置上
        for bit_pos in range(num_bits):
            M[row_offset, j*num_bits + bit_pos] = h_row[bit_pos]
        R[row_offset] = s[i]
        row_offset += 1

key_bits = M.solve_right(R)


# --------------------------part5----------------------------------

key_str = "".join(map(str, key_bits))
recovered_key_int = int(key_str, 2)
print(f"key: {recovered_key_int}")

aes_key = md5(str(recovered_key_int).encode()).digest()

cipher = AES.new(key=aes_key, nonce=b"Tiffany", mode=AES.MODE_CTR)

decrypted_flag = cipher.decrypt(encrypted_flag)

print(f"Flag: {decrypted_flag.decode()}")

# Flag: LILCTF{Un1qUe_s0luti0n_1N_sUbSp4C3!}

baaaaaaaag

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
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 = [965032030645819473226880279, 699680391768891665598556373, 1022177754214744901247677527, 680767714574395595448529297, 1051144590442830830160656147, 1168660688736302219798380151, 796387349856554292443995049, 740579849809188939723024937, 940772121362440582976978071, 787438752754751885229607747, 1057710371763143522769262019, 792170184324681833710987771, 912844392679297386754386581, 906787506373115208506221831, 1073356067972226734803331711, 1230248891920689478236428803, 713426848479513005774497331, 979527247256538239116435051, 979496765566798546828265437, 836939515442243300252499479, 1185281999050646451167583269, 673490198827213717568519179, 776378201435505605316348517, 809920773352200236442451667, 1032450692535471534282750757, 1116346000400545215913754039, 1147788846283552769049123803, 994439464049503065517009393, 825645323767262265006257537, 1076742721724413264636318241, 731782018659142904179016783, 656162889354758353371699131, 1045520414263498704019552571, 1213714972395170583781976983, 949950729999198576080781001, 1150032993579134750099465519, 975992662970919388672800773, 1129148699796142943831843099, 898871798141537568624106939, 997718314505250470787513281, 631543452089232890507925619, 831335899173370929279633943, 1186748765521175593031174791, 884252194903912680865071301, 1016020417916761281986717467, 896205582917201847609656147, 959440423632738884107086307, 993368100536690520995612807, 702602277993849887546504851, 1102807438605649402749034481, 629539427333081638691538089, 887663258680338594196147387, 1001965883259152684661493409, 1043811683483962480162133633, 938713759383186904819771339, 1023699641268310599371568653, 784025822858960757703945309, 986182634512707587971047731, 1064739425741411525721437119, 1209428051066908071290286953, 667510673843333963641751177, 642828919542760339851273551, 1086628537309368288204342599, 1084848944960506663668298859, 667827295200373631038775959, 752634137348312783761723507, 707994297795744761368888949, 747998982630688589828284363, 710184791175333909291593189, 651183930154725716807946709, 724836607223400074343868079, 1118993538091590299721647899]
b = 34962396275078207988771864327
ciphertext = b'Lo~G\xf46>\xd609\x8e\x8e\xf5\xf83\xb5\xf0\x8f\x9f6&\xea\x02\xfa\xb1_L\x85\x93\x93\xf7,`|\xc6\xbe\x05&\x85\x8bC\xcd\xe6?TV4q'

一个背包格子问题，给出72位的，给出 同时我们的是已知的，可以用这个手法给降低一下格的维度，我们设新方程为

一般来说是造格子 但是格的效果很差，参考鸡块师傅的博客思路，可以对背包格进行如下优化

这样我们格出来的目标向量就是1，-1 数量级很接近，使用24格维度的BKZ就能解决了,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
from Crypto.Util.number import *
import random
from Crypto.Cipher import AES
import hashlib
from Crypto.Util.Padding import pad

a = [...]
b = 34962396275078207988771864327
ct = b'Lo~G\xf46>\xd609\x8e\x8e\xf5\xf83\xb5\xf0\x8f\x9f6&\xea\x02\xfa\xb1_L\x85\x93\x93\xf7,`|\xc6\xbe\x05&\x85\x8bC\xcd\xe6?TV4q'


# ------------------------------data process-----------------------------
aa = a[:-1]
bb = b - a[-1]
m = len(aa)
C = 2^100

# ------------------------------lattice construct-----------------------------
L = Matrix(ZZ, m+1, m+1)

for i in range(m):
    L[i, i] = 2
    L[i, -1] = aa[i]* C
    L[-1,i] = -1
L[-1, -1] = -bb*C

L = L.BKZ(block_size =24)
# L = L.LLL()
# print(L)

# ------------------------------search & verify-----------------------------
for idx, row in enumerate(L):
    if row[-1] == 0 and all(abs(i) <= 1 for i in row):
        prow = (list(row))[:-1]
        prow = prow[::-1]
        str_p = ""
        for i in prow:
            if i == 1:
                str_p += "1"
            elif i == -1:
                str_p += "0"
        str_p = '1' + str_p
        assert len(str_p) == 72
        candidate_p = int(str_p, 2)
        print(f"{idx}th pp = ", candidate_p)
        pb = 0
        t = candidate_p
        for i in a:
            temp = t % 2
            pb += temp * i
            t = t >> 1
        if pb == b:
            print(f"found p = ", candidate_p)
            p = candidate_p
            break

# ------------------------------decrypt-----------------------------
key = hashlib.sha256(str(p).encode()).digest()
cipher = AES.new(key, AES.MODE_ECB)
flag = cipher.decrypt(ct)
print(flag)
'''
0th pp =  4208626653103825685156
found p =  4208626653103825685156
b'LILCTF{M4ybe_7he_brut3_f0rce_1s_be5t}\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b'

'''