WMCTF2025 • Misay's blog

写在前面#

和DAWN的师傅们一起打了WMCTF2025 主要参与并负责了密码方向 SplitMaster&IshowSplit 两道以及 MISC方向 Pishing Mail的解出，各位学长都很给力，最终DAWN也是打进了前10，本文主要复现Crypto方向的5道赛题，以及MISC方向的两道赛题

Crypto#

SplitMaster#

task.py

from Crypto.Util.number import *
import socketserver
import socket

def split_master(B_decimal, segment_bits):
    if len(segment_bits) < 3:
        raise ValueError("no")
    
    if sum(segment_bits) != 512:
        raise ValueError("no")
    
    n = len(segment_bits)
    found_combination = None
    for k in range(n,1,-1):
        from itertools import combinations
        for indices in combinations(range(n), k):
            if sum(segment_bits[i] for i in indices) > 30:
                continue

            valid = True
            for i in range(len(indices)):
                for j in range(i+1, len(indices)):
                    if abs(indices[i] - indices[j]) <= 1:
                        valid = False
                        break
                if not valid:
                    break
            if not valid:
                continue

            if 0 in indices and (n-1) in indices:
                continue
            if any(segment_bits[i]>=25 for i in indices):
                continue
            found_combination = indices
            break
        
        if found_combination is not None:
            break
    
    if found_combination is None:
        raise ValueError("no")
    
    binary_str = bin(B_decimal)[2:].zfill(512)
    if len(binary_str) > 512:
        raise ValueError("no")

    segments_binary = []
    start = 0
    for bits in segment_bits:
        end = start + bits
        segments_binary.append(binary_str[start:end])
        start = end
    
    segments_decimal = [int(segment, 2) for segment in segments_binary]
    
    return [segments_decimal[i] for i in found_combination]

class Task(socketserver.BaseRequestHandler):
    def _recvall(self):
        BUFF_SIZE = 2048
        data = b''
        while True:
            part = self.request.recv(BUFF_SIZE)
            data += part
            if len(part) < BUFF_SIZE:
                break
        return data.strip()

    def send(self, msg, newline=True):
        try:
            if newline:
                msg += b'\n'
            self.request.sendall(msg)
        except:
            pass

    def recv(self, prompt=b'[-] '):
        self.send(prompt, newline=False)
        return self._recvall()

    def handle(self):
        # 设置socket超时而不是使用signal.alarm
        self.request.settimeout(90)  # 90秒超时
        
        try:
            flag = b'WMCTF{test}'
            self.send(b"Welcome to WMCTF2025")
            key = getPrime(512)
            print(key)
            q = getPrime(512)
            self.send(b"q:"+str(q).encode())
            for i in range(20):
                a = getPrime(512)
                b = a * key % q
                gift = split_master(b, list(map(int, self.recv(b"> ").split())))
                self.send(b"a:"+str(a).encode())
                self.send(b"gift:"+str(gift).encode())  
            x = self.recv(b"the key to the flag is: ").decode()
            if x == str(key):
                self.send(flag)
        except socket.timeout:
            self.send(b"Time's up!")
        finally:
            self.request.close()  # 确保连接被关闭


class ThreadedServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
    pass

if __name__ == "__main__":

    HOST, PORT = '0.0.0.0', 10003

    print("HOST:POST " + HOST + ":" + str(PORT))
    server = ThreadedServer((HOST, PORT), Task)
    server.allow_reuse_address = True
    server.serve_forever()

函数split_master会根据接收的数组以及数字返回有关传入数字的比特的信息保证总比特数不超过30 且连续比特长不超过24

我们需要利用20组已知的a和我们能得到的有关b的比特泄露gift求出私钥b

赛中想到利用构造 segment_bits = [10, 160, 10, 161, 10, 161],我们能将b比较均匀的拆成6个部分拥有离散的10*3的比特泄露

转化为随机位置泄露的HNP问题我们参考Tover师傅的博客板子 ↗

造格子然后去打即可，exp

from pwn import *
from Crypto.Util.number import inverse

# --- 配置 ---
HOST = '127.0.0.1'
PORT = 10003

# 43.138.4.37:31055

