1. 从一道CTF题说起当RSA公钥被用来“加签”最近在复盘一些CTFCapture The Flag比赛的题目特别是密码学方向的发现一个挺有意思的现象很多刚入门的朋友一看到“RSA”和“公钥”这两个词绑在一起脑子里第一反应就是“加密”。这没错RSA公钥加密、私钥解密这是教科书里的经典场景。但如果你在BUUCTF这类平台上看到一道题目标题或描述里带着“RSA公钥加签”这几个字还按加密的思路去硬套那大概率会卡住甚至钻进死胡同。这道题或这类题型的核心陷阱和教学意义就在于此它故意使用了“加签”这个说法而不是更常见的“签名”。对于熟悉PKI公钥基础设施的朋友来说“签名”是私钥干的事验证才用公钥。那“公钥加签”是什么鬼是不是出题人写错了其实不然这正是CTF题目的魅力所在——它往往在玩文字游戏或者是在考察你对密码学原语Cryptographic Primitive本质的理解是否僵化。简单来说在这类题目里“公钥加签”很可能不是一个标准的密码学术语而是一个描述题面行为的“黑话”。它的真实含义可能是“题目给出了一段数据以及一个RSA公钥这段数据看起来像是用某种方式‘处理’过的你需要利用这个公钥来解读出原始信息而这个‘处理’过程逆向来看模拟了‘签名’的某些步骤但用的是公钥。” 这听起来有点绕我们拆开看。首先为什么公钥不能用来“加签”在标准的RSA数字签名方案中如RSASSA-PKCS1-v1_5或RSASSA-PSS签名生成对消息的哈希值比如SHA256进行填充然后用私钥进行RSA解密运算是的从运算角度看是“解密”。验签验证对收到的签名值用公钥进行RSA加密运算运算角度看是“加密”得到结果后去掉填充与消息的哈希值对比。所以公钥在签名体系里的角色是“验证”它做的是加密运算。那么如果一道题说“用公钥加签”一种可能是它偷换了概念把公钥参与的“加密运算”这个过程类比成了“对数据进行某种锁定”并称之为“加签”。实际上它可能描述的是这样一个非标准流程对某个数据可能是flag也可能是中间值直接使用公钥进行RSA加密即教科书式的公钥加密操作然后将这个加密结果作为“签名值”给出。在这种情况下解题者需要做的恰恰是拿到对应的私钥去“解密”这个“签名”才能得到原始数据。但题目只给了公钥私钥呢这就需要结合其他信息了。另一种可能是题目涉及了RSA的数学性质。RSA算法中加密和解密、签名和验证在数学上都是模幂运算密钥对e, d, n满足m^(e*d) ≡ m (mod n)。在某些简化或错误的实现中如果混淆了e, n和d, n的角色就可能出现“用公钥指数e去进行签名生成运算”的情况。这时如果你有私钥d自然可以反向操作。但题目只给公钥就可能需要利用RSA的其他漏洞比如模数n分解、共模攻击、小指数攻击等来破解出私钥信息从而完成“验签”实为解密。所以面对“BUUCTF RSA公钥加签”我们首先要做的是心态转换别被字面意思带偏。它不是让你学习一个标准的签名流程而是给你一个场景其中“公钥”和“加签”这两个元素的组合是题目的突破口。你的任务不是实现标准签名而是逆向这个非标准过程。接下来我们就深入CTF实战场景拆解这类题目的常见套路和解题工具箱。2. 解题第一步解剖题面与文件识别真实操作拿到一道CTF密码学题尤其是RSA相关第一步永远不是急着写脚本而是仔细阅读题目的每一个字并检查所有附件。对于“公钥加签”这类描述模糊的题这一步更是至关重要。通常题目会提供一个压缩包或直接给出几个文件。常见的文件包括一个文本文件pubkey.txt或public.key里面是RSA公钥。可能是PEM格式-----BEGIN PUBLIC KEY-----也可能是直接给出了n, e两个数字。一个密文/签名文件flag.enc,signature.bin, 或直接写在描述里的一段十六进制/Base64字符串这就是所谓的被“加签”后的数据。可能有一个Python脚本task.py,challenge.py展示了加密/签名过程。这是最重要的线索一定要仔细分析。假设我们有一个最典型的场景题目描述为“我们使用RSA公钥对flag进行了加签你能找到flag吗”并附带了pubkey.pem和signature.bin。首先用openssl或Python的Crypto/cryptography库查看公钥详情openssl rsa -pubin -in pubkey.pem -text -modulus这会输出模数n一个大整数和公钥指数e通常是65537。记下这两个值。然后查看signature.bin文件。用十六进制查看器或Python读取with open(signature.bin, rb) as f: sig f.read() print(sig.hex()) # 查看十六进制 print(len(sig)) # 查看字节长度关键比对比较signature.bin的字节长度和模数n的字节长度n.bit_length() // 8 1。如果它们长度相近那么signature.bin极有可能就是一个经过RSA模幂运算后的结果即一个大整数它要么是m^e mod n加密要么是hash(m)^d mod n标准签名。由于题目说是“公钥加签”我们更倾向于猜测它是m^e mod n也就是用公钥加密了消息m。但这里有个死结如果真是标准RSA加密没有私钥d我们无法解密。这就是CTF题目的设计点——它绝不会让你陷入真正的密码学困境。所以我们需要寻找n或e的弱点。这就是下一步。3. 核心攻击面当RSA参数不再安全在CTF的RSA题目中安全的、大整数分解不可行的n是不会出现的否则题目无解。出题人一定会留下漏洞。针对“公钥加签”这种可能实质是“公钥加密”的题目我们有几条经典的攻击路径。3.1 模数分解获取私钥的直球对决这是最根本的方法。如果模数n可以被分解为两个大素数p和q那么私钥d满足e*d ≡ 1 mod φ(n)其中φ(n) (p-1)*(q-1)就可以直接计算出来。如何分解小素数如果n比较小比如小于512比特可以用本地工具如yafu、factordb.com网站或sage直接分解。共用模数如果题目给了多个公钥它们可能有相同的n。这非常危险因为知道同一n对应的不同密钥对可以通过计算最大公约数GCD来分解n。素数生成不当p和q过于接近可以使用费马分解法。p或q太小可以尝试用pollard-rho算法爆破。使用已知的素数有时n来自某些CTF常用素数库可以尝试匹配。实操步骤以分解成功为例假设我们用factordb.com查到了n p * q。from Crypto.Util.number import long_to_bytes, inverse import gmpy2 n 123456789... # 你的模数 e 65537 c int.from_bytes(signature, big) # 假设signature是密文整数 p 123... # 分解得到的p q 123... # 分解得到的q phi (p-1)*(q-1) d inverse(e, phi) # 计算私钥指数d m pow(c, d, n) # RSA解密c^d mod n flag long_to_bytes(m) print(flag)如果m解密出来是一段可读文本可能就是flag。如果不是可能需要继续处理见下文。3.2 小公钥指数攻击当e非常小时在RSA中公钥指数e通常取65537这是一个在安全性和计算效率间平衡的值。但如果出题人将e设置得非常小比如3甚至2而m也比较小使得m^e n那么加密或“加签”运算c m^e mod n实际上就等于m^e因为没超过模数n。这时直接对c开e次方根就能得到m。如何判断计算c int(signature)。如果c^(1/e)是一个整数或者非常接近整数那么攻击就成功了。用gmpy2的iroot函数可以高效计算整数根。import gmpy2 c int.from_bytes(signature, big) e 3 # 假设e3 m, is_exact gmpy2.iroot(c, e) if is_exact: flag long_to_bytes(int(m)) print(flag)为什么“公钥加签”场景下可能出现小e因为出题人可能为了简化计算或者故意留下这个漏洞让你忽略私钥直接通过公钥参数和密文恢复消息。这完美契合了“只用公钥就能破解”的诡异感。3.3 其他数学攻击与脚本识别除了上述两种还有共模攻击多个密文同一n不同e、低加密指数广播攻击同一消息用不同n但相同小e加密、维纳攻击d太小等。但这些更常见于标准的加密/解密题目。对于“加签”题我们更需要关注题目附带的Python脚本。仔细阅读脚本脚本里可能隐藏了真正的“加签”逻辑。例如# 错误示例但CTF中可能出现 def fake_sign(message, pub_key): n, e pub_key m bytes_to_long(message) # 这里用了公钥指数e进行运算但称之为sign s pow(m, e, n) return long_to_bytes(s)看到这样的代码你就立刻明白所谓的“签名”s其实就是m^e mod n即公钥加密。你需要做的就是解密它。如果脚本里还显示了n是由两个特定的素数生成的或者e是自定义的那更是直接给出了攻击路径。有时脚本里会进行多次“加签”或奇怪的填充。例如先对flag用公钥加密一次再对结果用公钥加密一次即c (m^e)^e mod n m^(e^2) mod n。这本质上还是加密只是指数变了。你需要解密的次数相应增加。4. 数据预处理与后处理Flag的“包装”与“拆包”在CTF中flag很少会被直接当作m进行RSA运算。通常会有各种预处理编码、填充、转换和后处理输出格式。在“公钥加签”题中这些处理可能正是混淆的一部分。常见预处理字符串转整数flag字符串先转换成bytes再用bytes_to_long变成大整数m。这是标准操作。拼接或填充在flag前后加上固定字符串如flag{ real_flag }或者进行PKCS#1 v1.5之类的填充。填充会增加m的随机性和长度。哈希如果是标准签名会对消息先哈希。但“公钥加签”可能省略这一步直接对原始消息或简单处理后的消息运算。常见后处理整数转字节运算结果大整数会转换成字节可能作为二进制文件signature.bin给出。Base64/Hex编码为了方便在题目描述中展示这个字节串可能被进一步编码为Base64或十六进制字符串。你需要先解码还原成原始字节。一个完整的处理链可能是flag字符串-bytes-bytes_to_long-RSA运算pow(m, e, n)-long_to_bytes-Base64编码- 呈现在题面。因此你的解题脚本也需要逆向这个过程import base64 from Crypto.Util.number import long_to_bytes, bytes_to_long # 1. 从题面获取Base64密文 b64_cipher ABCDEFG... # 2. Base64解码得到字节串 cipher_bytes base64.b64decode(b64_cipher) # 3. 字节串转整数大端序 c bytes_to_long(cipher_bytes) # 4. RSA解密假设已通过分解n得到d m pow(c, d, n) # 5. 整数转字节串 flag_bytes long_to_bytes(m) # 6. 尝试解码为字符串 try: flag flag_bytes.decode(utf-8) print(flag) except UnicodeDecodeError: # 可能不是直接可读字符串需要进一步分析 print(fRaw bytes: {flag_bytes.hex()})如果第6步解码失败flag_bytes可能包含非ASCII字符或者flag被藏在字节流的特定位置。你需要观察其十六进制形式寻找像666c6167‘flag’的hex或7d‘}’的hex这样的模式手动提取。5. 实战演练模拟一道“公钥加签”题让我们虚构一道符合“BUUCTF RSA公钥加签”风格的题目并一步步解构它。题目描述我们开发了一个新的签名系统为了提高效率我们尝试使用公钥进行加签这是公钥和签名结果你能验证出消息吗 附件pubkey.pem,signature.bin步骤1信息收集$ openssl rsa -pubin -in pubkey.pem -text -modulus Public-Key: (256 bit) Modulus: 00:d0:8b:... (很长一串十六进制) Exponent: 3 (0x3) ModulusD08B...发现关键信息模数n只有256比特非常小公钥指数e3。这是一个强烈的信号可能采用小公钥指数攻击。步骤2读取签名文件with open(signature.bin, rb) as f: sig f.read() print(fSignature length: {len(sig)} bytes) # 输出可能是32字节256位 print(fSignature hex: {sig.hex()}) c int.from_bytes(sig, big) print(fCiphertext as integer: {c})步骤3尝试小公钥指数攻击因为e3且n只有256位c m^3 mod n。我们首先尝试直接开立方根看是否m^3 n。import gmpy2 m_candidate, is_exact gmpy2.iroot(c, 3) if is_exact: print(fFound exact root! m {m_candidate}) flag long_to_bytes(int(m_candidate)) print(fPotential flag: {flag}) else: print(Not an exact cube root. Need to consider mod n.)如果is_exact为True恭喜直接得到m。但更可能的情况是m^3超过了n所以c是m^3被n取模后的结果直接开方无效。步骤4分解模数n256比特的n在CTF中几乎肯定是可以分解的。使用在线工具factordb.com或sage。 假设我们分解得到p 123456791 q 987654323 n p * q 121932631112359253验证一下n是否与公钥中的一致。步骤5计算私钥并解密from Crypto.Util.number import inverse n 121932631112359253 e 3 c ... # 从signature.bin读取的整数 p 123456791 q 987654323 phi (p-1)*(q-1) # 计算私钥指数d需要满足 e*d ≡ 1 mod phi # 注意因为e3需要检查gcd(e, phi)是否为1。如果不是则d不存在RSA无效。 if gmpy2.gcd(e, phi) ! 1: print(e and phi are not coprime, RSA invalid in this setting.) else: d inverse(e, phi) m pow(c, d, n) flag long_to_bytes(m) print(fDecrypted message: {flag})如果一切顺利flag就会以flag{...}的格式打印出来。步骤6处理意外情况如果解密出来的m转换成的字节不是可见字符串可能是以下原因Flag被反转了尝试flag_bytes[::-1]。Flag是hex编码尝试bytes.fromhex(flag_bytes.decode(ascii))。需要从长字节流中截取搜索bflag{或b}的索引。解密结果还需要进一步运算可能题目中的“加签”不是简单的m^e mod n而是(m padding)^e mod n你需要猜测或爆破padding。6. 工具链与调试技巧提升解题效率工欲善其事必先利其器。处理RSA题目一个顺手的工具链能节省大量时间。1. Python库PyCryptodome/Crypto经典库包含Crypto.Util.number模块提供long_to_bytes,bytes_to_long,inverse,GCD等关键函数。gmpy2处理大整数运算的利器开方、模逆、素数检测速度极快。sympy符号计算有时用于解方程或分解中等大小的整数。requests如果需要交互式攻击远程服务器。2. 在线工具与网站factordb.com分解模数n的首选。把n的十进制或十六进制值贴进去经常有惊喜。RsaCtfTool一个强大的RSA攻击集成工具GitHub可搜。它集成了数十种攻击方式分解、维纳、共模、广播等对于已知格式的公钥/密文可以一键尝试所有攻击。CyberChef瑞士军刀式的编解码网站。可以方便地在Hex、Base64、Raw bytes、整数之间转换进行XOR、移位等操作。3. 调试技巧打印中间变量在解题脚本中在每个关键步骤后打印出数据的长度、类型、前几个字节的hex值。这能帮你快速定位问题出在编码转换还是数学计算上。假设验证如果解密出一堆乱码先别放弃。计算一下这个乱码字节串的整数形式看看它是不是特别小比如小于256这可能意味着m本身就是一个字节的值或者flag是单字符。边界检查对于pow(c, d, n)计算出的m检查它是否小于n以及转换成的字节长度是否合理比如如果n是1024位解密出的m字节长度不应超过128字节。一个实用的解题脚本框架import base64 from Crypto.Util.number import long_to_bytes, bytes_to_long, inverse import gmpy2 # ---------- 1. 加载数据 ---------- # 从文件或题目描述中加载公钥(n, e)和密文c n 0x1234... e 65537 cipher_b64 ... # 解码密文 cipher_bytes base64.b64decode(cipher_b64) c bytes_to_long(cipher_bytes) # ---------- 2. 尝试攻击 ---------- # 攻击1: 检查n是否很小尝试分解 # 手动去 factordb.com 查询 n # 攻击2: 如果e很小尝试直接开方 if e 3 or e 2: m_root, exact gmpy2.iroot(c, e) if exact: print(f[!] Low exponent attack success! m {long_to_bytes(int(m_root))}) exit() # 攻击3: 如果分解成功常规解密 p ... q ... if p and q: phi (p-1)*(q-1) if gmpy2.gcd(e, phi) 1: d inverse(e, phi) m pow(c, d, n) flag_candidate long_to_bytes(m) print(f[*] Decrypted candidate: {flag_candidate}) # 尝试多种解码方式 try: print(f[] Flag (UTF-8): {flag_candidate.decode(utf-8)}) except: print(f[] Flag hex: {flag_candidate.hex()}) # 可能需要在hex中搜索flag格式 hex_str flag_candidate.hex() if 666c6167 in hex_str: # flag start hex_str.find(666c6167) # 尝试提取... else: print(f[!] e and phi not coprime. e{e}, gcd{gmpy2.gcd(e, phi)})7. 从解题到理解RSA签名与加密的本质再辨析通过解这道“公钥加签”题我们实际上被迫深刻理解了RSA中加密和签名的对称性。从数学上看RSA公钥操作n, e和私钥操作n, d都是模幂运算它们互为逆运算。加密/解密视角为了保密。发送者用接收者的公钥(e)加密c m^e mod n。接收者用自己的私钥(d)解密m c^d mod n。签名/验证视角为了认证和完整性。签名者用自己的私钥(d)对消息哈希值h进行“签名”运算s h^d mod n。验证者用签名者的公钥(e)进行“验证”运算h s^e mod n并对比h和计算出的h。注意这两个等式的形式c m^e mod n与h s^e mod n都使用了公钥指数e。m c^d mod n与s h^d mod n都使用了私钥指数d。所以从纯数学计算的角度看用公钥(e)运算可能是加密对消息m也可能是验证签名对签名值s。用私钥(d)运算可能是解密对密文c也可能是生成签名对哈希值h。“公钥加签”这个说法在数学上等价于“用公钥指数e对某个数据做模幂运算”。如果这个数据是原始消息m那就是加密。如果这个数据是消息的哈希值h但用公钥运算那在标准体系里是验证但验证不会叫“加签”。因此题目语境下的“加签”几乎可以确定是指非标准的、概念混淆的“用公钥进行了一次类似加密的操作”。理解这一点就能跳出术语的桎梏直指问题的核心无论它叫什么你拿到的是一个公钥(n, e)和一个经过data ^ e mod n计算后的结果。你的目标是从这个结果还原出data。还原的方法要么是找到d通过分解n等要么是利用e或n的弱点如小e、可分解n。8. 举一反三其他可能变体与防御性思考CTF题目不会一成不变。围绕“公钥”和“加签”还有一些常见的变体多次“加签”c pow(m, e**k, n)。即用公钥指数e连续加密k次。解密就需要连续解密k次前提还是你需要私钥d。如果k不大且你有d那么m pow(c, d**k, n)。但更可能的是出题人希望你注意到e**k可能很大导致新的指数与phi(n)不互质从而无法解密引导你寻找其他路径比如直接分解n。“加签”前混淆不是直接对m运算而是对m进行某种可逆变换如与固定值XOR或加上一个常数后再运算。解题时需要先解密再逆向这个变换。给出多个“签名”对同一个消息m用同一个公钥但不同的padding或随机数进行多次“加签”产生多个c_i。这可能指向相关消息攻击或Franklin-Reiter相关消息攻击。隐藏公钥参数公钥文件可能被损坏或者e、n被以特殊格式隐藏如图片隐写、内存dump。需要先进行隐写分析或数据提取才能获得攻击所需的参数。从防御视角看这道题给我们敲响了警钟切勿混淆加密和签名在设计和实现密码系统时必须严格区分加密和签目的使用标准的、经过验证的算法和填充方案如OAEP for加密PSS for签名。参数必须安全RSA的模数n必须足够大目前建议至少2048位并且由安全的随机素数生成。公钥指数e应使用65537避免使用小值。不要自己发明密码学正如这道题中“公钥加签”这种非标准操作是危险的在实际开发中绝对不要尝试修改或创造新的密码学原语应使用权威库如cryptography提供的高级API。最后解CTF题的过程是一个将理论知识与实战技巧结合并不断进行逻辑推理和试错的过程。“BUUCTF RSA公钥加签”这类题目与其说在考一个具体的算法不如说在考一种思维灵活性——不被表面描述迷惑直击底层数学原理和实现细节的能力。下次再看到令人困惑的术语不妨先把它翻译成“这里有一个用RSA公钥参数进行的模幂运算以及运算结果请找出输入。” 然后你的武器库分解、小指数、共模、脚本分析等就可以有条不紊地派上用场了。