文章总结： 本文解析CTF挑战OneTimePad2，揭示其加密实为基于GF(2^128)的伪随机数生成器。通过已知明文攻击、代数变换及离散对数求解，成功逆向密钥生成逻辑并获取flag。文章详细拆解了有限域运算与矩阵快速幂原理，警示自研加密算法的脆弱性及LCG不安全原则，建议采用标准加密方案。 综合评分： 90 文章分类： CTF,逆向分析,漏洞分析
OneTimePad2 CTF密码学挑战完整解析
原创
破镜安全
破镜安全
2026年1月12日 08:01 四川
OneTimePad2 CTF密码学挑战完整解析
前言
本文将详细分析一道CTF密码学挑战题目，该题目涉及有限域运算、矩阵代数、离散对数等多个密码学核心概念。通过本文的学习，读者将掌握如何分析自定义加密算法、识别密码学漏洞，以及运用数学工具进行密码破解。
题目背景
题目名称为”OneTimePad2″，暗示使用了一次性密码本（One-Time Pad）加密方式。题目提供了两个文件：
- oneTimePad2.py – 加密脚本源代码
- ciphertxt – 加密后的密文
密文内容（十六进制）：
0da8e9e84a99d24d0f788c716ef9e99cc447c3cf12c716206dee92b9ce591dc0722d42462918621120ece68ac64e493a41ea3a70dd7fe2b1d116ac48f08dbf2b26bd63834fa5b4cb75e3c60d496760921b91df5e5e631e8e9e50c9d80350249c
第一部分：加密算法分析
1.1 整体架构
首先，我们需要仔细阅读加密脚本，理解其工作流程。通过分析代码，可以发现加密过程包含以下几个关键步骤：
- 生成一个128位的随机初始密钥
- 将明文分成16字节的块
- 对每个块使用当前密钥进行异或加密
- 使用特定算法生成下一个密钥
- 重复步骤3-4直到所有明文块被加密
这是一个典型的流密码结构，关键在于密钥生成算法的安全性。
1.2 核心函数详解
加密脚本中包含三个核心函数，让我们逐一深入分析。
1.2.1 process1函数 – 有限域乘法
def process1(m, k):
res = 0
for i in bin(k)[2:]:
res = res << 1
if (int(i)):
res = res ^ m
if (res >> 128):
res = res ^ P
return res
功能识别：
这个函数实现的是有限域GF(2^128)上的乘法运算。要理解这个函数，我们需要先了解什么是有限域。
有限域基础知识：
有限域（Galois Field，简称GF）是包含有限个元素的代数结构。GF(2^128)表示一个包含2^128个元素的有限域。在这个域中：
- 加法运算就是按位异或（XOR）
- 乘法运算需要使用不可约多项式进行模运算
算法原理：
process1函数使用的是”俄罗�斯农民乘法”（Russian Peasant Multiplication）的变体：
- 将乘数k转换为二进制表示
- 从最高位开始遍历k的每一位
- 每次迭代将结果左移一位（相当于乘以x）
- 如果当前位为1，则将m加到结果上（在GF(2^128)中加法就是XOR）
- 如果结果超过128位，使用不可约多项式P进行模运算
不可约多项式P：
P = 0x100000000000000000000000000000087
这个值对应的多项式是：x^128 + x^7 + x^2 + x + 1
当结果超过128位时，通过异或P来保证结果始终在GF(2^128)范围内。
1.2.2 process2函数 – 矩阵乘法
def process2(a, b):
res = []
res.append(process1(a[0], b[0]) ^ process1(a[1], b[2]))
res.append(process1(a[0], b[1]) ^ process1(a[1], b[3]))
res.append(process1(a[2], b[0]) ^ process1(a[3], b[2]))
res.append(process1(a[2], b[1]) ^ process1(a[3], b[3]))
return res
功能识别：
通过仔细观察这个函数的计算模式，可以发现它实现的是2×2矩阵乘法。
矩阵表示：
将列表[a, b, c, d]看作矩阵：
[a b]
[c d]
矩阵乘法验证：
对于两个2×2矩阵A和B，它们的乘积C = A × B的计算公式为：
C[0,0] = A[0,0] * B[0,0] + A[0,1] * B[1,0]
C[0,1] = A[0,0] * B[0,1] + A[0,1] * B[1,1]
C[1,0] = A[1,0] * B[0,0] + A[1,1] * B[1,0]
C[1,1] = A[1,0] * B[0,1] + A[1,1] * B[1,1]
在GF(2^128)中：
- 加法 = 异或（XOR）
- 乘法 = process1函数
因此，process2函数正确实现了GF(2^128)上的2×2矩阵乘法。
1.2.3 nextrand函数 – 密钥生成核心
def nextrand(rand):
global N, A, B
tmp1 = [1, 0, 0, 1]
tmp2 = [A, B, 0, 1]
s = N
N = process1(N, N)
while s:
if s % 2:
tmp1 = process2(tmp2, tmp1)
tmp2 = process2(tmp2, tmp2)
s = s / 2
return process1(rand, tmp1[0]) ^ tmp1[1]
功能分析：
这个函数是整个加密系统的核心，它负责从当前密钥生成下一个密钥。
算法识别：
仔细观察while循环的结构，这是一个典型的二进制快速幂算法。该算法用于高效计算矩阵的N次幂。
矩阵定义：
M = [A B]
[0 1]
其中A和B是脚本中定义的常量：
A = 0xc6a5777f4dc639d7d1a50d6521e79bfd
B = 0x2e18716441db24baf79ff92393735345
快速幂算法原理：
快速幂算法通过二进制分解来高效计算幂次。例如，计算M^13：
- 13的二进制是1101
- M^13 = M^8 × M^4 × M^1
- 只需要3次矩阵乘法，而不是12次
关键观察：
函数最后返回：process1(rand, tmp1[0]) ^ tmp1[1]
其中tmp1是M^N的结果。如果M^N = [[m00, m01], [m10, m11]]，则返回值为：
rand * m00 + m01
这意味着下一个密钥的生成公式为：
KEY_next = A^N * KEY_current + M^N[0,1]
1.3 数学建模
通过对矩阵M的幂次进行数学分析，我们可以发现一个重要的规律。
矩阵M的幂次规律：
让我们计算M的前几次幂：
M^1 = [A B]
[0 1]
M^2 = [A^2 A*B + B]
[0 1]
M^3 = [A^3 A^2*B + A*B + B]
[0 1]
观察可得，M^N的一般形式为：
M^N = [A^N B*(A^(N-1) + A^(N-2) + ... + 1)]
[0 1]
等比数列求和：
右上角元素是一个等比数列的和，可以简化为：
B*(A^(N-1) + A^(N-2) + ... + 1) = B * (A^N - 1) / (A - 1)
因此，密钥生成的完整数学公式为：
KEY[i+1] = A^N * KEY[i] + B * (A^N - 1) / (A - 1)
重要发现：
每次调用nextrand后，全局变量N会更新为N^2。这意味着：
KEY[0] = K0（初始密钥）
KEY[1] = A^N * KEY[0] + B * (A^N - 1) / (A - 1)
KEY[2] = A^(N^2) * KEY[1] + B * (A^(N^2) - 1) / (A - 1)
KEY[3] = A^(N^4) * KEY[2] + B * (A^(N^4) - 1) / (A - 1)
第二部分：漏洞识别
2.1 为什么这不是真正的一次性密码本？
真正的一次性密码本（One-Time Pad）必须满足三个条件：
- 密钥必须完全随机
- 密钥长度必须等于明文长度
- 密钥只能使用一次
本题的加密系统虽然名为”OneTimePad”，但实际上是一个伪随机数生成器（PRNG）。密钥序列是通过确定性的数学公式生成的，而不是真正随机的。这就为密码分析提供了可能。
2.2 已知明文的发现
查看加密脚本的第79行：
plain = "One-Time Pad is used here. You won't know that the flag is flag{%s}." % top_secret
这行代码揭示了一个关键信息：明文的格式是固定的！前64个字节的内容是：
"One-Time Pad is used here. You won't know that the flag is flag{"
这是一个典型的已知明文攻击场景。
2.3 攻击思路
基于以上分析，我们可以制定攻击策略：
- 利用已知明文恢复前4个密钥块
- 利用密钥生成的数学关系建立方程
- 求解方程得到A^N
- 通过离散对数求解N
- 重建密钥生成器，解密完整密文
第三部分：攻击实施
3.1 步骤一：提取密钥流
由于加密使用的是异或操作，我们可以直接恢复密钥：
KEY = PLAINTEXT XOR CIPHERTEXT
编写Python脚本实现：
def str2num(s):
if isinstance(s, str):
return int(s.encode().hex(), 16)
return int(s.hex(), 16)
# 读取密文
with open('ciphertxt', 'r') as f:
ct = bytes.fromhex(f.read().strip())
# 已知明文
plain = "One-Time Pad is used here. You won't know that the flag is flag{"
# 提取前4个密钥块（每块16字节）
keys = []
for i in range(0, 64, 16):
key = str2num(plain[i:i+16]) ^ str2num(ct[i:i+16])
keys.append(key)
运行后得到：
KEY[0] = 0x42c68cc51ef0bf282f28ed154e909abc
KEY[1] = 0xb134a6ab32af735208c0b2e0a12c3db7
KEY[2] = 0x1d43653209730c7e57cc92e2a73a694e
KEY[3] = 0x298f1a16b11e8591b8658c2e9cecd850
3.2 步骤二：建立数学方程
根据前面的数学建模，我们知道：
KEY[1] = A^N * KEY[0] + B * (A^N - 1) / (A - 1)
我们的目标是求解A^N。这个方程中，KEY[0]、KEY[1]、A、B都是已知的，只有A^N是未知数。
3.3 步骤三：代数变换求解A^N
让我们对方程进行变换。首先将方程两边同时乘以(A-1)：
KEY[1] * (A - 1) = A^N * KEY[0] * (A - 1) + B * (A^N - 1)
展开右边：
KEY[1] * (A - 1) = A^N * KEY[0] * (A - 1) + B * A^N - B
移项整理：
KEY[1] * (A - 1) + B = A^N * (KEY[0] * (A - 1) + B)
因此：
A^N = [KEY[1] * (A - 1) + B] / [KEY[0] * (A - 1) + B]
3.4 步骤四：计算有限域逆元
在GF(2^128)中，除法等价于乘以逆元。我们需要计算分母的逆元。
费马小定理：
在有限域GF(2^128)中，对于任意非零元素a，有：
a^(2^128) = a
因此：
a^(2^128 - 1) = 1
a^(-1) = a^(2^128 - 2)
这样我们可以通过快速幂算法计算逆元。
实现代码：
P = 0x100000000000000000000000000000087
A = 0xc6a5777f4dc639d7d1a50d6521e79bfd
B = 0x2e18716441db24baf79ff92393735345
def process1(m, k):
res = 0
for i in bin(k)[2:]:
res = res << 1
if (int(i)):
res = res ^ m
if (res >> 128):
res = res ^ P
return res
def pow1(m, k):
"""GF(2^128)上的快速幂运算"""
res = 1
while k:
if k % 2:
res = process1(res, m)
m = process1(m, m)
k = k // 2
return res
# 计算A^N
p0 = keys[0]
p1 = keys[1]
# 计算分子: KEY[1] * (A - 1) + B
uppp = process1(p1, A ^ 1) ^ B
# 计算分母: KEY[0] * (A - 1) + B
down = process1(p0, A ^ 1) ^ B
# 计算分母的逆元
down_inv = pow1(down, 2**128 - 2)
# 计算A^N
AN = process1(uppp, down_inv)
运行后得到：
A^N = 0x837790eaa9f443442382e6bf24ef525
3.5 步骤五：求解离散对数
现在我们知道了A^N的值，但还需要求出N本身。这是一个离散对数问题：
问题定义：
已知：A = 0xc6a5777f4dc639d7d1a50d6521e79bfd
已知：A^N = 0x837790eaa9f443442382e6bf24ef525
求解：N
离散对数问题：
离散对数问题是密码学中的经典难题。给定g^x = h，求解x。
在不同的群结构中，离散对数的难度不同：
- 在整数模p的乘法群中，这是一个困难问题
- 在GF(2^n)中，可以使用次指数时间算法求解
- 对于128位的GF(2^128)，使用现代计算机可以在合理时间内求解
使用Sage求解：
我们使用Sage数学软件来求解离散对数。Sage提供了强大的有限域运算和离散对数求解功能。
from sage.all import *
P = 0x100000000000000000000000000000087
A = 0xc6a5777f4dc639d7d1a50d6521e79bfd
AN = 0x837790eaa9f443442382e6bf24ef525
# 将整数转换为GF(2^128)中的多项式
def ntopoly(npoly):
return sum(c*X**e for e, c in enumerate(Integer(npoly).bits()))
X = GF(2).polynomial_ring().gen()
poly = ntopoly(P)
F = GF(2**128, modulus=poly, name='a')
# 将A和A^N转换为有限域元素
a = F(ntopoly(A))
an = F(ntopoly(AN))
# 求解离散对数（这个过程需要几分钟）
N = int(discrete_log(an, a))
# 验证结果
assert a**N == an
运行后得到：
N = 76716889654539547639031458229653027958
验证通过，说明我们成功求解了N值。
3.6 步骤六：重建密钥生成器并解密
现在我们已经知道了初始密钥KEY[0]和参数N，可以重建整个密钥生成器来解密完整的密文。
完整解密代码：
def str2num(s):
if isinstance(s, str):
return int(s.encode().hex(), 16)
return int(s.hex(), 16)
def num2str(n, block=16):
s = hex(n)[2:].rstrip('L')
s = '0' * ((32-len(s)) % 32) + s
return bytes.fromhex(s)
P = 0x100000000000000000000000000000087
A = 0xc6a5777f4dc639d7d1a50d6521e79bfd
B = 0x2e18716441db24baf79ff92393735345
N = 76716889654539547639031458229653027958
def process1(m, k):
res = 0
for i in bin(k)[2:]:
res = res << 1
if (int(i)):
res = res ^ m
if (res >> 128):
res = res ^ P
return res
def process2(a, b):
res = []
res.append(process1(a[0], b[0]) ^ process1(a[1], b[2]))
res.append(process1(a[0], b[1]) ^ process1(a[1], b[3]))
res.append(process1(a[2], b[0]) ^ process1(a[3], b[2]))
res.append(process1(a[2], b[1]) ^ process1(a[3], b[3]))
return res
def nextrand(rand):
global N, A, B
tmp1 = [1, 0, 0, 1]
tmp2 = [A, B, 0, 1]
s = N
N = process1(N, N)
while s:
if s % 2:
tmp1 = process2(tmp2, tmp1)
tmp2 = process2(tmp2, tmp2)
s = s // 2
return process1(rand, tmp1[0]) ^ tmp1[1]
def keygen(key):
while True:
yield key
key = nextrand(key)
# 读取密文
with open('ciphertxt', 'r') as f:
ct = bytes.fromhex(f.read().strip())
# 获取初始密钥
plain = "One-Time Pad is used here. You won't know that the flag is flag{"
K = str2num(plain[0:16]) ^ str2num(ct[0:16])
# 解密
result = b''
generator = keygen(K)
for i in range(0, len(ct), 16):
key = next(generator)
block = str2num(ct[i:i+16]) ^ key
result += num2str(block)
print(result.decode('utf-8', errors='ignore'))
解密结果：
One-Time Pad is used here. You won't know that the flag is flag{LCG1sN3ver5aFe!!}.
成功获取flag：flag{LCG1sN3ver5aFe!!}
第四部分：技术深度解析
4.1 为什么GF(2^128)中的离散对数可解？
离散对数问题的难度取决于群的结构和大小。在GF(2^n)这样的有限域中，存在次指数时间算法：
Pohlig-Hellman算法：
- 当群的阶可以分解为小素数的乘积时，可以将离散对数问题分解为多个小问题
- 时间复杂度约为O(√p)，其中p是最大素因子
Index Calculus算法：
- 专门用于有限域的离散对数求解
- 对于GF(2^128)，复杂度约为L(1/3)，是次指数级的
这就是为什么128位的GF(2^128)虽然看起来很大，但在现代计算机上仍然可以在几分钟内求解。
4.2 矩阵快速幂的数学原理
矩阵快速幂算法利用了矩阵乘法的结合律。对于矩阵M和指数N：
二进制分解：
如果 N = 13 = 1101(二进制)
则 M^13 = M^8 × M^4 × M^1
算法流程：
- 初始化结果矩阵为单位矩阵I
- 将N转换为二进制
- 从低位到高位遍历N的每一位
- 如果当前位为1，将当前的M^(2^i)乘到结果上
- 每次迭代将M平方
这样只需要O(log N)次矩阵乘法，而不是O(N)次。
4.3 已知明文攻击的威力
已知明文攻击是密码分析中最基本但也最有效的攻击方式之一。
攻击条件：
- 攻击者知道部分明文和对应的密文
- 加密算法使用确定性的密钥生成方式
- 密钥生成算法存在数学结构
本题中的应用：
- 明文格式固定，前64字节已知
- 流密码使用异或，可直接恢复密钥
- 密钥生成遵循数学公式，可建立方程求解
这充分说明了为什么密码系统不能依赖于明文格式的保密性。
4.4 流密码的安全性要求
流密码的安全性完全依赖于密钥流的质量。一个安全的流密码必须满足：
密钥流要求：
- 不可预测性：无法从已知的密钥流推测未来的密钥
- 周期性：周期必须足够长，避免重复
- 统计随机性：通过各种随机性测试
本题的问题：
- 密钥生成算法是确定性的
- 存在明确的数学关系
- 可以通过代数方程求解
这就是为什么真正的一次性密码本要求密钥必须是真随机的，而不能使用伪随机数生成器。
第五部分：安全性分析与防御
5.1 本题加密系统的安全缺陷
通过完整的分析和攻击，我们可以总结出这个加密系统存在以下致命缺陷：
1. 明文格式可预测
- Flag格式固定，导致大量已知明文
- 没有使用随机化技术（如加盐）
2. 密钥生成器可逆
- 密钥序列遵循确定性数学规律
- 可以通过代数方程求解参数
3. 域大小不足
- GF(2^128)的离散对数在现代计算能力下可解
- 应该使用更大的域或不同的群结构
4. 缺乏认证机制
- 没有消息认证码（MAC）
- 容易受到篡改攻击
5. 伪随机数生成器设计不当
- 使用了类似LCG的结构
- 存在明显的数学关系
5.2 如何设计安全的加密系统
基于本题的教训，设计安全的加密系统应该遵循以下原则：
1. 使用标准算法
- 使用经过充分验证的加密算法（如AES-GCM）
- 不要自己设计加密算法
2. 避免明文格式泄露
- 不要在明文中包含固定格式
- 使用随机化技术增加不确定性
3. 使用密码学安全的随机数生成器
- 使用CSPRNG（Cryptographically Secure Pseudo-Random Number Generator）
- 确保随机数生成器通过了严格的统计测试
4. 添加认证机制
- 使用AEAD（Authenticated Encryption with Associated Data）模式
- 确保密文的完整性和真实性
5. 密钥管理
- 使用足够长的密钥
- 实现安全的密钥交换协议
- 定期更换密钥
第六部分：总结与启示
6.1 解题步骤回顾
本题的完整攻击流程可以总结为以下步骤：
- 算法分析：识别出process1是GF(2^128)乘法，process2是矩阵乘法，nextrand是矩阵快速幂
- 数学建模：推导出密钥生成的数学公式
- 已知明文攻击：利用固定格式恢复前4个密钥块
- 代数求解：通过方程变换求解A^N
- 计算逆元：使用费马小定理计算GF(2^128)中的逆元
- 离散对数：使用Sage求解离散对数得到N
- 完整解密：重建密钥生成器，解密完整密文
6.2 关键技术点
密码学知识：
- 有限域GF(2^n)的运算规则
- 流密码的工作原理
- 已知明文攻击的方法
- 离散对数问题及其求解
数学技能：
- 矩阵运算和快速幂算法
- 代数方程的变换和求解
- 等比数列求和公式的应用
- 费马小定理的应用
编程能力：
- Python编程实现复杂数学运算
- Sage数学软件的使用
- 代码调试和结果验证
- 算法优化和效率提升
6.3 深层启示
1. 密码系统的安全性不能依赖于算法的复杂性
本题的加密算法看起来很复杂，涉及有限域运算、矩阵乘法等高级数学概念。但是，复杂性不等于安全性。只要存在数学结构，就可能被分析和破解。
2. 已知明文是流密码的致命弱点
流密码通过异或操作加密，一旦有已知明文，就可以直接恢复密钥流。这就是为什么现代密码系统要避免明文格式的可预测性。
3. 数学结构的存在可能导致代数攻击
本题的密钥生成算法存在明确的数学关系，这使得我们可以建立方程并求解。这说明密码系统的设计必须避免可被利用的数学结构。
4. 真正的安全需要使用标准算法
自己设计的加密算法往往存在未知的漏洞。使用经过学术界和工业界充分验证的标准算法（如AES、ChaCha20等）才是明智的选择。
5. LCG永远不安全
题目的flag”LCG1sN3ver5aFe!!”明确指出：线性同余生成器（Linear Congruential Generator）永远不安全。本题的密钥生成算法虽然使用了矩阵运算，但本质上仍然是一个确定性的伪随机数生成器，存在类似LCG的缺陷。
6.4 实战价值
本题不仅是一道CTF挑战，更是一次完整的密码分析实战演练：
学习价值：
- 掌握有限域运算的实际应用
- 理解流密码的工作原理和弱点
- 学会使用数学工具进行密码分析
- 培养从理论到实践的能力
实战技能：
- 代码审计和算法识别
- 数学建模和方程求解
- 工具使用（Python、Sage）
- 攻击策略的制定和实施
结论
本文通过对OneTimePad2这道CTF密码学挑战的完整分析，展示了如何系统性地分析和破解一个自定义加密算法。
核心发现：
- 该加密系统虽然名为”一次性密码本”，但实际上是一个存在严重缺陷的伪随机数生成器
- 通过已知明文攻击，我们成功恢复了密钥流
- 利用密钥生成算法的数学结构，通过代数方程求解出关键参数
- 使用Sage数学软件求解GF(2^128)中的离散对数
- 最终成功解密得到flag：
flag{LCG1sN3ver5aFe!!}
技术总结：
本题涉及的核心技术包括：
- 有限域GF(2^128)的乘法运算
- 2×2矩阵的快速幂算法
- 已知明文攻击方法
- 代数方程的变换与求解
- 费马小定理求逆元
- 离散对数问题的求解
安全启示：
密码系统的安全性建立在以下基础之上：
- 使用经过验证的标准算法
- 避免明文格式的可预测性
- 确保密钥生成器的密码学安全性
- 使用足够大的密钥空间
- 添加完整性验证机制
最后的思考：
正如flag所揭示的：”LCG1sN3ver5aFe!!”（LCG永远不安全），这道题目通过一个精心设计的例子，向我们展示了为什么不应该使用线性同余生成器或类似的确定性算法来生成密钥。
密码学是一门严谨的科学，任何看似微小的设计缺陷都可能导致整个系统的崩溃。作为安全研究人员，我们需要：
- 保持对密码系统的敬畏之心
- 深入理解密码学的数学基础
- 掌握密码分析的实战技能
- 始终使用经过验证的标准算法
希望本文的分析能够帮助读者深入理解密码学的原理，提升密码分析的能力，在CTF竞赛和实际安全工作中取得更好的成绩。
Flag:flag{LCG1sN3ver5aFe!!}
免责声明：
本文所载程序、技术方法仅面向合法合规的安全研究与教学场景，旨在提升网络安全防护能力，具有明确的技术研究属性。
任何单位或个人未经授权，将本文内容用于攻击、破坏等非法用途的，由此引发的全部法律责任、民事赔偿及连带责任，均由行为人独立承担，本站不承担任何连带责任。
本站内容均为技术交流与知识分享目的发布，若存在版权侵权或其他异议，请通过邮件联系处理，具体联系方式可点击页面上方的联系我。
本文转载自：破镜安全 破镜安全《OneTimePad2 CTF密码学挑战完整解析》
版权声明
本站仅做备份收录，仅供研究与教学参考之用。
读者将信息用于其他用途的，全部法律及连带责任由读者自行承担，本站不承担任何责任。
评论