博客快捷键

按住 Shift 键查看可用快捷键

ShiftK

开启/关闭快捷键功能

ShiftA

打开/关闭中控台

ShiftD

深色/浅色显示模式

ShiftS

站内搜索

ShiftR

随机访问

ShiftH

返回首页

ShiftL

友链页面

ShiftP

关于本站

ShiftI

原版/本站右键菜单

松开 Shift 键或点击外部区域关闭

文章详情

互动

HK LWE

272314分钟2026-02-12123未知0

这是一个基于椭圆曲线的LWE（Learning With Errors）变种问题，通常称为 EC-LWE。

核心分析

问题结构:
- 题目给出了矩阵 $A$ 和结果向量 $b⃗\vec{b}$ 。
- 方程形式为: $b⃗=A⋅s⃗+e⃗\vec{b} = A \cdot \vec{s} + \vec{e}$ 。
- 运算是在椭圆曲线 $E$ 上进行的（点加法和标量乘法）。
漏洞点:
- 弱误差 (Weak Error): 这里的误差 $e⃗\vec{e}$ 不是通常LWE中的高斯分布小误差，而是从仅包含两个随机点 ${E_0, E_1\}$ 的集合中选取的。这意味着误差只有 1 bit 的熵。
- 超奇异曲线 (Supersingular Curve):
  - 给定的 $p = 1096126227998177188652856107362412783873814431647$ 。
  - 计算 $\pmod 3$ ，结果为 $2$ 。
  - 对于 $y^2 = x^3 + 5$ ，当 $\equiv 2 \pmod 3$ 时，曲线是超奇异的，且阶 (Order) 刚好为 $p + 1$ 。
  - 这不仅意味着我们可以利用 MOV 攻击将点映射到有限域，而且在这个特定大小下（约160位），离散对数（DLog）通常是可解的（如果 $p + 1$ 是光滑的，或者通过 Pollard's Rho/Index Calculus）。

攻击策略

第一步：将 EC-LWE 转换为标量 LWE

由于是在椭圆曲线上，直接处理点比较麻烦。我们需要计算所有点 $P$ 相对于某个生成元 $G$ 的离散对数 $x$ ，使得 $P = x G$ 。

由于曲线是超奇异的且 $p$ 只有 160 bit，我们可以尝试计算 $A$ 、 $b⃗\vec{b}$ 中所有元素的离散对数。这将问题转化为模 $N$ (曲线的阶) 上的线性方程组：

b⃗′=A⋅s⃗′+e⃗′(modN)\vec{b}' = A \cdot \vec{s}' + \vec{e}' \pmod N

其中 $e⃗′\vec{e}'$ 的每个元素只能取两个标量值之一 ${e_0, e_1\}$ 。

第二步：利用 Kernel (核) 消除 $s⃗\vec{s}$

由于 $A$ 是 $137 \times 73$ 的矩阵，这是一个超定方程组。我们可以找到矩阵 $A$ 的左零空间（Kernel），即找到向量 $v⃗\vec{v}$ 使得 $v⃗⋅A≡0⃗(modN)\vec{v} \cdot A \equiv \vec{0} \pmod N$ 。

将 $v⃗\vec{v}$ 作用于方程两边：

v⃗⋅b⃗′=v⃗⋅(As⃗′)+v⃗⋅e⃗′=0+v⃗⋅e⃗′\vec{v} \cdot \vec{b}' = \vec{v} \cdot (A \vec{s}') + \vec{v} \cdot \vec{e}' = 0 + \vec{v} \cdot \vec{e}'

\sum v_i \epsilon_i

其中 $ϵi∈{e0,e1}\epsilon_i \in \{e_0, e_1\}$ 。这实际上是一个子集和问题（或者说是 Hidden Subset Sum），我们可以设 $ϵi=e0+ui(e1−e0)\epsilon_i = e_0 + u_i(e_1 - e_0)$ ，其中 $ui∈{0,1}u_i \in \{0, 1\}$ 。

第三步：构造格 (Lattice) 使用 LLL 求解

我们会有多个 Kernel 向量，从而得到多个关于 $u_i$ 的线性方程。

