密码学题的附件经常只有一行:n = 1022117、e = 65537、c = 689345。没有源码,没有提示,没有密文文件。会做的人看一眼 n,发现它只有七位,随手分解成两个质数,几分钟就解出来;不会的人会去搜「RSA 破解工具」,下载一堆来路不明的脚本,跑半天没有结果。

CTF 里的密码学不是让你攻破现代密码系统,而是考「能不能看出这道题的参数是故意造弱的」。真实 RSA 的 n 是 2048 位以上,分解它超出所有公开能力;题目里的 n 可能只有几十位,或者 p 和 q 非常接近,或者 e 选得极小。这篇只讲这些题目里的数学常识和识别方法,不提供针对真实系统的攻击步骤。

先划边界:这里讲什么,不讲什么

CTF 密码题的对象是题目自己生成的参数,作者知道私钥,故意留下可解的缺口。真实系统的密钥不会这样生成,也不允许你拿题目技巧去试。所以本文的所有方法都限定在「题目附件、自己生成的参数、公开靶场」范围内。

不要用这里的思路去尝试破解真实网站、App、支付系统、Wi-Fi 或他人的加密文件。也不要用「解密工具」处理来路不明的样本。真实系统上的未授权测试可能违法,且大多数现代实现不会出现本文这些弱参数。遇到真实系统的安全问题,正确方向是报告、修复和合规评估。

还要区分「加密」和「编码」。base64 不是加密,哈希不是加密,异或也不一定是加密。密码学题通常有数学结构:模运算、质数、指数、有限域。看到只有字母表重排,先想古典密码;看到大整数和模运算,先想 RSA 或离散对数;看到一段固定长度的十六进制,可能是分组密码或哈希。

拿到一道密码题,先把附件里的信息列成一张清单:有哪些整数、哪些字符串、有没有源码、有没有提示文字。数字的位数、字符串的长度、变量名(n、e、c 本身就说明是 RSA)都是判断依据。清单列完再看「哪一项明显不符合常规」:n 太短、e 太小、p 和 q 位数接近、密文长度固定,异常的那一项就是题目的入口。不要跳过这一步直接套脚本,脚本不会告诉你条件是否满足。

古典密码:先看字母分布

凯撒密码是把每个字母按固定位数平移。识别特征是「字母频率分布和正常英文相似,但整体错位」。试 26 种平移就能穷举完,不需要任何工具。下面是一个最小实现:

def caesar(s, shift):
    out = []
    for ch in s:
        if ch.isalpha():
            base = ord('A') if ch.isupper() else ord('a')
            out.append(chr((ord(ch) - base + shift) % 26 + base))
        else:
            out.append(ch)
    return ''.join(out)

for k in range(26):
    print(k, caesar("synt{ynlref_bx}", k))

运行后会看到 k=13 时输出 flag{layers_ok}。凯撒的变体是「每个位置平移量不同」,比如按位置递增;这类题先试固定平移,再观察相邻字符的差值。差值稳定,说明是固定平移;差值按规律变化,说明是变种。

维吉尼亚密码用关键词决定每个位置的平移量,频率分布会被打散,单看频率不好判断。识别方法是找重复片段:相同明文在相同密钥位置会得到相同密文,重复间隔可能是密钥长度的倍数。知道密钥长度后,按列拆开,每列又退化成凯撒。CTF 题通常会给出密钥、提示词,或者密文短到可以直接猜。

