1. 项目概述从两道CTF密码学题看实战解题思维最近在带新人入门CTFCapture The Flag时发现很多朋友对密码学题目既感兴趣又有点发怵。理论公式看懂了但一到实战面对一个压缩包里的几个看似随机的数字和文本文件就不知道从何下手。这太正常了密码学实战和课本学习完全是两码事。今天我就以两道非常经典的题目——“Power Tower”和“easy_RSA”为例用Python手把手地带你走一遍完整的解题流程。我的目的不是让你死记硬背这几行代码而是希望通过这两个案例帮你建立起一套遇到密码学题目时的“条件反射”和解题框架。你会发现很多看似复杂的题目拆解后核心就是几个数学原理和编程技巧的组合。无论你是刚接触CTF的新手还是想巩固密码学实战经验的朋友这篇分享都能给你带来直接的帮助。“Power Tower”这道题名字听起来很唬人像是要处理一个巨大的指数塔但它本质上考察的是模运算下的欧拉定理应用关键在于如何高效计算 a^b^c^... mod n。而“easy_RSA”作为RSA入门题的常客名字就暗示了它的基础性但它完美涵盖了RSA加解密的全部核心步骤大素数生成、密钥计算、加密解密是理解非对称加密实战的绝佳起点。我们将使用Python因为它有丰富的数学库如gmpy2,pycryptodome语法简洁是CTF密码学解题的“瑞士军刀”。接下来我会先带你看清每道题的设计思路和考点然后一步步实现破解最后分享我踩过的坑和调试技巧。2. 解题环境与核心工具准备工欲善其事必先利其器。在开始写代码之前我们需要一个顺手的环境。我个人强烈推荐使用VSCode配合Python虚拟环境这能保证项目依赖的纯净性避免不同项目间库版本冲突的噩梦。首先确保你安装了Python3.8及以上版本。你可以从官网下载安装时务必勾选“Add Python to PATH”。安装后在终端输入python --version检查是否成功。接下来我们创建项目目录并设置虚拟环境mkdir ctf_crypto_lab cd ctf_crypto_lab python -m venv venv激活虚拟环境Windows:venv\Scripts\activateLinux/Mac:source venv/bin/activate激活后命令行提示符前会出现(venv)字样。然后安装我们本次实战的核心库pip install pycryptodome gmpy2这里解释一下为什么是这两个库pycryptodome这是PyCrypto库的维护分支功能强大且稳定。它提供了完整的RSA实现、AES、DES等对称加密算法以及各种编码解码工具。在CTF中我们经常需要用它来加载题目提供的RSA公钥文件.pem格式或进行标准的加密解密操作。gmpy2这是Python的一个C语言扩展库专门用于高精度计算。它的核心优势在于处理大整数几百位甚至上千位的运算速度极快并且内置了高效的模逆元计算、素数检测、下一个素数查找等功能。在RSA题目中动辄1024位、2048位的大素数运算用Python原生的int类型虽然也可以但效率会低很多gmpy2是必备的性能加速器。注意gmpy2的安装有时会因为缺少底层C库如MPIR或GMP而失败。如果遇到问题可以尝试访问其官网查看针对你操作系统的预编译轮子wheel或者使用pip install gmpy22.1.0b5指定一个较旧但可能更稳定的版本。对于纯粹的学习和解题如果gmpy2实在装不上临时用Python原生int和pow(a, b, n)函数也能完成大部分计算只是遇到超大数时可能会慢一些。除了库你还需要一个文本编辑器来写代码VSCode、PyCharm都可以及一个可以运行Python脚本的终端。环境准备好后我们就可以开始拆解第一道题目了。3. 题目一“Power Tower”的数学原理与降维打击我们先来看“Power Tower”。题目通常会给你一个类似这样的表达式a^(b^(c^(...))) mod n以及a, b, c, ...和n的具体数值。直接计算是不可能的因为指数塔的数值会大到超出宇宙原子总数。这道题的考点非常明确利用欧拉定理Euler‘s Theorem对指数进行降幂。欧拉定理告诉我们如果整数a与n互质即gcd(a, n) 1那么a^φ(n) ≡ 1 (mod n)。其中φ(n)是欧拉函数表示小于n且与n互质的正整数的个数。这个定理的强大之处在于它允许我们将一个巨大的指数对φ(n)取模从而大幅减小计算量。但对于“Power Tower”我们需要一个更通用的工具——扩展欧拉定理。它放松了互质的条件其核心思想是当指数b大于等于φ(n)时有a^b ≡ a^(b mod φ(n) φ(n)) (mod n)。注意这里的“大于等于”条件和额外的 φ(n)这是处理非互质情况的关键。我们的解题步骤因此变得清晰递归计算从指数塔的顶端开始逐层向下计算。应用扩展欧拉定理在每一层判断当前指数是否大于等于当前模数的欧拉函数值。如果是则对指数进行降幂处理。模数更新在递归下降的过程中模数会依次变为n,φ(n),φ(φ(n)), ...直到变为1因为φ(φ(...φ(n)...))会迅速减小到1。边界处理当模数变为1时任何数模1都为0这是递归的终止条件。光说理论有点抽象我们直接上代码。假设题目给出的指数塔是2^(3^(4^5)) mod 1000这里用一个小例子演示原理。import gmpy2 from gmpy2 import mpz def phi(n): 计算欧拉函数φ(n)的简单实现适用于n可分解的情况实战中n可能很大 result mpz(n) p mpz(2) # 试除法分解质因数对于大的n这里可能需要更高效的算法如pollard rho temp n while p * p temp: if temp % p 0: while temp % p 0: temp // p result - result // p p gmpy2.next_prime(p) if temp 1: result - result // temp return result def power_tower(tower, mod): 递归计算指数塔模 mod 的值 :param tower: 指数塔列表例如 [2, 3, 4, 5] 表示 2^(3^(4^5)) :param mod: 当前的模数 :return: 计算结果 if len(tower) 1: return tower[0] % mod if mod 1: return 0 # 任何数模1都为0 # 计算下一层的模数 phi_mod phi_mod phi(mod) # 递归计算指数部分计算 tower[1:] 在模 phi_mod 下的值并根据扩展欧拉定理判断是否加 phi_mod exp power_tower(tower[1:], phi_mod) # 应用扩展欧拉定理 if exp phi_mod: exp exp % phi_mod phi_mod # 计算 base^exp % mod base tower[0] return pow(base, exp, mod) # 示例计算 2^(3^(4^5)) mod 1000 tower [2, 3, 4, 5] n mpz(1000) result power_tower(tower, n) print(f计算结果: {result})这段代码中power_tower函数是核心。它采用递归tower[0]是底数tower[1:]是剩下的指数塔。在计算指数exp时它先递归调用自身但模数换成了φ(mod)。得到exp后判断其是否大于等于φ(mod)以决定是否应用扩展欧拉定理的“加φ(mod)”规则。最后用Python内置的pow(base, exp, mod)进行模幂运算这个函数是优化过的非常高效。实操心得在实际CTF题目中n可能是一个合数并且可能非常大。上面phi(n)函数的试除法分解对于大数效率很低。更常见的场景是题目会直接给你n的分解比如n p * q或者n本身就是一个素数此时φ(n) n-1。所以先仔细阅读题目描述和附件尝试分解n或者寻找n的特殊性质往往比写一个通用的质因数分解函数更重要。如果n真的又大又难以分解那这道题很可能考察的是其他知识点比如n是光滑数适用Pohlig-Hellman算法。4. 题目二“easy_RSA”的完整流程与参数解析接下来我们看“easy_RSA”。这道题是CTF密码学的“Hello World”但它涵盖了RSA的所有关键环节。通常题目会给你一个公钥文件pubkey.pem和一个加密后的文件flag.enc或者直接给你n, e, c模数、公钥指数、密文的数值。我们的任务就是解出明文m。RSA的原理这里快速回顾一下选择两个大素数p和q。计算n p * qφ(n) (p-1)*(q-1)。选择一个整数e作为公钥指数满足1 e φ(n)且gcd(e, φ(n)) 1。常见的有e 65537。计算私钥指数d满足e * d ≡ 1 (mod φ(n))即d是e模φ(n)的逆元。加密c ≡ m^e (mod n)。解密m ≡ c^d (mod n)。对于“easy”级别的题目破解的突破口往往在于私钥d的计算而这需要知道φ(n)进而需要知道p和q。所以解题的核心就变成了如何从已知的n和e恢复出p和q“easy_RSA”之所以简单通常是因为以下原因之一n很小可以直接用工具如yafu、factordb网站或简单的试除法分解。p和q很接近导致n的开平方根附近就是p和q可以用费马分解法。使用了不安全的素数比如p或q太小或者p-1是光滑数适用Pollard‘s p-1算法。共模攻击如果两次加密使用了相同的n但不同的e且e1和e2互质可能可以恢复明文。低加密指数攻击如果e很小比如3并且明文m也很小使得m^e n那么直接对c开e次方就能得到m。我们假设一个最常见的场景题目给了我们n,e,c并且n不大可以分解。我们用Python来实现完整的解密流程。from Crypto.Util.number import long_to_bytes, bytes_to_long import gmpy2 # 假设题目给出的参数 n mpz(3233) # 一个非常小的n仅用于示例 e mpz(17) c mpz(855) # 假设的密文 # 第一步分解n这里因为n很小我们直接给出分解实战中可能需要调用factorint p mpz(61) q mpz(53) # 验证 assert p * q n # 第二步计算φ(n)和私钥d phi_n (p - 1) * (q - 1) # 计算e模phi_n的逆元即私钥d d gmpy2.invert(e, phi_n) print(f私钥d: {d}) # 第三步解密 m pow(c, d, n) # m c^d mod n print(f解密得到的数字m: {m}) # 第四步将数字m转换为字节即flag try: flag long_to_bytes(m).decode(utf-8) print(fFlag: {flag}) except UnicodeDecodeError: # 如果解码失败可能m不是UTF-8文本直接输出16进制或字节形式 print(f解密结果字节: {long_to_bytes(m)}) print(f解密结果16进制: {hex(m)})这段代码清晰展示了RSA解密的四个步骤。其中最关键的一步是gmpy2.invert(e, phi_n)它使用扩展欧几里得算法高效地计算出了模逆元d。注意事项在实际CTF题目中n、c等数字往往非常长是一串几百位的十进制或十六进制数。你需要将它们正确转换为mpz大整数。从文件读取时要注意字符串的格式是否有0x前缀是否是Base64编码等。一个常见的技巧是使用Python的int(hex_string, 16)或mpz(hex_string, 16)来转换十六进制字符串。5. 实战进阶当“easy_RSA”不简单时上面我们演示了最理想的、n可分解的情况。但“easy”有时只是个名字题目可能会设置一些小障碍。下面分享几种变种及其破解方法。5.1 已知n、e、d求p和q有时题目会给你n,e,d让你求p和q来解密。这需要一点数学推导。我们知道e*d ≡ 1 (mod φ(n))即存在整数k使得e*d - 1 k * φ(n)。由于φ(n) (p-1)(q-1) n - (pq) 1所以pq n - φ(n) 1。又知道n p*q联立方程即可解出p和q。更实用的方法是利用gmpy2import gmpy2 from Crypto.Util.number import getPrime, inverse # 模拟生成一组参数 bits 512 p getPrime(bits) q getPrime(bits) n p * q phi_n (p-1)*(q-1) e 65537 d inverse(e, phi_n) # 已知 n, e, d 求 p, q k e * d - 1 # 寻找一个 g使得 g^(k/2^t) 模 n 不为 1 或 -1 g 2 t 0 temp k while temp % 2 0: temp // 2 t 1 for i in range(1, t1): x pow(g, k // (2**i), n) if x ! 1 and x ! n-1: p_candidate gmpy2.gcd(x-1, n) if p_candidate ! 1 and p_candidate ! n: q_candidate n // p_candidate print(f找到分解: p {p_candidate}, q {q_candidate}) break这段代码利用了k e*d -1是φ(n)的倍数这一性质通过随机选取g并计算g^(k/2^i)有很大概率能找到n的一个非平凡因子。5.2 低加密指数攻击e3如果公钥指数e非常小比如3并且明文m也较小满足m^e n那么加密过程c m^e mod n实际上就等于m^e因为没超过模数。此时直接对密文c开e次方即可得到明文。import gmpy2 def low_e_attack(c, e): 低加密指数攻击当 m^e n 时有效 # 尝试开e次方根 m, exact gmpy2.iroot(c, e) if exact: return m else: return None # 示例 c mpz(27) # 假设密文是27 e 3 m low_e_attack(c, e) if m is not None: print(f低加密指数攻击成功明文m: {m})5.3 共模攻击如果同一份明文m用相同的n但不同的e1和e2加密得到c1和c2且gcd(e1, e2)1那么可以利用扩展欧几里得算法找到整数s1和s2使得e1*s1 e2*s2 1。那么m (c1^s1 * c2^s2) mod n。import gmpy2 from Crypto.Util.number import long_to_bytes def common_modulus_attack(c1, c2, e1, e2, n): 共模攻击 # 使用扩展欧几里得算法求 s1, s2 gcd, s1, s2 gmpy2.gcdext(e1, e2) assert gcd 1 # 确保e1和e2互质 # 计算明文 if s1 0: c1 gmpy2.invert(c1, n) s1 -s1 if s2 0: c2 gmpy2.invert(c2, n) s2 -s2 m (pow(c1, s1, n) * pow(c2, s2, n)) % n return m # 示例参数 n mpz(3233) e1, e2 mpz(17), mpz(19) m_original mpz(123) # 原始明文 c1 pow(m_original, e1, n) c2 pow(m_original, e2, n) m_recovered common_modulus_attack(c1, c2, e1, e2, n) print(f共模攻击恢复的明文: {m_recovered}) assert m_recovered m_original6. 常见问题、调试技巧与避坑指南在实战中代码写出来只是第一步能跑通并得到正确结果才是关键。下面是我在解这类题目时积累的一些常见问题排查经验和技巧。6.1 数据格式处理错误这是新手最容易栽跟头的地方。题目给的数字可能是十进制、十六进制带或不带0x、Base64编码、或者直接写在文件里。十六进制转整数int(hex_str, 16)或mpz(hex_str, 16)。如果字符串有0x前缀这两个函数都能处理。Base64解码使用base64.b64decode()得到字节串再用bytes_to_long()转为整数。从PEM文件读取公钥使用Crypto.PublicKey.RSA.import_key(open(‘pubkey.pem’).read())然后通过key.n和key.e获取参数。多行数据注意换行符。读取文件后使用.strip()去除首尾空白字符。一个健壮的参数读取函数可能是这样的def load_numbers_from_file(filename): with open(filename, r) as f: data f.read().strip() # 尝试判断格式 if data.startswith(0x): return mpz(data, 16) elif all(c in 0123456789abcdefABCDEF for c in data if c not in \n): # 可能是无前缀的16进制 return mpz(data, 16) else: # 尝试作为十进制整数 try: return mpz(data) except: # 可能是Base64 import base64 decoded_bytes base64.b64decode(data) return bytes_to_long(decoded_bytes)6.2 解密结果乱码或不是flag解密得到一个大整数m转成字节后是一堆乱码这通常有几个原因解密错误p和q找错了或者d计算错了。重新检查分解步骤和逆元计算。编码问题Flag可能不是UTF-8文本。尝试其他编码如latin-1或者直接输出16进制形式hex(m)看其是否符合某种格式如flag{...}、FLAG{...}、CTF{...}。有时flag可能被进一步编码如Base64、Hex后加密所以解密后的字节还需要再做一次解码。需要字节反转由于大小端序问题有时需要将long_to_bytes(m)的结果用.decode(‘utf-8’)[::-1]反转一下试试。填充问题标准的RSA加密会使用PKCS#1 v1.5或OAEP等填充方案。但CTF中的“简单”RSA题很多是直接对明文对应的整数进行加密即“教科书式RSA”不涉及填充。如果题目提示了填充方式解密后需要去除填充。6.3 性能问题与大数运算当n达到2048位或更大时所有的运算幂运算、求逆、素数检测都会变慢。使用gmpy2如前所述这是必须的。确保你用的是mpz类型而不是Python原生int。优化算法比如在寻找p和q时如果知道它们接近用费马分解gmpy2.isqrt比试除法快得多。利用已知信息题目描述、注释、甚至文件名都可能隐藏线索比如p和q是相邻素数。6.4 工具链辅助不要只埋头写Python。善用外部工具能极大提高效率。因数分解对于较小的n 100位可以试试在线网站 factordb.com 。对于更大的n可以尝试使用yafu一个强大的因数分解工具尤其擅长Pollard Rho和SIQS算法。在Python中对于光滑数可以尝试sympy库的factorint函数但它对于大数也很慢。RSA密钥解析如果给的是.pem或.der文件可以用命令行工具openssl rsa -pubin -in pubkey.pem -text -modulus来快速提取n和e。交互式环境在VSCode的Python交互式窗口或Jupyter Notebook中分步执行代码随时查看中间变量的值是调试复杂计算过程的神器。6.5 一个综合调试案例假设你写好了“Power Tower”的代码但计算结果和预期不符比如题目给的示例答案对不上。你可以按以下步骤排查验证欧拉函数计算用一个小素数n比如7测试你的phi(n)函数是否正确φ(7)6。验证递归逻辑用一个极小的指数塔测试比如计算2^(3) mod 10手工算一下是8看程序输出是否为8。打印递归过程在power_tower函数中添加打印语句输出每一层递归的mod、phi_mod、exp的值看是否和你的手工推导一致。检查扩展欧拉定理的应用条件确认你的代码在exp phi_mod时才加phi_mod这是最容易出错的地方。使用已知结果验证在网上搜索“Power Tower modulo”计算器用你的参数去验证。7. 从解题到出题逆向思维提升当你熟练破解这些题目后可以尝试从出题人的角度思考这能极大加深你对漏洞的理解。比如要出一道“easy_RSA”题你会怎么设计让n可分解这是最基本的。你可以选择两个较小的素数比如512位或者故意使用一个已知的、有公开分解的n。隐藏p和q不直接给n而是给n p*q以及pq或p-q的某个函数让选手通过解方程来求p和q。考察对e和φ(n)不互质的处理如果gcd(e, φ(n)) ! 1那么d不存在标准RSA解密失效。但此时可能仍有办法解密这考察了对RSA更深入的理解。结合其他编码将flag进行Base64、Hex或ROT13编码后再加密增加一步解码过程。多步RSA设计一个需要连续进行两次或多次RSA解密/加密的流程。对于“Power Tower”出题点可以更多改变模数n的性质让n是一个素数、两个素数的乘积、或者一个光滑数影响φ(n)的计算复杂度。设计特殊的指数塔让指数塔的某一层是0或1导致整个塔的值快速收敛。与非RSA结合将Power Tower的计算结果作为RSA的明文m或密钥的一部分。通过这种逆向思考你再看到新题目时就能更快地洞察到题目的考点和可能的破解路径。CTF密码学就像一场攻防游戏了解如何构建防线出题能让你更擅长找到防线的漏洞解题。
CTF密码学实战：从欧拉定理到RSA破解的Python实现
1. 项目概述从两道CTF密码学题看实战解题思维最近在带新人入门CTFCapture The Flag时发现很多朋友对密码学题目既感兴趣又有点发怵。理论公式看懂了但一到实战面对一个压缩包里的几个看似随机的数字和文本文件就不知道从何下手。这太正常了密码学实战和课本学习完全是两码事。今天我就以两道非常经典的题目——“Power Tower”和“easy_RSA”为例用Python手把手地带你走一遍完整的解题流程。我的目的不是让你死记硬背这几行代码而是希望通过这两个案例帮你建立起一套遇到密码学题目时的“条件反射”和解题框架。你会发现很多看似复杂的题目拆解后核心就是几个数学原理和编程技巧的组合。无论你是刚接触CTF的新手还是想巩固密码学实战经验的朋友这篇分享都能给你带来直接的帮助。“Power Tower”这道题名字听起来很唬人像是要处理一个巨大的指数塔但它本质上考察的是模运算下的欧拉定理应用关键在于如何高效计算 a^b^c^... mod n。而“easy_RSA”作为RSA入门题的常客名字就暗示了它的基础性但它完美涵盖了RSA加解密的全部核心步骤大素数生成、密钥计算、加密解密是理解非对称加密实战的绝佳起点。我们将使用Python因为它有丰富的数学库如gmpy2,pycryptodome语法简洁是CTF密码学解题的“瑞士军刀”。接下来我会先带你看清每道题的设计思路和考点然后一步步实现破解最后分享我踩过的坑和调试技巧。2. 解题环境与核心工具准备工欲善其事必先利其器。在开始写代码之前我们需要一个顺手的环境。我个人强烈推荐使用VSCode配合Python虚拟环境这能保证项目依赖的纯净性避免不同项目间库版本冲突的噩梦。首先确保你安装了Python3.8及以上版本。你可以从官网下载安装时务必勾选“Add Python to PATH”。安装后在终端输入python --version检查是否成功。接下来我们创建项目目录并设置虚拟环境mkdir ctf_crypto_lab cd ctf_crypto_lab python -m venv venv激活虚拟环境Windows:venv\Scripts\activateLinux/Mac:source venv/bin/activate激活后命令行提示符前会出现(venv)字样。然后安装我们本次实战的核心库pip install pycryptodome gmpy2这里解释一下为什么是这两个库pycryptodome这是PyCrypto库的维护分支功能强大且稳定。它提供了完整的RSA实现、AES、DES等对称加密算法以及各种编码解码工具。在CTF中我们经常需要用它来加载题目提供的RSA公钥文件.pem格式或进行标准的加密解密操作。gmpy2这是Python的一个C语言扩展库专门用于高精度计算。它的核心优势在于处理大整数几百位甚至上千位的运算速度极快并且内置了高效的模逆元计算、素数检测、下一个素数查找等功能。在RSA题目中动辄1024位、2048位的大素数运算用Python原生的int类型虽然也可以但效率会低很多gmpy2是必备的性能加速器。注意gmpy2的安装有时会因为缺少底层C库如MPIR或GMP而失败。如果遇到问题可以尝试访问其官网查看针对你操作系统的预编译轮子wheel或者使用pip install gmpy22.1.0b5指定一个较旧但可能更稳定的版本。对于纯粹的学习和解题如果gmpy2实在装不上临时用Python原生int和pow(a, b, n)函数也能完成大部分计算只是遇到超大数时可能会慢一些。除了库你还需要一个文本编辑器来写代码VSCode、PyCharm都可以及一个可以运行Python脚本的终端。环境准备好后我们就可以开始拆解第一道题目了。3. 题目一“Power Tower”的数学原理与降维打击我们先来看“Power Tower”。题目通常会给你一个类似这样的表达式a^(b^(c^(...))) mod n以及a, b, c, ...和n的具体数值。直接计算是不可能的因为指数塔的数值会大到超出宇宙原子总数。这道题的考点非常明确利用欧拉定理Euler‘s Theorem对指数进行降幂。欧拉定理告诉我们如果整数a与n互质即gcd(a, n) 1那么a^φ(n) ≡ 1 (mod n)。其中φ(n)是欧拉函数表示小于n且与n互质的正整数的个数。这个定理的强大之处在于它允许我们将一个巨大的指数对φ(n)取模从而大幅减小计算量。但对于“Power Tower”我们需要一个更通用的工具——扩展欧拉定理。它放松了互质的条件其核心思想是当指数b大于等于φ(n)时有a^b ≡ a^(b mod φ(n) φ(n)) (mod n)。注意这里的“大于等于”条件和额外的 φ(n)这是处理非互质情况的关键。我们的解题步骤因此变得清晰递归计算从指数塔的顶端开始逐层向下计算。应用扩展欧拉定理在每一层判断当前指数是否大于等于当前模数的欧拉函数值。如果是则对指数进行降幂处理。模数更新在递归下降的过程中模数会依次变为n,φ(n),φ(φ(n)), ...直到变为1因为φ(φ(...φ(n)...))会迅速减小到1。边界处理当模数变为1时任何数模1都为0这是递归的终止条件。光说理论有点抽象我们直接上代码。假设题目给出的指数塔是2^(3^(4^5)) mod 1000这里用一个小例子演示原理。import gmpy2 from gmpy2 import mpz def phi(n): 计算欧拉函数φ(n)的简单实现适用于n可分解的情况实战中n可能很大 result mpz(n) p mpz(2) # 试除法分解质因数对于大的n这里可能需要更高效的算法如pollard rho temp n while p * p temp: if temp % p 0: while temp % p 0: temp // p result - result // p p gmpy2.next_prime(p) if temp 1: result - result // temp return result def power_tower(tower, mod): 递归计算指数塔模 mod 的值 :param tower: 指数塔列表例如 [2, 3, 4, 5] 表示 2^(3^(4^5)) :param mod: 当前的模数 :return: 计算结果 if len(tower) 1: return tower[0] % mod if mod 1: return 0 # 任何数模1都为0 # 计算下一层的模数 phi_mod phi_mod phi(mod) # 递归计算指数部分计算 tower[1:] 在模 phi_mod 下的值并根据扩展欧拉定理判断是否加 phi_mod exp power_tower(tower[1:], phi_mod) # 应用扩展欧拉定理 if exp phi_mod: exp exp % phi_mod phi_mod # 计算 base^exp % mod base tower[0] return pow(base, exp, mod) # 示例计算 2^(3^(4^5)) mod 1000 tower [2, 3, 4, 5] n mpz(1000) result power_tower(tower, n) print(f计算结果: {result})这段代码中power_tower函数是核心。它采用递归tower[0]是底数tower[1:]是剩下的指数塔。在计算指数exp时它先递归调用自身但模数换成了φ(mod)。得到exp后判断其是否大于等于φ(mod)以决定是否应用扩展欧拉定理的“加φ(mod)”规则。最后用Python内置的pow(base, exp, mod)进行模幂运算这个函数是优化过的非常高效。实操心得在实际CTF题目中n可能是一个合数并且可能非常大。上面phi(n)函数的试除法分解对于大数效率很低。更常见的场景是题目会直接给你n的分解比如n p * q或者n本身就是一个素数此时φ(n) n-1。所以先仔细阅读题目描述和附件尝试分解n或者寻找n的特殊性质往往比写一个通用的质因数分解函数更重要。如果n真的又大又难以分解那这道题很可能考察的是其他知识点比如n是光滑数适用Pohlig-Hellman算法。4. 题目二“easy_RSA”的完整流程与参数解析接下来我们看“easy_RSA”。这道题是CTF密码学的“Hello World”但它涵盖了RSA的所有关键环节。通常题目会给你一个公钥文件pubkey.pem和一个加密后的文件flag.enc或者直接给你n, e, c模数、公钥指数、密文的数值。我们的任务就是解出明文m。RSA的原理这里快速回顾一下选择两个大素数p和q。计算n p * qφ(n) (p-1)*(q-1)。选择一个整数e作为公钥指数满足1 e φ(n)且gcd(e, φ(n)) 1。常见的有e 65537。计算私钥指数d满足e * d ≡ 1 (mod φ(n))即d是e模φ(n)的逆元。加密c ≡ m^e (mod n)。解密m ≡ c^d (mod n)。对于“easy”级别的题目破解的突破口往往在于私钥d的计算而这需要知道φ(n)进而需要知道p和q。所以解题的核心就变成了如何从已知的n和e恢复出p和q“easy_RSA”之所以简单通常是因为以下原因之一n很小可以直接用工具如yafu、factordb网站或简单的试除法分解。p和q很接近导致n的开平方根附近就是p和q可以用费马分解法。使用了不安全的素数比如p或q太小或者p-1是光滑数适用Pollard‘s p-1算法。共模攻击如果两次加密使用了相同的n但不同的e且e1和e2互质可能可以恢复明文。低加密指数攻击如果e很小比如3并且明文m也很小使得m^e n那么直接对c开e次方就能得到m。我们假设一个最常见的场景题目给了我们n,e,c并且n不大可以分解。我们用Python来实现完整的解密流程。from Crypto.Util.number import long_to_bytes, bytes_to_long import gmpy2 # 假设题目给出的参数 n mpz(3233) # 一个非常小的n仅用于示例 e mpz(17) c mpz(855) # 假设的密文 # 第一步分解n这里因为n很小我们直接给出分解实战中可能需要调用factorint p mpz(61) q mpz(53) # 验证 assert p * q n # 第二步计算φ(n)和私钥d phi_n (p - 1) * (q - 1) # 计算e模phi_n的逆元即私钥d d gmpy2.invert(e, phi_n) print(f私钥d: {d}) # 第三步解密 m pow(c, d, n) # m c^d mod n print(f解密得到的数字m: {m}) # 第四步将数字m转换为字节即flag try: flag long_to_bytes(m).decode(utf-8) print(fFlag: {flag}) except UnicodeDecodeError: # 如果解码失败可能m不是UTF-8文本直接输出16进制或字节形式 print(f解密结果字节: {long_to_bytes(m)}) print(f解密结果16进制: {hex(m)})这段代码清晰展示了RSA解密的四个步骤。其中最关键的一步是gmpy2.invert(e, phi_n)它使用扩展欧几里得算法高效地计算出了模逆元d。注意事项在实际CTF题目中n、c等数字往往非常长是一串几百位的十进制或十六进制数。你需要将它们正确转换为mpz大整数。从文件读取时要注意字符串的格式是否有0x前缀是否是Base64编码等。一个常见的技巧是使用Python的int(hex_string, 16)或mpz(hex_string, 16)来转换十六进制字符串。5. 实战进阶当“easy_RSA”不简单时上面我们演示了最理想的、n可分解的情况。但“easy”有时只是个名字题目可能会设置一些小障碍。下面分享几种变种及其破解方法。5.1 已知n、e、d求p和q有时题目会给你n,e,d让你求p和q来解密。这需要一点数学推导。我们知道e*d ≡ 1 (mod φ(n))即存在整数k使得e*d - 1 k * φ(n)。由于φ(n) (p-1)(q-1) n - (pq) 1所以pq n - φ(n) 1。又知道n p*q联立方程即可解出p和q。更实用的方法是利用gmpy2import gmpy2 from Crypto.Util.number import getPrime, inverse # 模拟生成一组参数 bits 512 p getPrime(bits) q getPrime(bits) n p * q phi_n (p-1)*(q-1) e 65537 d inverse(e, phi_n) # 已知 n, e, d 求 p, q k e * d - 1 # 寻找一个 g使得 g^(k/2^t) 模 n 不为 1 或 -1 g 2 t 0 temp k while temp % 2 0: temp // 2 t 1 for i in range(1, t1): x pow(g, k // (2**i), n) if x ! 1 and x ! n-1: p_candidate gmpy2.gcd(x-1, n) if p_candidate ! 1 and p_candidate ! n: q_candidate n // p_candidate print(f找到分解: p {p_candidate}, q {q_candidate}) break这段代码利用了k e*d -1是φ(n)的倍数这一性质通过随机选取g并计算g^(k/2^i)有很大概率能找到n的一个非平凡因子。5.2 低加密指数攻击e3如果公钥指数e非常小比如3并且明文m也较小满足m^e n那么加密过程c m^e mod n实际上就等于m^e因为没超过模数。此时直接对密文c开e次方即可得到明文。import gmpy2 def low_e_attack(c, e): 低加密指数攻击当 m^e n 时有效 # 尝试开e次方根 m, exact gmpy2.iroot(c, e) if exact: return m else: return None # 示例 c mpz(27) # 假设密文是27 e 3 m low_e_attack(c, e) if m is not None: print(f低加密指数攻击成功明文m: {m})5.3 共模攻击如果同一份明文m用相同的n但不同的e1和e2加密得到c1和c2且gcd(e1, e2)1那么可以利用扩展欧几里得算法找到整数s1和s2使得e1*s1 e2*s2 1。那么m (c1^s1 * c2^s2) mod n。import gmpy2 from Crypto.Util.number import long_to_bytes def common_modulus_attack(c1, c2, e1, e2, n): 共模攻击 # 使用扩展欧几里得算法求 s1, s2 gcd, s1, s2 gmpy2.gcdext(e1, e2) assert gcd 1 # 确保e1和e2互质 # 计算明文 if s1 0: c1 gmpy2.invert(c1, n) s1 -s1 if s2 0: c2 gmpy2.invert(c2, n) s2 -s2 m (pow(c1, s1, n) * pow(c2, s2, n)) % n return m # 示例参数 n mpz(3233) e1, e2 mpz(17), mpz(19) m_original mpz(123) # 原始明文 c1 pow(m_original, e1, n) c2 pow(m_original, e2, n) m_recovered common_modulus_attack(c1, c2, e1, e2, n) print(f共模攻击恢复的明文: {m_recovered}) assert m_recovered m_original6. 常见问题、调试技巧与避坑指南在实战中代码写出来只是第一步能跑通并得到正确结果才是关键。下面是我在解这类题目时积累的一些常见问题排查经验和技巧。6.1 数据格式处理错误这是新手最容易栽跟头的地方。题目给的数字可能是十进制、十六进制带或不带0x、Base64编码、或者直接写在文件里。十六进制转整数int(hex_str, 16)或mpz(hex_str, 16)。如果字符串有0x前缀这两个函数都能处理。Base64解码使用base64.b64decode()得到字节串再用bytes_to_long()转为整数。从PEM文件读取公钥使用Crypto.PublicKey.RSA.import_key(open(‘pubkey.pem’).read())然后通过key.n和key.e获取参数。多行数据注意换行符。读取文件后使用.strip()去除首尾空白字符。一个健壮的参数读取函数可能是这样的def load_numbers_from_file(filename): with open(filename, r) as f: data f.read().strip() # 尝试判断格式 if data.startswith(0x): return mpz(data, 16) elif all(c in 0123456789abcdefABCDEF for c in data if c not in \n): # 可能是无前缀的16进制 return mpz(data, 16) else: # 尝试作为十进制整数 try: return mpz(data) except: # 可能是Base64 import base64 decoded_bytes base64.b64decode(data) return bytes_to_long(decoded_bytes)6.2 解密结果乱码或不是flag解密得到一个大整数m转成字节后是一堆乱码这通常有几个原因解密错误p和q找错了或者d计算错了。重新检查分解步骤和逆元计算。编码问题Flag可能不是UTF-8文本。尝试其他编码如latin-1或者直接输出16进制形式hex(m)看其是否符合某种格式如flag{...}、FLAG{...}、CTF{...}。有时flag可能被进一步编码如Base64、Hex后加密所以解密后的字节还需要再做一次解码。需要字节反转由于大小端序问题有时需要将long_to_bytes(m)的结果用.decode(‘utf-8’)[::-1]反转一下试试。填充问题标准的RSA加密会使用PKCS#1 v1.5或OAEP等填充方案。但CTF中的“简单”RSA题很多是直接对明文对应的整数进行加密即“教科书式RSA”不涉及填充。如果题目提示了填充方式解密后需要去除填充。6.3 性能问题与大数运算当n达到2048位或更大时所有的运算幂运算、求逆、素数检测都会变慢。使用gmpy2如前所述这是必须的。确保你用的是mpz类型而不是Python原生int。优化算法比如在寻找p和q时如果知道它们接近用费马分解gmpy2.isqrt比试除法快得多。利用已知信息题目描述、注释、甚至文件名都可能隐藏线索比如p和q是相邻素数。6.4 工具链辅助不要只埋头写Python。善用外部工具能极大提高效率。因数分解对于较小的n 100位可以试试在线网站 factordb.com 。对于更大的n可以尝试使用yafu一个强大的因数分解工具尤其擅长Pollard Rho和SIQS算法。在Python中对于光滑数可以尝试sympy库的factorint函数但它对于大数也很慢。RSA密钥解析如果给的是.pem或.der文件可以用命令行工具openssl rsa -pubin -in pubkey.pem -text -modulus来快速提取n和e。交互式环境在VSCode的Python交互式窗口或Jupyter Notebook中分步执行代码随时查看中间变量的值是调试复杂计算过程的神器。6.5 一个综合调试案例假设你写好了“Power Tower”的代码但计算结果和预期不符比如题目给的示例答案对不上。你可以按以下步骤排查验证欧拉函数计算用一个小素数n比如7测试你的phi(n)函数是否正确φ(7)6。验证递归逻辑用一个极小的指数塔测试比如计算2^(3) mod 10手工算一下是8看程序输出是否为8。打印递归过程在power_tower函数中添加打印语句输出每一层递归的mod、phi_mod、exp的值看是否和你的手工推导一致。检查扩展欧拉定理的应用条件确认你的代码在exp phi_mod时才加phi_mod这是最容易出错的地方。使用已知结果验证在网上搜索“Power Tower modulo”计算器用你的参数去验证。7. 从解题到出题逆向思维提升当你熟练破解这些题目后可以尝试从出题人的角度思考这能极大加深你对漏洞的理解。比如要出一道“easy_RSA”题你会怎么设计让n可分解这是最基本的。你可以选择两个较小的素数比如512位或者故意使用一个已知的、有公开分解的n。隐藏p和q不直接给n而是给n p*q以及pq或p-q的某个函数让选手通过解方程来求p和q。考察对e和φ(n)不互质的处理如果gcd(e, φ(n)) ! 1那么d不存在标准RSA解密失效。但此时可能仍有办法解密这考察了对RSA更深入的理解。结合其他编码将flag进行Base64、Hex或ROT13编码后再加密增加一步解码过程。多步RSA设计一个需要连续进行两次或多次RSA解密/加密的流程。对于“Power Tower”出题点可以更多改变模数n的性质让n是一个素数、两个素数的乘积、或者一个光滑数影响φ(n)的计算复杂度。设计特殊的指数塔让指数塔的某一层是0或1导致整个塔的值快速收敛。与非RSA结合将Power Tower的计算结果作为RSA的明文m或密钥的一部分。通过这种逆向思考你再看到新题目时就能更快地洞察到题目的考点和可能的破解路径。CTF密码学就像一场攻防游戏了解如何构建防线出题能让你更擅长找到防线的漏洞解题。
