1. 项目概述从实战视角重新审视RSA攻击如果你接触过CTFCapture The Flag竞赛或者对密码学安全感兴趣那么“RSA攻击”这个词你一定不陌生。但很多时候我们学到的RSA知识停留在教科书层面两个大质数相乘得到N公钥加密私钥解密安全基于大数分解难题。这没错但它只是故事的开头。真正的战场往往发生在那些教科书认为“理所当然”的假设被打破的时候。比如为什么CTF题目里总给你一个巨大的N为什么有时候又会故意给你一个很小的加密指数e这些都不是出题人的随意之举而是精心设计的“陷阱”引导你去发现并利用RSA在实际实现或使用中可能出现的脆弱点。今天我们就抛开复杂的数学证明从一个实战参与者和安全研究者的角度深入解析RSA的几种基础但极其有效的攻击方式。我们将聚焦于三个核心场景因数分解攻击、共享素数攻击和低加密指数攻击。我不会只告诉你“用什么工具跑一下”而是会拆解每一种攻击背后的数学原理和逻辑链条让你明白为什么这样能成功以及在什么条件下会失效。你会发现攻击RSA很多时候更像是在解一道条件不完整的数学谜题你需要从给定的碎片信息密文C、模数N、公钥指数e或许还有一点点其他提示中拼凑出私钥的真相。无论你是正在入门CTF的新手还是希望加固自己应用安全性的开发者理解这些攻击方式都至关重要。对攻击者而言这是打开密文的钥匙对防御者而言这是检查自身系统是否存在“低级错误”的清单。接下来我们就直接进入正题看看当RSA的“完美假设”出现裂缝时我们该如何行动。2. 核心攻击方式一因数分解攻击因数分解攻击是RSA最直接、最经典的攻击方式其核心思想直击RSA安全性的根本如果我能快速分解大整数N得到它的两个质因子p和q那么整个RSA体系在我面前就透明了。听起来很简单但为什么这能成为所有攻击的起点我们又该如何在实战中操作2.1 攻击原理与逻辑链条首先我们快速回顾一下RSA密钥生成过程选择两个大质数p和q。计算模数N p * q。计算欧拉函数φ(N) (p-1)*(q-1)。选择一个整数e作为公钥指数满足1 e φ(N)且gcd(e, φ(N)) 1即e与φ(N)互质。计算私钥指数d满足e * d ≡ 1 (mod φ(N))。公钥是(N, e)私钥是(N, d)。加密过程为C ≡ M^e (mod N)解密为M ≡ C^d (mod N)。攻击逻辑在只知道公钥(N, e)和密文C的情况下如果我们能成功分解N p * q那么整个攻击链条就打通了分解N- 得到p和q。计算φ(N)-φ(N) (p-1)*(q-1)。计算私钥d- 利用扩展欧几里得算法求解e * d ≡ 1 (mod φ(N))中的d。解密- 计算M ≡ C^d (mod N)得到明文。所以整个攻击成败的关键就在于第一步分解N。理论上对于足够大的N如2048位及以上使用通用数域筛GNFS等算法进行分解所需的时间在目前计算能力下是不可行的这构成了RSA的安全基础。然而“足够大”和“质数质量”是其中的关键变量。2.2 实战因数分解的工具与方法在CTF或安全评估中我们遇到的N往往不是密码学标准推荐的2048位可能是256位、512位、1024位或者虽然位数大但存在特殊结构。这时分解就变得可能。以下是我在实战中常用的工具链和判断流程第一步初步探测与信息收集拿到一个RSA题目首先看N的位数。可以用Python快速判断from Crypto.Util.number import long_to_bytes, bytes_to_long, getPrime, inverse, GCD import gmpy2 N 0xabcdef... # 你的N print(f“N的比特长度{N.bit_length()}”) print(f“N的十进制长度{len(str(N))}”)小于256位几乎可以瞬间分解直接尝试用最基础的方法。256位 ~ 512位属于CTF常见范围需要动用一些高效的分解工具。1024位需要警惕可能隐含其他漏洞如共享素数纯分解难度较大。大于2048位基本可以排除直接分解的可能必须寻找其他攻击路径。第二步选择分解工具根据N的大小和特点选择不同的工具在线分解网站用于小整数factordb.com 这是一个神奇的网站它不仅尝试分解你提交的数还维护了一个巨大的已知因数数据库。对于CTF中常见的、出题人可能复用过的N经常能直接查询到结果。这应该是你的第一站。用法直接输入N的十进制或十六进制值。本地工具 - Yafu功能非常强大的整数分解工具集成了多种算法Pollard-rho, ECM, SIQS等。它特别擅长自动选择算法对512位以下的整数分解效率很高。基本用法将N保存到文件num.txt中然后运行yafu “factor()” -batchfile num.txt。实战心得Yafu的siqs二次筛算法对于256-512位的数非常有效。如果数比较小它可能会直接用pollard rho或p-1算法秒出结果。记得在Linux环境下使用Windows下可能配置稍麻烦。本地工具 - SageMathSage是一个强大的数学软件系统。它的factor()函数在遇到有特殊结构的数时如平方数、光滑数可能比Yafu更快发现模式。用法在Sage单元格里直接输入factor(N)。适用场景当你怀疑N是某个光滑数smooth number即质因子都很小时或者想尝试一些数论攻击时Sage是很好的选择。Python库 - gmpy2gmpy2是Python的一个多精度算术库它的gmpy2.is_prime和gmpy2.next_prime有时能帮你快速判断一些边界情况。虽然它不直接分解大数但可以配合其他算法使用。更常用的是gmpy2.gcd(a, b)在共享素数攻击中至关重要后面会详细讲。第三步分解流程与示例假设我们拿到一个CTF题目公钥文件pub.key可以用openssl rsa -pubin -in pub.key -text -modulus查看提取出N和e以及密文C。# 假设我们已经提取出 N 742449129124467073921545687640895127535705902454369756401331 e 65537 C 0x... # 你的密文 # 1. 尝试factordb手动或模拟 # 访问 factordb.com输入 N。假设我们幸运地发现它已被收录。 # 得到 p 752708788837165590355094155871, q 986369682585281993933185289261 p 752708788837165590355094155871 q 986369682585281993933185289261 # 2. 验证 assert p * q N # 3. 计算φ(N)和私钥d phi (p-1) * (q-1) # 使用gmpy2求模逆元 import gmpy2 d int(gmpy2.invert(e, phi)) # 4. 解密 from Crypto.Util.number import long_to_bytes M pow(C, d, N) print(long_to_bytes(M))注意在实际CTF中N可能以十进制、十六进制0x开头或\n分隔、Base64等多种形式给出。密文C也可能如此。务必先统一转换成Python的整数类型int再进行运算。long_to_bytes和bytes_to_long是你的好朋友。2.3 因数分解的局限性为什么不能分解所有N理解了攻击方法更要理解它的边界。因数分解攻击并非万能。计算复杂度对于现代密码学标准RSA-2048, RSA-4096N的位数巨大即使使用最先进的算法和超级计算机分解所需的时间也远超宇宙年龄。因此使用足够长的密钥目前推荐至少2048位是抵御分解攻击的根本。质数质量p和q必须是真的“随机”大质数。如果p和q过小或者它们相差很小例如p和q接近sqrt(N)那么通过费马分解法或简单枚举区间可能会很快找到它们。这就是为什么密钥生成时要使用安全的随机数生成器。特殊结构如果p-1或q-1是光滑数即它的质因子都很小那么Pollard‘s p-1算法可能会高效地分解N。但这依赖于p-1或q-1的因子性质不是普遍适用的。给开发者的启示在实现RSA密钥对生成时务必使用经过严格审计的密码学库如OpenSSL,cryptography等。不要自己写密钥生成逻辑很容易在质数选择上引入弱点。3. 核心攻击方式二共享素数攻击这是一种非常有趣且在实际中曾真实发生过的攻击。想象一个场景一个机构内部多个服务或产品为了“方便”使用了相同的RSA密钥生成算法但可能因为随机数生成器RNG出现问题导致不同的密钥对使用了相同的质数。或者在CTF题目中出题人故意给了你多个公钥文件。这时共享素数攻击就可能派上用场。3.1 攻击原理欧几里得算法的妙用攻击原理基于一个简单的数学事实如果两个不同的模数N1和N2共享一个相同的质因子p那么p必然是N1和N2的最大公约数gcd。即N1 p * q1N2 p * q2则gcd(N1, N2) p因为q1和q2互质一旦我们通过计算gcd(N1, N2)得到了这个公共的质因子p那么分解这两个N就都迎刃而解了对于N1q1 N1 // p对于N2q2 N2 // p随后我们就可以分别计算各自的φ(N)和私钥d从而解密对应的密文。为什么这会发生在现实世界劣质随机数生成器在一些嵌入式设备、旧系统或定制化硬件中随机数生成器的熵源不足导致生成的“随机”质数实际上在一个很小的集合内循环碰撞概率大大增加。密钥生成流程漏洞某些实现可能在生成密钥时错误地复用了部分随机状态。人为因素在测试或开发环境中为了方便直接写死了某些质数。3.2 实战演练从多个公钥中恢复私钥假设我们在CTF题目中拿到了两个公钥文件pub1.key和pub2.key以及分别用它们加密的密文C1和C2。步骤1提取模数N1和N2使用OpenSSL命令或Python的Crypto.PublicKey.RSA模块来提取。from Crypto.PublicKey import RSA # 读取公钥文件1 with open(‘pub1.key’, ‘r’) as f: key1 RSA.import_key(f.read()) N1 key1.n e1 key1.e # 读取公钥文件2 with open(‘pub2.key’, ‘r’) as f: key2 RSA.import_key(f.read()) N2 key2.n e2 key2.e print(f“N1 {N1}”) print(f“N2 {N2}”)步骤2计算最大公约数GCD使用gmpy2.gcd或Python自带的math.gcdPython 3.5来计算。import gmpy2 p gmpy2.gcd(N1, N2) print(f“共享的质因子 p {p}”) if p 1: # 找到了共享素数 q1 N1 // p q2 N2 // p # 验证 assert p * q1 N1 assert p * q2 N2 print(f“N1的另一个因子 q1 {q1}”) print(f“N2的另一个因子 q2 {q2}”) else: print(“未发现共享素数需尝试其他攻击方法。”)步骤3分别计算私钥并解密# 计算φ(N)和私钥d phi1 (p-1) * (q1-1) phi2 (p-1) * (q2-1) d1 int(gmpy2.invert(e1, phi1)) d2 int(gmpy2.invert(e2, phi2)) # 解密 (假设C1, C2已知) from Crypto.Util.number import long_to_bytes M1 pow(C1, d1, N1) M2 pow(C2, d2, N2) print(f“明文1 {long_to_bytes(M1)}”) print(f“明文2 {long_to_bytes(M2)}”)实战心得与陷阱不止两个N有时题目会给出多个比如5个公钥。这时你需要两两计算gcd。最坏情况下你需要计算C(5,2)10次gcd。写个循环即可。如果其中存在共享素数你一定能找到。gcd结果等于1如果所有gcd(Ni, Nj)都等于1说明这些N两两互质不存在共享素数攻击的条件。但这并不意味着它们绝对安全可能隐藏着其他漏洞比如下面要讲的低加密指数广播攻击。p就是N本身在计算gcd时如果发现gcd(N1, N2) N1这意味着N1整除N2即N1是N2的一个因子。这在实际中极为罕见但理论上可能处理方式类似。3.3 防御措施如何避免共享素数风险对于开发者而言避免共享素数攻击是基本要求使用密码学安全的随机数生成器CSPRNG在生成质数p和q时必须使用操作系统提供的安全随机源如/dev/urandomCryptGenRandomgetrandom()系统调用。绝对不要使用自己写的伪随机算法或时间戳等熵源不足的种子。定期更换密钥即使随机源安全长期使用同一对密钥也会增加风险。建立合理的密钥轮换机制。审计与监控对于大规模部署可以定期抽取公钥批量计算gcd进行自查这是一个成本很低但能发现重大隐患的检查。4. 核心攻击方式三低加密指数攻击这是一种因公钥指数e选取过小而导致的攻击。在RSA中e通常取655370x10001这是一个在安全性和加密/验证效率之间很好的平衡。但有时为了提升加密速度特别是在资源受限的设备上可能会选择更小的e比如3、17等。当e很小并且满足特定条件时就可能被攻击。4.1 低加密指数攻击e3的数学原理这种攻击主要分为两类情况我们分别来看。情况一明文过小未进行填充如果明文M很小使得M^e N那么加密运算C ≡ M^e (mod N)实际上就等于M^e因为模运算没有起作用。那么攻击者只需要对密文C开e次方根就能直接得到明文M。攻击条件M^e N攻击方法直接计算M C^(1/e)即e次根。在整数域中这等价于M round(C ** (1/e))或使用gmpy2.iroot(C, e)函数。import gmpy2 from Crypto.Util.number import long_to_bytes N 非常大的数 e 3 C 密文整数 # 尝试对C开e次方 root, is_exact gmpy2.iroot(C, e) if is_exact: print(f“找到明文 {long_to_bytes(int(root))}”) else: print(“开方不精确不是这种情况。”)情况二低加密指数广播攻击Håstad‘s Broadcast Attack这是更常见、也更强大的一种攻击。假设同一个明文M用相同的低加密指数e比如e3但不同的模数N1, N2, N3进行加密得到三个密文C1, C2, C3。即C1 ≡ M^3 (mod N1)C2 ≡ M^3 (mod N2)C3 ≡ M^3 (mod N3)根据中国剩余定理CRT我们可以找到一个唯一的整数X满足X ≡ C1 (mod N1)X ≡ C2 (mod N2)X ≡ C3 (mod N3)并且这个X在模N1*N2*N3的意义下是唯一的。关键在于由于M小于每个Ni那么M^3也小于每个Ni。如果M^3 N1*N2*N3那么通过CRT计算出来的X实际上就等于M^3而不仅仅是在模N1*N2*N3下同余。因为X是满足所有同余式的最小正整数解而M^3也满足且M^3 N1*N2*N3所以X M^3。于是攻击就变成了收集至少e组这里e3使用相同小e加密的密文和模数对利用CRT求出X M^e然后对X开e次方即可得到明文M。4.2 实战演练广播攻击e3假设我们拿到三组数据N1, e13, C1 N2, e23, C2 N3, e33, C3步骤1验证攻击条件e相同且很小这里是3。明文M是相同的。模数N1, N2, N3两两互质通常都是因为由不同的质数生成。可以用gcd验证。步骤2使用中国剩余定理CRT求解Python的gmpy2或sympy库提供了CRT函数。这里我们用sympy.ntheory.modular.crt。import gmpy2 from sympy.ntheory.modular import crt from Crypto.Util.number import long_to_bytes # 假设数据 N [N1, N2, N3] # 三个模数的列表 C [C1, C2, C3] # 三个密文的列表 e 3 # 使用CRT求解 X ≡ Ci (mod Ni) X, _ crt(N, C) # X 是满足同余式的最小正整数解 # 对X开e次方 root, is_exact gmpy2.iroot(X, e) if is_exact: M int(root) print(f“破解的明文 M {M}”) print(f“明文文本 {long_to_bytes(M)}”) else: print(“开方失败可能收集的密文组数不够或者M^e超过了所有N的乘积。”)步骤3为什么需要至少e组数据从上面的推导可以看出我们需要保证M^e N1 * N2 * ... * Nk。M通常小于单个N因为明文需要编码成小于N的整数。为了确保M^e小于所有N的乘积我们需要足够多的N来“撑大”这个乘积。理论上当k e时N1 * N2 * ... * Nk极有可能大于M^e。所以对于e3我们至少需要3组密文。4.3 低加密指数攻击的变种与防御Coppersmith攻击当e很小但明文M的某些部分已知或者M是某种有格式的消息如已知开头是“flag{”时可以使用更强大的Coppersmith定理进行攻击。这属于更高级的范畴但思想依然是利用e小带来的数学上的“线性”或“低次”特性。防御措施永远不要使用小e公钥指数e必须足够大。65537是目前绝对的标准和最佳实践。它只有两个比特位为1使得模幂运算平方乘算法非常高效同时又足够大以抵抗低加密指数攻击。使用正确的填充方案如PKCS#1 v1.5 (RSAES-PKCS1-v1_5) 或 OAEP (RSAES-OAEP)。填充会在明文前加入随机字节使得即使相同的明文、相同的公钥每次加密结果也不同并且确保加密后的消息即M非常大接近N的大小从而使得M^e N的条件几乎不可能成立。这是抵御低加密指数攻击和许多其他攻击如选择密文攻击的关键。重要提示在实际的密码学应用中“裸”RSA即不对明文进行填充直接加密是极其危险和不安全的。所有安全的RSA实现都必须使用填充方案。CTF题目中出现的“裸”RSA正是为了考察对这些基础攻击的理解。5. 实战问题排查与技巧实录在真正动手解题或进行安全测试时你会遇到各种各样的问题。下面是我总结的一些常见坑点和解决技巧。5.1 数据格式处理乱码与解码问题从题目文件或网络抓包中提取出的N、e、C经常不是干净的整数。可能是十六进制字符串带或不带0x、Base64、PEM格式、ASN.1 DER编码等。技巧PEM格式公钥使用openssl rsa -pubin -in pub.key -text -modulus查看-modulus参数会直接输出16进制的N。或者用Python的Crypto.PublicKey.RSA.import_key()。Base64编码先base64.b64decode()然后根据内容判断。如果是PEM通常以-----BEGIN PUBLIC KEY-----开头如果是纯数据可能需要解析ASN.1结构。对于简单的十六进制Base64解码后就是hex字符串。Python处理示例import base64 from Crypto.Util.number import bytes_to_long, long_to_bytes # 情况1: Base64编码的十六进制字符串 b64_str “MDk4NTY0NzMx...” hex_str base64.b64decode(b64_str).decode(‘ascii’) # 解码后得到hex字符串 N int(hex_str, 16) # 转整数 # 情况2: PEM文件 from Crypto.PublicKey import RSA with open(‘public.pem’, ‘r’) as f: key RSA.import_key(f.read()) N key.n e key.e # 情况3: 直接给十六进制字符串可能有换行或空格 hex_str_with_spaces “”” 00:aa:bb:cc:dd ee:ff:00:11:22 “”” clean_hex hex_str_with_spaces.replace(‘:’, ‘’).replace(‘\n’, ‘’).replace(‘ ‘, ‘’) N int(clean_hex, 16)5.2 分解失败下一步该怎么办问题你把N扔进factordb和Yafu都失败了。N有1024位看起来没法直接分解。排查思路检查是否为共享素数攻击这是优先级非常高的检查。看看题目是否提供了多个公钥或密文立刻写脚本计算所有N两两之间的gcd。检查公钥指数ee是不是特别小如3如果是思考是否是低加密指数广播攻击。收集所有使用相同e加密的密文和模数。检查e是否很大如果e很大比如和N差不多大这可能暗示私钥d很小可能存在维纳攻击Wiener‘s Attack。这需要更专业的工具如RsaCtfTool的--wiener选项。检查N是否有特殊形式用gmpy2.iroot(N, 2)检查N是不是一个完全平方数即p q这严重违反RSA安全要求。或者检查N是否能被一些小质数整除虽然概率极低。查看其他提示题目描述、文件名、注释里有没有提示比如“快速幂”、“小明用了相同的质数”等。考虑其他高级攻击如果以上都不行可能是更复杂的攻击如共模攻击相同N不同e加密相同明文、选择密文攻击、或需要利用Coppersmith定理的场景已知明文高位、低位等。这时可能需要使用像RsaCtfTool、sage这样的强大工具。5.3 工具链推荐与使用心得RsaCtfTool这是一个用Python写的、功能极其全面的RSA攻击工具集合。它自动化了大部分我们上面提到的攻击方式。安装git clone https://github.com/RsaCtfTool/RsaCtfTool.git基本使用python RsaCtfTool.py --publickey pub.key --uncipherfile cipher.bin强大之处它会自动尝试数十种攻击方法包括因数分解连接factordb、维纳攻击、低加密指数攻击、共模攻击、各种Coppersmith攻击等。当你没有明确思路时把它当作第一道自动化工序非常有效。心得学会看它的输出日志了解它尝试了哪些攻击失败的原因是什么这本身也是学习过程。SageMath对于需要复杂数论运算的攻击如CoppersmithSage是首选。它的PolynomialRing和small_roots方法非常强大。典型场景已知明文的部分字节或者知道p或q的部分比特。Python gmpy2 pycryptodome这是我的主力编程环境。gmpy2处理大整数运算飞快pycryptodome或cryptography提供了标准的密码学原语和格式解析。一个完整的实战排查流程建议信息收集提取所有N,e,C。记录位数、数量。自动化初筛用RsaCtfTool跑一遍看能否自动破解。手动检查检查e的大小。检查是否有多个N尝试gcd。检查是否有多个相同e的(N, C)对尝试广播攻击。深入分析如果以上都失败重新审题寻找隐藏信息考虑更高级的攻击模型。理解这些基础攻击方式就像是掌握了破解RSA谜题的几把最常用的钥匙。它们对应着RSA在实现和使用中最容易犯的几种错误。对于安全研究者这是攻击面评估的清单对于开发者这是绝对要避免的陷阱清单。密码学的安全性往往就建立在“别人都知道这些攻击所以我们必须做得更好”的基础之上。当你下次再看到一段RSA加密的密文时希望你能像侦探一样有条不紊地检查这些“常见漏洞”或许就能发现那条通往明文的隐秘小径。