文章总结： 这篇文章详细解析了一道名为青梅竹马的CTF逆向题，该题融合了密码学与中国文化元素。文章从题目名称的文化隐喻入手，识别出这是一道基于RSA算法的破解题，目标是通过求解幂模方程M^e≡2(modN)找到正确的序列号。作者系统介绍了RSA算法原理、欧拉函数、模逆元等密码学基础，并提供了完整的解题流程，包括生成素数列表、构造模数N、计算欧拉函数、求解私钥d等步骤。文章还详细解释了自定义Base64编码的实现过程，并提供了完整的验证代码。最终得出序列号为PEDIyV9102dVreadyu，并通过数学验证确认其正确性。文章不仅展示了CTF解题技巧，还深入分析了RSA安全性的数学基础，对密码学学习者有很高的参考价值。 综合评分： 92 文章分类： CTF,逆向分析,密码学,漏洞分析,实战经验
青梅竹马：一道融合密码学与文化的CTF逆向题深度解析
原创
破镜安全
破镜安全
2025年12月13日 08:02 四川
青梅竹马：一道融合密码学与文化的CTF逆向题深度解析
前言
在CTF（Capture The Flag）竞赛中，crypto类题目往往结合了数学、密码学和编程技巧。今天要介绍的”青梅竹马”是一道设计精巧的题目，它不仅考察密码学知识，还巧妙地融入了中国传统文化元素。
本文将从零开始，带领大家完整地分析和解决这道题目，让即使是密码学新手也能理解其中的原理和技巧。
一、题目初探
1.1 题目信息
拿到题目后，我们首先了解基本信息：
- 题目名称：青梅竹马
- 题目文件：
crackme_readyu2019_FIX1.exe - 题目类型：Crypto + Reverse
- 目标：找到正确的序列号（Serial Number）
- 验证要求：序列号只能包含大小写字母和数字
- 成功提示：输入正确序列号后显示 “yes, correct sn!”
1.2 文件信息
先查看文件的基本信息：
$ file crackme_readyu2019_FIX1.exe
crackme_readyu2019_FIX1.exe: PE32 executable (GUI) Intel 80386, for MS Windows
这是一个32位的Windows可执行文件。
1.3 题目名称的玄机
在开始技术分析之前，我们先思考一个问题：为什么题目叫”青梅竹马”？
“青梅竹马”源自李白的诗句”郎骑竹马来，绕床弄青梅”，形容从小一起长大的男女。这个成语让我们联想到另一个相关的成语——“两小无猜”。
这里的关键词是”两小”，在数学语境中，它暗示着：
- “两” = 数字 2
- “小” = 小素数
这个文化隐喻实际上在提示我们：
- 最终答案可能与数字2有关
- 题目可能涉及小素数的使用
这是出题者留下的第一个重要线索！
二、密码学基础知识
在深入分析题目之前，我们需要掌握一些必要的密码学知识。
2.1 什么是RSA算法？
RSA是一种非对称加密算法，由Ron Rivest、Adi Shamir和Leonard Adleman在1977年提出。它的安全性基于大整数分解的困难性。
RSA的基本流程：
1. 密钥生成
① 选择两个大素数 p 和 q
② 计算 N = p × q（N称为模数）
③ 计算 φ(N) = (p-1) × (q-1)（欧拉函数）
④ 选择公钥指数 e，满足 1 < e < φ(N) 且 gcd(e, φ(N)) = 1
⑤ 计算私钥指数 d，满足 e × d ≡ 1 (mod φ(N))
2. 加密
密文 C = M^e mod N
3. 解密
明文 M = C^d mod N
2.2 欧拉函数 φ(n)
欧拉函数 φ(n) 表示小于等于n的正整数中与n互质的数的个数。
重要性质：
- 素数的欧拉函数：
- 对于素数 p：φ(p) = p – 1
- 原因：除了p本身，所有小于p的正整数都与p互质
- 积性性质：
- 如果 gcd(m, n) = 1，则 φ(m × n) = φ(m) × φ(n)
- 素数乘积的欧拉函数：
- φ(p₁ × p₂ × … × pₖ) = (p₁-1) × (p₂-1) × … × (pₖ-1)
举例说明：
# 计算 φ(15)
# 15 = 3 × 5
φ(15) = φ(3 × 5) = φ(3) × φ(5) = (3-1) × (5-1) = 2 × 4 = 8
# 验证：小于15且与15互质的数：1, 2, 4, 7, 8, 11, 13, 14，共8个
2.3 模逆元
定义：对于整数 a 和模数 m，如果存在整数 x 使得：
a × x ≡ 1 (mod m)
则称 x 为 a 模 m 的逆元，记作 a⁻¹ 或 x ≡ a⁻¹ (mod m)。
求解方法：使用扩展欧几里得算法（Extended Euclidean Algorithm）
算法原理：
- 普通欧几里得算法求 gcd(a, b)
- 扩展版本还能找到 x 和 y，使得 a×x + b×y = gcd(a, b)
- 当 gcd(a, b) = 1 时，两边对 b 取模：a×x ≡ 1 (mod b)
- 此时 x 就是 a 的模逆元
代码实现：
def extended_gcd(a, b):
"""扩展欧几里得算法"""
if a == 0:
return b, 0, 1
gcd, x1, y1 = extended_gcd(b % a, a)
x = y1 - (b // a) * x1
y = x1
return gcd, x, y
def mod_inverse(e, phi):
"""求模逆元"""
gcd, x, y = extended_gcd(e, phi)
if gcd != 1:
raise Exception("模逆元不存在")
return (x % phi + phi) % phi
2.4 欧拉定理
定理内容：如果 gcd(a, n) = 1，则：
a^φ(n) ≡ 1 (mod n)
这个定理是RSA算法正确性的数学基础。
RSA为什么能正确解密？
已知：e × d ≡ 1 (mod φ(N))
即：e × d = k × φ(N) + 1（k为某个整数）
解密过程：
C^d = (M^e)^d = M^(e×d) = M^(k×φ(N)+1) = M × (M^φ(N))^k
根据欧拉定理：M^φ(N) ≡ 1 (mod N)
所以：M × (M^φ(N))^k ≡ M × 1^k ≡ M (mod N)
因此解密能正确恢复明文 M
三、题目分析与建模
现在我们有了必要的理论基础，开始分析这道题目。
3.1 题目的核心机制
通过分析题目设计思路，我们发现这道题的核心是求解一个幂模方程：
M^e ≡ 2 (mod N)
其中：
- M：我们要求的未知数（最终会编码成序列号）
- e：加密指数（需要确定）
- N：一个特殊构造的合数（需要分析）
- 2：方程右侧（对应”两小无猜”的提示）
3.2 为什么这个方程可解？
在标准RSA中，给定密文C和公钥(e, N)，在不知道私钥d的情况下，解密是计算困难的（这是RSA安全性的基础）。
但这道题设计了一个特殊场景：
关键点1：N是小素数的乘积
- N = p₁ × p₂ × … × pₖ（多个小素数）
- 这意味着我们可以轻松”分解”N
关键点2：可以直接计算 φ(N)
- 因为知道所有素因子，可以直接计算欧拉函数
- φ(N) = (p₁-1) × (p₂-1) × … × (pₖ-1)
关键点3：可以求出私钥 d
- 通过 d = e⁻¹ mod φ(N)，我们能计算出私钥
关键点4：反向求解 M
- 有了私钥d，就能通过 M = 2^d mod N 求出M
这实际上是一个**”已知公钥和密文，通过分解N来破解RSA”**的教学案例。
3.3 解题思路总览
第一步：生成100以内的素数列表
↓
第二步：构造模数N（排除2，从3到73）
↓
第三步：计算欧拉函数 φ(N)
↓
第四步：确定加密指数e（选择83）
↓
第五步：求私钥 d = e⁻¹ mod φ(N)
↓
第六步：计算 M = 2^d mod N
↓
第七步：将M转为16进制
↓
第八步：使用自定义Base64编码
↓
第九步：添加分隔符得到最终序列号
四、完整解题过程
4.1 生成素数列表
首先，我们需要生成100以内的所有素数。
素数判断算法（试除法）：
def is_prime(n):
"""判断一个数是否为素数"""
if n < 2:
return False
if n == 2:
return True
if n % 2 == 0: # 排除偶数
return False
# 只需检查到√n
for i in range(3, int(n**0.5) + 1, 2):
if n % i == 0:
return False
return True
def generate_primes_under(limit):
"""生成小于limit的所有素数"""
primes = []
for i in range(2, limit):
if is_prime(i):
primes.append(i)
return primes
# 生成100以内的素数
primes = generate_primes_under(100)
print(primes)
输出结果：
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
共有 25个素数。
4.2 构造模数N
接下来需要构造N，但这里有几个关键问题需要理解。
问题1：为什么排除素数2？
原因分析：
- 题目提示：”两小无猜” → 2应该在方程右侧，而不是N的因子
- 数学要求：方程是 M^e ≡ 2 (mod N)
- 如果2是N的因子，那么N是偶数
- 这会导致方程性质改变，可能无唯一解
- 保证互质：M和N需要互质，而右侧是2，所以N不能包含2
问题2：为什么在79处截止？
分析：
- 79的十六进制：0x4F
- ASCII码：0x4F = ‘O’（大写字母O）
- 这是出题者设置的一个技巧性边界
N的计算
N = 1
factors = []
for p in primes:
if p == 2: # 排除2
continue
if p >= 79: # 在79处截止
break
N *= p
factors.append(p)
print(f"N的素因子: {factors}")
print(f"N = {N}")
计算结果：
N的素因子: [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73]
N = 20364840299624512075310661735
N是一个 93位（bit）的大整数，由20个素数相乘得到。
4.3 计算欧拉函数 φ(N)
根据欧拉函数的积性性质：
phi_N = 1
phi_factors = []
for p in factors:
phi_N *= (p - 1)
phi_factors.append(p - 1)
print(f"φ(N)的因子: {phi_factors}")
print(f"φ(N) = {phi_N}")
计算过程：
φ(N) = φ(3) × φ(5) × φ(7) × ... × φ(73)
= (3-1) × (5-1) × (7-1) × ... × (73-1)
= 2 × 4 × 6 × 10 × 12 × 16 × 18 × 22 × 28 × 30 × 36 × 40 × 42 × 46 × 52 × 58 × 60 × 66 × 70 × 72
= 5133855159158901099724800000
结果：
φ(N) = 5133855159158901099724800000
4.4 选择加密指数e
题目选择 e = 83 作为加密指数。
为什么选择83？
必要条件：e 必须满足 gcd(e, φ(N)) = 1
验证83的合理性：
- 83是素数：素数只与1互质或与自身相等
- 83 > 73：83大于N的最大素因子，所以不是N的因子
- φ(N)的因子分析：
- φ(N)的所有因子项：2, 4, 6, …, 72
- 都小于83
- 所以83不可能整除φ(N)
e = 83
# 验证互质性
gcd, _, _ = extended_gcd(e, phi_N)
print(f"gcd({e}, φ(N)) = {gcd}")
if gcd == 1:
print("✓ e和φ(N)互质，模逆元存在")
输出：
gcd(83, φ(N)) = 1
✓ e和φ(N)互质，模逆元存在
4.5 求解私钥d
现在求解私钥d，使得：
e × d ≡ 1 (mod φ(N))
即求83在模φ(N)下的逆元。
d = mod_inverse(e, phi_N)
print(f"私钥 d = {d}")
计算结果：
d = 1855610298491169072189686747
验证：
# 验证 e × d ≡ 1 (mod φ(N))
result = (e * d) % phi_N
print(f"e × d mod φ(N) = {result}") # 应该等于1
4.6 计算M
现在我们可以计算M了！
数学推导：
原方程：M^e ≡ 2 (mod N)
两边取d次方：(M^e)^d ≡ 2^d (mod N)
化简左边：M^(e×d) ≡ 2^d (mod N)
因为 e×d ≡ 1 (mod φ(N))，设 e×d = k×φ(N) + 1
所以：M^(k×φ(N)+1) ≡ 2^d (mod N)
M × (M^φ(N))^k ≡ 2^d (mod N)
根据欧拉定理：M^φ(N) ≡ 1 (mod N)（假设gcd(M,N)=1）
所以：M × 1^k ≡ 2^d (mod N)
M ≡ 2^d (mod N)
代码实现：
M = pow(2, d, N) # Python内置的快速幂模运算
print(f"M = {M}")
计算结果：
M = 6602940601029543050476765433
关键：Python的pow函数
pow(base, exp, mod)使用快速幂算法- 时间复杂度：O(log exp)
- 即使d非常大，也能快速计算
4.7 验证解的正确性
在继续之前，我们必须验证M是否正确：
# 验证 M^e mod N 是否等于 2
verification = pow(M, e, N)
print(f"M^{e} mod N = {verification}")
if verification == 2:
print("✓ 验证成功！M是正确的解")
else:
print("✗ 验证失败")
输出：
M^83 mod N = 2
✓ 验证成功！M是正确的解
4.8 转换为16进制
将M转换为16进制表示，为后续编码做准备：
M_hex = hex(M)[2:].upper() # 去掉'0x'前缀，转大写
print(f"M (16进制) = {M_hex}")
print(f"长度: {len(M_hex)//2} 字节")
输出：
M (16进制) = 1555D30F38B0DBCAEC83C0F9
长度: 12 字节
这是一个12字节（96位）的数据。
五、自定义Base64编码
5.1 为什么需要编码？
虽然我们已经得到了数学上的解M，但：
- M是一个很大的数字，不便记忆和输入
- 题目要求序列号只能包含字母和数字
- 需要一种编码方案将二进制数据转为可打印字符
Base64 是一种常见的二进制到文本的编码方案。
5.2 Base64编码原理
基本概念：
- Base64使用64个ASCII字符来表示二进制数据
- 标准字符表：
ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/
编码过程：
1. 将数据按每3个字节（24位）分组
2. 每组24位分成4个6位的片段
3. 每个6位片段（值0-63）对应Base64表中的一个字符
4. 如果最后不足3字节，用'='填充
图解示例：
原始数据（3字节）: 0x15 0x55 0xD3
二进制: 00010101 01010101 11010011
分成4组（每组6位）:
000101 | 010101 | 010111 | 010011
5 | 21 | 23 | 19
查表（标准Base64）:
5→F, 21→V, 23→X, 19→T
编码结果: FVXT
5.3 自定义Base64字符表
题目使用了一个自定义的Base64字符表：
standard_table = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"
custom_table = "ABCyVPGHTJKLMNOFQRSIUEWDYZgbc8sfah1jklmnopqret5v0xX9wi234u67dz+/"
对比分析：
| 位置 | 标准 | 自定义 | 备注 | | — | — | — | — | | 0-2 | ABC | ABC | 相同 | | 3 | D | y | 替换 | | 4 | E | V | 替换 | | 5 | F | P | 替换 | | … | … | … | … |
为什么使用自定义表？
- 增加趣味性：让编码结果看起来”有意义”
- 隐藏特征：不容易被直接识别为Base64
- 嵌入信息：可以让结果包含特定字符串（如”readyu”）
5.4 实现自定义Base64编码
def custom_base64_encode(data_hex):
"""
自定义Base64编码
输入：16进制字符串
输出：自定义Base64编码字符串
"""
standard_table = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"
custom_table = "ABCyVPGHTJKLMNOFQRSIUEWDYZgbc8sfah1jklmnopqret5v0xX9wi234u67dz+/"
# 1. 将16进制字符串转为字节数组
data_bytes = bytes.fromhex(data_hex)
# 2. 标准Base64编码
result = []
for i in range(0, len(data_bytes), 3):
chunk = data_bytes[i:i+3] # 取3个字节
# 将3个字节转为一个24位整数
n = 0
for b in chunk:
n = (n << 8) | b
# 根据字节数生成Base64字符
if len(chunk) == 3:
# 3字节 → 4个Base64字符
indices = [
(n >> 18) & 0x3F, # 最高6位
(n >> 12) & 0x3F, # 次高6位
(n >> 6) & 0x3F, # 次低6位
n & 0x3F # 最低6位
]
for idx in indices:
result.append(standard_table[idx])
standard_encoded = ''.join(result)
# 3. 转换为自定义Base64
custom_encoded = ''
for c in standard_encoded:
idx = standard_table.index(c)
custom_encoded += custom_table[idx]
return custom_encoded
# 编码M
M_hex = "1555D30F38B0DBCAEC83C0F9"
sn = custom_base64_encode(M_hex)
print(f"编码结果: {sn}")
详细执行过程：
M_hex = 1555D30F38B0DBCAEC83C0F9 (12字节)
第1组（3字节）: 15 55 D3
二进制: 00010101 01010101 11010011
分组: 000101 010101 010111 010011
索引: 5, 21, 23, 19
标准: F, V, X, T
自定义: P, E, D, I
第2组（3字节）: 0F 38 B0
二进制: 00001111 00111000 10110000
分组: 000011 110011 100010 110000
索引: 3, 51, 34, 48
标准: D, z, i, w
自定义: y, 9, 1, 0
第3组（3字节）: DB CA EC
二进制: 11011011 11001010 11101100
分组: 110110 111100 101011 101100
索引: 54, 60, 43, 44
标准: 2, 8, r, s
自定义: 2, d, r, e
第4组（3字节）: 83 C0 F9
二进制: 10000011 11000000 11111001
分组: 100000 111100 000011 111001
索引: 32, 60, 3, 57
标准: g, 8, D, 5
自定义: g, d, y, u
拼接: P+E+D+I + y+9+1+0 + 2+d+r+e + g+d+y+u
= PEDIy9102dreadyu
输出结果：
编码结果: PEDIy9102dreadyu
注意到结果中包含了”readyu”，这正是文件名中的ID！
5.5 生成最终序列号
题目规则只允许使用字母和数字，不能使用特殊字符（如’-‘）。
分隔符的选择：
- 原本想用：
PEDIy-9102d-readyu - 实际使用：
PEDIyV9102dVreadyu（用’V’作为分隔符）
sn_clean = sn.rstrip('=') # 移除可能的填充字符
print(f"Base64编码: {sn_clean}")
# 在特定位置插入V分隔符
# PEDIy9102dreadyu → PEDIyV9102dVreadyu
# 分段：PEDIy + V + 9102d + V + readyu (5-5-6)
final_code = sn_clean[:5] + 'V' + sn_clean[5:10] + 'V' + sn_clean[10:]
print(f"最终序列号: {final_code}")
输出：
Base64编码: PEDIy9102dreadyu
最终序列号: PEDIyV9102dVreadyu
六、验证机制分析
6.1 程序验证流程
当用户输入序列号后，crackme程序执行以下验证：
┌─────────────────────────────────────────┐
│ 1. 输入CODE：PEDIyV9102dVreadyu │
└─────────────┬───────────────────────────┘
│
▼
┌─────────────────────────────────────────┐
│ 2. 格式检查：只包含字母和数字？ │
│ 不通过 → 错误提示 │
└─────────────┬───────────────────────────┘
│ ✓
▼
┌─────────────────────────────────────────┐
│ 3. 去除分隔符V：PEDIy9102dreadyu │
└─────────────┬───────────────────────────┘
│
▼
┌─────────────────────────────────────────┐
│ 4. 自定义Base64解码 │
│ → 得到M = 6602940601029543050476... │
└─────────────┬───────────────────────────┘
│
▼
┌─────────────────────────────────────────┐
│ 5. 构造N（生成3到73的素数乘积） │
│ N = 20364840299624512075310661735 │
└─────────────┬───────────────────────────┘
│
▼
┌─────────────────────────────────────────┐
│ 6. 范围检查：2 ≤ M < N ？ │
│ 不通过 → 错误提示 │
└─────────────┬───────────────────────────┘
│ ✓
▼
┌─────────────────────────────────────────┐
│ 7. 计算 X = M^83 mod N │
└─────────────┬───────────────────────────┘
│
▼
┌─────────────────────────────────────────┐
│ 8. 位长检查：X的比特长度 < 32 ？ │
│ 否 → "sn doesn't work!" │
└─────────────┬───────────────────────────┘
│ ✓
▼
┌─────────────────────────────────────────┐
│ 9. 值检查：X == 2 ？ │
│ 是 → "yes, correct sn!" ✓ │
│ 否 → "no, wrong sn!!!!" │
└─────────────────────────────────────────┘
6.2 为什么检查位长？
程序限制X的位长必须小于32位，这是一个安全检查：
if X.bit_length() >= 32:
print("sn doesn't work!")
return False
原因分析：
- 防止大数溢出：如果X很大，转换为32位整数会溢出
- 快速过滤：大部分错误输入会产生很大的X值，可以快速排除
- 唯一性保证：正确的M应该使得X = 2，而2只需2个比特
6.3 实现验证程序
我们可以用Python实现完整的验证逻辑：
def verify_code(code):
"""验证CODE的正确性"""
print(f"输入的CODE: {code}")
# 步骤1: 移除分隔符V
sn = code.replace('V', '')
print(f"移除分隔符后: {sn}")
# 步骤2: 自定义Base64解码
standard_table = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"
custom_table = "ABCyVPGHTJKLMNOFQRSIUEWDYZgbc8sfah1jklmnopqret5v0xX9wi234u67dz+/"
# 转换为标准Base64
standard_sn = ''
for c in sn:
idx = custom_table.index(c)
standard_sn += standard_table[idx]
# 添加填充
while len(standard_sn) % 4 != 0:
standard_sn += '='
# 解码
from base64 import b64decode
decoded_bytes = b64decode(standard_sn)
M = int(decoded_bytes.hex(), 16)
print(f"解码得到M: {M}")
# 步骤3: 构造N
N = 1
for i in range(3, 79):
if is_prime(i):
N *= i
print(f"N = {N}")
# 步骤4: 范围检查
if M < 2 or M >= N:
print("✗ M不在有效范围")
return False
print("✓ M在有效范围内")
# 步骤5: 计算X = M^83 mod N
e = 83
X = pow(M, e, N)
print(f"X = M^{e} mod N = {X}")
# 步骤6: 位长检查
if X.bit_length() >= 32:
print("✗ X的位长过大")
print("提示: sn doesn't work!")
return False
# 步骤7: 值检查
if X == 2:
print("✓ X == 2")
print("提示: yes, correct sn!")
return True
else:
print(f"✗ X = {X} ≠ 2")
print("提示: no, wrong sn!!!!")
return False
# 测试
result = verify_code("PEDIyV9102dVreadyu")
运行结果：
输入的CODE: PEDIyV9102dVreadyu
移除分隔符后: PEDIy9102dreadyu
解码得到M: 6602940601029543050476765433
N = 20364840299624512075310661735
✓ M在有效范围内
X = M^83 mod N = 2
✓ X == 2
提示: yes, correct sn!
七、完整解题代码
7.1 求解脚本（solve.py）
#!/usr/bin/env python3
"""
青梅竹马 CTF Crypto Challenge - 完整解题脚本
"""
def is_prime(n):
"""判断是否为素数"""
if n < 2:
return False
if n == 2:
return True
if n % 2 == 0:
return False
for i in range(3, int(n**0.5) + 1, 2):
if n % i == 0:
return False
return True
def extended_gcd(a, b):
"""扩展欧几里得算法"""
if a == 0:
return b, 0, 1
gcd, x1, y1 = extended_gcd(b % a, a)
x = y1 - (b // a) * x1
y = x1
return gcd, x, y
def mod_inverse(e, phi):
"""求模逆元"""
gcd, x, y = extended_gcd(e, phi)
if gcd != 1:
raise Exception("模逆元不存在")
return (x % phi + phi) % phi
def custom_base64_encode(data_hex):
"""自定义Base64编码"""
standard_table = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"
custom_table = "ABCyVPGHTJKLMNOFQRSIUEWDYZgbc8sfah1jklmnopqret5v0xX9wi234u67dz+/"
data_bytes = bytes.fromhex(data_hex)
result = []
for i in range(0, len(data_bytes), 3):
chunk = data_bytes[i:i+3]
n = 0
for b in chunk:
n = (n << 8) | b
if len(chunk) == 3:
indices = [
(n >> 18) & 0x3F,
(n >> 12) & 0x3F,
(n >> 6) & 0x3F,
n & 0x3F
]
for idx in indices:
result.append(standard_table[idx])
standard_encoded = ''.join(result)
custom_encoded = ''
for c in standard_encoded:
idx = standard_table.index(c)
custom_encoded += custom_table[idx]
return custom_encoded
def main():
print("="*70)
print("青梅竹马 CTF Crypto Challenge - 完整解题")
print("="*70)
print()
# 步骤1: 生成素数
primes = [i for i in range(2, 100) if is_prime(i)]
print(f"[1] 100以内素数共 {len(primes)} 个")
# 步骤2: 构造N
N = 1
for p in primes:
if p == 2:
continue
if p >= 79:
break
N *= p
print(f"[2] N = {N}")
# 步骤3: 计算φ(N)
phi_N = 1
for p in primes:
if p == 2:
continue
if p >= 79:
break
phi_N *= (p - 1)
print(f"[3] φ(N) = {phi_N}")
# 步骤4: 求私钥d
e = 83
d = mod_inverse(e, phi_N)
print(f"[4] e = {e}, d = {d}")
# 步骤5: 计算M
M = pow(2, d, N)
print(f"[5] M = {M}")
# 步骤6: 验证
verification = pow(M, e, N)
print(f"[6] 验证: M^{e} mod N = {verification} {'✓' if verification == 2 else '✗'}")
# 步骤7: 转16进制
M_hex = hex(M)[2:].upper()
print(f"[7] M (hex) = {M_hex}")
# 步骤8: Base64编码
sn = custom_base64_encode(M_hex)
print(f"[8] Base64编码 = {sn}")
# 步骤9: 添加分隔符
final_code = sn[:5] + 'V' + sn[5:10] + 'V' + sn[10:]
print(f"[9] 最终序列号 = {final_code}")
print()
print("="*70)
print(f"✓✓✓ 答案: {final_code} ✓✓✓")
print("="*70)
return final_code
if __name__ == "__main__":
main()
7.2 运行结果
======================================================================
青梅竹马 CTF Crypto Challenge - 完整解题
======================================================================
[1] 100以内素数共 25 个
[2] N = 20364840299624512075310661735
[3] φ(N) = 5133855159158901099724800000
[4] e = 83, d = 1855610298491169072189686747
[5] M = 6602940601029543050476765433
[6] 验证: M^83 mod N = 2 ✓
[7] M (hex) = 1555D30F38B0DBCAEC83C0F9
[8] Base64编码 = PEDIy9102dreadyu
[9] 最终序列号 = PEDIyV9102dVreadyu
======================================================================
✓✓✓ 答案: PEDIyV9102dVreadyu ✓✓✓
======================================================================
八、技术要点深入解析
8.1 RSA安全性分析
为什么RSA通常是安全的？
- 大整数分解困难：
- 在实际应用中，N是两个大素数的乘积（通常2048位或更长）
- 已知N，分解出p和q在计算上是不可行的
- 目前没有已知的多项式时间算法能分解大整数
- 计算φ(N)困难：
- 不知道p和q，就无法直接计算φ(N)
- φ(N) = (p-1)(q-1) 需要知道素因子
- 求私钥d困难：
- 不知道φ(N)，就无法求出d = e⁻¹ mod φ(N)
这道题为什么不安全？
- N可分解：
- N是多个小素数的乘积
- 可以轻松枚举出所有素因子
- φ(N)可计算：
- 知道所有素因子，直接计算φ(N)
- 私钥可求：
- 有了φ(N)，用扩展欧几里得算法求出d
启示：RSA的安全性完全依赖于N的不可分解性！
8.2 为什么使用快速幂模算法？
在计算 2^d mod N 时，d是一个非常大的数：
d = 1855610298491169072189686747
朴素算法的问题：
# 朴素算法（错误示范）
result = 1
for i in range(d): # 需要循环10^27次！
result = (result * 2) % N
这需要约 10^27 次运算，即使每秒进行10^9次运算，也需要10^18秒（约300亿年）！
快速幂算法：
基本思想：将指数写成二进制，利用：
a^13 = a^(1101₂) = a^8 × a^4 × a^1
def fast_pow_mod(base, exp, mod):
"""快速幂模算法"""
result = 1
base = base % mod
while exp > 0:
if exp % 2 == 1: # 如果exp是奇数
result = (result * base) % mod
exp = exp >> 1 # exp除以2
base = (base * base) % mod
return result
时间复杂度：
- 朴素算法：O(exp)
- 快速幂：O(log exp)
对于 d = 1855610298491169072189686747：
- log₂(d) ≈ 90
- 只需约90次运算！
Python内置实现：
# Python的pow函数内部使用快速幂模算法
result = pow(2, d, N) # 非常快速
8.3 Base64编码的数学原理
为什么是3字节→4字符？
输入：3字节 = 24位
输出：4字符，每字符表示6位
24位 ÷ 6位/字符 = 4字符
编码效率：
原始数据：n字节
编码后：⌈4n/3⌉字符
膨胀率：约33%
为什么选择6位分组？
- 2^6 = 64，正好64个字符
- 6位是24（3×8）的因子，便于整除
- 生成的字符都是可打印的ASCII字符
8.4 欧拉定理的证明思路
定理：如果 gcd(a, n) = 1，则 a^φ(n) ≡ 1 (mod n)
证明思路（针对n为素数乘积的情况）：
设 n = p₁ × p₂ × … × pₖ（素数）
- 费马小定理：对于素数p，a^(p-1) ≡ 1 (mod p)
- 推广：
- a^φ(p₁) ≡ 1 (mod p₁)
- a^φ(p₂) ≡ 1 (mod p₂)
- …
- 中国剩余定理：如果对所有素数pi都有 a^φ(n) ≡ 1 (mod pi)， 则 a^φ(n) ≡ 1 (mod n)
这个定理是RSA正确性的数学保证。
九、解题技巧总结
9.1 CTF密码学题通用思路
1. 识别算法
├─ RSA特征：大数、模运算、公钥/私钥
├─ AES特征：块加密、轮函数
└─ 其他经典算法特征
2. 寻找弱点
├─ 参数选择不当（如小素数）
├─ 实现错误
└─ 侧信道信息泄露
3. 利用数学工具
├─ 数论：gcd、模逆元、欧拉定理
├─ 代数：群、环、域
└─ 概率统计
4. 编写脚本验证
├─ Python：sympy、pycrypto
├─ SageMath：强大的数学工具
└─ 在线工具：factordb、RSA calculator
9.2 逆向分析技巧
1. 静态分析
├─ strings：查找字符串
├─ objdump/IDA：反汇编
└─ 识别加密常数（如S盒）
2. 动态分析
├─ 调试器：gdb、x64dbg
├─ 追踪：ltrace、strace
└─ Hook：Frida、DBI
3. 符号执行
├─ angr
└─ Z3约束求解
4. 模式识别
├─ 识别库函数
├─ 识别算法特征
└─ 对比已知实现
9.3 本题关键点回顾
- 文化线索：”青梅竹马”→”两小无猜”→2
- 数学建模：识别RSA变体，建立幂模方程
- 参数确定：分析为何排除2、为何在79截止
- 算法实现：正确实现扩展欧几里得、快速幂模
- 编码转换：理解自定义Base64的设计意图
十、拓展思考
10.1 如何加固这个系统？
如果要让这个验证系统更安全：
- 使用大素数：
# 使用2048位的素数
p = generate_large_prime(1024)
q = generate_large_prime(1024)
N = p * q
- 隐藏φ(N)：
- 不公开N的因子
- 使用真正的大素数，使分解不可行
- 选择合适的e：
- 通常选择 e = 65537（2^16 + 1）
- 既保证安全性，又便于快速加密
- 添加填充：
- 使用OAEP等填充方案
- 防止数学攻击
10.2 实际应用中的RSA
密钥长度建议：
- 2048位：目前主流，安全期约到2030年
- 3072位：长期安全
- 4096位：极高安全性，但计算开销大
RSA的应用场景：
- 数字签名：证明消息的真实性和完整性
- 密钥交换：在TLS/SSL中协商对称密钥
- 身份认证：SSH公钥认证
RSA的局限性：
- 加密速度慢：通常只用于加密对称密钥
- 密钥长度大：相比椭圆曲线加密（ECC）
- 量子威胁：量子计算机可能破解RSA
10.3 从这道题学到什么？
密码学原理：
- RSA的数学基础（欧拉函数、模逆元）
- 加密与解密的对称性
- 参数选择对安全性的影响
编程技巧：
- 大整数运算
- 快速幂模算法
- Base64编码实现
逆向思维：
- 从题目名称挖掘线索
- 分析魔术数字的含义
- 理解算法意图
实践能力：
- 完整实现一个密码系统
- 验证和调试数学算法
- 编写清晰的技术文档
十一、总结
这道”青梅竹马”题目是一道设计精巧的密码学题目，它完美地融合了：
技术层面
- RSA密码学原理：从密钥生成到加解密的完整流程
- 数论知识：素数、欧拉函数、模逆元、欧拉定理
- 编码技术：自定义Base64实现
- 算法优化：快速幂模算法
文化层面
- 成语隐喻：”青梅竹马”→”两小无猜”
- 数字寓意：”两”指数字2，”小”指小素数
- 趣味性：在技术中融入文化元素
教育意义
- 理论与实践结合：从数学推导到代码实现
- 安全意识培养：理解什么使密码系统安全/不安全
- 解决问题的方法论：分析、建模、实现、验证
最终答案
序列号（Serial Number）: PEDIyV9102dVreadyu
验证提示: yes, correct sn!
完整验证：
- M = 6602940601029543050476765433
- M^83 mod N = 2 ✓
- 所有数学验证通过 ✓
参考资料：
- [1] RSA算法原理与应用
- [2] 数论基础：欧拉函数与欧拉定理
- [3] Base64编码标准（RFC 4648）
- [4] 密码学：原理与实践
- [5] CTF密码学题解题思路
作者寄语：
密码学是一门美丽的学科，它将抽象的数学理论应用于实际的信息安全。希望这篇文章能帮助大家：
- 理解RSA的工作原理
- 掌握基本的密码学分析方法
- 培养对安全问题的思考
- 享受解题的乐趣
记住：密码学的安全性，永远建立在数学的坚实基础之上。
本文为技术研究分享，仅用于学习交流。
查看原文：《青梅竹马：一道融合密码学与文化的CTF逆向题深度解析》
版权声明
本站仅做备份收录，仅供研究与教学参考之用。
读者将信息用于其他用途的，全部法律及连带责任由读者自行承担，本站不承担任何责任。
评论