Unwind On Vacation

题目

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
from ast import literal_eval
from hashlib import shake_128
import secrets

FLAG = "flag{redacted}"

def Hash(msg):
    h = int(shake_128(msg).hexdigest(3*m),16)
    return vector(GF(q),[(h:=h//q)%q if i else h%q for i in range(m)])
#h=a0+a1q+a2q^2+...    H(msg)=(a0,a1,a2,...)

class UOV:
    def __init__(self, m, n, q):
        self.params = (m, n, q)
        self.pub = None
        self.O = random_matrix(ZZ, n-m, m)  #矩阵O较小
        self.refresh()

    def keygen(self):
        set_random_seed(seed:=secrets.randbits(128))  #生成一个128位的随机种子
        print("🌻", seed)      #种子已知
        m, n, q = self.params
        F = GF(q)
        Ps = []
        for _ in range(m):
            P1 = random_matrix(F, n-m, n-m)
            P2 = random_matrix(F, n-m, m)
            P3 = (-self.O.T*P1*self.O-self.O.T*P2)    #P3=-OT*P1*O-OT*P2
            P = block_matrix(F, [[P1, P2], [zero_matrix(F, m, n-m), P3]])
            print(P3.list())
            Ps.append(P)
        set_random_seed(secrets.randbits(128))
        return Ps

    def refresh(self):
        self.pub = self.keygen()

    def sign(self, msg):
        if msg == "Unwind On Vacation": return None
        m, n, q = self.params
        F = GF(q)
        O = block_matrix(F, 2, 1, [self.O, identity_matrix(F, m)])
        v = random_vector(F, n, 1)
        M = matrix(F, [v*(self.pub[i]+self.pub[i].T)*O for i in range(m)])
        u = Hash(msg.encode())-vector([(v*self.pub[i]*v) for i in range(m)])
        return v+O*M.solve_right(u)

    def verify(self, msg, token):
        msg = Hash(msg.encode())
        t = vector(token)
        for i in range(self.params[0]):
            if t*self.pub[i]*t != msg[i]:
                return False
        return True

m, n = 73, 180
q = 0x10001
uov = UOV(m, n, q)
__import__("signal").alarm(1200)
for _ in range(80):
    match input("> "):
        case "R": uov.refresh()  #生成一组P
        case "S": print(f"{uov.sign(input("💬 "))}")     #请求签名，得到一个180维向量
        case "V": print("🚩", uov.verify("Unwind On Vacation",
                                        literal_eval(input("📝 ")))*FLAG)

思路

题目原理：

6e8ab878e212737179ad65ed5ef1ca4d.jpeg

解题思路：刷新密钥但私钥不变

f4197045184043826c42b54f3b80d740.jpeg

对于o1,将它线性化会有$\frac{(n-m)(n-m-1)}{2}+2（n-m)=5885个变量，题目可以收集到80m=5840个方程，那么解空间还有q^{45}，O中元素均为小整数，利用LLL恢复O_1，又O_1P_iO_2=0进而求出O$

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
# exp.sage
from ast import literal_eval
from hashlib import shake_128
import secrets
from pwn import process, remote, context
import re
from tqdm import trange, tqdm

context.log_level = "error"
path = "task.sage"
io = process(["sage", path])
m, n = 73, 180
q = 0x10001
F = GF(q)

#接受并重建公钥
def recvpk():
    io.recvuntil("🌻 ".encode())
    seed = int(io.recvline())
    set_random_seed(seed)
    pk = []
    for _ in range(m):
        P1 = random_matrix(F, n-m, n-m)
        P2 = random_matrix(F, n-m, m)
        P3 = matrix(F, m, m, literal_eval(io.recvline().decode()))
        pk.append(block_matrix([[P1, P2], [0, P3]]))
    return pk

#多次刷新收集公钥
pks = []
pks.extend(recvpk())
for i in trange(79):
    io.sendlineafter(b"> ", b"R")
    pks.extend(recvpk())

A = []
u = []
for pk in tqdm(pks):
    # pk = pks[ind]
    v = []
    for i in range(n - m):
        for j in range(i, n - m):
            if i == j:
                v.append(pk[i, j])
            else:
                v.append(pk[i, j] + pk[j, i])
    for i in range(n - m):
        v.append(pk[i, n-m])
    A.append(v)
    u.append(-pk[n - m, n - m])

A = matrix(F, A)
u = vector(F, u)

#只要xi
v = A.solve_right(u)[-(n - m):].change_ring(ZZ)
Ker = A.right_kernel_matrix()[:, -(n - m):].change_ring(ZZ)
#齐次解空间的最后107个坐标

H = Ker.change_ring(F).echelon_form().change_ring(ZZ)
M = H.stack(v).stack(q * identity_matrix(Ker.ncols()))
M = M.augment(column_matrix([0] * M.nrows()))
M[Ker.nrows(), -1] = 32

ML = M.LLL()
for i in range(ML.nrows()):
    if abs(ML[i][-1]) == 32:
        o1 = ML[i] * (ML[i][-1]) / 32
        o1 = o1[:-1].list() + [1] + [0] * (m - 1)
        break

o1 = vector(F, o1)
print(o1)
assert o1*pks[0]*o1 == 0

M = []
for pk in tqdm(pks):
    M.append(o1 * pk)
M = matrix(F, M)
O = M.right_kernel_matrix().T

def Hash(msg):
    h = int(shake_128(msg).hexdigest(3*m),16)
    return vector(GF(q),[(h:=h//q)%q if i else h%q for i in range(m)])

def sign(msg, O, pks):
    v = random_vector(F, n, 1)
    M = matrix(F, [v*(pks[i]+pks[i].T)*O for i in range(m)])
    u = Hash(msg.encode())-vector([(v*pks[i]*v) for i in range(m)])
    return v+O*M.solve_right(u)

pub = pks[-m:]
io.sendlineafter("> ", "V")
io.sendlineafter("📝 ".encode(), str(list(sign("Unwind On Vacation", O, pub))).encode())
print(io.recvall(3))

参考:2025京麒CTF挑战赛-Crypto复现🙏🏻