# 构造 segment_bits 以获取3个在512位空间中分布更均匀的10位信息。
# 总泄露位数仍然是30位。
segment_bits = [10, 160, 10, 161, 10, 161]
payload = " ".join(map(str, segment_bits)).encode()

# --- 连接服务器 ---
log.info(f"Connecting to {HOST}:{PORT}...")
try:
    sh = remote(HOST, PORT)
    log.success("Connection established!")
except PwnlibException as e:
    log.error(f"Failed to connect: {e}")
    log.error("Please make sure task.py is running in another terminal window!")
    exit()

# --- Step 1: 接收欢迎信息并提取 q ---
sh.recvuntil(b"q:")
q_str = sh.recvline().strip()
q = int(q_str)
log.success(f"Successfully retrieved q: {q}")

# --- Step 2: 初始化用于存储数据的列表 ---
a_list = []
bh1_list = []
bh2_list = []
bh3_list = []

# 循环20次来收集数据
for i in range(20):
    log.info(f"--- Round {i+1}/20 ---")
    
    sh.recvuntil(b"> ")
    sh.sendline(payload)
    log.info(f"Sent segment_bits: {payload.decode()}")
    
    sh.recvuntil(b"a:")
    a_str = sh.recvline().strip()
    a = int(a_str)
    
    sh.recvuntil(b"gift:")
    gift_str = sh.recvline().strip().decode()
    gift_list = eval(gift_str)

    sh.recvuntil(b"key:")
    key_str = sh.recvline().strip().decode()
    true_key = int(key_str)
    
    if len(gift_list) == 3:
        bh1, bh2, bh3 = gift_list
        log.info(f"Received gift: {gift_list}, extracted parts: bh1={bh1}, bh2={bh2}, bh3={bh3}")
        
        a_list.append(a)
        bh1_list.append(bh1)
        bh2_list.append(bh2)
        bh3_list.append(bh3)
    else:
        log.warning(f"Received an unexpected gift format: {gift_list}")


# 现在你可以直接使用 a_list, bh1_list, bh2_list, bh3_list 和 q 
# 来进行后续的密码分析。

length = 512
leak_length = 10
T1 = 2^(512-leak_length)
T2 = 2^(512-leak_length-160)
T3 = 2^(512-leak_length*2-160)
T4 = 2^(512-leak_length*2-160-161)
T5 = 2^(512-leak_length*3-160-161)
print(len(a_list))
inv_a0 = inverse_mod(a_list[0],q)


D = []
Ai = []
E = []
F = []

for i in range(1,20):
    A = a_list[i] * inv_a0
    Ai.append(A % q)
    D1 = bh1_list[i]*T1 - A*bh1_list[0]*T1
    D2 = bh2_list[i]*T3 - A*bh2_list[0]*T3
    D3 = bh3_list[i]*T5 - A*bh3_list[0]*T5
    D.append((D1+D2+D3) % q)
    E.append(A * T2 % q)
    F.append(A * T4 % q)

R = 2^161
n = 19

M = Matrix(ZZ,3*n+4)
for i in range(n):
    M[3*i,3*i] = -q
    M[3*i+1,3*i] = -T2
    M[3*i+2,3*i] = -T4
    M[3*i+1,3*i+1] = 1
    M[3*i+2,3*i+2] = 1

    M[-4,3*i] = Ai[i]
    M[-3,3*i] = F[i]
    M[-2,3*i] = E[i]
    M[-1,3*i] = D[i]

M[-4,-4] = 1
M[-3,-3] = 1
M[-2,-2] = 1
M[-1,-1] = R

L = M.BKZ(block_size=24)

key_candidate = []
for l in L:
    if l[-1]:
        b0 = vector(l)
        b01 = b0[-2]
        b03 = b0[-3]
        b05 = b0[-4]
        key = (bh1_list[0]*T1 + b01*T2 + bh2_list[0]*T3 + b03*T4 + bh3_list[0]*T5 + b05) * inv_a0 % q

        key_candidate.append(key)

print(key_candidate)
print(true_key)
# if true_key in key_candidate:
#     print("found")

# 43.138.4.37:31055

sh.sendlineafter(b"the key to the flag is: ", str(true_key).encode())
response= sh.recvall(timeout=2)
print(response)

python

格的参数还可以进一步优化大概有1/3的概率能找到key，本地出了后交给 Ramoor师傅 ↗用代码打远程成功出了，拿下二血

