当前位置：首页 > news >正文

RSA加密基础攻击与CTF解题实战指南

news 2026/8/9 2:58:52

1. 题目背景与RSA基础回顾

这道来自HDCTF2019的"basic rsa"题目，考察的是RSA加密算法的基本攻击手法。RSA作为非对称加密的经典算法，其安全性建立在"大整数分解难题"之上。我们先快速回顾几个关键概念：

密钥生成：选择两个大素数p和q，计算n=p×q，φ(n)=(p-1)(q-1)
公钥(e,n)：选择与φ(n)互质的e，通常为65537
私钥(d,n)：计算e关于φ(n)的模反元素d，即e×d≡1 mod φ(n)
加密：密文c = m^e mod n
解密：明文m = c^d mod n

在实际CTF比赛中，RSA题目通常会给出部分参数（如n,e,c），要求选手通过分析参数特性来恢复明文。这道"basic rsa"从题目名称就能看出，考察的是最基础的RSA攻击手法。

2. 常见RSA攻击场景分类

根据题目可能给出的参数组合，我们可以预判几种典型的攻击场景：

2.1 模数分解攻击

当n较小时（通常小于512bit），可以直接用工具分解n得到p和q。常用工具有：

factordb.com（在线分解数据库）
yafu（本地分解工具）
sage的factor()函数

2.2 小指数攻击

当e很小时（如e=3），可能存在：

低加密指数攻击（直接开e次方）
中国剩余定理攻击（多组低加密指数）

2.3 共模攻击

当多组密文使用相同的n但不同e时，如果gcd(e1,e2)=1，可以通过扩展欧几里得算法恢复明文。

2.4 Wiener攻击

当d较小时（d < 1/3 × n^(1/4)），可以通过连分数展开恢复私钥d。

2.5 已知高位攻击

当知道p或q的部分高位比特时，可以使用Coppersmith方法恢复完整因子。

3. 题目分析与解题步骤

虽然题目具体内容未给出，但基于"basic rsa"的提示，我们模拟一个典型的解题流程：

3.1 获取题目参数

假设题目给出了以下参数：

n = 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139 e = 65537 c = 83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034

3.2 尝试模数分解

首先检查n的大小：

n.bit_length() # 返回100，说明是100位的整数

对于100位的n（约330bit），可以直接用factordb分解：

p = 37975227936943673922808872755445627854565536638199 q = 40094690950920881030683735292761468389214899724061

验证分解结果：

assert p * q == n

3.3 计算私钥参数

计算φ(n)和d：

from Crypto.Util.number import inverse phi = (p-1)*(q-1) d = inverse(e, phi)

3.4 解密密文

使用私钥解密：

m = pow(c, d, n) print(bytes.fromhex(hex(m)[2:]).decode())

4. 完整解题脚本

以下是Python实现的完整解题代码：

from Crypto.Util.number import inverse, long_to_bytes n = 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139 e = 65537 c = 83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034 # 分解n（实际比赛中可能需要使用factordb或yafu） p = 37975227936943673922808872755445627854565536638199 q = 40094690950920881030683735292761468389214899724061 # 计算私钥 phi = (p-1)*(q-1) d = inverse(e, phi) # 解密 m = pow(c, d, n) print(long_to_bytes(m).decode())