文章总结： 本文为第四届黄河流域CTF赛题writeup，重点分析两道Web题目。realGrafana利用CVE-2024-9264漏洞通过DuckDB的readblob函数实现任意文件读取获取flag；ezlog通过原型污染绕过proto过滤污染Object.prototype，结合数组特性绕过路径校验实现文件读取。文档提供完整漏洞原理分析、利用步骤和可执行PoC代码。 综合评分： 85 文章分类： CTF,WEB安全,漏洞分析
1.3 数据特征分析
提取结果包含两部分：
1.559位十进制数字 — 这是一个非常大的整数2.3913字节二进制数据 — 恰好等于 559 × 7
4472 = 559 × 8 = 3913 × 8 / 7
这种完美对齐暗示：每个数字对应 7 字节二进制数据（56 位），可能是 7×8 的位图字体数据。
Phase 2：Tupper 自指公式
2.1 关键发现
对提取的 559 位数字进行整除性检测：
num % 2 = 0num % 17 = 0 ← 关键！
Tupper 自指公式的标准形式为：
½ < ⌊mod(⌊y/17⌋ × 2^(-17⌊x⌋ - mod(⌊y⌋, 17)), 2)⌋
其中参数 k 由 k = num / 17 计算得到。
2.2 渲染实现
from PIL import Image
k = num // 17# 计算渲染宽度：k的二进制位数除以17后向上取整W = (k.bit_length() + 16) // 17 # = 109H = 17
img = Image.new("1", (W, H))for x in range(W): for y in range(H): # Tupper公式的核心位运算 bit = (k >> (17 * x + y)) & 1 img.putpixel((x, H - 1 - y), 255 if bit else 0)
img.resize((W * 16, H * 16), Image.NEAREST).save("tupper_result.png")
2.3 宽度问题（踩坑点）
经典的 Tupper 公式演示通常用 106 列宽度，但本题的 k 参数需要 109 列才能完整渲染出所有字符。如果仅渲染 106 列，最右侧的字符”Y”会被截断，导致密码错误。
验证方法：
print(k.bit_length() / 17) # ≈ 108.82 → 需要ceil=109列
2.4 渲染结果
██ ██████ ████ ████ ████ ██ ██ ███ ██ ████ ██ ████ ██ ██ ██ ██ ██ ██ ██ ██ █████ ████ █ ██ ██ ██ █ ██ █ ██ ██ ██ █ ██ ██ █ ██ ██ █ ██ ██ ██ ██ ██ ██ ██ ██ ██ ████ █ ████ ██ ██ ██ ██ ██ ██ █ ██ ██ █ ██ ██ ██████ ██ ██ ██ ██ ██ ██ ██ ██ ██ ████ █ █ ██ ██ ██ ██ ██ ██ █ ██ ██ █ ██ ██ ██ █ ██ ██ ██ ██ ██████ ██████ ██ ████ █ ██ █ ██ █ ██ █ ██ ██ █ ██ █ ██ ██ █ ██ ██ █ ██ █ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ █████ ███ ███ ███ ██ ██ █ ███ ███ ████ ██ ███ ██ █ ███ ████ ██ ██ ██ ██ ██ ██ █ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██
读取得到密码：4thHHLY
观察图像可发现，”4th”是序数词”第四”的缩写，”HHLY”是四个大写字母，整体看起来像是一串随机密码。
Phase 3：SilentEye 解密
3.1 工具选择依据
题目描述中的”寂静”二字（英文 silent）直接指向 SilentEye这款隐写工具。SilentEye 是一个跨平台的隐写工具，支持 BMP/JPEG/WAV 格式，使用 F5 算法 对 JPEG 图像进行隐写。
F5 算法的特点：
•在 JPEG 的 DCT 量化系数中嵌入数据•使用矩阵编码（matrix embedding）减少修改量•支持密码保护的伪随机系数选择•支持 AES 加密和 zlib 压缩
3.2 解密操作
打开 SilentEye，执行：
1.拖入 2.jpg 到窗口2.选择 Decode 模式3.输入密码 4thHHLY4.点击提取
3.3 关联验证
“高塔之巅”的双关含义：
| 中文 | 英文 | 对应 | | — | — | — | | 高塔 | Tower → Tupper | Tupper 自指公式（谐音双关） | | 寂静 | Silent → SilentEye | SilentEye 隐写工具 |
Tupper 公式生成密码 → SilentEye 用密码解密 → 最终 flag 呼应了这条链条：
Flag
sdpcsec{get_to_the_upper_and_to_the_Tupper}
flag 语义：”去往高塔之巅，到达 Tupper”——与题目描述”于高塔之巅，窥视寂静中的真相”完美呼应。
encrypt
一道将算法逆向与数字水印结合的 Misc 题，考察 PyInstaller 解包、SRPM 置换分析与频域水印提取能力。
文件清单
| 文件 | 说明 |
| — | — |
| Encrypt.exe | PyInstaller 打包的加密程序 |
| 3.png | 加密后的图片，文件名提示轮数 |
0x1 Encrypt.exe 逆向
用 pyinstxtractor 解包 Encrypt.exe，发现是 Python 3.13 打包。入口为 srpm_cli.py，核心加密逻辑在 encrypt.py 中。
加密算法是一种 SRPM（Self-Reversible Permutation）置换，对 RGB 三通道分别独立操作：
1.将图片每个通道展平为一维数组（长度 length = width × height）2.对每个通道执行 rounds 轮置换3.每轮中，从前到后遍历下标 i，与 swap_target(i) 处的像素交换
def swap_target(index, length, round_index, channel_index): return ( index * index + (2 * round_index + 3) * index + 7 * (channel_index + 1) ) % length
参数说明：
•index — 当前处理的下标•length — 通道数组长度•round_index — 当前轮次（0 到 rounds-1）•channel_index — 通道编号（RGB 对应 0, 1, 2）
0x2 置换的可逆性分析
观察到置换函数是确定性的纯函数——给定相同输入，输出总是相同。且交换操作是对合的（交换两次恢复原状）。
因此解密只需：
•轮次逆序：从最后一轮回到第一轮•下标逆序：从最后一个元素往前处理
关键细节——3.png 的文件名暗示 rounds = 3。如果使用程序默认的 5 轮，解密后仍是噪声。
0x3 逆置换复原
from pathlib import Pathimport numpy as npfrom PIL import Image
INPUT = Path("3.png")ROUNDS = 3
def swap_target(index, length, round_index, channel_index): return (index * index + (2 * round_index + 3) * index + 7 * (channel_index + 1)) % length
img = Image.open(INPUT).convert("RGB")w, h = img.sizeraw = img.tobytes()length = w * h
# 分离 RGB 三通道channels = [bytearray(raw[ch::3]) for ch in range(3)]
# 逆置换（逆序轮次 + 逆序下标）for ci, vals in enumerate(channels): for ri in range(ROUNDS - 1, -1, -1): for i in range(length - 1, -1, -1): t = swap_target(i, length, ri, ci) vals[i], vals[t] = vals[t], vals[i]
# 合并通道merged = bytearray(len(raw))merged[0::3] = channels[0]merged[1::3] = channels[1]merged[2::3] = channels[2]
Image.frombytes("RGB", (w, h), bytes(merged)).save("restored.png")
运行后得到一张清晰的海边风景图，但肉眼看不到 flag。
0x4 FFT 盲水印提取
还原图没有明显水印，考虑单图盲水印——将信息隐藏在频域中。
对灰度图做二维离散傅里叶变换（2D-FFT）：
from PIL import ImageOps
gray = img.convert("L")arr = np.array(gray, dtype=np.float32)
freq = np.fft.fftshift(np.fft.fft2(arr))mag = np.log1p(np.abs(freq)) # 对数压缩mag = (mag - mag.min()) / (mag.max() - mag.min()) * 255 # 归一化
ImageOps.autocontrast( Image.fromarray(mag.astype(np.uint8))).save("watermark_fft.png")
关键操作说明：
| 步骤 | 作用 |
| — | — |
| fft2 | 二维 FFT，将空间域转到频域 |
| fftshift | 将低频移到中心，便于观察 |
| log1p | 对数压缩幅度谱的大动态范围 |
| autocontrast | 自动增强对比度，使水印清晰可见 |
在频谱图正中央清晰显示：
flag{Wei_Hai_journey}
同时在中心下方存在对称倒置副本——这是实信号 FFT 结果的共轭对称特性。
完整解题脚本
from pathlib import Pathimport numpy as npfrom PIL import Image, ImageOps
INPUT = Path("3.png")RESTORED = Path("restored.png")FFT_OUT = Path("watermark_fft.png")ROUNDS = 3
def swap_target(index, length, round_index, channel_index): return (index * index + (2 * round_index + 3) * index + 7 * (channel_index + 1)) % length
# Step 1: 逆置换img = Image.open(INPUT).convert("RGB")w, h = img.sizeraw = img.tobytes()length = w * h
channels = [bytearray(raw[ch::3]) for ch in range(3)]for ci, vals in enumerate(channels): for ri in range(ROUNDS - 1, -1, -1): for i in range(length - 1, -1, -1): t = swap_target(i, length, ri, ci) vals[i], vals[t] = vals[t], vals[i]
merged = bytearray(len(raw))merged[0::3] = channels[0]merged[1::3] = channels[1]merged[2::3] = channels[2]restored = Image.frombytes("RGB", (w, h), bytes(merged))restored.save(RESTORED)
# Step 2: FFT 水印提取gray = restored.convert("L")arr = np.array(gray, dtype=np.float32)freq = np.fft.fftshift(np.fft.fft2(arr))mag = np.log1p(np.abs(freq))mag = (mag - mag.min()) / (mag.max() - mag.min()) * 255fft_img = ImageOps.autocontrast(Image.fromarray(mag.astype(np.uint8)))fft_img.save(FFT_OUT)
print(f"[+] restored: {RESTORED}")print(f"[+] fft watermark: {FFT_OUT}")print(f"[+] flag: flag{{Wei_Hai_journey}}")
Flag
flag{Wei_Hai_journey}
鲨士比亚王国的金融危机
题目信息
•类型: Misc•flag 格式: flag{...}•附件: flag.png + SCB.png
文件分析
| 文件 | 尺寸 | 总像素数 |
| — | — | — |
| flag.png | 889 × 889 | 790,321 |
| SCB.png | 2587 × 307 | 794,209 |
肉眼观察：
•flag.png 是一张彩色图片•SCB.png 是黑底白字的 “SCB” 三个字母
关键发现：统计 SCB.png 中白色像素数量，恰好也是 790,321，与 flag.png 像素总数完全一致。
解题思路
Step 1 — 理解题意
两个图片像素数精确匹配，说明 flag.png 的每一个像素可以被填入 SCB.png 的白色区域。
“SCB” 暗示了填充顺序：Spiral Center Begin — 从中心开始螺旋。
Step 2 — 螺旋读取
对 flag.png 从中心像素出发，按照 右 → 下 → 左 → 上 的方向螺旋向外遍历，得到一维像素序列。
Step 3 — 填入模板
将螺旋序列按行优先顺序填入 SCB.png 的所有白色像素位置，黑色像素保持不变。
核心脚本
from pathlib import Pathimport numpy as npfrom PIL import Image
def center_spiral(n): """从 (n//2, n//2) 开始按右→下→左→上螺旋生成坐标""" x = y = n // 2 coords = [(y, x)] dirs = [(1, 0), (0, 1), (-1, 0), (0, -1)] # R, D, L, U step, d = 1, 0
while len(coords) < n * n: for _ in range(2): dx, dy = dirs[d % 4] for _ in range(step): x += dx y += dy if 0 <= x < n and 0 <= y < n: coords.append((y, x)) if len(coords) == n * n: return coords d += 1 step += 1 return coords
# 读取图片flag = np.array(Image.open("flag.png").convert("RGB"))scb = np.array(Image.open("SCB.png").convert("RGB"))n = flag.shape[0]
# 获取白色像素掩码white = (scb[:, :, 0] > 128) & (scb[:, :, 1] > 128) & (scb[:, :, 2] > 128)assert white.sum() == n * n # 验证像素数匹配
# 螺旋取像素 → 填入白色区域coords = center_spiral(n)spiral_pixels = flag[[y for y, _ in coords], [x for _, x in coords]]
recovered = scb.copy()recovered[white] = spiral_pixelsImage.fromarray(recovered).save("recovered_flag.png")
# 提取绿色文字（手写 flag）+ 黑色 SCB 轮廓r, g, b = recovered[:, :, 0].astype(int), recovered[:, :, 1].astype(int), recovered[:, :, 2].astype(int)green = (g > r + 25) & (g > b + 5) & (g > 90) & (r < 230) & (b < 230)
clean = np.full_like(recovered, 255) # 白色背景clean[green] = [34, 177, 76] # 绿色文字clean[~white] = [0, 0, 0] # 黑色 SCB 轮廓Image.fromarray(clean).save("recovered_flag_clean.png")
运行结果
执行脚本后得到 recovered_flag.png，图片中 “SCB” 三个黑色字母区域内出现了绿色的手写文字：
flag{You_saved_SCB_by_the_coin}
可选的 recovered_flag_clean.png 进一步过滤了背景杂色，仅保留绿色文字和黑色 SCB 轮廓，便于阅读。
Flag
flag{You_saved_SCB_by_the_coin}
AD ASTRA
题目信息
•题目名称: AD ASTRA•题目类型: Misc（隐写/套娃）•文件: flag.png、AD ASTRA.wav
解题思路
Step 1: flag.png 文件分析
首先用 file 或直接查看文件头，发现 flag.png 并非真正的 PNG 文件，而是 WebP/RIFF 格式。
$ xxd flag.png | head -152494646..... → RIFF header (WebP)
WebP 的 RIFF 头部记录了数据大小，由此可以算出 WebP 数据的结束位置：
import struct
data = open("flag.png", "rb").read()riff_size = struct.unpack("<I", data[4:8])[0]webp_end = 8 + riff_size
print(webp_end) # 68588print(data[webp_end:webp_end+4]) # b'PK\x03\x04'
在 WebP 数据之后（偏移 68588），发现了 ZIP 文件签名 PK\x03\x04，说明文件尾部被追加了一个 ZIP 压缩包。
提取并解压追加的 ZIP：
with open("hidden.zip", "wb") as f: f.write(data[webp_end:])
解压后得到 9 个文本文件：01.txt ~ 09.txt，每个文件内容都是 Base64 编码的片段。
Step 2: Base64 拼接 → 提示图
按文件名顺序拼接所有 Base64 片段并解码：
cat hidden/*.txt | base64 -d > clue.png
得到一张提示图，图中文字为：
To the starswe come from
这串文字是下一步 DeepSound 隐写的密码。
Step 3: AD ASTRA.wav — DeepSound 隐写分析
AD ASTRA.wav 是一个 WAV 音频文件。分析其结构，在 data chunk 的 PCM 采样数据中发现了 DeepSound 隐写特征。
提取 DeepSound 头部信息：
import struct
path = "AD ASTRA.wav"data = open(path, "rb").read()
# 找到 data chunkpos = 12while pos + 8 <= len(data): cid = data[pos:pos+4] size = struct.unpack("<I", data[pos+4:pos+8])[0] if cid == b"data": data_start = pos + 8 break pos += 8 + size + (size & 1)
# 解码函数（DeepSound 将每4个采样字节的低4位组合成1个数据字节）def decode_normal(buf): out = bytearray() for i in range(0, len(buf) // 4 * 4, 4): out.append(((buf[i] & 0x0f) << 4) | (buf[i+2] & 0x0f)) return bytes(out)
# 读取头部ds = decode_normal(data[data_start:data_start + 104])print("magic =", ds[:4]) # b'DSC2'print("mode =", ds[4]) # 4 (normal)print("encrypted =", ds[5]) # 1 (encrypted)print("hash =", ds[6:26].hex()) # SHA1 hash
输出结果：
magic = b'DSC2'mode = 4encrypted = 1hash = f54db3d444654ff613ca115add3377e62a17205e
头部标志 DSC2 确认这是 DeepSound 2.x 的隐写数据，并且文件处于加密状态。
Step 4: DeepSound 提取隐藏文件
使用 DeepSound 2.2打开 AD ASTRA.wav：
1.File → Open Carrier → 选择 AD ASTRA.wav2.输入密码：To the stars we come from3.File → Extract hidden files… → 选择输出目录
成功提取出 flag.docx。
Step 5: 解密 flag.docx
flag.docx 是加密的 Office 文档。使用 office2john.py 提取哈希：
python office2john.py flag.docx > hash.txt# flag.docx:$office$*2013*100000*256*16*...
得知密码为 skadi2530，使用 msoffcrypto-tool 解密：
import msoffcrypto
with open("flag.docx", "rb") as f: file = msoffcrypto.OfficeFile(f) file.load_key(password="skadi2530") with open("flag_decrypted.docx", "wb") as of: file.decrypt(of)
Step 6: 提取 Flag
DOCX 文件本质上是 ZIP 压缩包，直接解压 flag_decrypted.docx：
unzip flag_decrypted.docx -d docx_extracted
查看 word/document.xml 中的文本内容，发现 flag 被拆分成多行隐藏在文档 XML 中：
FLAG NOT THEREsdpcsec{AD_ASTRA_INFINITUM}
拼接得到最终 Flag。
Flag
sdpcsec{AD_ASTRA_INFINITUM}
Ad Astra Infinitum — 向着无尽的星辰
Crypto
Ledger Fog
题目描述
题目提供了一个故意损坏的 ZIP 文件 ledger.broken，其 ZIP 中央目录已被删除，但 local file header 和压缩数据流仍然完整。我们需要从带噪声的观测数据中恢复出一个 128 位的 ledger key。
解压后的每个 page 由 19 字节一条的记录组成，结构如下：
偏移 长度 字段0 2 row_id (每页的行号，恢复 key 时用不到)2 16 mask (128 位掩码，小端序)18 1 noisy_bit (0 或 1，带噪声的观测值)
可用的行满足如下关系：
noisy_bit = parity(mask & key) XOR noise
其中 noise 是一个未知比特，它为 1 的概率约为 14.56%。此外检查所有 mask 后发现其最高 4 位恒为 0，因此实际参与线性方程约束的只有低 124 位。最后 4 个 key bit 需要通过暴力枚举并用以下 sanity check 确认：
sha256(b"ledger-fog-check:" + key_bytes).hexdigest()[:4] == "8f42"
flag 的计算方式为：
flag{sha256(b"ledger-fog:" + key_bytes).hexdigest()[:32]}
第一步：从损坏的 ZIP 中恢复数据
由于中央目录丢失，常规的解压工具无法直接处理。我们可以逐字节扫描 PK\x03\x04 (即 50 4B 03 04) 标记，手动解析 local file header 中的元数据字段来定位和提取压缩流。
import structimport zlib
with open("ledger.broken", "rb") as f: data = f.read()
rows = []offset = 0while True: pos = data.find(b"PK\x03\x04", offset) if pos < 0: break # 解析 local file header fields = struct.unpack_from("<IHHHHHIIIHH", data, pos) sig, ver, flags, comp, mtime, mdate, crc, csize, usize, nlen, elen = fields # 文件数据从 header 末尾开始（30 字节固定头 + 文件名 + 扩展字段） page_start = pos + 30 + nlen + elen raw = data[page_start:page_start + csize] page = zlib.decompress(raw, -15) # raw deflate，无 zlib 头
for i in range(0, len(page), 19): bit = page[i + 18] if bit in (0, 1): # 只保留可用行 # 提取 16 字节 mask 并清除恒为 0 的高 4 位 mask = int.from_bytes(page[i + 2:i + 18], "little") mask &= (1 << 124) - 1 rows.append((mask, bit)) offset = pos + 1
共恢复出 3 个 page，合计 20480 条有效记录。
第二步：理解 LPN 问题
本题是一个经典的 Learning Parity with Noise (LPN) 问题实例：
•方程数 n = 20480•未知数 k = 124（key 的有效比特数）•噪声率 τ ≈ 0.1456
写成矩阵形式：
A · key = b + e (mod 2)
其中 A 是 20480×124 的 mask 矩阵，b 是 noisy_bit 向量，e 是噪声向量（每个比特以概率 τ 为 1）。
如果没有噪声，直接用 124 条线性无关的行做 GF(2) 高斯消元即可恢复 key。但噪声的存在使得这个简单方法失效——124 行中平均有约 18 行带有错误 bit，直接求解得到的结果完全是随机的。
对于当前参数 (n=20480, k=124, τ=0.1456)，几种常见方法的可行性如下：
| 方法 | 可行性分析 | | — | — | | 直接高斯消元（忽略噪声） | 失败 —— 124 行中 ~18 个错误使解完全混乱 | | BKW 算法 | 样本不足 —— 每轮归约使样本量减半同时噪声上升，3-4 轮后噪声 ~50% | | 迭代位翻转 | 随机起点不收敛 —— 无初始猜测时每位多数投票为 50/50 | | *信息集解码 (ISD) * | 可行 —— 通过枚举基中少量噪声位置的校正来恢复 key |
第三步：信息集解码 (ISD)
核心思想
随机选取 124 条线性无关的行构成一个基。求解该基对应的线性方程组得到候选 key key0。如果基中没有任何行被噪声污染（即 124 个方程完全正确），那么 key0 就是真 key。
如果基中有 h 行带有噪声，则有：
key0 = M⁻¹ · b = M⁻¹ · (A_basis · key_true + e_basis) = key_true + M⁻¹ · e_basis
修正项 M⁻¹ · e_basis 等于逆矩阵 M⁻¹ 中 h 个列的 XOR。因此真 key 可以通过候选 key 异或若干逆矩阵列得到：
key_true = key0 ⊕ (M⁻¹ 的第 i₁ 列) ⊕ ... ⊕ (M⁻¹ 的第 iₕ 列)
其中 i₁ … iₕ 是基中被噪声污染的行索引。
h ≤ 2 的概率分析
取 τ = 0.1456，124 行中恰好有 h 行带噪声的概率为：
•P(h = 0) = (1−τ)^124 ≈ 3.4×10⁻⁹•P(h = 1) = 124·τ·(1−τ)^123 ≈ 7.2×10⁻⁸•P(h = 2) = C(124,2)·τ²·(1−τ)^122 ≈ 7.5×10⁻⁷•P(h ≤ 2) ≈ 8.2×10⁻⁷
也就是说平均每 120 万个随机基中才有 1 个满足 h ≤ 2。这是整个求解过程的性能瓶颈。
算法流程
对每个随机选取的 124 行基： 1. GF(2) 高斯消元求解 key0，同时计算 M⁻¹ 2. 生成候选 key： - key0 本身（h=0，1 个） - key0 ⊕ inv_col[i]（h=1，124 个） - key0 ⊕ inv_col[i] ⊕ inv_col[j]（h=2，C(124,2)=7626 个） 3. 用 128~256 条随机验证行筛选所有候选 key： - 正确 key 的预期错误数：~18~37 - 随机 key 的预期错误数：~64~128 - 保留明显低于随机水平的候选 4. 对存活候选进行全量 20480 行评分 5. 正确 key 的错误数约为 2982（14.56%），随机 key 约为 10240（50%）
GF(2) 高斯消元求逆
关键子程序是在增广矩阵 [M | I | b] 上做原地高斯消元：
def gf2_invert_and_solve(M, v): """在 GF(2) 上求解 M·x = v 并返回 M⁻¹ 的各列。""" n = len(M) aug = [(M[i], 1 << i, v[i]) for i in range(n)]
for col in range(n): # 找主元 pivot = next((r for r in range(col, n) if (aug[r][0] >> col) & 1), -1) if pivot < 0: return None, None # 奇异矩阵 aug[col], aug[pivot] = aug[pivot], aug[col] pm, pi, pv = aug[col] # 消去其他行 for r in range(n): if r != col and ((aug[r][0] >> col) & 1): aug[r] = (aug[r][0] ^ pm, aug[r][1] ^ pi, aug[r][2] ^ pv)
# 提取解和逆矩阵的各列 x = 0 inv_cols = [0] * n for r in range(n): if aug[r][2]: x |= (1 << r) inv_row = aug[r][1] for j in range(n): if (inv_row >> j) & 1: inv_cols[j] |= (1 << r) return x, inv_cols
第四步：性能优化
验证集预计算
对于大量候选 key 的筛选，直接对每个候选计算 128 行的 parity 效率太低。可以预计算：
# 对候选 key_c = key0 ⊕ delta_c：# errors(c) = sum_i parity(verif_mask[i] & key_c) XOR verif_bit[i]# = sum_i [parity(verif_mask[i] & key0) XOR parity(verif_mask[i] & delta_c)] XOR verif_bit[i]## 预计算 base_errors[i] 和 parity(verif_mask[i] & inv_col[j])，# 则每个候选的筛选只需 O(128) 的 XOR 操作。
纯 Python 的性能瓶颈
在纯 Python 实现中，每个基的高斯消元约需 3ms，即每秒处理约 300 个基。要找到 h ≤ 2 的基（期望约 120 万次尝试）需要约 1 小时。一个实用化的求解器应使用 numpy 或 C 扩展来加速。
第五步：求解结果
恢复出的 128 位 key（小端序字节）：
93 35 7a 03 26 c0 95 9b 74 32 6f c8 74 54 cc b6
Sanity check 通过：
sha256(b"ledger-fog-check:" + key_bytes).hexdigest()[:4] = "8f42" ✓
全量验证的错误数：2982 / 20480 = 14.56%，与预期噪声率一致。
Flag
flag{e0237ecf9df86738a2b50ad66174efed}
λd
题目信息
•分值：500 pts•类型：Crypto•考点：RSA 变种 + LLL 小根求解
题目分析
题目是一个 RSA 变种，关键代码：
N = p * qM = (p ** 2 - 1) * (q ** 2 - 1)e = inverse(d, M)c = pow(m, e, N)
注意这里的模数 不是 标准的 φ(N) = (p-1)(q-1)，而是 (p²-1)(q²-1)。
此外参数有限制：
•p、q 是 1024 bit 素数，两者之差 |p-q| < 2⁸¹⁹•私钥 d 只有约 1331 bit，相对于模数 M（约 4096 bit）很小
由于 d 很小，考虑连分数/LLL 攻击路线。
数学推导
第一步：改写 M
展开：
M = (p² - 1)(q² - 1) = p²q² - p² - q² + 1 = N² - (p² + q²) + 1
利用恒等式 (p+q)² = p² + q² + 2N 代入：
M = N² - ((p+q)² - 2N) + 1 = (N+1)² - (p+q)²
所以 M = (N+1)² - s²，其中 s = p+q。
第二步：引入小变量
由于 |p-q| 很小，s = p+q 非常接近 √(4N)。令：
s0 = floor(√(4N)) # 已知量t = s - s0 # 小量，|t| < 2⁶²⁰
那么 M = (N+1)² - (s0 + t)²。
第三步：构造同余方程
私钥满足 e·d ≡ 1 (mod M)，即存在整数 k 使：
e·d - k·M = 1
代入 M 的表达式，两边模 e 消去 d：
k·((N+1)² - (s0+t)²) + 1 ≡ 0 (mod e)
令：
B = (N+1)² - s0² # 已知量x = k # 未知，x < 2¹³³²y = t # 未知，|y| < 2⁶²⁰
得到二元模方程：
f(x, y) = x·(B - 2·s0·y - y²) + 1 ≡ 0 (mod e)
展开即为：
f(x, y) = B·x - 2·s0·x·y - x·y² + 1 ≡ 0 (mod e)
这是一个关于 (x, y) 的二元二次模方程，且两个未知数都有较小的上界。
求解方法：二⽆ Coppersmith
使用 defund/coppersmith 风格的多元小根算法：
1.在模 e 的剩余类环上构造多项式 f(x, y)2.用参数 m=2, d=3 生成 shift 多项式：
•对 k=0..m、i,j=0..d-1：g = xⁱ·yʲ·fᵏ·eᵐ⁻ᵏ
3.构造系数矩阵，按 bounds X=2¹³³², Y=2⁶²⁰ 缩放列 4.用 LLL 约化格基 5.从短向量恢复多项式，利用结式消元求根
恢复私钥与解密
从 LLL 得到 y = t 后：
s = s0 + t # 恢复 p+qδ = √(s² - 4N) # 恢复 |p-q|p = (s + δ) / 2q = (s - δ) / 2
验证 p·q = N，然后按题目方式恢复私钥：
M = (p² - 1)(q² - 1)d = inverse(e, M)m = pow(c, d, N)
核心代码
from fpylll import IntegerMatrix, LLLfrom math import isqrtfrom Crypto.Util.number import long_to_bytesimport sympy as spimport itertools
N = ...e = ...c = ...
s0 = isqrt(4 * N)B_val = (N + 1) ** 2 - s0 ** 2X = 1 << 1332Y = 1 << 620
x, y = sp.symbols('x y')f_expr = B_val * x - 2 * s0 * x * y - x * y ** 2 + 1
# 构造 shift 多项式shifts = []for k in range(3): # m = 2 base = (e ** (2 - k)) * (f_expr ** k) for i, j in itertools.product(range(3), repeat=2): # d = 3 shifts.append(sp.expand(base * x ** i * y ** j))
# 构建系数矩阵 + 列缩放mons = sorted(monomial_set, key=...)factors = [X ** mi * Y ** mj for (mi, mj) in mons]rows = []for g in shifts: row = [coeff * factors[c] for c, mon in enumerate(mons)] rows.append(row)
# 补齐为方阵while len(rows) < len(mons): rows.append([0] * len(mons))
# LLL 约化M = IntegerMatrix.from_matrix(rows)L = LLL.reduction(M)
# 恢复短向量为多项式# 利用结式消去 x，得到 y 的单变量方程# 求根得到 t，进而恢复 p,q,d 并解密
Flag
flag{Lattice_LLL_Defeats_Large_Delta_RSA_Variants!}
Split Personality: Gauge
题目结论
最终 flag：
flag{d73ca785bb4082865e722cff9cdfcca0}
这题的关键不是直接把 30 个 facet 一把梭拟合成一个 4 x 4 矩阵，而是：
1.先把复合模数 m 按素因子拆开。2.在每个素因子模下，用配对把点转成坐标。3.发现 facet 实际上混了多个局部 action，要先分簇。4.再用 alternating pairing multiplier μ 把各个素因子上的正确分支对齐。5.最后对矩阵做 CRT 拼接，并按题目给的 KDF 出 flag。
题目给的信息
题面给了：
•有限域 Fp2 = Fp[i] / (i^2 + 1)•4 条椭圆曲线 E0, E1, E2, E3•每条曲线上 2 个公开 anchor•30 个 facet，每个 facet 都是：
•source 上一对点，位于 E0 x E3•target 上一对点，位于 E1 x E2
目标是恢复全局 action：
target_vector = action_matrix * source_vector over Z/mZ
其中坐标顺序固定为：
source = (E0.anchor0, E0.anchor1, E3.anchor0, E3.anchor1)target = (E1.anchor0, E1.anchor1, E2.anchor0, E2.anchor1)
第一步：分解 m
题目里的
m = 66614477777873634335261379299463884620134966921892327060987261
分解后是 8 个互异素数：
261047391440964340868029882291115984762913212929929085139213541963
也就是：
Z/mZ ≅ ∏ Z/li Z
所以题目里的所有线性关系、离散对数、矩阵恢复，都可以拆到每个素因子 li 上分别做，再用 CRT 合并回来。
这一步是全题最重要的入口，因为后面所有“混合 action”的现象，都是在各个素因子模下先看清楚，最后再拼回去。
第二步：用 Weil/Tate pairing 把点转成 anchor 基
每条曲线给了两个 anchor，记作 A0, A1。它们张成同一个 m-torsion。
对曲线上任意 m-torsion 点 P，如果
P = a*A0 + b*A1
那么可以用配对把 (a, b) 求出来。
设
zeta = e_m(A0, A1)
则有：
e_m(P, A1) = zeta^ae_m(A0, P) = zeta^b
于是离散对数就能恢复 a, b。
因为 m 是合数，所以离散对数不是直接在模 m 上硬做，而是：
1.对每个素因子 li 分开做。2.在 li 上求离散对数。3.再用 CRT 合成 a, b mod m。
这样，每个 facet 都能转成：
•一个 source 向量 s ∈ (Z/mZ)^4•一个 target 向量 t ∈ (Z/mZ)^4
满足某个局部 action：
t = M * s
第三步：为什么不能直接拿 30 个 facet 拟合同一个矩阵
题面已经提示了：
Several locally consistent residue-channel actions have been spliced together
意思是 30 个 facet 不是全都来自同一个 action，而是混进了多个“局部一致”的 action。
所以如果直接把全部 facet 当作
t = M * s
去解一个统一矩阵，通常会得到假解，或者只能拟合极少数 facet。
正确做法是：
•对每个素因子 *li *单独看•在 F_li 上把 30 个 facet 分成若干个局部 action 簇
你已经跑出来，这里实际会分成 3 个局部 action 簇。
也就是说：每个 li 上，不是唯一一个候选矩阵，而是 3 个候选分支。
第四步：在每个素因子上恢复局部 action
在固定一个素因子 li 后：
1.把所有 facet 的 source/target 坐标都降到 mod li2.每个 facet 给出 4 条线性方程3.在 F_li 上恢复候选 4 x 4 矩阵
由于混有 3 个 action，所以这里不是单次解线性方程就结束，而是要做“分簇/分支恢复”：
•哪些 facet 彼此线性一致，就归到同一个簇•每个簇对应一个局部 action M_li^(k)
做到这一步以后，每个 li 上会拿到 3 个候选局部 action。
第五步：用 alternating pairing multiplier μ 对齐各个素因子的正确分支
这一步是本题真正的“校准”。
题目里说：
weight is the unique positive CRT lift below 2^20 of the alternating-pairing multiplier
对每个局部 action M，它都应该满足一个交替配对的相似关系：
M^T * J * M = μ * J
这里 J 是对应 source/target 基的交替型矩阵。
重点不是公式本身，而是：
•同一个真正的全局 action•在每个素因子 li 上降模以后•它的 multiplier μ mod li 必须是同一个整数 μ 的局部投影
所以流程变成：
1.在每个 li 上，对 3 个候选局部 action 分别算 μ2.把这些候选分支横向对齐3.看哪一条分支能在 所有 8 个素因子上 同时成立并 CRT 拼起来
最后唯一能全局对齐的分支，对应：
μ = 65537
这一步也顺手解释了 weight：
因为题目要求的是“小于 2^20 的唯一正 CRT lift”，而这里
65537 < 2^20
所以：
weight = 65537
第六步：对矩阵 entry 做 CRT，恢复全局 action_matrix
当每个素因子上的正确分支都选出来之后，就得到了：
M mod li
对矩阵的 16 个 entry 分别做 CRT，就能恢复唯一的
M mod m
也就是题目要求的全局 action_matrix。
这里要注意题面规定的编码方式：
•矩阵按 row-major•entry 取 [0, m) 中的最小非负代表元
第七步：按题目 KDF 出 flag
题目给了明确 KDF：
flag = "flag{" + sha256("split-mirage-gauge-v1|" + ";".join(map(str, [weight] + row_major(action_matrix)))).hexdigest()[:32] + "}"
把：
•weight = 65537•恢复出的 action_matrix 按 row-major 展开
拼进去做 SHA-256，取前 32 个 hex，就得到：
flag{d73ca785bb4082865e722cff9cdfcca0}
Double²
这个题到公众号格式有点问题，可看语雀
https://www.yuque.com/g/maple-uuprx/zpp8n3/ae36wki27i9vogtv/collaborator/join?token=FapiGiWLjowGt0yD&source=doc_collaborator# 《黄河流域wp》
免责声明：
本文所载程序、技术方法仅面向合法合规的安全研究与教学场景，旨在提升网络安全防护能力，具有明确的技术研究属性。
任何单位或个人未经授权，将本文内容用于攻击、破坏等非法用途的，由此引发的全部法律责任、民事赔偿及连带责任，均由行为人独立承担，本站不承担任何连带责任。
本站内容均为技术交流与知识分享目的发布，若存在版权侵权或其他异议，请通过邮件联系处理，具体联系方式可点击页面上方的联系我。
本文转载自：赛查查 《第四届黄河流域wp》
版权声明
本站仅做备份收录，仅供研究与教学参考之用。
读者将信息用于其他用途的，全部法律及连带责任由读者自行承担，本站不承担任何责任。
评论