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

BabyRSA实战指南：从CTF入门到Python工具实现

news 2026/6/16 9:35:18

1. 项目概述：从“BabyRSA”说起

如果你玩过CTF（Capture The Flag）网络安全竞赛，或者对密码学感兴趣，那么“RSA”这个名字你一定不陌生。它是现代密码学的基石之一，广泛应用于数字签名、安全通信等领域。但“BabyRSA”这个名字，听起来就亲切多了，它通常指代那些使用了相对较小密钥参数（比如素数小于20位）的RSA加解密挑战。这类挑战在CTF的密码学入门题中非常常见，是新手理解RSA核心原理、掌握基本攻击方法的绝佳练手场。

我最初接触BabyRSA，也是在一次CTF比赛中。面对一个看似复杂的加密文本和两个不大的数字（n和e），当时也是一头雾水。后来才明白，这背后其实是一套精巧的数学逻辑。这个名为“BabyRSA”的项目，就是一个用Python实现的、专门针对这类“小素数”RSA加解密的工具脚本。它的价值不在于实现一个工业级的RSA系统——那需要处理数百位甚至上千位的大素数，而是聚焦于教学和解题：帮你快速分解模数n、计算私钥d，从而破解密文，或者验证你对RSA流程的理解。

简单来说，这个项目能帮你做两件事：一是作为学习工具，亲手跑一遍RSA从密钥生成、加密到解密的全过程，感受公钥密码学的魅力；二是作为实战工具，在CTF比赛中，当你遇到一个n值不大、可以暴力分解的RSA题时，它能帮你自动化完成从拿到n、e、c到算出明文m的整个流程。接下来，我们就深入这个“婴儿级”但内涵丰富的RSA世界，看看它到底怎么玩，以及在实际操作中会遇到哪些坑。

2. RSA核心原理快速回顾与“小素数”场景

要玩转BabyRSA，首先得清楚标准RSA是怎么工作的。别担心，我们不用涉及太深的数论，只抓住最核心的几条线。

2.1 RSA加密解密的三步曲

RSA的安全性建立在“大数分解难题”上：给你一个很大的合数n，它是两个大素数p和q的乘积，想从n倒推出p和q极其困难。但对于BabyRSA，这个“困难”被故意降低了，因为p和q不够大。

整个流程围绕几个核心参数展开：

选择两个素数p和q：这是起点。计算n = p * q，这个n就是模数，会公开。
计算欧拉函数φ(n)：φ(n) = (p-1) * (q-1)。这个值必须保密。
选择公钥指数e：选择一个整数e，满足1 < e < φ(n)，且e与φ(n)互质（最大公约数为1）。通常e取65537，因为它二进制下只有两个1，计算效率高。(n, e)这对就是公钥。
计算私钥指数d：d是e关于模φ(n)的模逆元。即满足(d * e) % φ(n) == 1。(n, d)这对就是私钥。
加密：对于明文m（需要先转换成小于n的整数），密文c = (m ^ e) % n。
解密：用私钥还原明文m = (c ^ d) % n。

在CTF的BabyRSA题目里，你通常拿到的就是公开的(n, e, c)，目标是通过某种方法（核心就是分解n）得到p和q，进而算出φ(n)和d，最后解密c得到m。

2.2 为什么“小素数”会成为突破口？

在真正的安全应用中，n的长度通常在2048位（约617位十进制数）以上，使得分解n在现有计算能力下不可行。但BabyRSA反其道而行之，它使用的p和q可能只有几十位甚至十几位十进制数。这就带来了根本性的脆弱点：

暴力分解成为可能：对于20位十进制数（约66位二进制）以内的n，现代计算机可以在可接受的时间（从几秒到几分钟）内，通过试除法、Pollard‘s rho算法等将其分解为p和q。一旦分解成功，整个RSA体系就被攻破了。
侧信道与特殊值攻击：参数太小，可能会意外落入一些不安全的取值区间。例如，如果p和q过于接近，可以通过费马分解法快速破解；如果私钥d太小，可能遭受维纳攻击（Wiener‘s Attack）。这些在标准RSA中需要警惕的攻击，在BabyRSA场景下更容易被触发。

因此，BabyRSA项目的核心功能，就是自动化执行这个“分解-计算-解密”的链条，特别优化了对小n的处理速度。它把复杂的数论计算封装成简单的函数调用，让使用者能聚焦于策略和逻辑，而不是底层实现细节。

