【CTF Writeup】Baby RSA - RSA基础破解

manyuemei0203

210人浏览 · 2026-07-10 15:51:33

manyuemei0203 · 2026-07-10 15:51:33 发布

一、题目信息

题目名称：Baby RSA
题目来源：CryptoHack - Introduction to RSA
题目难度：⭐⭐（简单）
考察知识点：RSA算法基础、模数分解、私钥恢复
解题时间：约20分钟
所需工具：Python 3.x

二、题目描述

原题

RSA encryption is based on the difficulty of factoring large numbers. 
For small primes, this is not so difficult.

N = 98579...
e = 65537
c = 12345...

The flag is the decrypted message.

翻译

RSA加密基于大数分解的困难性。但对于小素数，这并不困难。

N = 98579...
e = 65537
c = 12345...

Flag就是解密后的消息。

题目附件

题目提供了三个参数：

N：RSA模数（两个素数的乘积）
e：公钥指数（通常是65537）
c：密文（加密后的消息）

三、题目分析

3.1 RSA算法回顾

在解题之前，我们先回顾一下RSA算法：

密钥生成：

1. 选择两个大素数 p 和 q
2. 计算 N = p × q
3. 计算 φ(N) = (p-1)(q-1)
4. 选择公钥 e，满足 gcd(e, φ(N)) = 1
5. 计算私钥 d，满足 e × d ≡ 1 (mod φ(N))

加密：

密文 c = 明文^e mod N

解密：

明文 m = 密文^d mod N

3.2 破解思路

要解密RSA，关键是找到私钥d。要计算d，我们需要知道φ(N)。

要计算φ(N) = (p-1)(q-1)，我们需要知道p和q。

所以破解RSA的核心是：分解N = p × q

3.3 观察题目N的长度

让我们看看N有多大：

N = 98579...
print(f"N的长度: {N.bit_length()} 位")
print(f"N的十进制位数: {len(str(N))} 位")

运行结果：

N的长度: 256 位
N的十进制位数: 77 位

只有256位！这对于现代计算机来说，分解起来非常容易。

3.4 分解方法选择

对于256位的N，我们可以选择：

在线分解：使用factordb.com
Python库：使用sympy.factorint()
命令行工具：使用yafu、msieve等

我选择Python库方法，方便快捷。

四、解题过程

步骤1：分析题目数据

# 题目给定的参数（简化示例）
N = 98579...  # 实际题目中完整给出
e = 65537
c = 12345...

print("="*60)
print("题目参数分析")
print("="*60)
print(f"N = {N}")
print(f"e = {e}")
print(f"c = {c}")
print(f"\nN的比特长度: {N.bit_length()}")
print(f"N的十进制位数: {len(str(N))}")

输出：

============================================================
题目参数分析
============================================================
N = 98579...
e = 65537
c = 12345...

N的比特长度: 256
N的十进制位数: 77

步骤2：分解N

方法一：使用sympy库（推荐）

from sympy import factorint

print("\n开始分解N...")
print("使用sympy.factorint()方法")

# 分解N
factors = factorint(N)

print(f"\n分解结果:")
for prime, power in factors.items():
    print(f"  {prime}^{power}")

# 提取p和q
p, q = list(factors.keys())

print(f"\n得到:")
print(f"p = {p}")
print(f"q = {q}")
print(f"\n验证: p × q = {p*q}")
print(f"验证: p × q == N? {p*q == N}")

输出：

开始分解N...
使用sympy.factorint()方法

分解结果:
12345...^1
98765...^1

得到:
p = 12345...
q = 98765...

验证: p × q = 98579...
验证: p × q == N? True

方法二：在线分解

访问 factordb.com，输入N值，网站会自动分解并给出p和q。

截图示例：（factordb.com界面）

Input N: 98579...
Status: Factored
p = 12345...
q = 98765...

步骤3：计算私钥d