异或(XOR)在 CTF 里既是编码也是「弱加密」。如果明文是英文、密钥是单字节,可以按频率或已知开头(比如 flag{)反推密钥。多字节重复密钥则先猜密钥长度,再按列统计。注意:这些方法只对题目里刻意构造的短文本有效,不能用来处理真实通信。

古典密码的题目现在很少单考凯撒,更常见的是组合:先做一次替换,再按位异或,最后 base64。处理这类题的关键是「每一层的输出都要能被下一层识别」。如果解开一层后得到的是一串大小写字母和数字,先想编码;如果得到的是可读英文但语义不通,再想替换或换位。反过来,如果解出来的是完全随机的字节,多半是密钥或算法认错了,继续硬解没有意义。

RSA 的基本数学,只需要四个式子

RSA 的构造可以压缩成四步。选两个大质数 p 和 q,令 n = p * q;计算欧拉函数 φ(n) = (p-1)(q-1);选一个与 φ(n) 互质的 e;求 d,使得 e * d ≡ 1 (mod φ(n))。公钥是 (n, e),私钥是 (n, d)。

加密是 c = m^e mod n,解密是 m = c^d mod n。题目给你 n、e、c,正常路径是分解 n 得到 p、q,再算 d。CTF 的「弱」就弱在 n 能被分解,或者根本不需要分解。

p = 1009
q = 1013
n = p * q                 # 1022117
phi = (p - 1) * (q - 1)    # 1020096
e = 65537
d = pow(e, -1, phi)        # 832193
m = 12345
c = pow(m, e, n)           # 689345
print(pow(c, d, n))        # 12345

本机 Python 3.15 实际跑过这段代码,输出与注释一致。pow(e, -1, phi) 是 Python 3.8 以后支持的模逆运算;老版本需要自己写扩展欧几里得。题目里如果 e 和 φ(n) 不互质,d 不存在,这本身就是一种异常,说明参数构造有问题。

模运算有几个性质值得记住,它们解释了为什么 RSA 能工作。第一,(a * b) mod n = ((a mod n) * (b mod n)) mod n,所以可以先取模再相乘,不会溢出。第二,a^e mod n 可以用快速幂在 log(e) 步内算完,不需要真的把 a 乘 e 次。第三,只要 e * d ≡ 1 (mod φ(n)),就有 (m^e)^d ≡ m (mod n),这是解密的数学依据。理解这三条,比背公式更能应付参数变形的题目。

弱参数:题目通常从这几个地方放水

拿到 RSA 题,先做一个「体检」,不要直接上通用分解工具。下面这些特征按成本从低到高排列,命中任何一个,题目就有明确的解法方向。

弱参数识别方法解题方向
n 很小位数少,几十位以内直接试分解,或用 sympy.factorint
e 很小(如 3)e 明显小于常规的 65537若 m^e < n,密文没有取模,直接开方
已知 p 或 q题目另外给了其中一个因子直接算 φ(n) 和 d
p、q 很接近n 的平方根附近能试出因子费马分解,从平方根向两侧找
共模,同一 n 两个 e两组密文用同一个 n扩展欧几里得组合出明文
d 很小题目提示或参数异常维纳攻击,连分数逼近

这些方法都有严格的适用条件,不是「看到 RSA 就试一遍」。比如小 e 只有在 m^e 没有超过 n 时才能直接开方;共模要求两组密文加密的是同一条消息,且 e1、e2 互质。条件不满足,硬套公式只会得到垃圾。

走查一:已知因子,直接解密

题目给 p = 1009、q = 1013、e = 65537、c = 689345。这不需要分解,直接按公式算:

p, q, e, c = 1009, 1013, 65537, 689345
n = p * q
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
print(pow(c, d, n))

输出 12345。如果题目把明文做成了 ASCII 字节串,还需要把整数转回字节。常见做法是按固定块长拆分,或者直接 bytes.fromhex;如果明文很短,整数本身就是整个消息的编码。转换方式要看题目给的提示,不能默认。

这里演示的是「已知因子」的最短路径。现实题目更常见的是只给 n,需要先分解。对几十位以内的 n,可以用 sympy.factorint 或在线工具;对更大的 n,就要看有没有其他弱参数。不要对 2048 位的真实公钥做分解尝试,那不是 CTF 的范围。

走查二:小 e 且没有取模,直接开方

题目给 e = 3、c = 1881640295202816,没有给 n,或者 n 明显大于 c。如果明文 m 很小,m^3 根本没有超过 n,那么 c 就是 m^3 本身,取模没有起作用。这时直接求整数立方根即可:

c = 1881640295202816
lo, hi = 0, 1
while hi ** 3 <= c:
    hi *= 2
while lo < hi:
    mid = (lo + hi) // 2
    if mid ** 3 < c:
        lo = mid + 1
    else:
        hi = mid
print(lo, lo ** 3 == c)

输出 123456 True。本机实际跑过,结果一致。用浮点数的 c ** (1/3) 在大整数上会丢精度,得到接近但不准确的结果,所以这里用整数二分。这个细节在真实解题里很常见:看起来算出来了,转成字节却差一位。

如果 m^3 超过 n 并取了模,直接开方就不成立,需要结合 k * n 尝试,或者寻找其他弱点。题目通常会通过参数大小暗示属于哪一种,先算 c 的位数和 n 的位数,再判断有没有取模。

还有一个常被忽略的检查:明文的长度。RSA 加密前通常把消息转成整数,短消息直接当整数,长消息要分块。题目给的密文如果和明文长度对不上,先怀疑分块方式或填充。反过来,解出的整数位数太少,可能只是某一块的结果,需要按题目给的块长把多块拼起来。这条线索在「解出来是乱码」时特别有用。

现象、原因与第一步

现象真实原因第一步查什么
RSA 解出来是乱码整数到字节的转换方式不对看题目是否给了块长、编码或填充方式
小 e 开方得到小数m^e 超过 n,已经取模比较 c 与 n 的大小,换其他弱点
模逆算不出来e 与 φ(n) 不互质检查 p、q 和 e 的取值
分解 n 跑很久n 太大,没有弱参数先检查 e、p/q 是否接近、是否共模
凯撒试完没有可读文本不是固定平移,或是维吉尼亚看重复片段和频率分布
异或结果像乱码密钥长度不是 1,或明文不是英文用已知开头反推,或按列统计
套公式得到无意义结果不满足该攻击的适用条件回到题目参数,确认条件是否成立

边界与代价

CTF 密码题和真实密码学的差距很大。题目里的参数是作者为了可解而构造的,真实系统用的是经过审计的库、足够长的密钥、随机化的填充和成熟的协议。把题目技巧当成「通用破解方法」,既无效,也可能带来法律风险。学习这部分内容的正确收益是:理解 RSA 的数学结构、知道哪些参数不能弱、能读懂安全公告里的术语。

时间成本上,密码题最容易「方向对了但卡在转换」。解出整数后不知道怎么变回明文,或者明文是分块加密的,需要按块拼接。建议每道题都先写清「输入是什么、运算是什么、输出是什么格式」,再动手写脚本。保留中间值,比反复重跑省时间。

合规边界再说一次:只对题目附件和自己生成的参数运算。不要尝试解密他人的文件,不要对真实网站的登录令牌做数学分析,不要把脚本发到未经授权的目标上。遇到真实系统的加密问题,应该走漏洞报告和修复流程,而不是自己上手「验证」。

当天能自己验证的练习

  1. 用 p=1009、q=1013 自己生成一对密钥,加密一个整数再解密,确认结果一致。
  2. 把 e 改成 3,选择一个足够小的 m,验证 m^3 < n 时可以直接开方;再换一个大的 m,确认开方失败。
  3. 用 26 种平移解 synt{ynlref_bx},记录每种输出,找出唯一可读的那一行。
  4. 构造一段用单字节异或加密的英文,用已知开头 flag{ 反推密钥,再解出全文。
  5. 用 sympy.factorint 分解一个 30 位左右的合数,记录耗时;再换一个 60 位的,观察耗时变化,理解「位数决定难度」。

小结

三句话:CTF 密码题考的是识别弱参数,不是攻破真实系统;古典密码看频率和重复,RSA 先体检再看条件;解出整数只是中间步骤,转回明文还要看题目给的格式。

下一篇是 MISC 组的收尾:综合题演练。它会把这组文章里的编码、文件、流量、取证、密码学手段放进同一个题包,讲清楚线索怎么从一张图片传到压缩包、再传到流量,以及卡住时怎么回溯。