赛后看到别的师傅找到一个Trick

构造 -257 513 -257 513的序列

Welcome to WMCTF2025
q:9861430895025459477553092372852393541874339091269599286733236011532282532345396778429343483337130529182773612573595360674235802007820723008241118435213327
> -257 513 -257 513
a:10311738079985788524348250930378887840235618248819905021512068084058439869758091860311941760876644520871282741083309749114892507621255837856268626603123599
gift:[30524567771060486261423907587778820949788903093067527468240286198675156055398, 45779902845695456433368637342563313580177390291673538250967582387199430778996]

bash

能拿到510位b的比特那就很好做了多取几组打格子即可

IshowSplit#

task.py

from Crypto.Util.number import *

from hashlib import md5

def split_master(B_decimal, segment_bits):
    if len(segment_bits) < 3:
        raise ValueError("no")
    
    if sum(segment_bits) != 512:
        raise ValueError("no")
    
    n = len(segment_bits)
    found_combination = None
    for k in range(n,1,-1):
        from itertools import combinations
        for indices in combinations(range(n), k):
            if sum(segment_bits[i] for i in indices) > 30:
                continue

            valid = True
            for i in range(len(indices)):
                for j in range(i+1, len(indices)):
                    if abs(indices[i] - indices[j]) <= 1:
                        valid = False
                        break
                if not valid:
                    break
            if not valid:
                continue

            if 0 in indices and (n-1) in indices:
                continue
            
            if any(segment_bits[i]>=25 for i in indices):
                continue

            found_combination = indices
            break
        
        if found_combination is not None:
            break
    
    if found_combination is None:
        raise ValueError("no")
    
    binary_str = bin(B_decimal)[2:].zfill(512)
    if len(binary_str) > 512:
        raise ValueError("no")

    segments_binary = []
    start = 0
    for bits in segment_bits:
        end = start + bits
        segments_binary.append(binary_str[start:end])
        start = end
    
    segments_decimal = [int(segment, 2) for segment in segments_binary]
    
    return [segments_decimal[i] for i in found_combination]

p=getPrime(512)
key=randrange(1,p)
gift=split_master(key,[182,20,200,10,100])

flag="WMCTF{"+md5(str(key).encode()).hexdigest()+"}"

A=[]
B=[]
R=[]
M=[64, 128, 256]
for i in range(10):
    a=randrange(1,p)
    A.append(a)
    s=0
    rr=[]
    for j in range(3):
        r=randrange(1,p)
        k=randrange(1,2^M[j])
        s+=r*k%p
        rr.append(r)
    R.append(rr)
    B.append((a*key+s)%p)

print(f"p={p}")
print(f"A={A}")
print(f"B={B}")
print(f"R={R}")
print(f"gift={gift}")

类似上题是给定chunk泄露的HNP问题

通用的是造格子打的方法，这里关于noise的信息是

s_i\equiv r_{i,0}k_{i,0}+r_{i,1}k_{i,1}+r_{i,2}k_{i,2}\mod p

我们知道 $r_{i,j}$ 以及 $k_{i,j}$ 的范围上界，就不难想到把 $r_{i,j}$ 放到格子里面，用系数去配平 $k_{i,j}$ ，貌似这样就能出了，Polaris ↗的师傅就是这样做的再用gift来验证

详细说就是

B_i\equiv A_i\times key + s_i\mod p

消去 $key$ ，得到

A_iB_0-A_0B_i\equiv A_i(r_{0,0}k_{0,0}+r_{0,1}k_{0,1}+r_{0,2}k_{0,2})-A_0(r_{i,0}k_{i,0}+r_{i,1}k_{i,1}+r_{i,2}k_{i,2})\mod p

左边是已知量，记为 $C_i$ ,那么也就是

A_i(r_{0,0}k_{0,0}+r_{0,1}k_{0,1}+r_{0,2}k_{0,2})-A_0(r_{i,0}k_{i,0}+r_{i,1}k_{i,1}+r_{i,2}k_{i,2})-C_i-t_ip=0\;\;(i=1,\cdots,9)

我们想随便求出一组 $k_{i,0},k_{i,1},k_{i,2}$ 来恢复 $key$ ，那就把这里的

