rsa Writeup by AI

kang0x0

345人浏览 · 2026-03-23 09:21:40

kang0x0 · 2026-03-23 09:21:40 发布

rsa Writeup by AI

题目信息

题目来源: 攻防世界 (Adworld)
题目类型: Crypto (密码学)
题目名称: rsa

题目描述

本题是一个 RSA 加密挑战，提供了 RSA 公钥文件 (pubkey.pem) 和加密后的 flag 文件 (flag.enc)，需要解密获取原始 flag。

考点分析

RSA 公钥解析: 从 PEM 格式文件中提取 n 和 e
Fermat 分解攻击: 当 RSA 的两个素数 p 和 q 非常接近时，可以使用 Fermat 分解法快速分解大整数 n
RSA 解密: 使用私钥 d 对密文进行解密
数据编码转换: 处理二进制文件和字符串转换

解题思路

1. 分析公钥

首先读取 pubkey.pem 文件，提取 RSA 公钥参数：

n: 4096 位的大整数
e: 65537 (常用的 RSA 指数)

2. 分解 n

由于 n 是 4096 位，无法直接分解。但题目设计时可能让 p 和 q 很接近，因此尝试使用 Fermat 分解法。

Fermat 分解原理:
如果 n = p × q，且 p ≈ q，那么可以令：

a = ⌈√n⌉
b² = a² - n

通过不断递增 a，直到 b² 成为完全平方数，此时：

p = a - b
q = a + b

3. 计算私钥

一旦分解得到 p 和 q，就可以计算：

φ(n) = (p-1)(q-1)
d = e⁻¹ mod φ(n)

4. 解密 flag

使用 RSA 解密公式：m = c^d mod n

然后将解密结果转换为字符串格式。

详细步骤

步骤 1: 导入必要的库

from Crypto.PublicKey import RSA
import gmpy2
from libnum import n2s, s2n
import math

步骤 2: 读取公钥

with open('pubkey.pem', 'r') as f:
    pubkey = RSA.import_key(f.read())

n = pubkey.n
e = pubkey.e

步骤 3: Fermat 分解

def fermat_factor(n):
    a = math.isqrt(n) + 1
    for i in range(10**6):
        b2 = (a+i)*(a+i) - n
        if b2 < 0:
            continue
        b = gmpy2.iroot(b2, 2)
        if b[1]:  # b2 是完全平方数
            p = (a+i) - b[0]
            q = (a+i) + b[0]
            return p, q
    return None, None

p, q = fermat_factor(n)

步骤 4: 计算私钥并解密

phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi)

with open('flag.enc', 'rb') as f:
    cipher_bytes = f.read()

c = int.from_bytes(cipher_bytes, 'big')
m = pow(c, d, n)

flag_bytes = m.to_bytes((m.bit_length() + 7) // 8, 'big')
flag = flag_bytes.decode('utf-8', errors='ignore')

步骤 5: 提取 flag

从解码结果中查找符合 flag{...} 格式的内容。

完整代码

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
攻防世界 Crypto 12-rsa 解题脚本
考点：RSA 公钥解析与 Fermat 分解攻击
当 RSA 的两个素数 p 和 q 非常接近时，可以使用 Fermat 分解法快速分解 n
"""

from Crypto.PublicKey import RSA
import gmpy2
from libnum import n2s, s2n
import math

def fermat_factor(n):
    """Fermat 分解法：适用于 p 和 q 很接近的情况"""
    a = math.isqrt(n) + 1
    b2 = a*a - n
    
    # 尝试最多 10^6 次
    for i in range(10**6):
        b2 = (a+i)*(a+i) - n
        if b2 < 0:
            continue
        b = gmpy2.iroot(b2, 2)
        if b[1]:
            p = (a+i) - b[0]
            q = (a+i) + b[0]
            return p, q
    
    return None, None

def solve():
    # 读取公钥
    with open('pubkey.pem', 'r') as f:
        pubkey = RSA.import_key(f.read())
    
    n = pubkey.n
    e = pubkey.e
    
    print("=" * 60)
    print("攻防世界 Crypto 12-rsa 解题")
    print("=" * 60)
    print(f"\n公钥参数:")
    print(f"n 的位数：{n.bit_length()} bits")
    print(f"e = {e}")
    
    # 使用 Fermat 分解
    print("\n使用 Fermat 分解法分解 n...")
    p, q = fermat_factor(n)
    
    if p and q:
        print(f"✓ 分解成功!")
        print(f"p = {p}")
        print(f"q = {q}")
        
        # 验证
        assert p * q == n, "分解错误!"
        print("✓ 验证通过：p * q = n")
        
        # 计算私钥 d
        phi = (p - 1) * (q - 1)
        d = gmpy2.invert(e, phi)
        print(f"\n私钥 d 已计算")
        
        # 读取密文
        with open('flag.enc', 'rb') as f:
            cipher_bytes = f.read()
        
        c = int.from_bytes(cipher_bytes, 'big')
        
        # RSA 解密：m = c^d mod n
        print("\n解密中...")
        m = pow(c, d, n)
        
        # 尝试多种方式转换
        print("\n尝试解码明文...")
        
        # 方法 1：直接转换为字节
        try:
            flag_bytes = m.to_bytes((m.bit_length() + 7) // 8, 'big')
            
            # 尝试解码为字符串
            try:
                flag = flag_bytes.decode('utf-8', errors='ignore')
                
                # 提取有效的 flag 格式
                if 'flag{' in flag:
                    start = flag.find('flag{')
                    end = flag.find('}', start) + 1
                    if end > start:
                        clean_flag = flag[start:end].strip()
                        print(f"\n✅ 最终 Flag: {clean_flag}")
                        return clean_flag
            except:
                pass
        except Exception as ex:
            print(f"方法 1 失败：{ex}")
        
        return None
    else:
        print("✗ Fermat 分解失败")
        return None

if __name__ == "__main__":
    solve()

总结

关键知识点

Fermat 分解攻击适用条件: 当 RSA 的两个素数 p 和 q 非常接近时（即 |p-q| 很小），可以使用 Fermat 分解法在合理时间内分解 n
为什么 p 和 q 接近会有危险: 因为 Fermat 分解的时间复杂度取决于 |p-q| 的大小，当两者接近时，只需要很少的迭代次数就能找到因子
实际 RSA 应用中的防范: 在实际应用中，生成 RSA 密钥时应确保 p 和 q 足够随机且相差较大，避免此类攻击