AI摘要 本文介绍CTF MISC题目中，将01二进制数字串转换为二维码图像的方法：理解二进制与像素矩阵的映射关系，通过计算长度平方根确定边长，使用PIL库按行优先顺序将1映射为黑色、0映射为白色，生成图像后扫码获取flag。 以上内容由 AI 生成，仅供参考。背景在 CTF竞赛的 MISC（杂项） 类题目中，出题者经常会给出一段由 0 和 1 组成的数字串，要求选手将其还原为可视化的二维码图像，进而扫码获取 flag。这类题目的核心考察点是：理解二进制数据与像素矩阵之间的映射关系，以及如何利用编程手段完成图像重建。原理分析为什么 01 串能表示二维码？二维码（QR Code）本质上是一个二维像素矩阵。每个模块（module）只有两种状态：像素值二进制表示颜色深色模块1黑色(0, 0, 0)浅色模块0白色(255, 255, 255)当一段 01 数字串的长度恰好是某个整数 n 的平方时（即 len = n × n），它可以被排列成一个 n × n 的正方形矩阵——这正是二维码的像素布局方式。数据流转换过程01 数字串 → 一维数组 → 二维像素矩阵 → 二维码图像 625 bit [0,1,1,0,...] 25×25 矩阵 RGB 图像关键约束：数字串长度必须是完全平方数，否则无法构成正方形矩阵，也就不是合法的二维码。常见尺寸对照矩阵边长总像素数（bit）适用场景21441QR Version 1（最小）25625CTF 常见尺寸29841QR Version 3331089QR Version 4371369QR Version 5注意：CTF 题目中的矩阵不一定是标准 QR Code 的精确定位图案尺寸，但 25×25 是最常见的出题尺寸。解题代码完整脚本内容已锁定此处内容已被隐藏，请关注公众号后验证查看关注公众号验证代码逐行解析代码段说明Image.new("RGB", (MAX, MAX))创建 25×25 的 RGB 空白图像，默认全黑for y / for x双重循环按行优先（row-major）顺序遍历像素binary_str[i]逐字符读取，'1'→ 黑色，'0'→ 白色putpixel([x, y], color)将指定坐标像素设置为对应颜色pic.show()调用系统默认图片查看器显示结果pic.save("flag.png")保存为 PNG 文件，供扫码工具识别 扩展：另一种思路 — 使用 qrcode 库反向识别如果你拿到 01 串后不想手写转换逻辑，也可以先生成图像再用 pyzbar 等库自动解码：# 安装依赖: pip install Pillow pyzbar from pyzbar.pyzbar import decode from PIL import Image # 先用上面的方法生成图像，再解码 img = Image.open("flag.png") results = decode(img) for r in results: print(f"[+] 类型: {r.type}") print(f"[+] 内容: {r.data.decode()}")解题流程总结┌─────────────────────────────────────────┐ │ 1. 获取 01 数字串 │ │ ↓ │ │ 2. 计算长度，判断是否为完全平方数 │ │ ↓ │ │ 3. 求平方根 → 矩阵边长 n │ │ ↓ │ │ 4. 按行优先顺序，1→黑 0→白，填充 n×n 图像 │ │ ↓ │ │ 5. 保存图像，使用二维码扫描工具读取 flag │ └─────────────────────────────────────────┘常见问题Q: 数字串长度不是完全平方数怎么办？可能是以下情况：包含分隔符：检查数据中是否有空格、逗号、换行符需要清理多层编码：数据可能经过 Base64、Hex 等编码，需先解码非正方形：极少数题目可能是矩形（长 × 宽），需尝试不同因数组合Q: 生成的图像扫码失败？反转颜色：尝试将 1 和 0 对应的颜色互换（黑变白、白变黑）检查行列顺序：确认是行优先还是列优先添加白边：扫码器可能需要安静区（quiet zone），给图像加一圈白色边距小结本题属于 CTF MISC 中的图像隐写与还原类型，核心知识点：二进制与像素的映射：01 串本质上是像素矩阵的线性展开完全平方数约束：正方形矩阵要求数据长度为 n²PIL 图像操作：Image.new() 创建画布，putpixel() 逐像素绘制行优先遍历：(y, x) 的双重循环对应从左到右、从上到下的扫描顺序
AI摘要 本文介绍基于FFT的频域水印技术。利用Python和OpenCV，通过随机种子置乱水印位置，在频域嵌入信息。虽为非盲水印，但难以破解。文章详细阐述了数学原理、代码实现、命令行用法及CTF解题策略。 以上内容由 AI 生成，仅供参考。概述盲水印（Blind Watermark）是一种信息隐藏技术，将水印数据嵌入到载体图像中，肉眼不可见，只有通过特定算法才能提取。概念辨析概念说明是否需原图盲水印 (Blind Watermark)提取水印时不需要原图和原始水印否非盲水印 (Non-Blind)提取时需要原图参与计算是（本文实现）可见水印图片上肉眼可见的叠加标记（如版权 LOGO）—本文实现的是频域非盲水印，但通过种子（seed）对水印位置进行随机置乱，使攻击者即使知道算法也无法在无种子时恢复可读水印，达到变相"盲"提取的效果。数学原理傅里叶频域变换图像在空间域（像素点阵）和频率域之间存在对应关系：低频分量：图像中变化缓慢的区域（大面积色块、背景）高频分量：图像中变化剧烈的区域（边缘、纹理、噪点）通过 二维快速傅里叶变换（FFT-2D），可以将 $M \times N$ 的图像矩阵从空间域转换到频率域：$$ F(u,v) = \sum_{x=0}^{M-1} \sum_{y=0}^{N-1} f(x,y) \cdot e^{-j2\pi(ux/M + vy/N)} $$逆变换（IFFT）可将频率域还原回空间域：$$ f(x,y) = \frac{1}{MN} \sum_{u=0}^{M-1} \sum_{v=0}^{N-1} F(u,v) \cdot e^{j2\pi(ux/M + vy/N)} $$频域嵌入原理在频率域中修改图像的傅里叶系数（尤其是中高频分量），不会在视觉上引起明显变化，但编码了信息：空间域图像 频率域 逆变换后 ┌──────┐ FFT ┌──────────┐ IFFT ┌──────┐ │ 原图 │ ────────→ │ F(u,v) │ ───────→ │ 图像 │ └──────┘ │ + │ └──────┘ │ α·W(u,v) │ └──────────┘ ↑ 水印频率分量嵌入公式：$$ F'(u,v) = F(u,v) + \alpha \cdot W(u,v) $$其中：$F(u,v)$ — 原始图像的第 $(u,v)$ 个频率系数$W(u,v)$ — 水印图像在频率域的系数$\alpha$ — 嵌入强度系数（默认 3.0），越大则水印越清晰但可见性越高$F'(u,v)$ — 嵌入水印后的频率系数提取公式：$$ W(u,v) = \frac{F'(u,v) - F(u,v)}{\alpha} $$从公式可见：提取需要已知 原始图像 $F(u,v)$ 和 alpha 参数。这是非盲水印的根本原因。攻击链路图嵌入过程 (Encode) ═══════════════════ 原图 img 水印 wm │ │ ▼ ▼ FFT(img) 随机置乱 (seed) │ │ │ ┌─────────────────┘ ▼ ▼ F' = F + α × wm_shuffled │ ▼ IFFT(F') → 含水印图像 │ ▼ 保存为 JPEG (有损压缩引入微量误差) 提取过程 (Decode) ═══════════════════ 原图 img 含水印图 img_encoded │ │ ▼ ▼ FFT(img) = F1 FFT(img_encoded) = F2 │ │ │ ┌─────────────────┘ ▼ ▼ W = (F2 - F1) / α → 得到置乱后的水印 │ ▼ 用相同 seed 逆置乱 → 原始水印图像代码实现环境依赖pip install opencv-python numpy matplotlib核心导入与参数import cv2 import numpy as np import random alpha = 3.0 # 嵌入强度：越大水印越清晰，但对原图像素影响越大 seed = 20160930 # 随机种子：作为水印置乱的"密钥"BGR → RGB 转换工具OpenCV 使用 BGR 通道顺序，Matplotlib 使用 RGB 顺序，显示时需转换：def bgr_to_rgb(img): b, g, r = cv2.split(img) return cv2.merge([r, g, b])编码（Encode）：嵌入水印# 1. 读取原图与水印 img = cv2.imread('hui.png') wm = cv2.imread('wm.png') h, w = img.shape[0], img.shape[1] # 2. 将水印置入半高画布 (h/2 × w) hwm = np.zeros((int(h * 0.5), w, img.shape[2])) hwm2 = np.copy(hwm) for i in range(wm.shape[0]): for j in range(wm.shape[1]): hwm2[i][j] = wm[i][j] # 3. 用 seed 随机打乱 watermark 的像素位置 random.seed(seed) m, n = list(range(hwm.shape[0])), list(range(hwm.shape[1])) random.shuffle(m) # 行索引随机排列 random.shuffle(n) # 列索引随机排列 for i in range(hwm.shape[0]): for j in range(hwm.shape[1]): hwm[i][j] = hwm2[m[i]][n[j]] # 4. 对称复制（上半部分镜像到下半部分） rwm = np.zeros(img.shape) for i in range(hwm.shape[0]): for j in range(hwm.shape[1]): rwm[i][j] = hwm[i][j] rwm[rwm.shape[0] - i - 1][rwm.shape[1] - j - 1] = hwm[i][j]对称复制示意图：┌──────────────────┐ │ hwm (置乱后) │ ← 上半部分 │ │ │ ╲ │ │ mirror axis │ ← 水平中心线 │ ╱ │ │ hwm 对称镜像 │ ← 下半部分 └──────────────────┘# 5. FFT 频域嵌入 f1 = np.fft.fft2(img) # 原图 → 频域 f2 = f1 + alpha * rwm # 频域加法嵌入 img_encoded = np.fft.ifft2(f2) # 逆变换回空间域 img_encoded = np.real(img_encoded) # 取实部 # 6. 保存为 JPEG（无损质量） cv2.imwrite('output.jpg', img_encoded, [cv2.IMWRITE_JPEG_QUALITY, 100])为什么要取 np.real？FFT 结果包含实部和虚部。嵌入操作仅修改实部，但 IFFT 后可能因浮点精度产生极小虚部（~10⁻¹⁰），取实部即丢弃这些计算噪声。解码（Decode）：提取水印# 1. 读取原图与含水印图 img = cv2.imread('hui.png') img_wm = cv2.imread('output.jpg') # 2. 两种图分别做 FFT f1 = np.fft.fft2(img) # 原图频域 f2 = np.fft.fft2(img_wm) # 含水印图频域 # 3. 频域相减除以 alpha → 恢复置乱后的水印 rwm = (f2 - f1) / alpha rwm = np.real(rwm) # 4. 用相同的 seed 生成相同的置乱序列 random.seed(seed) m = list(range(int(rwm.shape[0] * 0.5))) n = list(range(rwm.shape[1])) random.shuffle(m) random.shuffle(n) # 5. 逆置乱 → 还原水印 wm = np.zeros(rwm.shape) for i in range(int(rwm.shape[0] * 0.5)): for j in range(rwm.shape[1]): wm[m[i]][n[j]] = np.uint8(rwm[i][j]) # 下半部分镜像 for i in range(rwm.shape[0] // 2): for j in range(rwm.shape[1]): wm[rwm.shape[0] - i - 1][rwm.shape[1] - j - 1] = wm[i][j] cv2.imwrite('extracted_wm.jpg', wm)保存误差度量JPEG 有损压缩会引入噪点。程序计算了写入前后的均方根误差：img_wm = np.real(img_encoded) # 内存中的原值 img_wm2 = cv2.imread(fn3) # JPEG 读取后的值 # 计算 RMS 误差百分比 sum = 0 for i in range(h): for j in range(w): for k in range(3): sum += (img_wm[i][j][k] - img_wm2[i][j][k]) ** 2 miss = np.sqrt(sum) / (h * w * 3) * 100 # 输出: "Miss X.XX% in save"命令行用法# 嵌入水印 python bwm.py encode hui.png wm.png output.jpg # 提取水印（必须提供原图） python bwm.py decode hui.png output.jpg extracted_wm.jpg # 调试模式（显示每步的可视化输出） python bwm.py encode hui.png wm.png output.jpg --debug # 自定义种子（密钥） python bwm.py encode hui.png wm.png output.jpg --seed 12345678 python bwm.py decode hui.png output.jpg extracted_wm.jpg --seed 12345678 # Python3 兼容 Python2 的 random 算法 python3 bwm.py decode hui.png output.jpg extracted_wm.jpg --oldseed # 调整嵌入强度（数值越小越隐蔽） python bwm.py encode hui.png wm.png output.jpg --alpha 1.5参数说明：参数默认值说明--debug关闭开启后弹出 Matplotlib 窗口，显示每一步的频域/空间域图像--seed <int>20160930随机置乱的种子，相当于水印"加密密钥"--oldseed关闭Python3 环境启用 Python2 兼容的 random 算法--alpha <float>3.0嵌入强度：越小越隐蔽；越大提取越清晰但可见性增加CTF 应用典型题目特征CTF MISC 题目中出现盲水印时，通常呈现以下形态：题目给出一张"正常"图片（原图）和一张"略有差异"的图片（含水印图）两张图片像素级肉眼不可区分利用频域相减可提取隐藏信息（Flag）通用解题流程获得两张相似图片 │ ▼ ┌──────────────────────┐ │ 判断水印类型 │ │ · 频域水印 (FFT) │ ← 本工具 │ · LSB 水印 │ │ · DCT/DWT 水印 │ └──────────┬───────────┘ │ ▼ ┌──────────────────────┐ │ 尝试默认 seed 提取 │ │ seed = 20160930 │ └──────────┬───────────┘ ├─ 成功 → 得到 Flag │ ▼ 失败 ┌──────────────────────┐ │ 暴力枚举 seed │ │ 或分析提示信息 │ └──────────┬───────────┘ │ ▼ ┌──────────────────────┐ │ 调整 alpha 值 │ │ 从 0.5 逐步增加到 10 │ └──────────┬───────────┘ │ ▼ 得到 Flag延伸阅读水印技术的数学分类类别变换域鲁棒性CTF 出现频率FFT (快速傅里叶变换)频率域中高 (本工具)DCT (离散余弦变换)频域 (JPEG 核心)高中DWT (离散小波变换)时频域高低LSB (最低有效位)空间域极低最高SVD (奇异值分解)矩阵分解高低alpha 选择指南alpha 过小 (0.1~0.5) alpha 适中 (2~5) alpha 过大 (>10) ┌─────────────────┐ ┌─────────────────┐ ┌─────────────────┐ │ 水印几乎不可见 │ │ 水印清晰可读 │ │ 原图出现可见噪点 │ │ 提取失败 / 噪声 │ │ 对原图视觉影响小 │ │ 水印暴露 │ │ 需原图精度极高 │ │ **推荐范围** │ │ 失去隐蔽意义 │ └─────────────────┘ └─────────────────┘ └─────────────────┘Python2/3 random 算法差异的根本原因Python2 的 random.shuffle 使用 Wichmann-Hill (1984) 算法；Python3 默认使用 Mersenne Twister (MT19937)。相同 seed 在不同算法下产生的置乱序列不同，导致提取的水印为噪点。解决方式：# 法 1：使用 Python2 运行 python2 bwm.py decode hui.png encoded.jpg out.jpg # 法 2：Python3 加 --oldseed（切换为 Python2 的 random 实现） python3 bwm.py decode hui.png encoded.jpg out.jpg --oldseed 参考文献chishaxie. BlindWaterMark - 盲水印 by Python [EB/OL]. GitHub, 2021. https://github.com/chishaxie/BlindWaterMarkNumPy Contributors. numpy.fft.fft2 — Discrete Fourier Transform [EB/OL]. https://numpy.org/doc/stable/reference/generated/numpy.fft.fft2.htmlOpenCV. Image file reading and writing [EB/OL]. https://docs.opencv.org/4.x/d4/da8/group__imgcodecs.htmlPython Software Foundation. random — Generate pseudo-random numbers [EB/OL]. https://docs.python.org/3/library/random.htmlMallat S. A Wavelet Tour of Signal Processing [M]. Academic Press, 1999.
AI摘要 文章针对CTF中Flag被多层Base64/Base32随机混合编码的难题，提出利用Base16、Base32、Base64字符集互斥的特性，通过依次尝试解码来还原Flag。核心策略是先试Base16排除，再试Base32，最后试Base64，并提供了相关Python脚本。 以上内容由 AI 生成，仅供参考。概述CTF Crypto / MISC 中常见一类题目：将 Flag 用 Base64 / Base32 随机混合编码多层，要求选手解码还原。核心挑战在于——编码轮次未知、每轮用的是哪种 Base 也未知，需要"盲破"。Flag 原文 │ ▼ 随机选取 base64 或 base32 ┌──────────┐ │ Round 1 │ → 编码后 └────┬─────┘ │ ▼ 再次随机选取 ┌──────────┐ │ Round 2 │ → 编码后 └────┬─────┘ │ ▼ ... 重复 c 次 (c ∈ [20, 40]) │ ▼ 最终密文 (base2.txt)编码总轮次 $c \in [20, 40]$，每轮 base64 或 base32 二选一。理论上总组合数为 $2^{20} \sim 2^{40}$，无法穷举——必须用"试探解码"策略。Base 家族速查三种编码对比属性Base16 (Hex)Base32Base64字符表大小163264字符集0-9 A-FA-Z 2-7A-Z a-z 0-9 + /每组输入1 字节5 字节3 字节每组输出2 字符8 字符4 字符膨胀率200%160%133%= 填充无有 (=)有 (=)输出长度倍数2 的倍数8 的倍数4 的倍数三种编码的互斥识别最重要的特性：每种编码的合法输入字符集互不包含。Base16 合法字符: 0123456789ABCDEFabcdef ↑ 不含 G-Z，不含 +/= Base32 合法字符: ABCDEFGHIJKLMNOPQRSTUVWXYZ234567 = ↑ 不含 0 1 8 9 + / Base64 合法字符: A-Z a-z 0-9 + / = ↑ 几乎包含所有可打印字符利用这个互斥性：尝试 base16 解码 → 若报错 → 不是 base16 → 换 base32 → 若还报错 → 一定是 base64。 ┌─────────┐ │ 输入密文 │ └────┬────┘ ▼ ┌─ try base16_decode ──┐ │ 含 G/K/+ 等非法字符 │ ▼ 报错 ▼ 报错 非 base16 ┌─ try base32_decode ──┐ │ 含 0/1/8/9/+ 等 │ ▼ 报错 ▼ 报错 非 base32 try base64_decode │ ▼ 继续下一轮编码脚本import base64 import random a = random.randint(0, 10) # a ∈ [0, 10] b = random.randint(20, 30) # b ∈ [20, 30] rounds = a + b # 总轮次 ∈ [20, 40] print(f'编码轮次: {rounds}') flag = b'flag{lalala}' for _ in range(rounds): k = random.randint(0, 1) if k == 0: flag = base64.b64encode(flag) else: flag = base64.b32encode(flag) with open('base2.txt', 'wb') as f: f.write(flag) print('finish!')关键参数：变量范围说明a0~10随机因子一b20~30随机因子二rounds = a+b20~40总编码轮次k0 或 10 → base64; 1 → base32编码路径总数$2^{rounds}$约$10^6 \sim 10^{12}$（不可穷举）解密脚本import base64 with open('base2.txt', 'rb') as f: data = f.read() decoders = [base64.b16decode, base64.b32decode, base64.b64decode] while True: for decoder in decoders: try: data = decoder(data) break except Exception: continue else: print('[错误] 全部解码尝试失败，密文可能已损坏') break try: text = data.decode('utf-8') except UnicodeDecodeError: continue if text.startswith('flag{') or text.startswith('flag'): print(text) break试探顺序和原理：顺序解码方式失败条件为什么会失败1base16输入含G-Z、g-z、+、/、=编码从未使用 base16，密文中必然存在非 hex 字符2base32输入含0、1、8、9、+、/base32 仅含A-Z 2-7，base64 输出含上述非法字符3base64几乎不会失败（若失败则密文损坏）base64 接受几乎所有字符为什么不先试 base64？因为 base64 字符集包含 base32 和 base16 的全部字符——base64 总是"成功"解码，但输出是乱码。所以必须从最严格的（base16）到最宽松的（base64）依次尝试。深层原理为什么 Base16 放在第一位编码脚本仅使用了 b64encode 和 b32encode，从未使用 b16encode。但解密脚本仍把 base16 放在第一位的原因：base64 的输出一定包含不属于 base16 字符集的字符（如 g-z、+/=），因此 base16 解码必然失败。它充当一个方向探测器——快速排除不可能的路径，自动 fallthrough 到 base32。# Base16 非法字符触发的异常 base64.b16decode(b'abc') # 成功 ('abc' 都是合法 hex) base64.b16decode(b'abg') # 报错: Non-base16 digit found概率分析项目值每轮选择 base64 的概率50%每轮选择 base32 的概率50%总轮次期望值$E[rounds]$$E[a]+E[b] = 5+25 = 30$密文长度膨胀期望$1.33^{15} \times 1.6^{15} \approx 3.5 \times 10^4$ 倍原始 flag 约 12 字节 → 最终密文约~420 KB数据结构追踪原始: "flag{lalala}" (12 字节) │ ▼ b64encode "ZmxhZ3tsYWxhbGF9" (16 字符) │ ▼ b32encode "KNUGK4TDMUQGK3RA..." (更长) │ ▼ ... 重复 20~40 轮 │ ▼ 最终密文: 数十万字符CTF 应用常见变体编码组合解密顺序备注b16 + b32 + b64b16 → b32 → b64最严格在前b32 + b64b32 → b64跳过 b16 也可b16 + b64b16 → b64b32 报错自动跳过+ b85 (Ascii85)b16→b32→b85→b64在 decoders 列表中间插入base64.b85decode+ URL-Safe Base64使用base64.urlsafe_b64decode字符集为A-Z a-z 0-9 - _ 不含 +/+ 反转 + b32需额外判断密文反转后再解码与 base64 隐写术的区别 混合编码（本文）Base64 隐写目的混淆明文隐藏信息在= 填充位操作多层 baseXX 编码修改填充位或等号前的 bit解密逆序逐层尝试提取特定 bit 并重组CTF 识别密文极长（多轮膨胀）密文长度正常，但可能含异常=参考文献Python Software Foundation. base64 — Base16, Base32, Base64, Base85 Data Encodings [EB/OL]. https://docs.python.org/3/library/base64.htmlJosefsson S. RFC 4648 — The Base16, Base32, and Base64 Data Encodings [EB/OL]. https://datatracker.ietf.org/doc/html/rfc4648Wikipedia. Base64 [EB/OL]. https://en.wikipedia.org/wiki/Base64
AI摘要 云影密码（01248）是一种利用0、1、2、4、8通过贪婪求和分解字母序号的古典替换密码。文章阐述了其原理、编码表、Python加解密实现及CTF实战技巧。 以上内容由 AI 生成，仅供参考。概述云影密码（又称 01248 密码）是一种古典替换密码，它仅使用数字 0、1、2、4、8 来编码完整的 A-Z 字母表。原理详解编码逻辑云影密码采用贪婪求和分解的方式：每个字母的序号 $n$ (1~26) 被拆分为 $\{1, 2, 4, 8\}$ 的允许重复的加权和，数字间用 0 分隔。核心规则：用 0 分割不同字母对应的编码组每组内的数字（1、2、4、8）可以重复出现组内所有数字之和 = 字母在字母表中的序号序号映射：1→A, 2→B, ..., 26→Z密文: 8842101220480224404014224202480122 │ │ │ │ ... ▼ ▼ ▼ ▼ 分割: 88421 122 8 ↓ ↓ ↓ 求和: 8+8+4+2+1=23 1+2+2=5 8=8 ↓ ↓ ↓ 字母: W E H完整编码表字母序号分解密文组A111B222C32+121D444E54+141F64+242G74+2+1421H888I98+181J108+282K118+2+1821L128+484M138+4+1841N148+4+2842O158+4+2+18421P168+888Q178+8+1881R188+8+2882S198+8+2+18821T208+8+4884U218+8+4+18841V228+8+4+28842W238+8+4+2+188421X248+8+8888Y258+8+8+18881Z268+8+8+28882编码使用贪婪策略：从大到小依次从 $\{8, 4, 2, 1\}$ 中选取，可重复。同一序号可以有多种合法编码（如 16 = 88 也可写成 4444 或 84211），上表采用的是"最少位数"贪婪编码。Python 加解密实现解密（密文 → 明文）与原文思路一致，用 0 分割、逐组求和、chr(sum+64) 映射字母：def decode_01248(cipher: str) -> str: """云影密码解密：密文 → 明文""" groups = cipher.split('0') result = [] for group in groups: if not group: continue total = sum(int(d) for d in group) result.append(chr(total + 64)) return ''.join(result) # 示例 print(decode_01248('8842101220480224404014224202480122')) # 输出: WELCOMETOCFF解密流程：步骤操作示例 (884210...)1cipher.split('0')['88421', '122', '8', ...]2逐组求和23, 5, 8, ...3chr(sum+64)23→W, 5→E, 8→H, ...加密（明文 → 密文）使用贪婪算法，从 $\{8, 4, 2, 1\}$ 中从大到小反复减去可用的最大值：def encode_01248(plain: str) -> str: """云影密码加密：明文 → 密文（贪婪策略）""" weights = [8, 4, 2, 1] # 从大到小，贪婪选取 code = [] for ch in plain.upper(): if not 'A' <= ch <= 'Z': raise ValueError(f'无效字符: {ch}') n = ord(ch) - ord('A') + 1 # 序号 1~26 group = '' for w in weights: while n >= w: # 关键：允许重复！ group += str(w) n -= w code.append(group) return '0'.join(code) # 示例 print(encode_01248('HELLO')) # 输出: 801404801248 print(encode_01248('WXYZ')) # 输出: 884210888108881088820加密流程（以 Z=26 为例）：轮次当前 n权重 8剩余 n126while 26>=8 → "8", n=18 218while 18>=8 → "88", n=10 310while 10>=8 → "888", n=2 428 > 2 跳过 → 4 > 2 跳过 → while 2>=2 → "8882", n=0 50结束，密文组 =8882 命令行工具import sys if __name__ == '__main__': if len(sys.argv) < 3: print('用法: python yunying.py decode|encode ') sys.exit(1) mode, data = sys.argv[1], sys.argv[2] if mode == 'decode': print(decode_01248(data)) elif mode == 'encode': print(encode_01248(data))编码同值歧义由于允许重复，同一字母存在多种合法编码。以下均解码为同一个字母：字母序号编码方式 A（8 优先）编码方式 B编码方式 CC321 (2+1)111 (1+1+1)12 (1+2)P1688 (8+8)4444 (4+4+4+4)84211 (8+4+2+1+1)Z268882 (8+8+8+2)88442 (8+8+4+4+2)88811 (8+8+8+1+1)与其他古典密码对比密码编码空间核心机制常见场景云影密码 (01248)A~Z1/2/4/8 允许重复求和CTF Crypto 入门培根密码 (Bacon)A~Z5-bit 二进制映射隐写、历史密码栅栏密码 (Rail Fence)不限字符位置重排简单置换凯撒密码 (Caesar)A~Z固定偏移替换最经典替换密码维吉尼亚密码 (Vigenère)A~Z多表替换进阶古典密码棋盘密码 (Polybius)A~Z5×5 矩阵坐标坐标替换CTF 实战技巧识别特征密文仅由数字 0、1、2、4、8 组成，且 0 频繁出现作为分隔符：8842101220480224404014224202480122 ↑ 仅含 0 1 2 4 8混淆变体变体示例解密要点标准884210122048直接split('0')多 0 分隔8842100012200048过滤空串或压缩连续 0数字乱序488210221048不受影响（求和与顺序无关）套娃编码Base64 → 云影 → Hex需逐层解码套娃解密示例import base64 # 混合编码的密文（先 Base64，再云影） raw = base64.b64decode('某某Base64字符串').decode() flag = decode_01248(raw) print(flag) # 得到最终 Flag
AI摘要 本文介绍利用已知密码片段（前缀/后缀）爆破加密 ZIP/RAR 压缩包的方法。内容涵盖暴力枚举原理、Python 单/多线程实现、字符集优化及 hashcat 工具加速，适用于 CTF 密码破解场景。 以上内容由 AI 生成，仅供参考。概述CTF MISC / Crypto 题目中常见一类题型：给出一个加密的 ZIP/RAR 压缩包，并提示密码的一部分（如前缀、后缀或已知片段），要求爆破剩余未知位得到完整密码。全空间爆破 $62^6 \approx 5.6 \times 10^{10}$ 不可行，但已知部分后剩余空间缩小到 $62^n$（$n$ 为未知位数），枚举即可。已知密码格式: ? ? ? ? LiHua ↑ ↑ 4个未知字符 (62种可能/位) 总尝试次数: 62^4 ≈ 1.48 × 10^7暴力枚举原理搜索空间计算未知位数字符集大小尝试次数单线程耗时估算2623,844< 1 秒362238,328~2 秒46214,776,336~2 分钟562916,132,832~2 小时662$5.68 \times 10^{10}$不可行瓶颈不在 CPU 而在 I/O：每尝试一次密码都需要打开压缩包 → 文件 I/O 是主要耗时。攻击链路已知部分密码: "LiHua" (后缀) 未知位: 前 4 位 │ ▼ ┌──────────────────────┐ │ 生成候选密码 │ │ itertools.product │ │ '????' + 'LiHua' │ └──────────┬───────────┘ │ 逐条生成 ▼ ┌──────────────────────┐ │ 尝试解压 │ │ zipfile.extractall │ │ / rarfile.extract │ └──────────┬───────────┘ ├─ 密码错误 → 下一条 │ (无异常或 RuntimeError) │ ▼ 解压成功！ ┌──────────────────────┐ │ 输出正确密码 │ │ 文件成功提取 │ └──────────────────────┘Python 实现原始脚本分析（MD5 匹配法）import string from hashlib import md5 a = string.ascii_letters + string.digits # 62 个字符: a-z, A-Z, 0-9 for a1 in a: for a2 in a: for a3 in a: for a4 in a: pwd = a1 + a2 + a3 + a4 + 'LiHua' h = md5(pwd.encode('ascii')).hexdigest() if '1a4fb3fb5ee' in h: print(pwd) break脚本解读：行说明string.ascii_letters + string.digits字符集 = 52 个字母 + 10 个数字 = 62四层嵌套for枚举所有 4 位组合，时间复杂度$O(62^4)$md5(...).hexdigest()对候选密码做 MD5 哈希'1a4fb3fb5ee' in h比对部分哈希值（CTF 常只给出哈希片段）break仅跳出最内层循环（Python 的 break 不穿透多层）此方法的适用场景： 题目只给了密码的 MD5 部分值（而非加密压缩包），只需匹配哈希片段即可。完整版：ZIP 密码爆破import zipfile import itertools import string def crack_zip(zip_path: str, known_suffix: str, unknown_len: int, charset: str = None, output_dir: str = '.') -> str: """ 已知密码后缀，爆破 ZIP 文件的前缀部分 参数: zip_path: 加密 ZIP 文件路径 known_suffix: 已知的密码后缀（如 'LiHua'） unknown_len: 未知前缀的位数 charset: 字符集（默认 a-z, A-Z, 0-9） output_dir: 解压输出目录 返回: 完整密码，或 None """ if charset is None: charset = string.ascii_letters + string.digits # 62 字符 total = len(charset) ** unknown_len print(f'字符集大小: {len(charset)}, 未知位: {unknown_len}') print(f'总尝试次数: {total:,}') with zipfile.ZipFile(zip_path, 'r') as zf: for idx, prefix in enumerate( itertools.product(charset, repeat=unknown_len) ): pwd = ''.join(prefix) + known_suffix if idx % 50000 == 0: progress = idx / total * 100 print(f'[{progress:.2f}%] 尝试中... 当前: {pwd}', end='\r') try: zf.extractall(path=output_dir, pwd=pwd.encode()) print(f'\n[成功] 密码: {pwd} (第 {idx:,} 次尝试)') return pwd except (RuntimeError, zipfile.BadZipFile): continue # 密码错误，继续 print(f'\n[失败] 遍历全部 {total:,} 个组合未找到密码') return None # 使用示例 crack_zip('flag.zip', known_suffix='LiHua', unknown_len=4)多线程加速版单线程瓶颈在 ZIP 解压 I/O，多线程可并行尝试不同前缀：import zipfile import itertools import string from concurrent.futures import ThreadPoolExecutor, as_completed def try_password(zip_path, pwd, output_dir): """尝试单个密码，成功返回密码，失败返回 None""" try: with zipfile.ZipFile(zip_path, 'r') as zf: zf.extractall(path=output_dir, pwd=pwd.encode()) return pwd except (RuntimeError, zipfile.BadZipFile): return None def crack_zip_mt(zip_path, known_suffix, unknown_len, charset=None, workers=8): if charset is None: charset = string.ascii_letters + string.digits total = len(charset) ** unknown_len print(f'总尝试: {total:,} | 线程: {workers}') # 预生成所有候选密码 passwords = ( ''.join(p) + known_suffix for p in itertools.product(charset, repeat=unknown_len) ) with ThreadPoolExecutor(max_workers=workers) as executor: futures = { executor.submit(try_password, zip_path, pwd, '.'): pwd for pwd in itertools.islice(passwords, 10000) # 批次提交 } for future in as_completed(futures): result = future.result() if result: print(f'[成功] 密码: {result}') executor.shutdown(wait=False, cancel_futures=True) return result return NoneRAR 文件爆破import rarfile import itertools import string def crack_rar(rar_path: str, known_part: str, unknown_len: int, position: str = 'prefix') -> str: """ RAR 密码爆破 (需要系统安装 unrar) position: 'prefix' (未知在前) / 'suffix' (未知在后) """ charset = string.ascii_letters + string.digits for combo in itertools.product(charset, repeat=unknown_len): extra = ''.join(combo) pwd = (extra + known_part) if position == 'prefix' \ else (known_part + extra) try: with rarfile.RarFile(rar_path) as rf: rf.extractall(pwd=pwd) print(f'[成功] 密码: {pwd}') return pwd except rarfile.BadRarFile: continue return None字符集优化场景自适应已知信息推荐字符集大小4 位枚举次数无提示ascii_letters + digits62$1.48 \times 10^7$仅小写字母ascii_lowercase26456,976仅数字digits1010,000仅小写+数字ascii_lowercase + digits36$1.68 \times 10^6$已知密码为常见词自定义词表~10³极快# CTF 常见字符集预设 CHARSETS = { 'lower': string.ascii_lowercase, # 26 'upper': string.ascii_uppercase, # 26 'letters': string.ascii_letters, # 52 'digits': string.digits, # 10 'lower+digits': string.ascii_lowercase + string.digits, # 36 'all': string.ascii_letters + string.digits, # 62 'printable': string.printable.strip(), # 94 }优化策略对比# 原始写法：4 层嵌套 — 代码冗余，无法动态调整位数 for a1 in a: for a2 in a: for a3 in a: for a4 in a: pwd = a1 + a2 + a3 + a4 + 'LiHua' # ... # 优化写法：itertools.product — 一行搞定任意位数 for prefix in itertools.product(a, repeat=4): pwd = ''.join(prefix) + 'LiHua' # ...CTF 实战常见题目模式题型特征解法已知后缀爆破提示"密码后4位是 LiHua"枚举前缀，如本文示例已知前缀爆破提示"密码以 FLAG 开头"枚举后缀已知结构爆破提示"密码为 字母+4位数字"先枚举字母，再枚举数字段已知 MD5 片段给出md5(pwd)[6:16] 的部分值仅做 MD5 比对，无需解压（速度极快）掩码爆破提示格式????LiHua????前后同时枚举，或分步还原生日攻击提示"密码是某人生日"生成 1950~2020 所有日期格式字典 + 规则提示"密码是英文单词+2位数字"加载字典文件 + 枚举数字后缀MD5 片段匹配 vs 解压尝试方法每次操作耗时适用场景MD5 哈希比对~0.5 μs（微秒）仅给出哈希片段，无需实际压缩包ZIP 解压尝试~5 ms（毫秒）有实际加密 ZIP，需要解密RAR 解压尝试~20 msRAR 加密包（比 ZIP 慢 4 倍）MD5 比对比 ZIP 解压快 10,000 倍。如果题目给了哈希片段且明确密码格式，优先用 MD5 匹配效率最高。利用 hashcat 加速对于更大搜索空间（如 6 位未知），Python 单线程太慢，可结合 hashcat 掩码模式：# hashcat 掩码攻击：已知后缀 LiHua，前 4 位为小写字母 # 先提取 ZIP 的 hash zip2john flag.zip > hash.txt # 掩码爆破 (?l = 小写字母) hashcat -m 13600 -a 3 hash.txt '?l?l?l?lLiHua' # 数字 (?d) + 字母 (?l) 混合 hashcat -m 13600 -a 3 hash.txt '?l?d?l?dLiHua'工具适用搜索空间速度（4 位未知）Python (单线程)$< 10^7$~2 分钟Python (8 线程)$< 10^8$~30 秒John the Ripper$< 10^9$~10 秒hashcat (GPU)$< 10^{12}$< 1 秒常见掩码模式速查# hashcat 掩码字符 ?l = abcdefghijklmnopqrstuvwxyz ?u = ABCDEFGHIJKLMNOPQRSTUVWXYZ ?d = 0123456789 ?h = 0123456789abcdef ?H = 0123456789ABCDEF ?s = !"#$%&'()*+,-./:;<=>?@[\]^_`{|}~ ?a = ?l?u?d?s (95 字符全集) ?b = 0x00 - 0xff # 常见掩码示例 ?a?a?a?a # 4 位全字符 (95^4) ?d?d?d?d # 4 位纯数字 (10^4) ?l?l?l?lLiHua # 4 位小写 + 固定后缀 FLAG?d?d?d?d # 固定前缀 + 4 位数字 ?u?l?l?l?l?d?d # 1大写 + 4小写 + 2数字参考文献Python Software Foundation. itertools — Functions creating iterators for efficient looping [EB/OL]. https://docs.python.org/3/library/itertools.htmlPython Software Foundation. zipfile — Work with ZIP archives [EB/OL]. https://docs.python.org/3/library/zipfile.htmlhashcat. hashcat — Advanced Password Recovery [EB/OL]. https://hashcat.net/hashcat/Openwall. John the Ripper password cracker [EB/OL]. https://www.openwall.com/john/Python Software Foundation. hashlib — Secure hashes and message digests [EB/OL]. https://docs.python.org/3/library/hashlib.html
AI摘要 培根密码是弗朗西斯·培根提出的隐写术，利用两种状态（如大小写）编码字母，每个字母对应5位二进制。文章介绍了其原理、码表、Python实现及CTF中的识别与解题方法。 以上内容由 AI 生成，仅供参考。概述培根密码（Baconian Cipher / Bacon's cipher）由英国哲学家弗朗西斯·培根（Francis Bacon）于 1605 年在《学术的进展》中提出。与凯撒、仿射等替换密码不同，它的本质是一种隐写术（steganography）：秘密不在于字母被替换成了什么，而在于信息被藏进了载体文本的"外在形式"——两种字体、两种大小写、两种符号……只要能区分出两种状态，就能承载信息。每个明文字母被编码成长度为 5 的 A/B 序列（因为 $2^5 = 32 \ge 26$，5 位足以覆盖 26 个字母）。在 CTF 中，培根密码常以"密文只含两种符号、且有效长度为 5 的倍数"这一特征出现。编码: 字母 → 5 位 A/B 序列 (2^5 = 32 ≥ 26) 隐写: A/B → 载体文本的两种"形态" (小写/大写、正体/斜体、两种符号…) 解码: 载体形态 → A/B 序列 → 每 5 位一组 → 查表还原字母 两套码表: 26 字母版 每个字母独立（现代 / CTF 常用，等价 5-bit 二进制） 24 字母版 I=J、U=V 合并（培根原版，1605）编码原理隐写而非替换：为什么叫"双字母密码"培根本人称之为 biliteral cipher（双字母密码）。"双字母"指整套系统只用两个基本符号（记作 a 和 b）就能表达全部字母表——这正是二进制编码思想的雏形，比莱布尼茨系统化二进制（1703）早了近一个世纪。它与普通替换密码的根本差异，不在算法强度，而在"秘密藏在哪里"：维度替换密码（凯撒 / 仿射）培根密码秘密藏在内容：字母被换成别的字母形式：字母的字体 / 大小写 / 符号密文外观一串明显的乱码字母一段"看似正常"的文本安全依赖敌人不知道密钥敌人没意识到存在密文学科归属密码学 Cryptography隐写术 Steganography信息论视角：编码一个英文字母的理论下限是 $\log_2 26 \approx 4.70$ bit，而至少需要 $\lceil 4.70 \rceil = 5$ 位（$2^4=16 < 26 \le 32 = 2^5$）才能一一区分，所以培根固定用 5 位。代价是每位只承载 1 bit——每个载体符号仅携带 1 bit，编码 1 个字母需要 5 个载体符号，载体文本因此膨胀 5 倍。这也是隐写容量的核心约束：要藏 $n$ 个字母，载体至少要有 $5n$ 个可区分单元。培根密码的精妙不在替换本身（替换极其简单），而在于它把 0/1 悄悄"焊"进了正常文本的排版里。理解了这一点，就理解了从零宽字符到图片 LSB 的一整条现代隐写脉络。编码对照表26 字母版（现代 / CTF 常用）——本质就是"字母序号的 5 位二进制"，a=0、b=1：字母序号二进制Bacon 码字母序号二进制Bacon 码[binary] 字母版（培根 1605 原版，I/J、U/V 各占同一码）：字母码字母码字母码字母码AaaaaaGaabbaNabbaaTbaabaBaaaabHaabbbOabbabU/VbaabbCaaabaI/JabaaaPabbbaWbabaaDaaabbKabaabQabbbbXbababEaabaaLababaRbaaaaYbabbaFaababMababbSbaaabZbabbb关键差异：24 版从 I/J 合并处起，后续每个字母的码值都比 26 版"错位"。例如 26 版 K=ababa，24 版 K=abaab。CTF 解题时若一版解出乱码，务必换另一版再试。编码 / 解码示意① 明文编码（26 版，把 BACON 转成 A/B 序列）：明文 B A C O N 序号 1 0 2 14 13 ↓ ↓ ↓ ↓ ↓ 二进制 00001 00000 00010 01110 01101 ↓ ↓ ↓ ↓ ↓ Bacon aaaab aaaaa aaaba abbba abbab 拼接: aaaab aaaaa aaaba abbba abbab = aaaabaaaaaaaabaabbbaabbab (25 位 = 5×5)② 隐写解码（大小写载体，小写=a、大写=b）——这是培根密码的"杀手锏"，密文伪装成一个普通单词：载体 c r Y P T o G r a m ← "crYPToGram" 看着只是大小写怪异 大小写 ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ 小 小 大 大 大 小 大 小 小 小 A/B a a b b b a b a a a └──── aabbb ────┘└──── abaaa ────┘ 分组: aabbb abaaa 查表: H I 明文: "HI"Python 完整实现编码 / 解码类同时支持 26 版与 24 版；解码时对无法识别的 5 位组返回 ?，便于定位噪声。class BaconCipher: """培根密码编解码器，支持 24 / 26 两种码表""" # 24 字母版：I=J、U=V 合并（培根 1605 原版） TABLE_24 = { 'A': 'aaaaa', 'B': 'aaaab', 'C': 'aaaba', 'D': 'aaabb', 'E': 'aabaa', 'F': 'aabab', 'G': 'aabba', 'H': 'aabbb', 'I': 'abaaa', 'J': 'abaaa', 'K': 'abaab', 'L': 'ababa', 'M': 'ababb', 'N': 'abbaa', 'O': 'abbab', 'P': 'abbba', 'Q': 'abbbb', 'R': 'baaaa', 'S': 'baaab', 'T': 'baaba', 'U': 'baabb', 'V': 'baabb', 'W': 'babaa', 'X': 'babab', 'Y': 'babba', 'Z': 'babbb', } def __init__(self, version: int = 26): if version not in (24, 26): raise ValueError('version 只能是 24 或 26') self.version = version if version == 26: # 26 版 = 字母序号的 5 位二进制，0→a、1→b self.enc_table = { chr(ord('A') + i): format(i, '05b').replace('0', 'a').replace('1', 'b') for i in range(26) } else: self.enc_table = dict(self.TABLE_24) # 解码表：24 版中 abaaa/baabb 一码对应 I/J、U/V，取首个字母 self.dec_table = {} for ch, code in self.enc_table.items(): self.dec_table.setdefault(code, ch) def encode(self, text: str) -> str: """明文 → a/b 序列（忽略所有非字母字符）""" return ''.join(self.enc_table[ch] for ch in text.upper() if ch.isalpha()) def decode(self, seq: str) -> str: """a/b 序列 → 明文（每 5 位一组，多余位丢弃）""" seq = seq.lower() groups = [seq[i:i + 5] for i in range(0, len(seq) - len(seq) % 5, 5)] return ''.join(self.dec_table.get(g, '?') for g in groups) # 使用示例 b = BaconCipher(version=26) s = b.encode('BACON') print(s) # aaaabaaaaaaaabaabbbaabbab print(b.decode(s)) # BACON隐写：把密文藏进大小写培根的原意是用两种字型（正体/斜体）承载 a/b；在纯文本环境里，最常见的等价载体是大小写。def hide_in_case(secret: str, carrier: str, version: int = 26, a_is_lower: bool = True) -> str: """ 把 secret 编码为 a/b 序列后，藏进 carrier 的大小写中。 a_is_lower=True 表示 'a'→小写、'b'→大写。 carrier 的字母数必须 ≥ 5 × secret 的有效字母数。 """ bits = BaconCipher(version).encode(secret) letters = [c for c in carrier if c.isalpha()] if len(letters) < len(bits): raise ValueError(f'载体字母不足：需 {len(bits)} 个，仅有 {len(letters)} 个') out, bi = [], 0 for ch in carrier: if ch.isalpha() and bi < len(bits): want_lower = (bits[bi] == 'a') == a_is_lower out.append(ch.lower() if want_lower else ch.upper()) bi += 1 else: out.append(ch) return ''.join(out) def reveal_from_case(stego: str, version: int = 26, a_is_lower: bool = True) -> str: """从大小写隐写文本中提取 a/b 序列并解码""" bits = ''.join( 'a' if (ch.islower() == a_is_lower) else 'b' for ch in stego if ch.isalpha() ) return BaconCipher(version).decode(bits) # 使用示例 stego = hide_in_case('HI', 'cryptogram') print(stego) # crYPToGram print(reveal_from_case(stego)) # HI自动识别与变种爆破CTF 里 a/b 未必是字母，可能是 01、大小写、两种标点、长短音……而且 a↔b 可能被反转、码表可能是 24 或 26。把"归一化"与"爆破"拆开处理：def normalize(cipher: str) -> str: """把常见的两态载体统一成 a/b 序列""" chars = [c for c in cipher if not c.isspace()] kinds = set(chars) # 情况 1：全文只由两种符号构成（AB、01、./- 等） if len(kinds) == 2: lo = sorted(kinds)[0] return ''.join('a' if c == lo else 'b' for c in chars) # 情况 2：大小写混合的字母 → 小写=a、大写=b（隐写载体） letters = [c for c in cipher if c.isalpha()] if letters and any(c.islower() for c in letters) and any(c.isupper() for c in letters): return ''.join('a' if c.islower() else 'b' for c in letters) raise ValueError('无法自动识别两种状态，请手动指定映射') def auto_decode(cipher: str, hint: str = 'flag') -> list: """对归一化序列做 正反映射 × 24/26 版本 的全爆破，命中 hint 者排前""" seq = normalize(cipher) flip = seq.translate(str.maketrans('ab', 'ba')) out = [] for label, s in (('原映射', seq), ('翻转 a↔b', flip)): for ver in (26, 24): plain = BaconCipher(ver).decode(s) out.append((ver, label, plain)) out.sort(key=lambda r: hint.lower() in r[2].lower(), reverse=True) return out # 示例：一段大小写隐写，自动还原 for ver, label, plain in auto_decode('crYPToGram', hint='hi'): print(f'[{ver}版 / {label}] {plain}') # [26版 / 原映射] HI ← 命中，排在最前 # [24版 / 原映射] HI # [26版 / 翻转 a↔b] YX # [24版 / 翻转 a↔b] YWCTF 实战常见载体形式（题型）培根密码的"变装"能力极强，识别关键始终是找出那两种状态：载体形式密文特征识别 / 解法两种字母只含 A、B（或 a、b），长度 5 的倍数直接查表，试 A↔B 反转二进制 01 串只含 0、1，长度 5 的倍数0=a 1=b（或反）按 5 位分组大小写隐写一段"正常"英文，大小写异常小写=a、大写=b（或反）提取字体 / 格式隐写正体 vs 斜体、粗体、下划线两种字型 → a/b（培根本意）长短 / 高低两种长度的横线、两种音高…归一化为两种符号套娃编码培根 → 摩斯 / Base 等叠加逐层按字符集判断识别与解题流程快速判定：密文是否同时满足——① 只有两种可区分状态；② 有效符号数是 5 的倍数（或去噪后接近）。两条都命中，优先怀疑培根密码。步骤操作说明1 识别统计字符 / 大小写 / 字型种类恰好两种状态是强信号2 归一两种状态 →a、b约定其一为 a，另一为 b3 对齐按 5 位分组长度非 5 倍数 → 排查噪声字符4 查表每组 a/b → 字母26 版、24 版各试一次5 试反A↔B 反转再解一遍出题人常故意反转映射6 验证是否出现 flag 头命中flag{、ctf{ 即停穷举空间极小：2（映射反转）× 2（24/26 版本）= 4 种组合，毫秒级即可全部试完。与其他编码 / 隐写对比方案基本符号本质典型识别特征培根密码2 种状态隐写 + 二进制编码两态、有效长度为 5 的倍数摩斯电码· —变长编码点划、有分隔、变长二进制 / ASCII0 1定长编码长度为 8 的倍数Base6464 字符编码出现+ / =，长度 4 的倍数栅栏密码26 字母置换字母表不变，仅顺序被打乱凯撒 / 仿射26 字母替换一串无意义字母培根密码的"强度"几乎为零——一旦被识别，穷举只有 4 种组合。它的全部价值在于隐蔽而非强度：只要对手没发现文本里藏了东西，再弱的编码也是安全的。这正是隐写术与密码学的分野。
AI摘要 栅栏密码是一种置换密码，分为W型锯齿和分组矩阵转置两种。文章阐述了其原理、Python实现及CTF中的暴力破解方法。 以上内容由 AI 生成，仅供参考。概述栅栏密码（Rail Fence Cipher）是一种典型的置换密码（transposition cipher）：它不改变任何字母本身，只打乱字母的位置。这与凯撒、仿射等"替换密码"（改变字母内容）以及培根密码（隐藏于形式）都属于不同的家族。中文语境下的"栅栏密码"实际上混指两种做法，务必先分清：W 型（锯齿 / Zigzag）栅栏：把明文沿"之"字形写在 N 条轨道（rail）上，再逐行读出——这是国际标准的 Rail Fence Cipher。分组（栏栅）栅栏：把明文每 N 个字符切成一组，再按"列"的顺序取字重排——本质是矩阵转置，中文 CTF 工具里最常见。本质: 密文是明文的一个「位置置换」π，字母集合完全不变 c[i] = p[π(i)] 解密 = 逆置换 π⁻¹ W 型 明文沿 N 条轨道锯齿排列 → 逐行读 (周期 2(N-1)) 分组 明文按 N 字一组填入矩阵 → 逐列读 (等价矩阵转置) 密钥 W 型: 轨道数 rails ∈ [2, L-1] 分组: 每组字数 key（多取 L 的因子）编码原理置换而非替换：为什么"字母没变，却读不通"栅栏密码的加密可以形式化为对下标集合 $\{0,1,\dots,L-1\}$ 的一个置换 $\pi$：密文第 $i$ 位等于明文第 $\pi(i)$ 位。解密只需应用逆置换 $\pi^{-1}$。因为置换是双射，解密天然唯一——这一点与仿射密码"必须 $\gcd(a,26)=1$ 才可逆"形成对照：置换密码的可逆性由结构保证，无需额外条件。三大古典密码家族的根本差异：家族代表操作对象字母本身单字母频率替换凯撒 / 仿射字母的值改变整体平移，分布形状保留置换栅栏 / 列置换字母的位置不变完全不变隐写培根字母的形式承载于载体——这正是识别置换密码的关键指纹：密文的单字母频率和正常英文几乎一致，读起来却毫无意义。因为只是换位，E 还是那么多、T 还是那么多——频率分析能一眼看出"这是置换而非替换"，但单字母频率对求解密钥毫无帮助，真正被破坏的是双字母 / N-gram 的相邻关系。W 型栅栏：锯齿排列与周期设轨道数为 $N$。字符在轨道间上下往返，形成周期为 $\text{cycle} = 2(N-1)$ 的三角波。第 $i$ 个字符所在的轨道号可由下式直接算出：$$ r = i \bmod 2(N-1), \qquad \text{rail}(i) = \min(r,\ 2(N-1) - r) $$以明文 FLAGISHERE、$N=3$（$\text{cycle}=4$）为例： 0 1 2 3 4 5 6 7 8 9 ← 明文位置 rail0: F . . . I . . . R . rail1: . L . G . S . E . E rail2: . . A . . . H . . . 逐行读出 → [FIR] [LGSEE] [AH] = FIRLGSEEAH轨道数越多，锯齿越"深"，相邻字母被拉得越开。但密钥空间仅 $N \in [2, L-1]$，即 $L-2$ 种，暴力枚举是平凡的。分组栅栏：矩阵转置视角分组栅栏等价于：把明文按行填进一个 列数 = key 的矩阵，再按列读出——也就是矩阵转置。以明文 WELCOMETOCTF、$key=3$ 为例：按行填入 (每行 key=3): 按列读出: W E L 列0: W C E C C O M → 列1: E O T T E T O 列2: L M O F C T F 密文: WCECEOTTLMOF解密时行列互换即可还原。它的密钥（每组字数 $key$）通常取明文长度 $L$ 的因子，否则末组不齐，需引入填充约定——因此分组栅栏的可用密钥比 W 型更少，破解更快。Python 完整实现W 型栅栏加解密def rail_fence_encrypt(text: str, rails: int) -> str: """W 型栅栏加密：沿 rails 条轨道锯齿排列后逐行读出""" if rails < 2: return text fence = [[] for _ in range(rails)] rail, step = 0, 1 for ch in text: fence[rail].append(ch) if rail == 0: step = 1 # 触底折返向下 elif rail == rails - 1: step = -1 # 触顶折返向上 rail += step return ''.join(''.join(row) for row in fence) def rail_fence_decrypt(cipher: str, rails: int) -> str: """W 型栅栏解密：先复原锯齿骨架，再按列回填""" if rails < 2: return cipher n = len(cipher) # 1) 标记每个位置属于哪条轨道 pattern, rail, step = [], 0, 1 for _ in range(n): pattern.append(rail) if rail == 0: step = 1 elif rail == rails - 1: step = -1 rail += step # 2) 按轨道顺序把密文依次填回原位 result, idx = [None] * n, 0 for r in range(rails): for i in range(n): if pattern[i] == r: result[i] = cipher[idx] idx += 1 return ''.join(result) # 使用示例 c = rail_fence_encrypt('WEAREDISCOVEREDFLEEATONCE', 3) print(c) # WECRLTEERDSOEEFEAOCAIVDEN print(rail_fence_decrypt(c, 3)) # WEAREDISCOVEREDFLEEATONCE分组栅栏加解密def fence_group_encrypt(text: str, key: int) -> str: """分组栅栏加密：每 key 个字符一组，逐列读出（矩阵转置）""" groups = [text[i:i + key] for i in range(0, len(text), key)] out = [] for col in range(key): for g in groups: if col < len(g): # 兼容长度不整除时的短末组 out.append(g[col]) return ''.join(out) def fence_group_decrypt(cipher: str, key: int) -> str: """分组栅栏解密（假设 len 可被 key 整除）""" n = len(cipher) rows = n // key # 组数 = 每列长度 cols = [cipher[i * rows:(i + 1) * rows] for i in range(key)] out = [] for r in range(rows): for c in range(key): out.append(cols[c][r]) return ''.join(out) # 使用示例 c = fence_group_encrypt('WELCOMETOCTF', 3) print(c) # WCECEOTTLMOF print(fence_group_decrypt(c, 3)) # WELCOMETOCTF暴力破解（未知密钥）栅栏密码的密钥空间极小，直接枚举 + flag 头判分即可：def crack_rail_fence(cipher: str, hint: str = 'flag') -> list: """同时爆破 W 型（枚举轨道数）与分组型（枚举长度因子）""" n, results = len(cipher), [] # W 型：轨道数 2 ~ n-1 for rails in range(2, n): plain = rail_fence_decrypt(cipher, rails) if hint.lower() in plain.lower(): results.append(('W型', rails, plain)) # 分组型：每组字数取 n 的真因子 for key in range(2, n): if n % key == 0: plain = fence_group_decrypt(cipher, key) if hint.lower() in plain.lower(): results.append(('分组', key, plain)) return results # 示例：未知参数，自动命中含 flag 的解 cipher = rail_fence_encrypt('flagblrailfenceyes', 4) for kind, key, plain in crack_rail_fence(cipher, hint='flag'): print(f'[{kind} / key={key}] {plain}')若无 flag 头，可把判分函数换成"英文常见词命中数"或"字母 N-gram 对数似然"，对每个候选打分排序，人工确认最高分即可。CTF 实战常见题型题型特征解法W 型未知栏数字母乱序、无重复规律枚举rails 2 ~ L-1分组未知组数长度含小因子枚举 L 的因子作key已知栏数 / 组数题面直接给 N直接解，秒出带起始偏移锯齿不从顶部起笔额外枚举起点 / 相位置换 + 替换套娃栅栏 + 凯撒 / Base64先还原位置再解替换，逐层剥离解题流程快速判定：若密文的单字母频率接近自然英文、却完全读不通，几乎可锁定为置换密码，栅栏是首选尝试。步骤操作说明1 判类统计字母频率分布正常但不可读 → 置换密码2 分解对长度 L 做质因数分解决定分组型可行的key 集合3 枚举 Wrails 从 2 试到 L-1空间仅 L-2，毫秒级4 枚举分组key 取 L 的因子因子很少，极快5 验证检查 flag 头 / 词频命中flag{、ctf{ 即停6 剥层若仍乱码叠加了替换 / 编码，继续解与其他古典密码对比密码类型密钥空间字母是否改变抗频率分析栅栏（W型）置换$L-2$否弱（单频不变，暴露置换特征）栅栏（分组）置换$L$ 的因子数否弱列置换密码置换$n!$（n=列数）否中凯撒密码替换25是极弱仿射密码替换312是弱维吉尼亚密码替换$26^n$是中栅栏密码的密钥空间随明文长度线性增长（$L-2$），看似不小，实则每个密钥都能瞬间验证，暴力破解毫无门槛。它的真正意义在于展示"置换"这一密码学基本操作，而非提供安全性。
AI摘要 仿射密码是基于模运算的单表替换密码，加密公式为y=(ax+b) mod 26。文章阐述了其数学原理（a需与26互质）、Python实现（含加密解密及爆破函数），并探讨了CTF中的已知明文攻击与频率分析破解方法。 以上内容由 AI 生成，仅供参考。概述仿射密码（Affine Cipher）是一种基于模运算的单表替换密码。其加密函数为线性变换加偏移，解密依赖模逆元。在 CTF 中常以"已知部分明文（如 flag 头）→ 爆破参数 a、b → 还原完整明文"的形式出现。加密: y = (a·x + b) mod m 解密: x = a⁻¹·(y - b) mod m x = 明文字母序号 (0~25) y = 密文字母序号 (0~25) m = 字母表大小 (26) a, b = 密钥 (a 必须与 m 互质)数学原理为什么 a 必须与 m 互质如果要解密唯一，加密必须是双射（一一对应）。加密函数 $E(x) = (ax + b) \bmod m$ 是双射的充分必要条件是 $\gcd(a, m) = 1$。证明：若 $\gcd(a, m) = d > 1$，则存在 $x_1 \neq x_2$ 使得：$$ ax_1 \equiv ax_2 \pmod{m} $$即 $a(x_1 - x_2) \equiv 0 \pmod{m}$。由于 $d \mid a$ 且 $d \mid m$，可取 $x_1 - x_2 = m/d < m$，使得 $a \cdot (m/d) \equiv 0 \pmod{m}$。此时 $E(x_1) = E(x_2)$，加密不再是一对一。$\gcd(a, 26)$a 的取值范围数量解密可行性11, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 2512唯一可逆> 1其余 14 个数14映射多对一，解密不唯一模逆元与解密解密需要求 $a$ 在模 $m$ 下的逆元 $a^{-1}$，满足：$$ a \cdot a^{-1} \equiv 1 \pmod{m} $$对于 $m=26$，各有效 $a$ 的逆元：| a | 1 | 3 | 5 | 7 | 9 | 11 | 15 | 17 | 19 | 21 | 23 | 25 || :-------: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: || a⁻¹ | 1 | 9 | 21 | 15 | 3 | 19 | 7 | 23 | 11 | 5 | 17 | 25 |# 计算模逆元（扩展欧几里得算法） def mod_inverse(a: int, m: int = 26) -> int: """返回 a 在模 m 下的逆元，若不互质则返回 None""" def egcd(a, b): if b == 0: return a, 1, 0 g, x1, y1 = egcd(b, a % b) return g, y1, x1 - (a // b) * y1 g, x, _ = egcd(a, m) if g != 1: return None return x % m # 示例 print(mod_inverse(5, 26)) # 输出: 21 print(mod_inverse(20, 26)) # 输出: None (gcd(20,26)=2)加密/解密示意以 a=5, b=8 加密 "HELLO" 为例 明文 H → 7 E → 4 L → 11 L → 11 O → 14 ↓ ↓ ↓ ↓ ↓ 加密 y=(5·7+8)%26 (5·4+8)%26 (5·11+8)%26 (5·11+8)%26 (5·14+8)%26 =43%26=17 =28%26=2 =63%26=11 =63%26=11 =78%26=0 ↓ ↓ ↓ ↓ ↓ 密文 R → 17 C → 2 L → 11 L → 11 A → 0 结果: "RCLLA"Python 完整实现加密类import math class AffineCipher: def __init__(self, a: int, b: int, m: int = 26): if math.gcd(a, m) != 1: raise ValueError( f'a={a} 与 m={m} 不互质 (gcd={math.gcd(a,m)})，' f'解密不唯一，请使用以下合法值之一: ' f'{[x for x in range(1,m) if math.gcd(x,m)==1]}' ) self.a = a self.b = b self.m = m self.a_inv = self._mod_inverse(a, m) @staticmethod def _mod_inverse(a: int, m: int) -> int: def egcd(a, b): if b == 0: return a, 1, 0 g, x1, y1 = egcd(b, a % b) return g, y1, x1 - (a // b) * y1 g, x, _ = egcd(a, m) return x % m def encrypt(self, plain: str) -> str: """加密 (仅处理 a-z，其他字符原样保留)""" result = [] for ch in plain: if 'a' <= ch <= 'z': x = ord(ch) - ord('a') y = (self.a * x + self.b) % self.m result.append(chr(y + ord('a'))) elif 'A' <= ch <= 'Z': x = ord(ch) - ord('A') y = (self.a * x + self.b) % self.m result.append(chr(y + ord('A'))) else: result.append(ch) return ''.join(result) def decrypt(self, cipher: str) -> str: """解密: D(y) = a⁻¹·(y - b) mod m""" result = [] for ch in cipher: if 'a' <= ch <= 'z': y = ord(ch) - ord('a') x = (self.a_inv * (y - self.b)) % self.m result.append(chr(x + ord('a'))) elif 'A' <= ch <= 'Z': y = ord(ch) - ord('A') x = (self.a_inv * (y - self.b)) % self.m result.append(chr(x + ord('A'))) else: result.append(ch) return ''.join(result) # 使用示例 cipher = AffineCipher(a=5, b=8) enc = cipher.encrypt('HELLO') print(enc) # RCLLA print(cipher.decrypt(enc)) # HELLO已知明文爆破CTF 中最常见的场景：已知密文 + 部分明文（如 flag 头 flag{），爆破参数 $(a, b)$。def crack_affine(ciphertext: str, known_plain: str) -> list: """ 已知明文攻击：用已知的明文-密文对应关系爆破 a, b 返回: [(a, b, 解密结果), ...] """ results = [] c_part = ciphertext[:len(known_plain)] for a in range(1, 26): if math.gcd(a, 26) != 1: # 跳过不互质的 a continue for b in range(0, 26): match = True for cp, kp in zip(c_part, known_plain): if not ('a' <= cp <= 'z' and 'a' <= kp <= 'z'): continue y = ord(cp) - ord('a') x = ord(kp) - ord('a') if y != (a * x + b) % 26: match = False break if match: cipher = AffineCipher(a, b) results.append((a, b, cipher.decrypt(ciphertext))) return results # 示例 c = 'siwm{ewk3ys28-10ks-11ye-80e5-8k1645499qee}' res = crack_affine(c, 'flag') for a, b, flag in res: print(f'a={a}, b={b} → {flag}')爆破过程说明：密文: s i w m { ... ↓ ↓ ↓ 已知明文: f l a g { (flag 的格式已知) ↓ ↓ ↓ 方程组: 18=(a·5 +b)%26 8=(a·11+b)%26 22=(a·0+b)%26 ↓ ↓ ↓ (s=18,f=5) (i=8,l=11) (w=22,a=0) 由第三式: b ≡ 22 (mod 26) → b = 22 代入第一式: 5a + 22 ≡ 18 (mod 26) → 5a ≡ 22 (mod 26) 5⁻¹ ≡ 21 (mod 26) → a ≡ 22×21 ≡ 20 (mod 26) 验证第二式: 11×20+22 = 242 ≡ 8 (mod 26) ✓ 结论: a=20, b=22 ⚠ a=20 与 26 不互质 → 解密存在二义性 → 需用枚举方式逐字解密逐字枚举解密（当 a 不互质时）仿射密码理论要求 $\gcd(a, m)=1$，但 CTF 出题时可能使用不互质的 $a$。此时解密不唯一，需逐字枚举：def decrypt_bruteforce(ciphertext: str, a: int, b: int) -> str: """逐字爆破解密：对每个密文字母尝试所有 26 种明文映射""" result = [] for ch in ciphertext: if 'a' <= ch <= 'z': y = ord(ch) - ord('a') for x in range(26): if (a * x + b) % 26 == y: result.append(chr(x + ord('a'))) break # 取第一个匹配（可能不唯一） else: result.append(ch) return ''.join(result) print(decrypt_bruteforce(c, a=20, b=22))CTF 实战常见题型题型特征解法已知明文头密文形如siwm{...}，已知 flag 格式用前 4 字符爆破 a、b全小写字母密文仅含 a-z，无其他字符频率分析 + 仿射参数验证已知 a 或 b题目提示密钥之一仅爆破剩余参数，空间缩小到 26分段仿射不同位置使用不同 (a,b)逐段爆破混合编码Base64 → 仿射 → Hex 套娃逐层解码频率分析法当密文足够长且未知密钥时，可利用英文字母频率分布推断参数：字母英语频率示例映射假设E12.7%密文最高频 → E (x=4)T9.1%密文第二高频 → T (x=19)A8.2%密文第三高频 → A (x=0)from collections import Counter def freq_attack(ciphertext: str) -> list: """基于频率分析的仿射密码破解""" # 统计密文字母频率 counts = Counter(ch for ch in ciphertext if 'a' <= ch <= 'z') most_common = counts.most_common(2) results = [] for a in [x for x in range(1, 26) if math.gcd(x, 26) == 1]: y1 = ord(most_common[0][0]) - ord('a') # 最高频密文 → E(4) y2 = ord(most_common[1][0]) - ord('a') # 次高频密文 → T(19) # 解方程组: y1 = a·4 + b, y2 = a·19 + b # → b = y1 - 4a, 代入 → y2 - y1 = 15a → a = (y2-y1)·15⁻¹ inv15 = mod_inverse(15, 26) if inv15 is None: continue a_candidate = ((y2 - y1) * inv15) % 26 if a_candidate != a: continue b_candidate = (y1 - a * 4) % 26 cipher = AffineCipher(a_candidate, b_candidate) results.append((a_candidate, b_candidate, cipher.decrypt(ciphertext))) return results与其他古典密码对比密码密钥空间加密公式抗频率分析仿射密码12 × 26 = 312$ax+b \bmod 26$弱凯撒密码25$x+b \bmod 26$极弱乘法密码12$ax \bmod 26$弱维吉尼亚密码$26^n$ (n=密钥长度)$x + k_i \bmod 26$中Hill 密码$26^{n^2}$$Ax \bmod 26$较强仿射密码的密钥空间仅 312，可在毫秒级完成爆破。比凯撒密码（25）略好，但远不足以对抗现代攻击。参考文献Wikipedia. Affine cipher [EB/OL]. https://en.wikipedia.org/wiki/Affine_cipherTrappe W, Washington L C. Introduction to Cryptography with Coding Theory [M]. Pearson, 2006.Stinson D R. Cryptography: Theory and Practice [M]. CRC Press, 2005.Python Software Foundation. math — Mathematical functions [EB/OL]. https://docs.python.org/3/library/math.html
AI摘要 本文解析了RSA算法原理，并详细列举了CTF中常见的RSA攻击方式，包括N分解、低加密指数、广播攻击、Wiener攻击及共模攻击等，附带代码实现。 以上内容由 AI 生成，仅供参考。算法核心选择两个大素数 $p, q$，令 $n = p \cdot q$，欧拉函数 $\varphi(n) = (p-1)(q-1)$。选取 $e$ 满足 $\gcd(e, \varphi(n)) = 1$，计算 $d \equiv e^{-1} \pmod{\varphi(n)}$。公钥：$(n, e)$私钥：$(n, d)$加密：$c \equiv m^e \pmod{n}$解密：$m \equiv c^d \pmod{n}$正确性证明：由 $ed \equiv 1 \pmod{\varphi(n)}$，存在整数 $k$ 使得 $ed = k\varphi(n) + 1$。$$ c^d \equiv (m^e)^d \equiv m^{ed} \equiv m^{k\varphi(n) + 1} \equiv (m^{\varphi(n)})^k \cdot m \pmod{n} $$根据欧拉定理，当 $\gcd(m, n) = 1$ 时 $m^{\varphi(n)} \equiv 1 \pmod{n}$，代入得 $c^d \equiv m \pmod{n}$。若 $\gcd(m, n) \neq 1$（即 $m$ 是 $p$ 或 $q$ 的倍数），可通过中国剩余定理分别验证模 $p$ 和模 $q$ 下成立，RSA 解密在该情况下仍然正确1。欧拉函数 $\varphi(n)$： 小于 $n$ 且与 $n$ 互质的正整数个数。积性：$\gcd(a, b) = 1$ 时 $\varphi(ab) = \varphi(a)\varphi(b)$。若 $p$ 为素数，$\varphi(p) = p - 1$由积性：$\varphi(pq) = (p-1)(q-1)$对于素数幂 $p^r$：$\varphi(p^r) = p^r - p^{r-1}$（区间 $[1, p^r]$ 中仅 $p, 2p, \dots, p^{r-1}p$ 共 $p^{r-1}$ 个数与 $p^r$ 不互素）几个 $\varphi(n)$ 的变形：情形$\varphi(n)$标准$n = pq$$(p-1)(q-1)$$n = p^r$$p^r - p^{r-1}$$n = pqr$（三素数）$(p-1)(q-1)(r-1)$模逆元： $d$ 满足 $e \cdot d \equiv 1 \pmod{\varphi(n)}$。可解性的充要条件是 $\gcd(e, \varphi(n)) = 1$——这正是密钥生成时选择 $e$ 的约束。求解使用扩展欧几里得算法（Extended Euclidean Algorithm），该算法在求出 $\gcd$ 的同时返回 Bézout 系数。d = libnum.invmod(e, phi_n) # libnum d = int(gmpy2.invert(e, phi_n)) # gmpy2 d = pow(e, -1, phi_n) # Python 3.8+基础加解密模板：import libnum p = libnum.generate_prime(1024) q = libnum.generate_prime(1024) m = libnum.s2n('flag{test}') n = p * q phi_n = (p - 1) * (q - 1) d = libnum.invmod(e, phi_n) c = pow(m, e, n) m = pow(c, d, n) print(libnum.n2s(m))N 的分解当 $p, q$ 选择不当，$n$ 可被分解，RSA 安全性直接瓦解。在线查询： factordb.com，常用的大数可能已有记录。yafu 本地分解：yafu-x64.exe factor(123456789) yafu-x64.exe "factor(@)" -batchfile n.txt$p, q$ 过于接近 — 费马分解：对于任意奇数 $n = pq$，可表示为平方差：$$ n = pq = \left(\frac{p+q}{2}\right)^2 - \left(\frac{p-q}{2}\right)^2 = a^2 - b^2 $$其中 $a = \frac{p+q}{2}$，$b = \frac{p-q}{2}$。而 $a = \sqrt{n + b^2} \ge \sqrt{n}$。当 $p, q$ 接近时，$b$ 很小，$a \approx \sqrt{n}$。从 $a = \lceil\sqrt{n}\rceil$ 开始递增，检查 $a^2 - n$ 是否为完全平方数。若 $a^2 - n = b^2$，则 $p = a+b$, $q = a-b$。时间复杂度取决于 $|p-q|$：差值为 $O(n^{1/4})$ 时约需 $O(n^{1/4})$ 步，远优于试除法。def fermat(n): a = gmpy2.iroot(n, 2)[0] while True: b2 = a * a - n b, ok = gmpy2.iroot(b2, 2) if ok: return int(a + b), int(a - b) a += 1低加密指数$e=3$ 且 $m^3 < n$ 时，模运算退化为普通整数运算：$c = m^3$（未发生取模回绕）。此时 $m = \sqrt[3]{c}$ 可直接在整数域求解。若 $m^e \ge n$，则 $c = m^e - kn$（$k$ 为取模时减去的 $n$ 的倍数）。由于 $m < n$，$k < e \cdot n^{e-1}$ 通常很小——爆破 $k$ 即可：$$ m = \sqrt[e]{c + k \cdot n} $$# 场景一：m^e < n，直接开根 m = gmpy2.iroot(c, e)[0] # 场景二：m^e >= n，爆破 k k = 0 while True: m, ok = gmpy2.iroot(c + k * n, e) if ok: break k += 1广播攻击 (Håstad)相同 $m$、相同 $e$，使用不同 $n_i$ 加密得到多组 $(n_i, c_i)$。攻击核心是 Håstad 定理：若 $n_i$ 两两互素且 $m < \min(n_i)$，则当密文数 $\ge e$ 时，可唯一确定 $m$。构造同余方程组：$$ \begin{cases} m^e \equiv c_1 \pmod{n_1} \\ m^e \equiv c_2 \pmod{n_2} \\ \quad\vdots \\ m^e \equiv c_k \pmod{n_k} \end{cases} $$由中国剩余定理，存在唯一解 $M \equiv m^e \pmod{\prod n_i}$。因 $m^e < \prod n_i$（当 $k \ge e$ 且每个 $n_i$ 足够大时），$M = m^e$ 在整数域上成立，对 $M$ 开 $e$ 次根即得 $m$。from functools import reduce def crt(remainders, moduli): M = reduce(lambda x, y: x * y, moduli) x = 0 for r, m in zip(remainders, moduli): Mi = M // m ti = gmpy2.invert(Mi, m) x += r * Mi * ti return x % M m_e = crt(c_list, n_list) m = gmpy2.iroot(m_e, e)[0]共模攻击同一 $n$ 下，用互素的两个 $e_1, e_2$ 加密同一 $m$ 得到 $c_1, c_2$。由 Bézout 恒等式，$\gcd(e_1, e_2) = 1$ 意味着存在整数 $s, t$ 使：$$ s \cdot e_1 + t \cdot e_2 = 1 $$因此：$$ c_1^s \cdot c_2^t \equiv (m^{e_1})^s \cdot (m^{e_2})^t \equiv m^{s e_1 + t e_2} \equiv m^1 \equiv m \pmod{n} $$$s$ 或 $t$ 可能为负，此时需要对应的模逆元：$c^{-s} \equiv (c^{-1})^s \pmod{n}$。_, s, t = gmpy2.gcdext(e1, e2) m = (pow(c1, s, n) * pow(c2, t, n)) % n若 $s$ 或 $t$ 为负，pow(c, -s, n) 等价于 pow(gmpy2.invert(c, n), s, n)。共享素数多个 $n$ 共用一个素因子：q = gmpy2.gcd(n1, n2) p1 = n1 // q p2 = n2 // qWiener 攻击当 $d$ 很小（$d < \frac{1}{3}n^{1/4}$）而 $e$ 相应很大时，Wiener 利用连分数展开恢复 $d$。推导思路： 由 $ed \equiv 1 \pmod{\varphi(n)}$ 得 $ed - k\varphi(n) = 1$，两边除以 $d\varphi(n)$：$$ \left|\frac{e}{\varphi(n)} - \frac{k}{d}\right| = \frac{1}{d\varphi(n)} $$由于 $p, q$ 是大素数，$\varphi(n) = n - p - q + 1 \approx n$，因此：$$ \left|\frac{e}{n} - \frac{k}{d}\right| \approx \frac{1}{d\varphi(n)} < \frac{1}{2d^2} $$根据 Dirichlet 逼近定理，$\frac{k}{d}$ 必然是 $\frac{e}{n}$ 的连分数展开中的某个渐近分数。逐一检查每个渐近分数的分母 $d_i$ 是否满足 $e \cdot d_i \equiv 1 \pmod{\varphi(n)}$（等价于用 $d_i$ 解密一段已知明文验证）。import owiener d = owiener.attack(e, n) if d: m = pow(c, d, n)dp / dq 泄露快速解密的一个常用优化（CRT-RSA）会计算 $dp = d \bmod (p-1)$ 和 $dq = d \bmod (q-1)$。一旦这些中间值泄露，即可攻破 RSA。仅有 dp 泄露：由定义 $dp \equiv d \pmod{p-1}$，两边同乘 $e$：$$ dp \cdot e \equiv d \cdot e \equiv 1 \pmod{p-1} $$因此存在整数 $k$ 使 $dp \cdot e - 1 = k(p-1)$。变形得 $p = \frac{dp \cdot e - 1}{k} + 1$。由于 $dp < p-1$，有 $k < e$，只需枚举 $k \in [1, e)$ 并验证 $n \bmod p = 0$：for k in range(1, e): if (dp * e - 1) % k == 0: p = (dp * e - 1) // k + 1 if n % p == 0: q = n // p break同时有 dp, dq： 直接用 CRT 解密，无需计算 $d$：由 $dp \equiv d \pmod{p-1}$ 知 $m \equiv c^{dp} \pmod{p}$（因为 $c^{dp} \equiv c^d \equiv m \pmod{p}$，其中 $c^d = c^{k(p-1) + dp}$ 且费马小定理消去 $c^{k(p-1)}$）。同理 $m \equiv c^{dq} \pmod{q}$。联立用 CRT 还原 $m \bmod n$：inv_q = gmpy2.invert(q, p) mp = pow(c, dp, p) mq = pow(c, dq, q) m = (((mp - mq) * inv_q) % p) * q + mq$n = p^r$$n$ 是单个素数的幂，无独立的 $q$。$\varphi(p^r)$ 的推导： 区间 $[1, p^r]$ 中共 $p^r$ 个整数。与 $p^r$ 不互素的数必定是 $p$ 的倍数：$p, 2p, 3p, \dots, p^{r-1} \cdot p$，共 $p^{r-1}$ 个。因此：$$ \varphi(p^r) = p^r - p^{r-1} = p^{r-1}(p-1) $$这也是 $\varphi$ 函数积性在单素数幂场景的直接结果。p = gmpy2.iroot(n, r)[0] phi_n = p**r - p**(r-1) d = gmpy2.invert(e, phi_n) m = pow(c, d, n)$e$ 与 $\varphi(n)$ 不互素$\gcd(e, \varphi(n)) = t > 1$ 时，$e$ 在模 $\varphi(n)$ 下不存在逆元，无法按常规方式生成 $d$。此时将 $e$ 约去公因子：令 $e' = e/t$，则 $\gcd(e', \varphi(n)) = 1$，可求 $d'$ 满足 $e' \cdot d' \equiv 1 \pmod{\varphi(n)}$。解密过程变为：$$ c^{d'} \equiv m^{e \cdot d'} \equiv m^{t \cdot e' \cdot d'} \equiv m^t \pmod{n} $$即解密得到 $m^t$，再在整数域上开 $t$ 次根恢复 $m$。前提是 $t$ 足够小且 $m^t < n$（否则需要枚举 $k$ 修正，类同低加密指数攻击）。t = gmpy2.gcd(e, phi_n) d = gmpy2.invert(e // t, phi_n) m_t = pow(c, d, n) m = gmpy2.iroot(m_t, t)[0]已知 $e, d, n$ 恢复 $p, q$同时拥有公钥和私钥时，可在不分解 $n$ 的情况下恢复 $p, q$。原理： $ed - 1$ 是 $\varphi(n) = (p-1)(q-1)$ 的倍数。令 $ed - 1 = 2^s \cdot t$（$t$ 为奇数）。考虑模 $n$ 下的乘法群 $\mathbb{Z}_n^*$。由 Carmichael 定理，对任意 $g \in \mathbb{Z}_n^*$ 有 $g^{\varphi(n)} \equiv 1 \pmod{n}$，因此 $g^{ed-1} \equiv 1 \pmod{n}$。关键观察：$x^2 \equiv 1 \pmod{n}$ 在 $n = pq$ 时有四个平方根：$\pm 1, \pm x_0$（其中 $x_0 \equiv 1 \pmod{p}, x_0 \equiv -1 \pmod{q}$）。若随机选取 $g$ 并计算 $g^{t}, g^{2t}, g^{4t}, \dots, g^{2^s t}$，必有一项 $x$ 是非平凡的平方根（$x \not\equiv \pm 1$ 但 $x^2 \equiv 1$），此时 $\gcd(x-1, n)$ 必为 $p$ 或 $q$。该算法成功的概率至少为 $1/2$（每次尝试失败后换一个 $g$ 即可）。k = e * d - 1 while True: g = random.randint(2, n - 1) t = k while t % 2 == 0: t //= 2 x = pow(g, t, n) if x > 1 and gmpy2.gcd(x - 1, n) > 1: p = gmpy2.gcd(x - 1, n) q = n // p return p, qPEM 文件解析from Crypto.PublicKey import RSA with open('pubkey.pem', 'rb') as f: key = RSA.import_key(f.read()) print(key.n, key.e) # 私钥文件同理，额外包含 .d .p .q其他攻击方向Coppersmith — $p$ 高位已知时，在 sage 中用 small_roots 求解Franklin-Reiter — 两条明文仅差已知固定值时，用 sage 求多项式 GCDBoneh-Durfee — Wiener 的增强版，$d < n^{0.292}$ 时适用高位攻击 / 格基归约 — 利用 LLL 处理部分已知比特参考文献Rivest R L, Shamir A, Adleman L. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems [J]. Communications of the ACM, 1978.Boneh D. Twenty Years of Attacks on the RSA Cryptosystem [J]. Notices of the AMS, 1999.Wiener M J. Cryptanalysis of Short RSA Secret Exponents [J]. IEEE Trans. on Info. Theory, 1990.Håstad J. Solving Simultaneous Modular Equations of Low Degree [J]. SIAM J. on Computing, 1988. 若 $\gcd(m, n) \neq 1$，不妨设 $p \mid m$，则 $m^{ed} \equiv m \pmod{p}$ 显然成立（两边均 $\equiv 0$）。对 $q$ 使用费马小定理，$m^{ed} = m^{k\varphi(n)+1} = m \cdot (m^{q-1})^{k(p-1)} \equiv m \pmod{q}$。CRT 联立得 $m^{ed} \equiv m \pmod{n}$。 ↩