Yk=(∑vk,i)e0+(∑vk,iui)δY_k = (\sum v_{k,i}) e_0 + (\sum v_{k,i} u_i) \delta

通过代数变换消除未知的 $e_0$ 和 $δ=e1−e0\delta = e_1 - e_0$ ，我们可以得到仅关于 $u_i$ 的模线性方程。

利用 LLL 算法（解决 Knapsack/Lattice 问题）恢复二进制向量 $u⃗\vec{u}$ 。

第四步：恢复 $s⃗\vec{s}$ 并解密

一旦知道了 $u⃗\vec{u}$ ，我们就知道了每一行使用了哪一个误差项。

修正 $b⃗\vec{b}$ 减去误差后，解线性方程组恢复 $s⃗\vec{s}$ 。

SageMath 求解脚本

你需要将题目输出的 A 和 b 填入脚本中。

Python

from sage.all import *
from Crypto.Cipher import AES
from hashlib import md5

# ==========================================
# 1. 填入题目数据 (需要你将输出的 A 和 b 填在这里)
# ==========================================
# 示例格式: A_list = [[123, 456, ...], ...]
# 示例格式: b_list = [(123, 456), ...]
A_list = [ ... ] 
b_list = [ ... ]
enc_flag = b'...' # 填入 enc 输出的字节串

# ==========================================
# 2. 初始化参数
# ==========================================
p = 1096126227998177188652856107362412783873814431647
E = EllipticCurve(GF(p), [0, 5])
N = E.order()
print(f"[*] Curve Order N = {N}")
print(f"[*] Is N smooth? {factor(N)}") # 检查光滑度，如果光滑 DLog 很快

# 重建矩阵和向量
# 注意：题目中 A.list() 输出的是扁平列表还是二维列表？
# 假设是二维列表。如果是扁平的，需要 reshape。
try:
    A_matrix = matrix(GF(p), 137, 73, A_list)
except:
    # 如果 A_list 是扁平的
    A_matrix = matrix(GF(p), 137, 73, A_list)

# b 是坐标元组列表，需要转为 Curve Point
B_points = [E(x, y) for x, y in b_list]

# ==========================================
# 3. 离散对数 (DLog) - 将点映射为标量
# ==========================================
print("[*] Computing Discrete Logs (This might take a moment)...")
G = E.gens()[0] # 取一个生成元

# 这里的 DLog 策略：
# 如果 N 光滑，Sage 会自动用 Pohlig-Hellman。
# 如果不光滑，对于 160bit，可能需要一点时间或者失败。
# 但这是一个 CTF 题目，通常会有弱点。
try:
    # 尝试直接计算。为了加速，可以将 bsgs 或 pollard_rho 作为参数，但默认自动选择最好。
    # 预计算 b 的 DLog
    b_scalars = vector(GF(N), [G.discrete_log(pt) for pt in B_points])
    print("[+] DLogs for b computed.")
except Exception as e:
    print(f"[-] DLog failed: {e}")
    exit()

# A 矩阵本身就是标量 (在题目代码中: sum(i*j ...) i是A的元素)
# 所以不需要对 A 做 DLog，只需要将 A 视为模 N 的矩阵
A_mod_N = matrix(GF(N), 137, 73, [list(row) for row in A_matrix])

# ==========================================
# 4. Kernel 消除与 Lattice 构造
# ==========================================
print("[*] Computing Kernel to eliminate s...")
# 计算左零空间: v * A = 0
K = A_mod_N.left_kernel()
# 取基向量
V = K.basis_matrix()
num_kernel_rows = V.nrows()
print(f"[*] Found {num_kernel_rows} kernel vectors.")

# 计算 y = V * b_scalars
y_vec = V * b_scalars

# 现在我们有方程: y_i = sigma_i * e0 + w_i * delta
# 其中 sigma_i = sum(V[i]), w_i = sum(V[i][k] * u[k])
# u[k] 是二进制 (0 或 1)

# 构造 Lattice 来求解 u
# 目标是求解 u (137 bits)。
# 消除 e0, delta 后，我们会得到关于 u 的线性方程。
# 但直接用 Lattice 包含 e0, delta 可能更简单，
# 或者使用标准的 "Hidden Subset Sum" 格式。

