RSA加密算法攻击：从数学原理到CTF实战攻击（CTF实战概念篇）

文章目录前言一、先建立一个“攻击全景图”二、基础攻击1、因式分解 n最直接2、小指数攻击e 很小3、共模攻击Common Modulus Attack4、广播攻击Håstad Attack三、进阶攻击5、Wiener Attack小 d 攻击6、已知部分信息Coppersmith7、低熵 / 弱随机数四、真实世界攻击8、Padding Oracle最经典Side Channel侧信道攻击五、CTF 解题思维Step 1看 nStep 2看 eStep 3看密文数量Step 4看提示Step 5看 padding小结前言学习这篇文章其实是共同学习了只要从知道RSA属于密码学中的Public Key Cryptography公钥密码学这个概念开始。如果读者说还不知道这个概念那么读者现在应当是知道了RSA是非对称密码属于公钥密码学。就可以开始学习实现从零到能打CTF的入门的这一系列。这是上一篇的前言复制了一下学习这一篇请先学习RSA算法详解从原理到实现全且深入浅出这是系列二旨在讲解CTF比赛中RSA加密算法可利用的攻击。一、先建立一个“攻击全景图”RSA 攻击本质几乎都在利用这三类问题1. 数学结构漏洞n 被分解d 太小e 不合理使用方式错误重复使用 n多次加密同一消息没有 padding实现漏洞真实世界padding oracleside-channel侧信道对于正常的CTF来说首先要学习的是数学结构漏洞。怎么说。RSA 本身很安全出问题的是“人怎么用它”二、基础攻击1、因式分解 n最直接条件n p × qp 或 q 太小 / 太接近方法直接分解 n一旦分解φ(n) (p-1)(q-1)求 d → 解密回顾之前的文章本质攻击的是整数分解问题Integer factorization problem。2、小指数攻击e 很小​常见e 3如果m e n m^enmen那么实际上没有发生 mod 运算。c m e cm^ecme直接开方m c e m \sqrt[e]{c}mec​道理简单但是 CTF 里非常常见3、共模攻击Common Modulus Attack条件同一个 n不同 e同一个 mc 1 m e 1 , c 2 m e 2 c_1 m^{e_1}, \quad c_2 m^{e_2}c1​me1​,c2​me2​且:​gcd ⁡ ( e 1 , e 2 ) 1 \gcd(e_1, e_2) 1gcd(e1​,e2​)1核心思路用扩展欧几里得a e 1 b e 2 1 a e_1 b e_2 1ae1​be2​1那么:m c 1 a ⋅ c 2 b m o d n m c_1^a \cdot c_2^b \mod nmc1a​⋅c2b​modn本质利用的是指数“线性组合可逆”4、广播攻击Håstad Attack条件同一个 m不同 n相同 e通常 e3用 Chinese Remainder Theorem合并多个密文 → 得到m e m^eme再开 e 次方 → 得 m本质“多次加密反而泄露信息”三、进阶攻击5、Wiener Attack小 d 攻击条件d 很小满足大约d 1 3 n 1 / 4 d \frac{1}{3} n^{1/4}d31​n1/4方法连分数展开 e/n恢复 d本质私钥太“简单”6、已知部分信息Coppersmith条件知道 p 的一部分或 m 的一部分使用格攻击LLL本质“已知一点点 → 推出全部”7、低熵 / 弱随机数如果p、q 生成不好或重复会出现不同 n 有公共因子直接gcd ⁡ ( n 1 , n 2 ) ≠ 1 \gcd(n_1, n_2) \ne 1gcd(n1​,n2​)1四、真实世界攻击8、Padding Oracle最经典针对PKCS#1 v1.5核心思想攻击者不断试探密文观察“是否合法”逐步恢复明文典型攻击Bleichenbacher Attack属于 CryptanalysisSide Channel侧信道攻击不是攻击数学而是攻击实现比如时间Timing Attack功耗Power Analysis缓存Cache Attack例子解密时间不同 → 推出 d五、CTF 解题思维Step 1看 n能不能分解多个 n 是否有 gcdStep 2看 e是否很小3 / 5是否多个 eStep 3看密文数量是否重复加密是否多个模数Step 4看提示是否泄露部分 p / d / mStep 5看 padding是否“裸 RSA”最危险小结为什么是概念篇因为这个密码学的学习给个概念理解就可以了这里给出例子给出代码用处不大主要还是自己做题。推荐一题2026软件系统安全赛初赛RSA