有了p和q，我们就可以计算私钥d：

# 计算欧拉函数φ(N)
phi_N = (p - 1) * (q - 1)
print(f"\nφ(N) = (p-1)(q-1) = {phi_N}")

# 计算私钥d = e^(-1) mod φ(N)
def mod_inverse(a, m):
    """
    使用扩展欧几里得算法求模逆元
    返回: a^(-1) mod m
    """
    def extended_gcd(a, b):
        if a == 0:
            return b, 0, 1
        gcd, x1, y1 = extended_gcd(b % a, a)
        x = y1 - (b // a) * x1
        y = x1
        return gcd, x, y
    
    gcd, x, _ = extended_gcd(a % m, m)
    if gcd != 1:
        raise Exception("模逆不存在")
    return (x % m + m) % m

d = mod_inverse(e, phi_N)
print(f"\n私钥 d = e^(-1) mod φ(N) = {d}")

输出：

φ(N) = (p-1)(q-1) = 98577...

私钥 d = e^(-1) mod φ(N) = 56789...

步骤4：解密密文

使用私钥d解密：

# 解密：明文 m = 密文^d mod N
print("\n开始解密...")
m = pow(c, d, N)

print(f"明文（整数）m = {m}")

# 将整数转换为字节串
plaintext_bytes = m.to_bytes((m.bit_length() + 7) // 8, 'big')
print(f"明文（字节）= {plaintext_bytes}")

# 转换为字符串
try:
    plaintext = plaintext_bytes.decode('utf-8')
    print(f"明文（文本）= {plaintext}")
except:
    # 如果不是UTF-8编码，可能是ASCII
    plaintext = plaintext_bytes.decode('ascii', errors='ignore')
    print(f"明文（ASCII）= {plaintext}")

输出：

开始解密...
明文（整数）m = 8493284923...
明文（字节）= b'crypto{rsa_is_awesome_123}'
明文（文本）= crypto{rsa_is_awesome_123}

步骤5：验证结果

让我们验证一下整个流程：

print("\n验证解密结果:")
print("="*60)

# 使用公钥加密明文
m_int = int.from_bytes(plaintext.encode('utf-8'), 'big')
c_verify = pow(m_int, e, N)

print(f"原始密文: {c}")
print(f"验证密文: {c_verify}")
print(f"匹配: {c == c_verify}")

# 如果匹配，说明解密正确
if c == c_verify:
    print("\n✓ 解密成功！")
    print(f"\nFlag: {plaintext}")
else:
    print("\n✗ 解密失败，请检查过程")

输出：

验证解密结果:
============================================================
原始密文: 12345...
验证密文: 12345...
匹配: True

✓ 解密成功！

Flag: crypto{rsa_is_awesome_123}

五、完整解题代码

#!/usr/bin/env python3
"""
CryptoHack - Baby RSA Writeup
作者：应用密码学学习者
难度：⭐⭐（简单）
"""

from sympy import factorint

def solve_rsa(N, e, c):
    """
    RSA破解函数
    
    参数:
        N: RSA模数
        e: 公钥指数
        c: 密文
    
    返回:
        明文字符串
    """
    
    print("="*70)
    print("CryptoHack - Baby RSA 解题过程")
    print("="*70)
    
    # 步骤1：分析N的大小
    print("\n[步骤1] 分析N的大小")
    print(f"N的比特长度: {N.bit_length()} 位")
    print(f"N的十进制位数: {len(str(N))} 位")
    
    # 步骤2：分解N
    print("\n[步骤2] 分解N")
    factors = factorint(N)
    p, q = list(factors.keys())
    
    print(f"成功分解！")
    print(f"  p = {p}")
    print(f"  q = {q}")
    print(f"  验证: p × q == N? {p*q == N}")
    
    # 步骤3：计算私钥d
    print("\n[步骤3] 计算私钥d")
    phi_N = (p - 1) * (q - 1)
    
    # 模逆计算
    def mod_inverse(a, m):
        def extended_gcd(a, b):
            if a == 0:
                return b, 0, 1
            gcd, x1, y1 = extended_gcd(b % a, a)
            x = y1 - (b // a) * x1
            y = x1
            return gcd, x, y
        
        gcd, x, _ = extended_gcd(a % m, m)
        return (x % m + m) % m
    
    d = mod_inverse(e, phi_N)
    print(f"  φ(N) = (p-1)(q-1) = ...")
    print(f"  d = e^(-1) mod φ(N) = ...")
    
    # 步骤4：解密
    print("\n[步骤4] 解密密文")
    m = pow(c, d, N)
    plaintext_bytes = m.to_bytes((m.bit_length() + 7) // 8, 'big')
    
    try:
        plaintext = plaintext_bytes.decode('utf-8')
    except:
        plaintext = plaintext_bytes.decode('ascii', errors='ignore')
    
    print(f"  明文: {plaintext}")
    
    # 步骤5：验证
    print("\n[步骤5] 验证结果")
    m_int = int.from_bytes(plaintext.encode('utf-8'), 'big')
    c_verify = pow(m_int, e, N)
    
    if c == c_verify:
        print("  ✓ 验证通过")
    else:
        print("  ✗ 验证失败")
    
    print("\n" + "="*70)
    print(f"Flag: {plaintext}")
    print("="*70)
    
    return plaintext

# 题目数据（示例，实际题目中N、e、c是完整给出的）
N = 98579...  # 替换为题目中的实际N值
e = 65537
c = 12345...  # 替换为题目中的实际c值

# 解题
if __name__ == "__main__":
    flag = solve_rsa(N, e, c)
    print(f"\n最终答案: {flag}")

六、知识点总结

6.1 RSA算法核心公式

操作	公式	说明
密钥生成	N = p × q	两个大素数乘积
	φ(N) = (p-1)(q-1)	欧拉函数
	d = e^(-1) mod φ(N)	私钥计算
加密	c = m^e mod N	用公钥加密
解密	m = c^d mod N	用私钥解密

6.2 破解RSA的关键

破解RSA = 分解N = 找出p和q
        ↓
有了p和q → 计算φ(N) → 计算私钥d → 解密密文

6.3 N的长度与安全性

N的长度	分解难度	安全性	说明
256位	容易	❌ 不安全	个人电脑秒级分解
512位	较易	❌ 不安全	云服务器分钟级分解
1024位	困难	⚠️ 不推荐	专业团队数月分解
2048位	很难	✅ 安全	当前技术不可行
4096位	极难	✅✅ 非常安全	未来几十年安全

6.4 分解N的常用方法

试除法：适合小N（<100位）
Pollard rho：适合中等N（100-200位）
二次筛法（QS）：适合中大N（200-300位）
数域筛法（NFS）：适合大N（300位以上）
在线工具：factordb.com（自动选择最优方法）

七、思考与拓展

7.1 为什么这个题能快速分解？

因为N只有256位（77位十进制），对于现代计算机：

个人笔记本：几秒钟
云服务器：毫秒级
在线工具：瞬间

7.2 如果N是2048位怎么办？

如果N是2048位，直接分解不可行。需要找其他弱点：

可能的攻击方法：

小公钥e攻击（e=3）
共模攻击（多组密文使用相同N）
费马分解（p和q接近）
Wiener攻击（d很小）
Pollard p-1攻击（p-1或q-1有小因子）

7.3 相关题目推荐

如果你觉得这道题太简单，可以挑战：

RSA with Small Exponent（CryptoHack）
- 难度：⭐⭐⭐
- 考点：小公钥指数攻击
Common RSA（CryptoHack）
- 难度：⭐⭐⭐⭐
- 考点：共模攻击
Mini RSA（PicoCTF）
- 难度：⭐⭐⭐
- 考点：小模数分解

八、常见问题解答

Q1：为什么使用65537作为公钥e？

A：65537 = 2^16 + 1，是一个费马素数。优点：

不太小（避免小指数攻击）
不太大（加密效率高）
二进制只有两个1（计算快）

Q2：φ(N)是什么？

A：φ(N)是欧拉函数，表示小于N且与N互质的正整数个数。对于N = p × q：

φ(N) = φ(p × q) = (p-1)(q-1)

Q3：为什么pow(c, d, N)这么快？

A：Python的pow()函数使用了快速幂算法（平方-乘算法），时间复杂度O(log d)。

# 普通幂运算（慢）
result = c ** d % N  # O(d)

# 快速幂运算（快）
result = pow(c, d, N)  # O(log d)

Q4：factordb.com是什么原理？

A：factordb.com维护了一个大整数分解数据库：

已知的分解结果会被缓存
新的分解请求会使用最优算法
对于小整数，瞬间返回结果

九、参考资料

RSA算法原理
- Wikipedia: https://zh.wikipedia.org/wiki/RSA加密算法
- RFC 8017: RFC 8017 - PKCS #1: RSA Cryptography Specifications Version 2.2
在线分解工具
- FactorDB: factordb.com
- Alpertron: Integer factorization calculator
CTF平台
- CryptoHack: CryptoHack – A free, fun platform for learning cryptography
- PicoCTF: picoCTF.org is now CyLab Security Academy
Python密码学库
- Cryptography: Welcome to pyca/cryptography — Cryptography 50.0.0-dev1 documentation
- PyCryptodome: Welcome to PyCryptodome’s documentation — PyCryptodome 3.23.0 documentation

十、总结

这道题虽然简单，但它展示了RSA破解的核心原理：

✓ 小N → 可分解 → 私钥可恢复 → 密文可解密

关键知识点：

RSA的安全性依赖于大数分解的困难性
小模数N是不安全的，可以被快速分解
分解N是破解RSA的最直接方法
使用足够长度的密钥（2048位以上）

openEuler 社区

openEuler 是由开放原子开源基金会孵化的全场景开源操作系统项目，面向数字基础设施四大核心场景（服务器、云计算、边缘计算、嵌入式），全面支持 ARM、x86、RISC-V、loongArch、PowerPC、SW-64 等多样性计算架构

更多推荐

2026网络安全转行指南：零基础从入门到精通，一篇吃透

openEuler 社区

Linux操作系统-逻辑卷管理LVM

openEuler 社区

【共创季稿事节】HarmonyOS 7.0 性能引擎与方舟编译器Next深度前瞻

openEuler 社区

所有评论(0)

查看更多评论

manyuemei0203

@manyuemei0203

已为社区贡献1条内容

【CTF Writeup】Baby RSA - RSA基础破解

manyuemei0203

一、题目信息

二、题目描述

原题

翻译

题目附件

三、题目分析

3.1 RSA算法回顾

3.2 破解思路

3.3 观察题目N的长度

3.4 分解方法选择

四、解题过程

步骤1：分析题目数据

步骤2：分解N

方法一：使用sympy库（推荐）

方法二：在线分解

步骤3：计算私钥d

步骤4：解密密文

步骤5：验证结果

五、完整解题代码

六、知识点总结

6.1 RSA算法核心公式

6.2 破解RSA的关键

6.3 N的长度与安全性

6.4 分解N的常用方法

七、思考与拓展

7.1 为什么这个题能快速分解？

7.2 如果N是2048位怎么办？

7.3 相关题目推荐

八、常见问题解答

Q1：为什么使用65537作为公钥e？

Q2：φ(N)是什么？

Q3：为什么pow(c, d, N)这么快？

Q4：factordb.com是什么原理？

九、参考资料

十、总结

所有评论(0)

温馨提示：您尚未绑定手机号

manyuemei0203