当前位置：首页 > news >正文

新手也能懂的RSA解密实战：用Python和RSA Tool搞定BUUCTF那道rsarsa题

news 2026/5/5 19:36:47

新手也能懂的RSA解密实战：用Python和RSA Tool搞定BUUCTF那道rsarsa题

第一次接触CTF密码学题目时，看到满屏的数字和术语总让人望而生畏。但RSA作为最经典的公钥加密算法，其核心原理其实可以用几个简单的数学概念串联起来。本文将以BUUCTF平台那道经典的rsarsa题为案例，带你用两种方式完成解密：纯Python代码实现和RSA Tool可视化操作。即使你从未接触过密码学，也能在30分钟内理解RSA的运作机制并亲手拿到flag。

1. RSA到底在做什么？——从信封比喻说起

想象Alice要给Bob寄一封密信。传统加密就像两人共用一个钥匙开锁，而RSA则创造性地使用了两把钥匙：

公钥：相当于任何人都能用的锁，Bob把它挂在门口，Alice用它锁上信封
私钥：只有Bob拥有的钥匙，用于打开用公钥锁定的信封

在BUUCTF题目中，我们已知的参数对应关系如下：

参数	实际含义	题目给定值（示例）
p	大质数1	9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483
q	大质数2	11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407
e	公钥指数	65537
c	密文（加密结果）	83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034
n	模数（p×q）	需计算
d	私钥指数	需计算

关键数学原理：RSA的安全性建立在大数分解难题上。已知n=p×q，但从n反推p和q在计算上不可行（当n足够大时）。我们的解密任务就是利用已知的p、q、e计算出私钥d，再用d解密密文c。

2. 手算私钥d：理解欧拉函数与模反元素

计算私钥d的核心是找到e关于φ(n)的模反元素。分步拆解：

2.1 计算φ(n) —— 欧拉函数

φ(n)表示小于n且与n互质的正整数的个数。对于n=p×q（p、q为质数）：

phi = (p - 1) * (q - 1) # 欧拉函数计算公式

2.2 求解模反元素d

d是满足以下条件的整数：

(e * d) % phi == 1

这可以通过扩展欧几里得算法实现。Python代码示例：

def extended_gcd(a, b): if b == 0: return a, 1, 0 else: gcd, x, y = extended_gcd(b, a % b) return gcd, y, x - (a // b) * y # 计算d gcd, d, _ = extended_gcd(e, phi) if gcd != 1: raise ValueError("e和φ(n)不互质") d = d % phi # 确保d为正数

注意：实际解题时可直接用Python内置的pow(e, -1, phi)求模反元素

3. 两种实战解密方法

3.1 纯Python实现（推荐学习用）

完整解密代码及逐行解析：

# 给定参数 p = 9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483 q = 11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407 e = 65537 c = 83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034 # 计算模数n和欧拉函数φ(n) n = p * q phi = (p - 1) * (q - 1) # 计算私钥d（方法1：使用pow内置函数） d = pow(e, -1, phi) # 解密得到明文m m = pow(c, d, n) # 输出十进制明文（需转换为ASCII） print("十进制明文:", m) print("十六进制:", hex(m)[2:]) # [2:]去除0x前缀 print("ASCII解码:", bytes.fromhex(hex(m)[2:]).decode())

3.2 RSA Tool可视化操作（适合快速验证）

下载工具：获取RSA Tool（Windows/macOS/Linux通用）
基础配置：
- 设置Number Base为十进制（Decimal）
- 输入已知的p、q值到对应字段
关键操作：
- 点击Calc. D按钮自动计算私钥d
- 在Ciphertext字段填入密文c
- 点击Decrypt获取明文

工具界面字段对照图：

（图示：P/Q输入区、D计算结果区、解密操作按钮位置）

4. 常见问题与调试技巧

4.1 数字转换问题

现象：解密得到一长串数字而非可读文本
解决：CTF中flag通常需要将十进制数转为ASCII字符

# 转换示例（假设解密结果m=123456） hex_str = hex(m)[2:] # 去掉0x前缀 bytes_obj = bytes.fromhex(hex_str) print(bytes_obj.decode('utf-8'))

4.2 大数运算超时

优化方案：使用Python的pow三参数形式（模幂运算）

# 低效写法（可能超时） m = (c ** d) % n # 高效写法 m = pow(c, d, n) # Python内置优化算法

4.3 编码格式问题

不同题目可能采用不同的编码方式：

编码类型	特征	处理方法
纯十进制	直接输出数字	`print(m)`
ASCII编码	每位对应一个字符	`chr(m)`
HEX字符串	类似'666c6167'	`bytes.fromhex(hex_str)`
Base64	结尾常有=号	`base64.b64decode()`

5. 扩展理解：为什么RSA需要大质数？

通过一个简化例子感受质数大小对安全性的影响：

# 不安全的参数示例（仅用于演示） small_p, small_q = 17, 23 small_n = small_p * small_q # 391（很容易被暴力分解） # 对比题目中的n（实际值约1157位） real_n = p * q print(f"真实n的位数: {len(str(real_n))}") # 输出约1157位

现代RSA应用通常要求：

质数长度 ≥ 2048位
n的位数 ≥ 4096位
使用安全的随机数生成器（如secrets模块）

6. 举一反三：其他CTF中的RSA变种

掌握了基础RSA后，你可能会遇到这些变种题型：

已知n和e求d：需要先分解n得到p、q（可用factordb.com尝试）
多组密文攻击：相同明文用不同公钥加密（中国剩余定理）
小指数攻击：当e很小时（如e=3）可能直接开立方
选择密文攻击：通过特定构造获取解密结果

# 中国剩余定理示例（简化版） def crt(a_list, m_list): M = 1 for m in m_list: M *= m result = 0 for a, m in zip(a_list, m_list): Mi = M // m inv = pow(Mi, -1, m) result += a * Mi * inv return result % M