RSA攻击方法及密码学题目解析

1. dp泄露攻击

1.1 攻击原理

dp泄露攻击是针对RSA密码系统的一种攻击方法，当攻击者知道dp = d mod (p-1)时，可以有效地分解模数n。

1.2 攻击条件

• 已知公钥(n, e)
• 已知dp = d mod (p-1)
• 加密指数e较小(通常e=65537)

1.3 攻击步骤

1. 计算tmp = e × dp - 1
2. 遍历k ∈ [1, e)，寻找满足条件的k：
   • tmp能被k整除
   • p = (tmp // k) + 1是n的因数
   • p是素数
3. 找到p后，计算q = n // p
4. 计算私钥d = e⁻¹ mod (p-1)(q-1)
5. 解密消息m = cᵈ mod n

1.4 示例代码

import gmpy2
import binascii

n = 110231451148882079381796143358970452100202953702391108796134950841737642949460527878714265898036116331356438846901198470479054762675790266666921561175879745335346704648242558094026330525194100460497557690574823790674495407503937159099381516207615786485815588440939371996099127648410831094531405905724333332751
dp = 3086447084488829312768217706085402222803155373133262724515307236287352098952292947424429554074367555883852997440538764377662477589192987750154075762783925
c = 59325046548488308883386075244531371583402390744927996480498220618691766045737849650329706821216622090853171635701444247741920578127703036446381752396125610456124290112692914728856924559989383692987222821742728733347723840032917282464481629726528696226995176072605314263644914703785378425284460609365608120126
e = 65537

tmp = e * dp - 1
for k in range(1, e):
    if tmp % k == 0:
        p = (tmp // k) + 1
        if n % p == 0:
            q = n // p
            if gmpy2.is_prime(p) and gmpy2.is_prime(q):
                break

d = gmpy2.invert(e, (p-1)*(q-1))
m = pow(c, d, n)
m = hex(m)[2:]
flag = binascii.unhexlify(m)
print(flag)  # b'flag{C5G0_1s_the_8eSt_FPS_G@m3}'

2. 费马分解法

2.1 适用场景

当RSA的两个素数p和q非常接近时，可以使用费马分解法快速分解n。

2.2 攻击步骤

1. 计算x = ⌈√n⌉
2. 检查x² - n是否为完全平方数
3. 如果是，设y = √(x² - n)
4. 则p = x + y，q = x - y

2.3 示例代码

import gmpy2
from Crypto.Util.number import *

e = 65537
n = 1000000000000000000000000000156000000000000000000000000005643
c = 418535905348643941073541505434424306523376401168593325605206

x = gmpy2.iroot(n, 2)[0]
while 1:
    z = pow(x, 2) - n
    if gmpy2.is_square(z):
        y = gmpy2.iroot(z, 2)[0]
        p = x + y
        q = x - y
        break
    x += 1

phi_n = (p-1)*(q-1)
d = gmpy2.invert(e, phi_n)
print(long_to_bytes(pow(c, d, n)))  # b'xuanyuanbei_easy_rsa!'

3. 简单编码分析

3.1 分析步骤

1. 观察字符长度为6或7，排除培根密码
2. 猜测是ASCII码的二进制表示
3. 长度6可能是ASCII码小于64导致的
4. 转换为二进制后解码

3.2 Base编码分析

遇到类似"ZmQ2NjMyNGU2bDQ2YjhlODVjM2U2MjJlNGVhMGVhOTBlNzgwZjE3NDA5OWdjM2FjY2IxNGVhY2Y2N2I4fXs0NTUzNzhhMQ=="的字符串：

1. "Zm"开头通常表示Base64编码
2. 如果Base64解码后不是明文，尝试栅栏密码等其他编码方式

4. p+1光滑攻击

4.1 攻击原理

当p+1是光滑数(即p+1的所有素因子都较小)时，可以使用Williams' p+1分解算法来分解n。

4.2 攻击步骤

1. 选择一个整数A和初始值x₀
2. 计算序列xᵢ = xᵢ₋₁² - A mod n
3. 定期计算gcd(xᵢ - xⱼ, n)，如果结果不为1或n，则找到因子

5. Boneh-Durfee攻击

5.1 适用场景

当RSA私钥d满足d < n⁰.²⁹²时，可以使用Boneh-Durfee攻击恢复私钥，即使维纳攻击不适用。

5.2 与维纳攻击对比

• 维纳攻击：d < n⁰.²⁵
• Boneh-Durfee攻击：d < n⁰.²⁹²

6. SPECK加密算法逆向

6.1 SPECK算法简介

SPECK是一种轻量级分组密码算法，采用ARX结构(加法-旋转-异或)。

6.2 逆向步骤

1. 分析加密轮函数的结构
2. 确定轮密钥生成方式
3. 逆向每一轮的运算
4. 实现解密函数

6.3 逆向要点

1. 识别加法、旋转和异或操作
2. 跟踪密钥扩展过程
3. 注意轮函数的可逆性
4. 按相反顺序应用轮密钥

7. 综合解题策略

1. 识别题目类型：根据给出的信息判断可能的攻击方法
2. 尝试常见攻击：
   • 小指数攻击(e很小)
   • 共模攻击(相同的n)
   • 因数分解(特殊形式的n)
   • 侧信道攻击(如dp泄露)
3. 编码分析：
   • 观察字符串特征
   • 尝试Base系列编码
   • 考虑二进制/ASCII转换
4. 特殊算法分析：
   • 识别自定义加密算法
   • 逆向算法流程
   • 寻找算法弱点

8. 实用工具推荐

1. 数学计算：
   • gmpy2：大整数运算
   • sympy：符号数学计算
2. 编码转换：
   • binascii：二进制与ASCII转换
   • base64：Base64编解码
3. 密码学工具：
   • Crypto.Util.number：长整数与字节转换
   • pycryptodome：密码学算法实现
4. 分解工具：
   • factordb：在线因数分解数据库
   • yafu：本地因数分解工具

通过掌握这些攻击方法和工具，可以有效地解决大多数CTF中的密码学挑战。