文章总结： 本文通过CTF实战解析RSA小模数分解攻击。针对256位密钥过短漏洞，分解模数获取私钥并解密Flag。文章详细阐述了RSA原理与攻击流程，强调生产环境须使用2048位以上密钥及安全填充方案，内容兼具理论深度与实战指导价值。 综合评分： 91 文章分类： CTF,漏洞分析
RSA密码学攻击实战：小模数分解攻击完全解析
原创
破镜安全 破镜安全
破镜安全
2026年1月26日 08:00 四川
RSA密码学攻击实战：小模数分解攻击完全解析
前言
RSA是现代密码学中最重要的公钥加密算法之一，广泛应用于网络安全、数字签名等领域。然而，如果RSA的参数选择不当，就会产生严重的安全隐患。本文将通过一道真实的CTF密码学题目，深入剖析RSA的工作原理、安全性基础，以及当密钥长度不足时如何实施攻击。
一、题目分析
1.1 题目文件
拿到题目后，我们发现有两个文件：
pubkey.pem - RSA公钥文件
flag.enc - 加密后的flag文件
这是一个典型的RSA加密挑战：攻击者拥有公钥和密文，需要想办法恢复出明文。
让我们首先查看这两个文件的具体内容：
# 查看公钥文件
cat pubkey.pem
输出：
-----BEGIN PUBLIC KEY-----
MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhAMJjauXD2OQ/+5erCQKPGqxsC/bNPXDr
yigb/+l/vjDdAgMBAAE=
-----END PUBLIC KEY-----
这是一个标准的PEM格式RSA公钥文件。PEM（Privacy-Enhanced Mail）是一种用Base64编码的密钥存储格式，被广泛应用于各种密码学工具中。
查看加密文件：
# 查看加密文件的十六进制内容
xxd flag.enc
输出：
00000000: 6d3e b7df 23ee e1d3 8710 beba 78a0 878e m>..#.......x...
00000010: 0e9c 65bd 3d08 496d da64 9241 9911 0c79 ..e.=.Im.d.A...y
这是32字节的二进制数据，是RSA加密后的密文。
1.2 初步思考
面对这道题，我们需要思考几个关键问题：
- RSA加密的原理是什么？ 理解算法才能找到攻击点
- 如何从公钥中提取参数？ 需要获取n和e的值
- RSA的安全性依赖什么？ 找到可能的薄弱环节
- 如何在没有私钥的情况下解密？ 考虑攻击思路
带着这些问题，让我们开始分析。
二、RSA加密算法原理深度解析
2.1 RSA算法的数学基础
RSA算法基于数论中的几个重要定理，主要包括：
1. 欧拉定理
对于互质的整数a和n，有：
a^φ(n) ≡ 1 (mod n)
其中φ(n)是欧拉函数，表示小于等于n且与n互质的正整数个数。
2. 欧拉函数的性质
当n是两个质数p和q的乘积时：
φ(n) = φ(p × q) = (p-1) × (q-1)
这是因为：
- 对于质数p，所有小于p的正整数都与p互质，所以φ(p) = p-1
- 欧拉函数具有积性：如果gcd(a,b)=1，则φ(a×b) = φ(a)×φ(b)
3. 模逆元
对于整数e和φ(n)，如果gcd(e, φ(n)) = 1，则存在整数d使得：
e × d ≡ 1 (mod φ(n))
这个d称为e在模φ(n)下的乘法逆元。
2.2 RSA密钥生成过程
理解RSA的密钥生成过程对于后续攻击至关重要：
步骤1：选择两个大质数
选择两个足够大的质数 p 和 q
要求：p ≠ q，且都是大质数
步骤2：计算模数
n = p × q
这个n就是RSA加密的模数，它的大小决定了密钥的长度。
步骤3：计算欧拉函数值
φ(n) = (p-1) × (q-1)
步骤4：选择公钥指数
选择整数 e，满足：1 < e < φ(n) 且 gcd(e, φ(n)) = 1
通常选择 e = 65537 = 2^16 + 1
为什么选择65537？
- 它是质数，容易保证与φ(n)互质
- 二进制表示只有2个1（10000000000000001），加密运算快
- 足够大，避免某些特殊攻击
步骤5：计算私钥指数
计算 d，使得 e × d ≡ 1 (mod φ(n))
使用扩展欧几里得算法求解
最终得到：
- 公钥：(n, e) – 可以公开
- 私钥：(n, d) – 必须保密
2.3 RSA加密和解密过程
加密过程：
发送方使用接收方的公钥(n, e)对明文M进行加密：
C = M^e mod n
这里使用了模幂运算，将明文转换为密文。
解密过程：
接收方使用自己的私钥(n, d)对密文C进行解密：
M = C^d mod n
为什么这样能正确解密？
这是RSA算法最精妙的地方。让我们来证明：
C^d = (M^e)^d = M^(e×d) (mod n)
因为 e × d ≡ 1 (mod φ(n))，所以可以写成：
e × d = k × φ(n) + 1 (k是某个整数)
代入得：
M^(e×d) = M^(k×φ(n)+1) = M^(k×φ(n)) × M = (M^φ(n))^k × M (mod n)
根据欧拉定理，如果gcd(M, n) = 1，则M^φ(n) ≡ 1 (mod n)，因此：
(M^φ(n))^k × M ≡ 1^k × M = M (mod n)
完美恢复明文！这就是RSA能够正确加解密的数学原理。
2.4 RSA安全性的核心
RSA的安全性完全依赖于一个数学难题：大整数因数分解问题。
如果攻击者知道公钥(n, e)，想要计算出私钥d，需要：
- 将n分解为p和q
- 计算φ(n) = (p-1)(q-1)
- 计算d = e^(-1) mod φ(n)
关键在于第一步：分解n。
目前，对于足够大的整数（如2048位以上），不存在高效的分解算法。即使用最强大的计算机和最优秀的算法（如通用数域筛法GNFS），分解一个2048位的整数也需要数百年时间。
这就是RSA安全性的基础：计算复杂度。
但如果n不够大会怎样？这就是本题的突破口。
三、解题思路：寻找安全漏洞
3.1 第一步：提取公钥参数
要分析RSA的安全性，首先需要从公钥文件中提取出n和e的具体值。
我们可以使用两种方法：
方法一：使用OpenSSL命令行工具
OpenSSL是一个功能强大的密码学工具包，可以解析和操作各种密钥格式。
openssl rsa -pubin -text -modulus -in pubkey.pem
参数说明：
-pubin：表示输入是公钥（而非私钥）-text：以文本形式显示密钥内容-modulus：显示模数的十六进制值-in pubkey.pem：指定输入文件
执行结果：
Public-Key: (256 bit)
Modulus:
00:c2:63:6a:e5:c3:d8:e4:3f:fb:97:ab:09:02:8f:
1a:ac:6c:0b:f6:cd:3d:70:eb:ca:28:1b:ff:e9:7f:
be:30:dd
Exponent: 65537 (0x10001)
Modulus=C2636AE5C3D8E43FFB97AB09028F1AAC6C0BF6CD3D70EBCA281BFFE97FBE30DD
从输出中我们提取到关键信息：
- 密钥长度：256位 ← 这是一个重要发现！
- e = 65537 （这是标准值）
- n = 0xC2636AE5C3D8E43FFB97AB09028F1AAC6C0BF6CD3D70EBCA281BFFE97FBE30DD （十六进制）
方法二：使用Python的Crypto库
编写Python脚本来解析：
from Crypto.PublicKey import RSA
# 读取公钥文件
with open('pubkey.pem', 'r') as f:
key = f.read()
pubkey = RSA.import_key(key)
# 显示参数
print('n (十进制):', pubkey.n)
print('e:', pubkey.e)
print('n (十六进制):', hex(pubkey.n))
print('密钥位数:', pubkey.n.bit_length(), 'bits')
运行结果：
n (十进制): 87924348264132406875276140514499937145050893665602592992418171647042491658461
e: 65537
n (十六进制): 0xc2636ae5c3d8e43ffb97ab09028f1aac6c0bf6cd3d70ebca281bffe97fbe30dd
密钥位数: 256 bits
两种方法得到相同的结果，验证了数据的正确性。
3.2 第二步：安全性评估
现在我们得到了关键参数：
- n = 87924348264132406875276140514499937145050893665602592992418171647042491658461
- e = 65537
- 密钥长度 = 256 bits
让我们评估这个RSA密钥的安全性。
业界推荐的RSA密钥长度标准：
| 密钥长度 | 安全等级 | 说明 | | — | — | — | | < 1024位 | 不安全 | 已被破解，禁止使用 | | 1024位 | 已过时 | 2015年后不再推荐 | | 2048位 | 基本安全 | 当前最低推荐标准 | | 3072位 | 中等安全 | 适用于敏感数据 | | 4096位 | 高安全 | 适用于高机密数据 |
而本题的密钥长度是256位！
这意味着什么？
256位整数分解的难度：
对于256位的合数，现代计算机使用通用的分解算法（如椭圆曲线方法ECM或二次筛法QS）可以在几秒到几分钟内完成分解。这完全在可接受的计算范围内。
结论：这个RSA密钥存在严重的安全漏洞，可以通过暴力分解n来破解。
3.3 第三步：攻击策略
明确了攻击思路后，我们的攻击链条如下：
1. 分解n得到p和q
↓
2. 计算φ(n) = (p-1) × (q-1)
↓
3. 计算d = e^(-1) mod φ(n)
↓
4. 构造完整的RSA私钥
↓
5. 使用私钥解密flag.enc
↓
6. 获得flag
接下来，让我们逐步实施这个攻击。
四、攻击实施过程
4.1 第一步：分解模数n
对于256位的整数分解，我们有多种选择：
方法1：使用在线分解数据库
factordb.com 是一个公开的质因数分解数据库，收录了大量已分解的整数。这些数据来自：
- 学术研究项目
- CTF比赛中使用的数值
- 密码学测试数据
访问 http://www.factordb.com/，在搜索框中输入n的值：
87924348264132406875276140514499937145050893665602592992418171647042491658461
查询结果显示n已经被成功分解：
p = 275127860351348928173285174381581152299
q = 319576316814478949870590164193048041239
方法2：使用本地分解工具
如果factordb上没有记录，也可以使用本地工具如：
- yafu（适合中等大小整数）
- msieve（通用数域筛法实现）
- sage（数学软件，包含多种分解算法）
对于256位整数，这些工具都能在合理时间内完成分解。
验证分解结果
无论使用哪种方法，都应该验证结果的正确性：
n = 87924348264132406875276140514499937145050893665602592992418171647042491658461
p = 275127860351348928173285174381581152299
q = 319576316814478949870590164193048041239
# 验证分解
print('验证分解结果:')
print('p * q =', p * q)
print('n =', n)
print('分解正确:', p * q == n)
# 检查p和q的位数
print('\np和q的位数:')
print('p:', p.bit_length(), 'bits')
print('q:', q.bit_length(), 'bits')
运行结果：
验证分解结果:
p * q = 87924348264132406875276140514499937145050893665602592992418171647042491658461
n = 87924348264132406875276140514499937145050893665602592992418171647042491658461
分解正确: True
p和q的位数:
p: 128 bits
q: 128 bits
可以看到，256位的n是由两个128位的质数相乘得到的。分解验证正确！
4.2 第二步：计算欧拉函数φ(n)
得到p和q后，根据欧拉函数的性质计算φ(n)。
公式回顾：
φ(n) = (p-1) × (q-1)
为什么是这个公式？
这涉及欧拉函数的定义和性质：
- 定义：φ(n)表示小于等于n且与n互质的正整数个数
- 对于质数p：所有小于p的正整数（1, 2, 3, …, p-1）都与p互质 因此：φ(p) = p – 1
- 积性性质：当gcd(a, b) = 1时，φ(a × b) = φ(a) × φ(b) 因为p和q是不同的质数，所以gcd(p, q) = 1 因此：φ(p × q) = φ(p) × φ(q) = (p-1) × (q-1)
计算代码：
p = 275127860351348928173285174381581152299
q = 319576316814478949870590164193048041239
# 计算欧拉函数
phi_n = (p - 1) * (q - 1)
print('欧拉函数计算:')
print('φ(n) = (p-1) × (q-1)')
print('φ(n) =', phi_n)
运行结果：
欧拉函数计算:
φ(n) = (p-1) × (q-1)
φ(n) = 87924348264132406875276140514499937144456189488436765114374296308467862464924
4.3 第三步：计算私钥指数d
私钥指数d需要满足以下关系：
e × d ≡ 1 (mod φ(n))
换句话说，d是e在模φ(n)意义下的乘法逆元。
为什么要计算模逆？
回顾RSA的解密原理：
C^d ≡ M (mod n)
这个等式成立的前提是：
e × d ≡ 1 (mod φ(n))
这样才能通过欧拉定理推导出M^(e×d) ≡ M (mod n)。
如何计算模逆？
计算模逆需要使用扩展欧几里得算法（Extended Euclidean Algorithm）。
扩展欧几里得算法不仅能计算gcd(a, b)，还能找到整数x和y使得：
a × x + b × y = gcd(a, b)
当gcd(e, φ(n)) = 1时，存在x和y使得：
e × x + φ(n) × y = 1
两边对φ(n)取模：
e × x ≡ 1 (mod φ(n))
这个x就是我们要找的d。
使用Python的gmpy2库计算：
import gmpy2 as gp
e = 65537
phi_n = 87924348264132406875276140514499937144456189488436765114374296308467862464924
# 计算模逆
d = gp.invert(e, phi_n)
print('私钥指数计算:')
print('d = e^(-1) mod φ(n)')
print('d =', d)
# 验证计算是否正确
verification = (e * d) % phi_n
print('\n验证:')
print('(e × d) mod φ(n) =', verification)
print('计算正确:', verification == 1)
运行结果：
私钥指数计算:
d = e^(-1) mod φ(n)
d = 10866948760844599168252082612378495977388271279679231539839049698621994994673
验证:
(e × d) mod φ(n) = 1
计算正确: True
验证通过！我们成功计算出了私钥指数d。
4.4 第四步：构造完整的RSA私钥
现在我们有了RSA的所有关键参数：
- n = 87924348264132406875276140514499937145050893665602592992418171647042491658461
- e = 65537
- d = 10866948760844599168252082612378495977388271279679231539839049698621994994673
可以使用这些参数构造一个完整的RSA私钥对象。
使用Python的Crypto库：
from Crypto.PublicKey import RSA
n = 87924348264132406875276140514499937145050893665602592992418171647042491658461
e = 65537
d = 10866948760844599168252082612378495977388271279679231539839049698621994994673
# 构造RSA密钥对象
# RSA.construct()参数: (n, e, d, p, q)
# 最后一个参数False表示不进行一致性检查（加快速度）
prikey = RSA.construct((n, e, d), False)
print('RSA私钥构造成功')
print('密钥信息:')
print(' n:', prikey.n)
print(' e:', prikey.e)
print(' d:', prikey.d)
# 导出为PEM格式
key_pem = prikey.export_key()
print('\n导出的私钥 (PEM格式):')
print(key_pem.decode('utf-8'))
# 保存到文件
with open('prikey.pem', 'wb') as f:
f.write(key_pem)
print('私钥已保存到 prikey.pem')
运行结果：
RSA私钥构造成功
密钥信息:
n: 87924348264132406875276140514499937145050893665602592992418171647042491658461
e: 65537
d: 10866948760844599168252082612378495977388271279679231539839049698621994994673
导出的私钥 (PEM格式):
-----BEGIN RSA PRIVATE KEY-----
MIGqAgEAAiEAwmNq5cPY5D/7l6sJAo8arGwL9s09cOvKKBv/6X++MN0CAwEAAQIg
GAZ5m9RM5kkSK3i0MGDHhvi3f7FZPghC2gY7oNhyi/ECEQDO+7LPfhipjr7cNuPn
w7ArAhEA8Gwo6RyJIrnCNuI1YMCXFwIRAJulRkclqWIHx5pNZIAp9VUCEGjeJLIZ
ek+lSut5m+LJ3p0CEDRBEd7C622/wt1+58xOIfE=
-----END RSA PRIVATE KEY-----
私钥已保存到 prikey.pem
成功！我们从公钥和密文出发，通过分解攻击，完整恢复了RSA私钥。
4.5 第五步：解密flag
有了私钥文件后，就可以使用OpenSSL工具解密flag.enc了。
使用OpenSSL解密：
openssl pkeyutl -decrypt -in flag.enc -inkey prikey.pem
命令参数说明：
pkeyutl：公钥算法实用工具（新版本推荐，替代旧的rsautl）-decrypt：执行解密操作-in flag.enc：输入的密文文件-inkey prikey.pem：使用的私钥文件
执行结果：
PCTF{256b_i5_m3dium}
成功获得flag！
也可以使用Python解密：
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_v1_5
# 读取私钥
with open('prikey.pem', 'rb') as f:
prikey = RSA.import_key(f.read())
# 读取密文
with open('flag.enc', 'rb') as f:
ciphertext = f.read()
# 创建解密器
cipher = PKCS1_v1_5.new(prikey)
# 解密
plaintext = cipher.decrypt(ciphertext, None)
print('解密结果:', plaintext.decode('utf-8'))
输出：
解密结果: PCTF{256b_i5_m3dium}
两种方法都成功解密，验证了我们的攻击是正确的。
五、完整攻击脚本
为了方便理解和复用，这里提供一个完整的自动化攻击脚本：
#!/usr/bin/env python3
"""
RSA小模数分解攻击脚本
适用于密钥长度不足的RSA加密系统
"""
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_v1_5
import gmpy2 as gp
def parse_public_key(pubkey_file):
"""解析公钥文件，提取n和e"""
print('[*] 步骤1: 解析公钥文件')
with open(pubkey_file, 'r') as f:
pubkey = RSA.import_key(f.read())
n = pubkey.n
e = pubkey.e
bits = n.bit_length()
print(f' n = {n}')
print(f' e = {e}')
print(f' 密钥长度: {bits} bits')
if bits < 1024:
print(f' [!] 警告: 密钥长度仅{bits}位，存在安全隐患')
return n, e
def factorize_n(n):
"""分解模数n为两个质因子"""
print('\n[*] 步骤2: 分解模数n')
print(' 提示: 可使用 factordb.com 或本地工具分解')
# 这里使用题目中已知的分解结果
# 实际攻击中需要使用分解工具
p = 275127860351348928173285174381581152299
q = 319576316814478949870590164193048041239
# 验证分解
if p * q != n:
raise ValueError('分解结果错误')
print(f' p = {p} ({p.bit_length()} bits)')
print(f' q = {q} ({q.bit_length()} bits)')
print(' [+] 分解验证通过')
return p, q
def calculate_private_key(n, e, p, q):
"""计算RSA私钥参数"""
print('\n[*] 步骤3: 计算私钥参数')
# 计算欧拉函数
phi_n = (p - 1) * (q - 1)
print(f' φ(n) = (p-1) × (q-1) = {phi_n}')
# 计算私钥指数d
d = gp.invert(e, phi_n)
print(f' d = e^(-1) mod φ(n) = {d}')
# 验证
if (e * d) % phi_n != 1:
raise ValueError('私钥计算错误')
print(' [+] 私钥计算验证通过')
return d
def construct_private_key(n, e, d, output_file):
"""构造并保存RSA私钥"""
print('\n[*] 步骤4: 构造并保存私钥')
prikey = RSA.construct((n, e, d), False)
with open(output_file, 'wb') as f:
key_pem = prikey.export_key()
f.write(key_pem)
print(f' [+] 私钥已保存到 {output_file}')
return prikey
def decrypt_flag(prikey, encrypted_file):
"""使用私钥解密flag"""
print('\n[*] 步骤5: 解密flag')
# 读取密文
with open(encrypted_file, 'rb') as f:
ciphertext = f.read()
# 创建解密器并解密
cipher = PKCS1_v1_5.new(prikey)
plaintext = cipher.decrypt(ciphertext, None)
if plaintext:
flag = plaintext.decode('utf-8')
print(f' [+] 解密成功!')
print(f' Flag: {flag}')
return flag
else:
print(' [-] 解密失败')
return None
def main():
"""主函数"""
print('='*60)
print('RSA小模数分解攻击工具')
print('='*60)
# 配置文件路径
pubkey_file = 'pubkey.pem'
encrypted_file = 'flag.enc'
prikey_file = 'prikey.pem'
try:
# 执行攻击流程
n, e = parse_public_key(pubkey_file)
p, q = factorize_n(n)
d = calculate_private_key(n, e, p, q)
prikey = construct_private_key(n, e, d, prikey_file)
flag = decrypt_flag(prikey, encrypted_file)
print('\n' + '='*60)
print('攻击完成!')
print('='*60)
except Exception as e:
print(f'\n[!] 错误: {e}')
import traceback
traceback.print_exc()
if __name__ == '__main__':
main()
运行这个脚本：
python3 attack.py
输出：
============================================================
RSA小模数分解攻击工具
============================================================
[*] 步骤1: 解析公钥文件
n = 87924348264132406875276140514499937145050893665602592992418171647042491658461
e = 65537
密钥长度: 256 bits
[!] 警告: 密钥长度仅256位，存在安全隐患
[*] 步骤2: 分解模数n
提示: 可使用 factordb.com 或本地工具分解
p = 275127860351348928173285174381581152299 (128 bits)
q = 319576316814478949870590164193048041239 (128 bits)
[+] 分解验证通过
[*] 步骤3: 计算私钥参数
φ(n) = (p-1) × (q-1) = 87924348264132406875276140514499937144456189488436765114374296308467862464924
d = e^(-1) mod φ(n) = 10866948760844599168252082612378495977388271279679231539839049698621994994673
[+] 私钥计算验证通过
[*] 步骤4: 构造并保存私钥
[+] 私钥已保存到 prikey.pem
[*] 步骤5: 解密flag
[+] 解密成功!
Flag: PCTF{256b_i5_m3dium}
============================================================
攻击完成!
============================================================
六、技术深入解析
6.1 为什么256位RSA如此脆弱？
让我们从计算复杂度的角度分析：
1. 分解算法的时间复杂度
最先进的通用分解算法是通用数域筛法（GNFS），其时间复杂度为：
O(exp((ln n)^(1/3) × (ln ln n)^(2/3)))
这是一个次指数级别的复杂度，意味着随着n的增大，分解时间呈指数级增长。
2. 不同密钥长度的分解难度
| 密钥长度 | 十进制位数 | 估计分解时间 | 实际案例 | | — | — | — | — | | 256位 | 77位 | 几秒到几分钟 | 普通PC即可 | | 512位 | 154位 | 几小时到几天 | 1999年已破解 | | 768位 | 232位 | 几个月 | 2009年破解，用时2年 | | 1024位 | 309位 | 数年（估算） | 理论上可行 | | 2048位 | 617位 | 数百万年（估算） | 目前安全 |
可以看到，256位RSA的分解难度微乎其微。
3. 为什么factordb能快速返回结果？
factordb是一个众包的分解数据库，包含：
- 学术界已分解的大整数
- CTF比赛中使用的整数
- 各种加密测试数据
- 志愿者贡献的分解结果
对于256位这样的小整数，几乎都已被预先分解并收录。
6.2 RSA密钥长度的演进历史
1977年：RSA算法发明，最初使用426位密钥
1994年：RSA-129（426位）被破解，用时8个月
1999年：RSA-512被破解，推荐使用1024位
2010年：开始推荐2048位作为最低标准
2015年：NIST要求政府系统使用至少2048位
2020年代：3072位和4096位逐渐成为高安全场景标准
未来展望：随着量子计算的发展，RSA可能需要更长的密钥，或被后量子密码算法替代
6.3 欧拉定理在RSA中的核心作用
让我们更深入地理解欧拉定理：
欧拉定理表述：
如果 gcd(a, n) = 1，则 a^φ(n) ≡ 1 (mod n)
费马小定理（欧拉定理的特殊情况）：
如果 p 是质数，gcd(a, p) = 1，则 a^(p-1) ≡ 1 (mod p)
在RSA中的应用：
设计d使得 e × d = k × φ(n) + 1，则：
M^(e×d) = M^(k×φ(n)+1) = M × M^(k×φ(n)) = M × (M^φ(n))^k
由欧拉定理，M^φ(n) ≡ 1 (mod n)，所以：
M × (M^φ(n))^k ≡ M × 1^k = M (mod n)
这就是RSA能够正确解密的数学基础。
一个有趣的思考：
如果不知道p和q，能否计算φ(n)？
答案是：非常困难！
事实上，计算φ(n)的难度与分解n的难度是等价的。如果能高效计算φ(n)，就能高效分解n，反之亦然。这就是为什么φ(n)必须保密的原因。
6.4 扩展欧几里得算法详解
扩展欧几里得算法是计算模逆的核心工具。让我们看看它是如何工作的：
算法原理：
欧几里得算法（辗转相除法）可以计算最大公约数：
gcd(a, b) = gcd(b, a mod b)
扩展版本不仅计算gcd，还找到整数x和y使得：
a × x + b × y = gcd(a, b)
算法实现：
def extended_gcd(a, b):
"""扩展欧几里得算法"""
if b == 0:
return a, 1, 0
else:
gcd, x1, y1 = extended_gcd(b, a % b)
x = y1
y = x1 - (a // b) * y1
return gcd, x, y
def mod_inverse(e, phi_n):
"""计算模逆"""
gcd, x, y = extended_gcd(e, phi_n)
if gcd != 1:
raise ValueError('模逆不存在')
else:
return (x % phi_n + phi_n) % phi_n
# 示例
e = 65537
phi_n = 87924348264132406875276140514499937144456189488436765114374296308467862464924
d = mod_inverse(e, phi_n)
print(f'd = {d}')
print(f'验证: (e × d) mod φ(n) = {(e * d) % phi_n}')
这个算法的时间复杂度是O(log min(a,b))，非常高效。
七、其他RSA攻击方法简介
除了本题使用的小模数分解攻击，RSA还存在其他攻击方式：
7.1 共模攻击（Common Modulus Attack）
场景： 多个用户使用相同的n，但不同的e加密同一消息M
原理： 如果gcd(e1, e2) = 1，可以使用扩展欧几里得算法找到s和t使得：
s × e1 + t × e2 = 1
则：
C1^s × C2^t ≡ M^(s×e1) × M^(t×e2) = M^(s×e1+t×e2) = M^1 = M (mod n)
无需私钥即可解密！
7.2 低加密指数攻击（Low Encryption Exponent Attack）
场景： 使用很小的e（如e=3），且明文M也很小
原理： 如果M^e < n，则加密后的C = M^e在整数域上成立，可以直接开e次方根得到M
防御： 使用OAEP等填充方案，确保M^e > n
7.3 Wiener攻击
场景： 当d相对较小时（d < n^0.25）
原理： 利用连分数逼近e/n，可以在多项式时间内恢复d
防御： 确保d足够大
7.4 选择密文攻击（Chosen Ciphertext Attack）
场景： 攻击者可以让系统解密任意密文（除了目标密文）
原理： 利用RSA的同态性：
(C × r^e)^d = C^d × r = M × r (mod n)
通过选择r，可以间接获取M的信息
防御： 使用OAEP等安全的填充方案
7.5 时序攻击（Timing Attack）
场景： 攻击者可以测量解密操作的时间
原理： 解密时间与私钥d的比特模式相关
防御： 使用固定时间的实现，或加入随机延迟
八、实际应用中的RSA安全建议
8.1 密钥长度选择
- 最低要求： 2048位（预计安全到2030年）
- 推荐配置： 3072位（预计安全到2040年）
- 高安全场景： 4096位
8.2 参数选择建议
1. 公钥指数e的选择：
- 推荐使用e = 65537（0x10001）
- 不要使用e = 3（容易受到低指数攻击）
- 确保gcd(e, φ(n)) = 1
2. 质数p和q的选择：
- p和q长度接近，都应为密钥长度的一半
- |p – q|要足够大，避免Fermat分解
- p-1和q-1都应有大质因子，避免Pollard p-1分解
3. 私钥指数d的选择：
- 确保d > n^0.29，避免Wiener攻击
8.3 使用安全的填充方案
不要使用：
- 教科书式RSA（无填充）
- PKCS#1 v1.5（已知有padding oracle攻击）
推荐使用：
- OAEP（Optimal Asymmetric Encryption Padding）
- PSS（对于签名）
8.4 密钥管理
- 定期更换密钥（建议每1-2年）
- 使用硬件安全模块（HSM）存储私钥
- 实施严格的访问控制
- 及时撤销泄露的密钥
8.5 后量子密码学考虑
随着量子计算的发展，Shor算法可以在多项式时间内分解大整数，RSA将不再安全。
应对措施：
- 关注NIST后量子密码标准化进程
- 考虑混合加密方案
- 提前规划向抗量子算法的迁移
九、总结与思考
9.1 本题的核心教训
通过这道题目，我们深刻认识到：
1. 密钥长度至关重要
密码学中没有”差不多安全”的概念。256位的RSA密钥看似是一个很大的数字，但在现代计算能力面前，它与完全不设防没有区别。
2. 安全标准需要与时俱进
随着计算能力的提升和算法的进步，昨天的安全标准可能成为今天的漏洞。必须持续关注最新的安全建议。
3. 理论与实践的结合
理解RSA的数学原理不仅能帮助我们正确使用它，还能让我们识别和利用其弱点。
9.2 从攻击者到防御者
作为安全研究人员，我们需要具备双重视角：
攻击者视角：
- 寻找系统的弱点
- 理解攻击的可行性
- 评估攻击的成本
防御者视角：
- 遵循安全最佳实践
- 使用经过验证的实现
- 进行定期的安全审计
9.3 RSA的未来
尽管存在各种攻击方式，RSA仍然是当今最重要的公钥密码系统之一。只要参数选择正确、实现得当，它仍然是安全的。
然而，量子计算的威胁日益临近。密码学界正在积极研究后量子密码算法，如：
- 基于格的密码学（Lattice-based）
- 基于编码的密码学（Code-based）
- 基于哈希的签名（Hash-based）
- 基于多变量的密码学（Multivariate）
未来的密码系统可能会采用混合方案，同时抵御传统和量子攻击。
9.4 延伸学习建议
如果你对密码学感兴趣，建议深入学习：
数学基础：
- 数论（质数、模运算、欧拉函数）
- 群论和域论
- 概率论和信息论
密码学理论：
- 对称加密算法（AES、ChaCha20）
- 其他公钥算法（ECC、DH密钥交换）
- 哈希函数和消息认证码
- 数字签名和证书体系
实践技能：
- 密码学库的使用（OpenSSL、Crypto）
- 密码协议分析（TLS/SSL）
- 侧信道攻击和防御
- 安全编程实践
推荐资源：
- 书籍：《应用密码学》（Bruce Schneier）
- 课程：Coursera的密码学课程（Dan Boneh）
- 平台：CryptoHack、CryptoPals挑战
- 工具：SageMath、yafu、factordb
十、总结
本文通过一道CTF密码学题目，完整展示了RSA小模数分解攻击的全过程：
攻击流程回顾：
解析公钥(n, e) → 发现密钥过短(256位) → 分解n得到(p, q) →
计算φ(n) → 计算私钥d → 构造完整私钥 → 解密获得flag
关键技术点：
- RSA算法的数学原理（欧拉定理、模逆运算）
- 公钥密钥文件的解析和操作
- 大整数因数分解方法
- 欧拉函数的计算
- 扩展欧几里得算法求模逆
- 密码学工具的实际使用
安全启示：
- 密钥长度直接决定安全性，必须使用足够长的密钥
- 密码学参数的选择需要严格遵循标准
- 理解算法原理对于安全使用至关重要
- 密码学是一个持续演进的领域，需要不断学习
Flag: PCTF{256b_i5_m3dium}
题目的flag直白地指出了问题所在：”256b_is_medium” – 256位是”medium”（中等），讽刺地暗示这样的密钥长度根本不安全，在攻击者眼中只是”中等难度”的练习题。
通过这道题目的学习，我们不仅掌握了RSA攻击的具体技术，更重要的是建立了密码学安全的正确认知。在实际应用中，我们应该：
- 使用至少2048位的RSA密钥
- 遵循最新的密码学安全标准
- 使用经过验证的密码学库
- 保持对新威胁和新技术的关注
密码学既是一门数学艺术，也是一项实践技能。希望本文能够帮助读者深入理解RSA算法，并在实际工作中正确、安全地使用密码学技术。
免责声明：
本文所载程序、技术方法仅面向合法合规的安全研究与教学场景，旨在提升网络安全防护能力，具有明确的技术研究属性。
任何单位或个人未经授权，将本文内容用于攻击、破坏等非法用途的，由此引发的全部法律责任、民事赔偿及连带责任，均由行为人独立承担，本站不承担任何连带责任。
本站内容均为技术交流与知识分享目的发布，若存在版权侵权或其他异议，请通过邮件联系处理，具体联系方式可点击页面上方的联系我。
本文转载自：破镜安全 破镜安全 破镜安全《RSA密码学攻击实战：小模数分解攻击完全解析》
版权声明
本站仅做备份收录，仅供研究与教学参考之用。
读者将信息用于其他用途的，全部法律及连带责任由读者自行承担，本站不承担任何责任。
评论