# 这里使用更直接的线性消除法构造格：
# 对每一行 i (i > 1):
# 我们可以利用前两行消除 e0, delta，得到关于 u 的纯线性约束
# Eq_i: LHS_i * (Sum C_u) - LHS_base * (Sum C_u_i) = 0
# 这有点复杂，不如直接把 delta 和 e0 也作为格中的大变量（虽然它们很大）。
# 
# 更好的方法：
# y_i - sigma_i * e0 - delta * sum(V_{i,j} * u_j) = 0 mod N
# 未知数: e0, delta, u_0...u_136
# u_j 很小 (0/1)。e0, delta 很大 (模 N)。
# 这是一个典型的 LWE/Knapsack。
# 我们可以通过格基规约消除大未知数 e0 和 delta。
# 
# 格构造 (行向量):
# [ 1, 0, ..., 0,  V_{0,0}, V_{1,0}, ..., V_{k,0} ]  <-- 对应 u_0
# ...
# [ 0, ..., 1, 0,  V_{0,136}, ..., V_{k,136} ]       <-- 对应 u_136
# [ 0, ..., 0, K,  sigma_0, sigma_1, ... ]           <-- 对应 e0 (权重 K 用于平衡?) 
#     注意：e0 是大数，不能直接放入短向量格。
#     必须先在代数上消除 e0 和 delta。

# --- 代数消除 e0 和 delta ---
# Eq_i: y_i = sigma_i * e0 + sum_j(V_{i,j} * u_j) * delta
# 选取基准行 0 和 1。
# 1. 消除 e0:
#    Z_i = sigma_0 * y_i - sigma_i * y_0
#    W_i(u) = sigma_0 * sum(V_{i,j}u_j) - sigma_i * sum(V_{0,j}u_j)
#    Z_i = W_i(u) * delta
# 2. 消除 delta:
#    Z_1 * W_i(u) - Z_i * W_1(u) = 0 mod N
#    这是一个关于 u_j 的线性方程！
#    系数 Coeff_{i,j} = Z_1 * (sigma_0 V_{i,j} - sigma_i V_{0,j}) - Z_i * (sigma_0 V_{1,j} - sigma_1 V_{0,j})
#    常数项 = 0 (因为是齐次的)

print("[*] Constructing LLL Matrix...")
sigma = [sum(row) for row in V]
Z = [sigma[0] * y_vec[i] - sigma[i] * y_vec[0] for i in range(num_kernel_rows)]

# 我们使用行 2 到 num_kernel_rows-1 来建立方程 (基于行 0 和 1)
lattice_rows = []
num_eqs = num_kernel_rows - 2
dim = 137

# 这是一个齐次线性方程组 M * u = 0 mod N
# 且 u 是 binary。
# 构造格:
# [ I_137 |  M^T * WEIGHT ]
# [ 0     |  N * I_eq * WEIGHT ]

M = []
for i in range(2, num_kernel_rows):
    row_coeffs = []
    # 计算 u_j 的系数
    for j in range(137):
        # Term 1 from W_i: sigma_0 * V_{i,j} - sigma_i * V_{0,j}
        term1 = sigma[0] * V[i, j] - sigma[i] * V[0, j]
        # Term 2 from W_1: sigma_0 * V_{1,j} - sigma_1 * V_{0,j}
        term2 = sigma[0] * V[1, j] - sigma[1] * V[0, j]
        
        coeff = Z[1] * term1 - Z[i] * term2
        row_coeffs.append(Integer(coeff % N))
    M.append(row_coeffs)

# 构建 Lattice
weight = Integer(2**100) # 权重需要足够大以强制满足模方程
L_mat = Matrix(ZZ, 137 + num_eqs, 137 + num_eqs)

# 左上: 单位矩阵 (限制 u 为小向量)
for i in range(137):
    L_mat[i, i] = 1
    # 右上: 方程系数
    for k in range(num_eqs):
        L_mat[i, 137 + k] = M[k][i] * weight