9个等于0的方程放在格子里面然后 $k$ 给放在右边，式子如下

\begin{bmatrix} k_{0,3} & k_{1,1} & k_{1,2} & k_{1,3} & k_{2,1} & k_{2,2} & k_{2,3} & \dots & k_{9,1} & k_{9,2} & k_{9,3} & -1 \end{bmatrix} \begin{bmatrix} p & 0 & \dots & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \dots & 0 & 0 & 0 \\ 0 & p & \dots & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \dots & 0 & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots & 0 & 0 & 0 \\ 0 & 0 & \dots & p & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \dots & 0 & 0 & 0 \\ A_1 r_{0,1} & A_2 r_{0,1} & \dots & A_9 r_{0,1} & 2^{192} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \dots & 0 & 0 & 0 \\ A_1 r_{0,2} & A_2 r_{0,2} & \dots & A_9 r_{0,2} & 0 & 2^{128} & 0 & 0 & 0 & 0 & 0 & 0 & \dots & 0 & 0 & 0 \\ A_1 r_{0,3} & A_2 r_{0,3} & \dots & A_9 r_{0,3} & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & \dots & 0 & 0 & 0 \\ -A_0 r_{1,1} & 0 & \dots & 0 & 0 & 0 & 0 & 2^{192} & 0 & 0 & 0 & 0 & \dots & 0 & 0 & 0 \\ -A_0 r_{1,2} & 0 & \dots & 0 & 0 & 0 & 0 & 0 & 2^{128} & 0 & 0 & 0 & \dots & 0 & 0 & 0 \\ -A_0 r_{1,3} & 0 & \dots & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & \dots & 0 & 0 & 0 \\ 0 & -A_0 r_{2,1} & \dots & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2^{192} & 0 & \dots & 0 & 0 & 0 \\ 0 & -A_0 r_{2,2} & \dots & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2^{128} & \dots & 0 & 0 & 0 \\ 0 & -A_0 r_{2,3} & \dots & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \dots & 0 & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots & 0 & 0 & 0 \\ 0 & 0 & \dots & -A_0 r_{9,1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \dots & 2^{192} & 0 & 0 \\ 0 & 0 & \dots & -A_0 r_{9,2} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \dots & 0 & 2^{128} & 0 \\ 0 & 0 & \dots & -A_0 r_{9,3} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \dots & 0 & 0 & 1 \\ C_1 & C_2 & \dots & C_9 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \dots & 0 & 0 & K \end{bmatrix} = \begin{bmatrix} 0 & 0 & \dots & 0 & k_{0,1} \times 2^{192} & k_{0,2} \times 2^{128} & k_{0,3} & k_{1,1} \times 2^{192} & k_{1,2} \times 2^{128} & k_{1,3} & k_{2,1} \times 2^{192} & k_{2,2} \times 2^{128} & k_{2,3} & \dots & k_{9,1} \times 2^{192} & k_{9,2} \times 2^{128} & k_{9,3} & K \end{bmatrix}

真的是很自然但又非常有效的思路感谢星盟的师傅们！

后续有参考官方的wp

给出了命题paperExtended Hidden Number Problem and Its Cryptanalytic Applications | SpringerLink ↗

命题的情景是

Definition1 即

\alpha_ix+\rho_ik_i\equiv\beta_i\mod p

的情况其中 $\alpha_i\;\beta_i\;\rho_i$ 我们都已知 $k_i$ 知道一个上界完美契合

在GPT师傅的帮助下实现了一个复现思路大致如下给定 $({(\alpha_i,\beta_i,\rho_i)}_{i=1}^d)$ 、 $(N=p)$ 、上界 $({2^{\mu_i}})$

设 $(\nu=\lceil\log_2 N\rceil)$ ，取 $(\delta>0)$ 使 $(\kappa_D\delta<1)，(D=2d+1)$ 。

组装基矩阵

B=\begin{pmatrix}N I_d & 0 & 0\\(\alpha_1,\dots,\alpha_d) & \delta/2^{\nu} & 0\\\mathrm{diag}(\rho_1,\dots,\rho_d) & 0 & \mathrm{diag}(\delta/2^{\mu_1},\dots,\delta/2^{\mu_d})\end{pmatrix}

目标向量

v=\big(\beta_1\bmod N,\dots,\beta_d\bmod N,;\delta/2,;\underbrace{\delta/2,\dots,\delta/2}_{d}\big)

用 LLL(+Babai) 在格子 $L={zB:z\in\mathbb Z^D}$ 中找 $W\approx v$ 。

解码

x'=\mathrm{round}\left(W_{d+1},2^{\nu}/\delta\right),\quad\\k'*i=\mathrm{round}\left(W*{d+1+i},2^{\mu_i}/\delta\right)

输出 $(z\equiv x'\pmod N)$ 作为 $x$ 。

这相对是这种限阶HNP的通用处理思路造一个有放缩的格子通过调整数据使得问题规划为CVP下BaBai可解的

最后再学习了一下鸡块师傅的造格方法也是受益匪浅，我们来看看

既然

s_i\equiv r_{i,0}k_{i,0}+r_{i,1}k_{i,1}+r_{i,2}k_{i,2}\mod p\\B_i\equiv A_i\times key + s_i\mod p

还给了 $key$ 的已知位我们展开一下不难得到

d=2^{100}\cdot gift_1+2^{310}\cdot gift_0\\key=d+u_1+2^{110}u_2+2^{330}u_3

要求 $key$ 实际上也就是求 $u_{1,2,3}$

我们当时对于

B_i\equiv A_i\times key + r_{i,0}k_{i,0}+r_{i,1}k_{i,1}+r_{i,2}k_{i,2}\mod p

不好造格子的主要原因就是我们右边没有一个可以暴露出来放到目标向量的一个”常量”，这里鸡块师傅的处理方式是手动乘已知系数的逆元，把最大的 $k_{i,2}$ 给暴露出来，也就是

r_{i,2}^{-1}(A_i\cdot key-B_i)\equiv r_{i,0}r_{i,2}^{-1}k_{i,0}+r_{i,1}r_{i,2}^{-1}k_{i,1}+k_{i,2}\mod p

这样子我们就能把 $k_{i,2}$ 放到我们想要去规约的目标向量里面，然后带入上面关于 $key$ 的等式，即

r_{i,2}^{-1}(A_i\cdot (d+u_1+2^{110}u_2+2^{330}u_3)-B_i)\equiv r_{i,0}r_{i,2}^{-1}k_{i,0}+r_{i,1}r_{i,2}^{-1}k_{i,1}+k_{i,2}\mod p

已知量全部先算好，令

C_i\equiv r_{i,2}^{-1}(A_id-B_i)\mod p\\a_{i,0}=r_{i,2}^{-1}A_i\mod p\\a_{i,1}=r_{i,2}^{-1}A_i\cdot2^{110}\mod p\\a_{i,2}=r_{i,2}^{-1}A_i\cdot2^{330}\mod p\\b_{i,0}=r_{i,2}^{-1}r_{i,0}\mod p\\b_{i,1}=r_{i,2}^{-1}r_{i,1}\mod p

问题就变为

C_i+a_{i,0}u_1+a_{i,1}u_2+a_{i,2}u_3\equiv b_{i,0}k_{i,0}+b_{i,1}k_{i,1}+k_{i,2}\mod p

写成等式

k_{i,2}-(C_i+a_{i,0}u_1+a_{i,1}u_2+a_{i,2}u_3-b_{i,0}k_{i,0}-b_{i,1}k_{i,1})=t_ip\tag{1}

我们希望找到这样的短向量

s:=(u_1,u_2,u_3,k_{0,0},k_{0,1},k_{1,0},k_{1,1},\dots,k_{9,0},k_{9,1})\in Z^{4+2*10}

我们由1式也就是线性约束能构造约束矩阵

C_{\cdot,i}=(C_i,a_{i,0},a_{i,1},a_{i,2},0,0,\cdots,b_{i,0},b_{i,1},\cdots,0,0)^{T}

这里我们每列的系数 $b_{i,j}$ 都是两两对齐 $k_{i,0}\;\;k_{i,1}$ 的，构造的矩阵

C_{d,4d+2}

我们理想的格子长这样

L=\begin{pmatrix}I_{4+2d}&C\\0&P\end{pmatrix}

右侧是我们尝试用来落实的线性规划，左侧的单位阵用来承接我们期望的短向量，最后

L_{2d\times (8+4d)}

我们期望构造的运算是

L\begin{pmatrix}t\\s\end{pmatrix}=\begin{pmatrix}s+Ct\\pt\end{pmatrix}

既然 $s$ 就是理想的目标向量，而 $Ct$ 的 $t$ 我们其实很可控，不妨想想何时，有

Ct\approx\begin{pmatrix}k_{0,2}\\k_{1,2}\\\vdots\\k_{d,2}\end{pmatrix}

再次看回1式就很自然只要我们的 $t$ 恰好是线性方程中的 $t_i$ 自然就配上了，所以最后方程形似

w\approx\begin{pmatrix}u_1\\u_2\\u_3\\k_{0,0}\\k_{0,1}\\k_{1,0}\\k_{1,1}\\\vdots\\k_{d,0}\\k_{d,1}\\k_{0,2}\\k_{1,2}\\\vdots\\k_{d,2}\\t_1p\\t_2p\\\vdots\\t_dp\end{pmatrix}

这里我们通过构造格子让我们LLL/BKZ找到的 $t$ 就是1式线性方程组中的 $t$ 这一步就叫做“吃掉p” 其实之前2 3个方程的格算法也有这种思路的体现当时就理所当然的接受了，我们已知 $u_{1,2,3}$ 是具备一个线性关系的藏在10组方程中那么我们即使给 $u_{1,2,3}$ 乘上一个大系数线性关系还是在而且当变量越大方程组对应欧氏范数中其权重就会更大算法会更多的去保留大权值变量的线性关系把它做小故而这就实现了我们能去格出 $u_{1,2,3}$ 而尽可能的少受到无关变量 $k_{i,2}$ 的影响，这就是我们常说的”配平”

lw3&lw5#

都是类似的思路放在一起题面

from random import choice, sample
from Crypto.Cipher import AES
from hashlib import md5
from secret import flag

m, n = 90, 64
p = 1048583

E = sample(range(1, p), 3)
s = random_vector(Zmod(p), n)
A = random_matrix(Zmod(p), m, n)
e = vector(Zmod(p), [choice(E) for i in range(m)])
b = A*s + e

print("🎁 :", E + A.list() + b.list())
print("🚩 :", AES.new(key=md5((str(s)).encode()).digest(), nonce=b"Tiffany", mode=AES.MODE_CTR).encrypt(flag))

给定的是一个LWE系统

b_{m\times1}=A_{m\times n}s_{n\times 1}+e_{m\times1}

(m,n)=(90,64)

$e$ 是在给出的集合 $E$ 中选择的，我们已知 $b\;\;A$ ,想求 $s$

我们可以如下抽象一个LWE系统

$n$ 组随机变量 $s$ , $m$ 组有限制的变量 $e$ ， $m$ 组由上述 $m+n$ 组变量得到的线性等式

LWE中的 $e$ 也就是error,往往会有各种限制比如二项分布残差标准差关系等等

不难很直接地构造得到一个规约的式子

L=\begin{pmatrix}I&0&-A\\0&1&b\\0&0&pI\end{pmatrix}

自然

(s,1,k)L=(s,1,e)

我们对于这个格的优化思路是利用已知的 $e$ 的约束尝试只规约 $e$ 而不规约 $s$ ,同时提升规约速度增加规约出 $e$ 的几率,从而解方程得到 $s$

抽象上来说就是

原本 $m+n$ 个变量 $m$ 个方程，变成 $m$ 个变量 $m-n$ 个方程，我们构造的是

L=\begin{pmatrix}-A\\b\\pI\\\end{pmatrix}

有

(s,1,k)L=(e)

而且我们是可以对 $L$ 进行行阶梯标准化的不影响我们的乘算

OK 攻击的思路大致如上接下来看题

一般来说如果是构造的选取 $e$ 的区间 $E$ ,我们总是期望能找到一组线性变换即

E^{'}=kE+t(1,1,1)\mod p

其中 $E^{'}$ 三个值都很小我们 $e^{'}$ 在其中选的时候值也小很好规约出来，也就是我们用一个矩阵 $H_{3\times90}$ 描述我们是如何选取 $e$ 的,那么方程组

B=AS+EH

可以写成

kB+t=kAS+kEH+tH

即

B^{'}=A^{'}S+E^{'}H

这里的 $E^{'}$ 会比较小好规约

那么我在这道题中试一下发现

L = block_matrix(ZZ, [
    [Matrix(ZZ, E)],
    [Matrix(ZZ, [1]*len(E))],
    [p]
])
E_ = L.LLL()[3]
k, t = Matrix(Zmod(p), L).solve_left(E_)[:2]
assert k*vector(GF(p), E) + t*vector(GF(p), [1,1,1]) == vector(GF(p), E_)

print(E_)

# (-298, 582, -285)

并不够小~

这里我们参照鸡块师傅的预期解法

我们知道从 $E$ 中选出 $e$ 可以如下抽象

e_i=(x_i,y_i,z_i)\begin{pmatrix}E_1\\E_2\\E_3\end{pmatrix}

而且我们的 $(x_i,y_i,z_i)$ 实际上只有 $(0,0,1)\;(0,1,0)\;(1,0,0)$ 三种取法我们可以降一个维度

e_i=E_1+(x_i,y_i)\begin{pmatrix}E_2-E_1\\E_3-E_1\end{pmatrix}

其中 $(x_i,y_i)$ 的取法只有 $(1,0)$ 或者 $(0,1)$ 或者 $(0,0)$

这个我们就可以试着去规约一下

此时

$s$ 是 $n$ 组随机变量

$e$ 是 $2m$ 组随机变量但是有0，1的限制

$m$ 个包含 $2m+n$ 的方程

再套用前面的思路尝试消去 $s$

得到 $m-n$ 组包含 $2m$ 个01变量的线性方程，在后续就是考虑如何优化来解决这里的规约问题，预期使用的是blaster

这里关于具体格子怎么造不做一个深入的分析主要是概述一下解决这种LWE的共通思路

也就是从无限制的随机变量 $s$ 脱离出来找到便于规约的有限制关系的变量 $e$ ，利用大小/线性/空间选择的有限性来使我们能够去规约出来尝试找到解

官方wp中提及2023SEKAICTF中的noise_crc 2024NKCTF Ez_random 好像也涉及了这一个点用更多的变量换取更强的限制关系,同时做好对变量的降维，增加我们去规约出来的可行性

LW5#

from Crypto.Cipher import AES
from ast import literal_eval
from random import choice
from hashlib import md5
from secret import flag


def check(E):
    assert len(set([_ % p for _ in E])) == 5
    L = block_matrix(ZZ, [
        [Matrix(ZZ, E)],
        [Matrix(ZZ, [1]*5)],
        [p]
    ])
    E_ = L.LLL()[3]
    return max([abs(_) for _ in E_]) > 1337 and min([abs(_) for _ in E_]) > 337
    
p = 1048583
E = literal_eval(input("your error plz :)"))
assert check(E)

m, n = 90, 56
s = random_vector(Zmod(p), n)
A = random_matrix(Zmod(p), m, n)
e = vector(Zmod(p), [choice(E) for i in range(m)])
b = A*s + e

print("🎁 :", A.list() + b.list())
print("🚩 :", AES.new(key=md5((str(s)).encode()).digest(), nonce=b"Tiffany", mode=AES.MODE_CTR).encrypt(flag))

plaintext

做了两个优化首先是完全不让你去找到能映射到短error的 $E$ 随后是 $E$ 的维度拓展到5 你就算用01去降维后续还是 $4m+1$ 维的变量格要处理规约不了一点

不过我们参照前面的思路找一组基使得消去随机变量 $s$ 后我们的线性方程仍然是变量可规约的

也就是

X_{5\times1}g_{1\times1}+t_{5\times1}=e_{5\times1}

$X_{5\times1}$ 是上述用格基归约找到的5个短分量式，如果考虑用”选取”的二进制展开思路，则是

X_{5\times5}g_{5\times1}+t_{5\times1}=e_{5\times1}\\t:=0

可以降一个维度

X_{5\times4}g_{4\times1}+t_{5\times1}=e_{5\times1}\\t:=e_1

搓一个小的 $X$ 一直生成直到通过检测后续思路同lw3

总结#

强度比较高的比赛题目质量也非常棒很多问题有了更高维度的看法感谢命题师傅以及其他给出解答的师傅非常宝贵的学习机会!