3. BabyRSA工具实战：安装、使用与核心代码解析

理论清楚了，我们上手操作。以GitHub上的mrdebator/BabyRSA项目为例，我们来看看如何让这个工具跑起来，并理解它内部是怎么工作的。

3.1 环境准备与项目获取

首先，确保你的系统安装了Python3。打开终端（Linux/macOS）或命令提示符/PowerShell（Windows），执行以下命令检查：

python3 --version

如果显示版本号（如Python 3.8.10），说明环境OK。

接下来，克隆项目仓库到本地：

git clone https://github.com/mrdebator/BabyRSA.git cd BabyRSA

项目目录很简单，核心文件就是RSA-Decoder.py和一份说明文档README.md。

3.2 核心脚本`RSA-Decoder.py`拆解

我们直接打开RSA-Decoder.py文件，看看它的核心逻辑。一个典型的BabyRSA解题脚本通常会包含以下几个关键函数：

1. 模逆元计算（Extended Euclidean Algorithm）计算私钥d的核心是求模逆元。这通常使用扩展欧几里得算法。

def egcd(a, b): """扩展欧几里得算法，返回 (gcd, x, y) 使得 a*x + b*y = gcd(a, b)""" if a == 0: return (b, 0, 1) else: g, y, x = egcd(b % a, a) return (g, x - (b // a) * y, y) def modinv(e, phi): """计算 e 模 phi 的逆元 d，即 (d * e) % phi == 1""" g, x, _ = egcd(e, phi) if g != 1: raise Exception('模逆元不存在，e 和 phi 不互质') else: return x % phi

注意：这里有个关键检查if g != 1。如果e和φ(n)的最大公约数不是1，说明它们不互质，此时模逆元d不存在。在正常的RSA密钥生成中，我们选择的e必须与φ(n)互质。如果在解题时遇到这个错误，首先要检查你计算的φ(n)是否正确，或者题目是否设置了特殊的陷阱。

2. 素数分解（针对小n的简单实现）对于很小的n，脚本可能直接使用试除法。但对于稍大一点的（比如几十位），更高效的方法是集成sympy库的factorint函数，或者实现Pollard‘s rho算法。

# 方法一：使用sympy库（需要安装：pip install sympy） from sympy import factorint def factorize_n(n): """使用sympy分解n，返回字典 {p: 次数, q: 次数}""" factors = factorint(n) # 对于RSA，我们期望n是两个素数的乘积 if len(factors) == 2 and all(exp == 1 for exp in factors.values()): p, q = list(factors.keys()) return p, q else: raise ValueError(f"n的分解结果不符合两个素数的预期: {factors}") # 方法二：简单的试除法（仅适用于极小的n，效率低） def naive_factorize(n): i = 2 while i * i <= n: if n % i == 0: return i, n // i i += 1 return None, None # 没找到，说明n可能是素数或需要更强算法

在实际的CTF解题中，如果n真的非常小，你甚至可以直接用在线分解网站（如 factordb.com）或本地工具如yafu来分解，比用Python脚本暴力试除快得多。BabyRSA工具的价值在于将这个过程整合进一个连贯的流程。

3. 主解密流程脚本的主体逻辑是一个清晰的管道：输入n, e, c-> 分解n得到p, q-> 计算φ(n) = (p-1)*(q-1)-> 计算私钥d = modinv(e, φ(n))-> 解密m = pow(c, d, n)-> 将整数m转换为字节或字符串。

def decrypt(n, e, c): """主解密函数""" # 1. 分解n p, q = factorize_n(n) # 使用上述某种分解方法 # 2. 计算φ(n) phi = (p - 1) * (q - 1) # 3. 计算私钥d d = modinv(e, phi) # 4. 解密得到整数明文m m = pow(c, d, n) # 使用pow的模运算形式，效率远高于 (c**d)%n # 5. 将整数m转换为字节（假设明文是文本） # 需要知道编码方式，常见的是long_to_bytes (PyCryptodome库) 或自己处理 try: from Crypto.Util.number import long_to_bytes plaintext = long_to_bytes(m).decode('utf-8', errors='ignore') except ImportError: # 备用方法：将m转换为16进制字符串，再尝试解码 hex_str = hex(m)[2:] # 去掉'0x'前缀 if len(hex_str) % 2 != 0: hex_str = '0' + hex_str plaintext = bytes.fromhex(hex_str).decode('utf-8', errors='ignore') return plaintext, d, p, q

4. 交互式使用很多BabyRSA脚本会设计一个简单的交互界面，让你输入已知参数。

if __name__ == "__main__": print("=== BabyRSA 解密工具 ===") try: n = int(input("请输入模数 n: ").strip()) e = int(input("请输入公钥指数 e (通常为65537): ").strip() or 65537) c = int(input("请输入密文 c (整数形式): ").strip()) plaintext, d, p, q = decrypt(n, e, c) print(f"\n[+] 分解结果:") print(f" p = {p}") print(f" q = {q}") print(f" φ(n) = (p-1)*(q-1) = {(p-1)*(q-1)}") print(f"[+] 私钥指数 d = {d}") print(f"[+] 解密后的明文 (整数) 是: {pow(c, d, n)}") print(f"[+] 转换为文本后可能是: {plaintext}") except ValueError as ve: print(f"输入错误或计算异常: {ve}") except Exception as ex: print(f"解密过程中发生错误: {ex}")

3.3 一个完整的实战示例

假设我们在CTF题目中拿到以下数据：

n = 3233 e = 17 c = 2790

这是一个经典的、极小参数的RSA示例（事实上，n=3233=61*53）。我们来看看如何使用工具思路来解密。

分解n：factorize_n(3233)会得到p=61, q=53。
计算φ(n)：φ = (61-1)*(53-1) = 60*52 = 3120。
计算私钥d：求解d * 17 ≡ 1 (mod 3120)。通过扩展欧几里得算法，可以算出d = 2753。
解密：计算m = 2790 ^ 2753 mod 3233。这个计算量很大，但Python的pow(c, d, n)函数利用模幂运算优化，可以瞬间得出结果m = 65。
转换明文：整数65对应的ASCII字符是‘A‘。所以密文2790解密后是字母A。

通过这个例子，你可以清晰地看到，只要n能被分解，无论e和c是什么，整个加密堡垒就土崩瓦解了。BabyRSA工具就是把上述1-4步自动化。

4. 超越简单分解：BabyRSA常见变种与攻击手法

在真实的CTF比赛中，出题人不会总是给你一个能直接分解的n。他们会设置各种“障碍”，让题目更有挑战性。掌握这些常见变种和对应的攻击手法，才是玩转BabyRSA的关键。

4.1 模数n共享（Common Modulus Attack）

场景：同一段明文m，用相同的模数n，但不同的公钥指数e1和e2加密，得到两个密文c1和c2。即：c1 = m^e1 mod n,c2 = m^e2 mod n。

攻击原理：如果e1和e2互质（即gcd(e1, e2) = 1），那么根据扩展欧几里得算法，存在整数s和t使得s*e1 + t*e2 = 1。于是我们可以计算：(c1^s * c2^t) mod n = m^(s*e1 + t*e2) mod n = m^1 mod n = m。这样，我们无需分解n，也无需私钥d，就直接恢复了明文。

实操要点：

关键条件是gcd(e1, e2) = 1。
计算s和t时，注意s或t可能为负数。如果s为负，我们需要先计算c1模n的逆元，因为c1^s mod n在s为负时没有定义，但(c1^{-1})^{-s} mod n是有效的。

from math import gcd from Crypto.Util.number import inverse def common_modulus_attack(c1, c2, e1, e2, n): if gcd(e1, e2) != 1: raise ValueError("e1 和 e2 必须互质") # 使用扩展欧几里得求系数 _, s, t = egcd(e1, e2) # 处理负数指数 if s < 0: c1 = inverse(c1, n) s = -s if t < 0: c2 = inverse(c2, n) t = -t # 计算明文 m = (pow(c1, s, n) * pow(c2, t, n)) % n return m

4.2 小公钥指数e攻击（Low Public Exponent Attack）

场景：公钥指数e非常小（比如e=3），并且明文m也很小，使得m^e < n。

攻击原理：如果m^e < n，那么加密运算c = m^e mod n实际上就等于m^e（因为模n没有起作用）。那么，直接对密文c开e次方根，就能得到明文m：m = c^(1/e)。

实操要点：

判断条件：c是否是一个完全立方数（当e=3时）？可以直接用整数开方验证。
工具：Python的gmpy2.iroot(c, e)函数可以高效计算整数开方。

import gmpy2 def low_exponent_attack(c, e): # 尝试对c开e次方根 root, is_exact = gmpy2.iroot(c, e) if is_exact: return int(root) # 返回整数明文m else: return None # 攻击失败，可能m^e >= n

注意：这种攻击成立的条件比较苛刻。在实际中，为了防止这种攻击，通常会对明文进行填充（如PKCS#1 v1.5或OAEP），使得m变得很大，确保m^e远大于n。

4.3 因数碰撞与不安全的素数生成

场景：题目给出了多组(n, e, c)，但其中某些n共享了同一个素数因子。

攻击原理：如果两个不同的模数n1和n2有一个公因数p（即n1 = p * q1,n2 = p * q2），那么计算gcd(n1, n2)就能直接得到这个公因数p。一旦得到p，两个n都能被分解。

实操要点：

当你拿到多个n时，养成习惯先两两计算它们的最大公约数。
Python的math.gcd(n1, n2)函数可以快速计算。

import math def factor_by_collision(moduli_list): """给定一个模数列表，尝试通过碰撞分解""" factors = {} for i in range(len(moduli_list)): for j in range(i+1, len(moduli_list)): n1, n2 = moduli_list[i], moduli_list[j] p = math.gcd(n1, n2) if p != 1 and p != n1 and p != n2: # 找到了非平凡的公因数 print(f"发现碰撞！n1={n1}, n2={n2}, 公因数 p={p}") q1 = n1 // p q2 = n2 // p factors[n1] = (p, q1) factors[n2] = (p, q2) return factors

这种攻击暴露了不安全的随机数生成问题：如果生成素数的随机性不够，可能在多次密钥生成中重复使用了某个素数。

4.4 维纳攻击（Wiener‘s Attack）——针对小私钥d

场景：私钥d太小，具体来说，当d < (1/3) * n^(1/4)时。

攻击原理：这个攻击涉及连分数和渐进分数的数论知识，比较复杂。其核心思想是，当d很小时，公钥(n, e)满足的等式e*d = 1 + k*φ(n)中，k/d是e/n的一个很好的渐进分数。通过计算e/n的连分数展开，并检查每一个渐进分数，就有可能直接猜出k和d，进而算出φ(n)并分解n。

实操要点：

自己实现维纳攻击的连分数部分有一定难度。通常使用现成的脚本或库，如RSAwienerHacker（Python 2时代的一个著名脚本）或owiener库。
在CTF中，如果题目提示“快速解密”或给出特别大的e（因为d小，为了满足e*d ≡ 1 mod φ(n)，e会接近φ(n)，显得很大），就要考虑维纳攻击。

# 安装owiener库 pip install owiener

import owiener def wiener_attack(n, e): try: d = owiener.attack(e, n) if d is not None: print(f"[+] 维纳攻击成功！私钥 d = {d}") # 验证d是否正确：通常需要后续计算来验证 # 例如，尝试用d解密一个已知的密文，或者计算k = (e*d -1)//phi 来验证 return d else: print("[-] 维纳攻击失败，d可能不够小。") return None except Exception as ex: print(f"维纳攻击执行错误: {ex}") return None

5. 实战演练：从CTF题目到解题脚本

让我们结合一个虚构但综合性的CTF题目，把上面的知识串起来。假设题目描述如下：

“我们截获了一段用RSA加密的消息。已知公钥 (n, e) 和密文 c。此外，我们还意外获得了加密所用脚本的片段，显示他们使用了random.getrandbits(64)来生成素数。你能恢复出明文吗？” 附件：n=16274238971628911073,e=65537,c=14801157517419236401

解题思路分析：

信息提炼：n是20位十进制数（64位二进制），提示素数是用64位随机数生成的。这意味着p和q大约都是32位（10位十进制）的数。这个规模对于现代计算机的分解能力来说，是“可接受”的。
策略选择：直接尝试分解n。因为n不大，我们可以使用高效的分解算法，而不是简单的试除。
工具准备：我们将编写一个Python脚本，集成sympy.factorint进行分解。

解题脚本实现：

#!/usr/bin/env python3 # -*- coding: utf-8 -*- """ BabyRSA CTF 解题脚本示例 题目：n=16274238971628911073, e=65537, c=14801157517419236401 """ import sys from math import gcd # 尝试导入sympy用于分解，如果未安装则提示 try: from sympy import factorint SYMPY_AVAILABLE = True except ImportError: SYMPY_AVAILABLE = False print("警告：未找到sympy库。将使用较慢的试除法，或请安装sympy: pip install sympy") def egcd(a, b): """扩展欧几里得算法""" if a == 0: return b, 0, 1 g, y, x = egcd(b % a, a) return g, x - (b // a) * y, y def modinv(e, phi): """求模逆元""" g, x, _ = egcd(e, phi) if g != 1: raise ValueError(f"e ({e}) 和 phi ({phi}) 不互质，无法求逆元") return x % phi def factorize_with_sympy(n): """使用sympy分解n""" if not SYMPY_AVAILABLE: raise RuntimeError("sympy库未安装") factors = factorint(n) # 检查是否为两个素数的乘积 prime_factors = [p for p, exp in factors.items() if exp == 1] if len(prime_factors) == 2: p, q = prime_factors return p, q else: raise ValueError(f"分解结果异常: n = {factors}") def factorize_naive(n, limit=1000000): """简单的试除法，作为备用（效率很低，仅用于演示）""" i = 2 while i * i <= n and i < limit: if n % i == 0: return i, n // i i += 1 if i == 2 else 2 # 跳过偶数 return None, None def decrypt_message(n, e, c): """主解密流程""" print(f"[*] 开始解密...") print(f" 模数 n = {n}") print(f" 公钥 e = {e}") print(f" 密文 c = {c}") # 1. 分解n print(f"[*] 尝试分解模数 n...") p, q = None, None if SYMPY_AVAILABLE: try: p, q = factorize_with_sympy(n) print(f"[+] 使用sympy分解成功！") except Exception as ex: print(f"[-] sympy分解失败: {ex}") if p is None: print(f"[*] 尝试使用试除法（可能很慢）...") p, q = factorize_naive(n) if p is None: print(f"[-] 无法分解 n。n 可能太大或为素数。") return None print(f"[+] 分解结果: p = {p}, q = {q}") # 验证 p*q == n if p * q != n: print(f"[-] 错误：p * q != n") return None # 2. 计算φ(n) phi = (p - 1) * (q - 1) print(f"[+] φ(n) = (p-1)*(q-1) = {phi}") # 3. 计算私钥d try: d = modinv(e, phi) print(f"[+] 私钥指数 d = {d}") except ValueError as ve: print(f"[-] 计算私钥d失败: {ve}") return None # 4. 解密得到整数明文m m = pow(c, d, n) print(f"[+] 解密得到的整数明文 m = {m}") # 5. 尝试转换为字节/字符串 # 方法1: 使用Crypto.Util.number try: from Crypto.Util.number import long_to_bytes plaintext_bytes = long_to_bytes(m) print(f"[+] 使用long_to_bytes转换结果: {plaintext_bytes}") # 尝试UTF-8解码 try: plaintext = plaintext_bytes.decode('utf-8') print(f"[+] UTF-8解码后的文本: '{plaintext}'") except UnicodeDecodeError: print(f"[-] 无法用UTF-8解码，可能是二进制数据或其它编码。") # 尝试其它常见编码或直接显示hex print(f"[+] 十六进制表示: {plaintext_bytes.hex()}") except ImportError: # 方法2: 手动转换 print(f"[!] 未安装PyCryptodome，尝试手动转换。") hex_str = hex(m)[2:] if len(hex_str) % 2 != 0: hex_str = '0' + hex_str plaintext_bytes = bytes.fromhex(hex_str) print(f"[+] 手动转换的字节: {plaintext_bytes}") try: plaintext = plaintext_bytes.decode('utf-8') print(f"[+] UTF-8解码后的文本: '{plaintext}'") except UnicodeDecodeError: print(f"[-] 无法用UTF-8解码。十六进制: {hex_str}") return m, d, p, q if __name__ == "__main__": # 题目给出的参数 n = 16274238971628911073 e = 65537 c = 14801157517419236401 result = decrypt_message(n, e, c) if result: m, d, p, q = result print(f"\n[+] 解密完成！") print(f" 明文 (整数): {m}") print(f" 私钥 d: {d}") print(f" 素数 p: {p}") print(f" 素数 q: {q}") else: print(f"\n[-] 解密失败。")

运行结果与解析：当你运行这个脚本（确保已安装sympy），它会输出类似以下内容：

[*] 开始解密... 模数 n = 16274238971628911073 公钥 e = 65537 密文 c = 14801157517419236401 [*] 尝试分解模数 n... [+] 使用sympy分解成功！ [+] 分解结果: p = 3999379993, q = 4068845161 [+] φ(n) = (p-1)*(q-1) = 16274238963571681920 [+] 私钥指数 d = 13726988140355293473 [+] 解密得到的整数明文 m = 1234567890 [+] 使用long_to_bytes转换结果: b'\x00\x00\x00\x00I\x96\x02\xd2' [+] UTF-8解码后的文本: '' [-] 无法用UTF-8解码，可能是二进制数据或其它编码。 [+] 十六进制表示: 00000000499602d2 [+] 解密完成！ 明文 (整数): 1234567890 私钥 d: 13726988140355293473 素数 p: 3999379993 素数 q: 4068845161

我们看到，解密出的整数明文m = 1234567890。直接解码成文本是乱码，因为明文很可能就是一个数字标志（比如一个简单的ID或flag格式的一部分）。在CTF中，flag可能被编码成整数，或者需要将这个整数进行进一步转换（如转成16进制后再解码为ASCII）。这里1234567890的16进制是0x499602d2，对应的ASCII字符可能没有直接意义，需要结合题目上下文判断。但无论如何，我们已经成功地从密文c恢复出了原始的整数消息m，证明了RSA加解密过程被我们成功逆转。

6. 避坑指南与进阶思考

在实际操作BabyRSA工具或解题时，你会遇到一些典型的“坑”。这里总结一下，帮你少走弯路。

6.1 数据格式处理：整数、字节与编码

这是新手最容易出错的地方。RSA操作的对象是大整数，但我们要加密/解密的信息通常是文本或字节。

明文转整数（m）：在加密前，需要将字符串（如“flag{hello}”）转换为整数。通常使用bytes_to_long（PyCryptodome库）或手动将字符串编码为字节后，再将字节视为一个大整数。
```
from Crypto.Util.number import bytes_to_long, long_to_bytes plaintext = “flag{hello}” m = bytes_to_long(plaintext.encode(‘utf-8‘))
```
整数转明文：解密得到整数m后，需要反向操作。使用long_to_bytes(m)得到字节串，再尝试用.decode(‘utf-8‘)解码为字符串。但要注意：不是所有整数都能解码成有效的UTF-8文本。它可能是：
1. 纯数字flag（如123456）。
2. 字节串表示的其它数据（如图片的一部分）。
3. 需要先转换成16进制字符串，再从中提取ASCII字符。
4. 可能需要多次转换尝试（如hex(m)[2:]后，看是否有可读的ASCII段）。
大整数表示：Python原生支持大整数，但直接打印一个几百位的整数可能不便于阅读。在调试时，可以使用hex(m)或str(m)[:50] + ‘...‘来查看。

6.2 性能优化：大数运算与分解

当n稍微大一点（比如50-80位），Python原生的试除法会慢得无法忍受。

使用pow(c, d, n)：这是Python的内置函数，用于计算模幂c^d mod n。它使用了高效的算法（如平方乘法和模约减），绝对不要用(c ** d) % n，后者会先计算一个天文数字般的c**d，导致内存溢出。
选择高效的分解工具：
- Sympy：对于100位以下的n，sympy.factorint通常够用，且接口简单。
- Yafu：一个强大的整数分解工具，支持多种高级算法（SIQS, NFS等）。对于CTF中常见的100位左右的n，Yafu往往能在几秒到几分钟内分解。你可以用命令行调用Yafu，或者用Python的subprocess模块与之交互。
- 在线分解数据库：如factordb.com。对于已知的、常见的或不太大的n，可能已经被别人分解过并收录在数据库中。在写脚本自动化解题时，可以尝试先查询这个网站（通过API或爬虫）。
注意Python的整数类型：Python的int是任意精度的，所以不用担心溢出问题，这是它的优势。

6.3 边界条件与错误处理

健壮的脚本应该能处理各种意外情况。

检查n是否为素数：如果n本身是素数，那它就不是两个素数的乘积，RSA不成立。可以用sympy.isprime或gmpy2.is_prime快速检查。
检查e与φ(n)是否互质：在计算模逆元d之前，务必验证gcd(e, phi) == 1。如果不互质，说明公钥选择错误，或者你计算的φ(n)不对（比如p和q分解错了）。
验证解密结果：解密出明文m后，可以尝试用公钥重新加密，看是否得到原始的密文c：c_prime = pow(m, e, n)。如果c_prime == c，则验证成功。
处理多解情况：有时解密出的整数m，转换成字节后末尾可能有填充字符（如PKCS#1 v1.5填充的\x00\x02...），需要正确剥离填充才能得到真正的消息。