# 右下: 模数
for k in range(num_eqs):
    L_mat[137 + k, 137 + k] = Integer(N) * weight

print("[*] Running LLL...")
L_reduced = L_mat.LLL()

# 寻找解
u_recovered = None
for row in L_reduced:
    # 检查后半部分是否全为 0 (满足方程)
    is_solution = True
    for k in range(num_eqs):
        if row[137+k] != 0:
            is_solution = False
            break
    
    if is_solution:
        # 检查前半部分是否由 0 和 1 (或 -1) 组成
        potential_u = row[:137]
        # LLL 可能会给出 u 或 -u，或者 u - 1 等
        # 这里假设 u 是短向量，应该直接出现
        if all(x in [0, 1, -1] for x in potential_u):
            # 如果是全负，反转
            if sum(potential_u) < 0:
                potential_u = [-x for x in potential_u]
            
            if all(x in [0, 1] for x in potential_u):
                print("[+] Found valid binary vector u!")
                u_recovered = potential_u
                break

if u_recovered is None:
    print("[-] Failed to recover u.")
    exit()

# ==========================================
# 5. 恢复 s 并解密
# ==========================================
print("[*] Recovering s...")
# 我们知道 u，意味着我们知道每行是 belong to E0 还是 E1
# 但是我们还不知道 E0 和 E1 具体是多少 (标量)。
# 不过我们只需要将行归类。
# 选取 u_i = u_j 的行，方程: A_i * s + e = b_i, A_j * s + e = b_j
# => (A_i - A_j) * s = b_i - b_j
# 收集足够的这种差分方程求解 s (标量形式)。

diff_A = []
diff_b = []

# 找到所有 u=0 的索引和 u=1 的索引
indices_0 = [i for i, x in enumerate(u_recovered) if x == 0]
# 只要 indices_0 长度 > 1，就可以构造方程
for k in range(len(indices_0) - 1):
    idx1 = indices_0[k]
    idx2 = indices_0[k+1]
    
    row_A = A_mod_N[idx1] - A_mod_N[idx2]
    val_b = b_scalars[idx1] - b_scalars[idx2]
    
    diff_A.append(list(row_A))
    diff_b.append(val_b)

# 如果不够，加上 u=1 的
indices_1 = [i for i, x in enumerate(u_recovered) if x == 1]
for k in range(len(indices_1) - 1):
    idx1 = indices_1[k]
    idx2 = indices_1[k+1]
    
    row_A = A_mod_N[idx1] - A_mod_N[idx2]
    val_b = b_scalars[idx1] - b_scalars[idx2]
    
    diff_A.append(list(row_A))
    diff_b.append(val_b)

Solver_Mat = matrix(GF(N), diff_A)
Solver_Vec = vector(GF(N), diff_b)

# 解线性方程 s_scalars
# 只需要 73 行
try:
    s_scalars = Solver_Mat.solve_right(Solver_Vec)
    print("[+] s recovered (scalars).")
except:
    # 尝试用最小二乘或选取子矩阵
    s_scalars = Solver_Mat[:73].solve_right(Solver_Vec[:73])

# 将 scalars 转回 Points
s_points = [s_val * G for s_val in s_scalars]

# 格式化 flag
# 题目中 key = md5(str(s).encode())
# s 是点列表。Sage 默认 str([P1, P2]) 格式通常是:
# "[(x1 : y1 : z1), (x2 : y2 : z2), ...]" (Projective)
# 题目中的 s 是 [E.random_element()...]，默认也是 Projective。
# 直接用 str(s_points) 应该可以。

key = md5(str(s_points).encode()).digest()
cipher = AES.new(key=key, nonce=b"LWECC", mode=AES.MODE_CTR)
flag = cipher.decrypt(enc_flag)
print(f"[!] Flag: {flag}")

1ceS1amese

生活明朗，万物可爱

本文是原创文章，采用 CC BY-NC-SA 4.0 协议，完整转载请注明来自 1ceS1amese

隐私政策

评论内容

0/500

昵称

邮箱

网址

滚动到此处加载评论...

安知鱼

来自安知鱼最新设计与科技的文章

查看全部