GF(41) 拉格朗日插值还原替换表:已知前缀定多项式 + 反查候选 + SHA-256 约束穷举
ctf/crypto · verified
一句话结论
替换密码的字符集大小是素数 41(!@#¥% + a-z + 0-9),已知 7 组明密文字符对即可在 GF(41) 上唯一确定一个次数 ≤6 的多项式 f(明文索引 → 密文索引);用拉格朗日插值补全整张映射表,反向映射得到每个密文字符的全部候选明文,再对约 354 万种组合逐一做 SHA-256 与目标哈希比对,即可恢复 flag flkejiyliafg77c3c4f49335c711avg。
原理
- 字符集:
CHARSET = "!@#¥%" + ascii_lowercase + digits,长度 41;41 是素数,索引 0..40 构成有限域 GF(41),任意非零元素都有乘法逆元。 - 加密模型:替换表被设计成低次多项式
c = f(p) mod 41;已知 7 个明文前缀flkejiy及其对应密文,得到 7 个点(p_i, c_i),可插值出次数最多 6 的多项式f(7 个点确定 7 个系数)。 - 拉格朗日插值:
f(x) = Σ y_i · Π_{j≠i} (x - x_j)/(x_i - x_j) mod 41;分母是 GF(41) 中的非零差值,用pow(den, -1, 41)求逆,因此可在全域x=0..40上算出完整映射f_values。 - 非一一映射:多项式
f未必是双射,一个密文字符 y 可能对应多个明文索引 x;反向映射inv_map[y] = {x | f(x)=y}会给出候选列表,密文越长组合空间越大(本题约 3.54M)。 - 哈希约束:题目给出明文的 SHA-256,穷举所有候选组合并逐个计算哈希,唯一匹配的字符串即为明文;已知前缀的位置直接固定,进一步缩小空间。
- 为什么成立:多项式次数远小于字符集大小,7 个已知点足以恢复整张表;哈希提供了强校验,使多候选组合可以被离线过滤;组合数在可枚举范围内。
触发条件
- CTF crypto 题:替换/代换密码的字符集是素数大小(或可嵌入有限域),映射由低次多项式或有理函数定义。
- 已知明文前缀长度不少于多项式次数 + 1(本题 7 个点、次数 ≤6)。
- 题目提供明文的哈希/校验值(或明确的 flag 格式),可用于过滤候选组合。
- 密文长度与候选组合数在可枚举范围(本题约 3.54M,纯 Python
itertools.product可跑)。 - 需要正确识别字符集与索引顺序(多一个字符或少一个字符都会让插值失败)。
利用步骤
- 确认字符集与索引:把
CHARSET映射为 0..40,注意特殊字符与大小写。 - 用已知前缀
known_prefix与密文前 7 个字符构造点对(idx[明文], idx[密文])。 - 在 GF(41) 上做拉格朗日插值,计算
f(0..40)得到完整映射表。 - 建立反向映射
y -> [x...];对密文每个位置列出候选明文字符,已知前缀位置固定。 - 用
itertools.product枚举所有组合,计算 SHA-256 与目标哈希比对,命中即输出 flag。 - 若组合过多,可改用 meet-in-the-middle、z3 约束或按 flag 格式分段校验;若函数是双射,反向映射唯一,可直接解码。
PoC
原文脚本(已整理缩进与空格):
from string import ascii_lowercase, digits
from itertools import product
import hashlib
CHARSET = "!@#¥%" + ascii_lowercase + digits
MOD = len(CHARSET) # 41
enc = "quw7f59u51q¥##w¥w6q6s¥¥#w#661d¥"
known_prefix = "flkejiy"
target_hash = "7d41757168a2199b32cb1744de130fdebda25271116bc64eccf4e397770d73c2"
idx = {c: i for i, c in enumerate(CHARSET)}
points = [(idx[known_prefix[i]], idx[enc[i]]) for i in range(len(known_prefix))]
def modinv(a, m=MOD):
return pow(a, -1, m)
def lagrange_eval(x, points, mod=MOD):
total = 0
for i, (xi, yi) in enumerate(points):
num, den = 1, 1
for j, (xj, _) in enumerate(points):
if i == j:
continue
num = (num * (x - xj)) % mod
den = (den * (xi - xj)) % mod
total = (total + yi * num * modinv(den, mod)) % mod
return total
f_values = [lagrange_eval(x, points) for x in range(MOD)]
inv_map = {}
for x, y in enumerate(f_values):
inv_map.setdefault(y, []).append(x)
candidates_list = []
for i, ch in enumerate(enc):
chars = [CHARSET[x] for x in inv_map.get(idx[ch], [])]
if i < len(known_prefix):
chars = [known_prefix[i]]
candidates_list.append(chars)
for combo in product(*candidates_list):
s = "".join(combo)
if hashlib.sha256(s.encode()).hexdigest() == target_hash:
print("Flag:", s)
break
输出:flkejiyliafg77c3c4f49335c711avg
变体与关联
- 变体(已知点数量):点数 = 次数 + 1;若只知道 6 个点则无法唯一确定,需要额外约束或枚举系数。
- 变体(映射类型):若映射是有理函数
f(x)=num(x)/den(x),需用 Berlekamp-Welch 或线性化方法;若映射是随机表,则退化为普通替换密码,需要频率分析/模拟退火。 - 变体(求解器):组合空间过大时可用 z3 建模每个位置的候选约束 + 哈希前缀匹配,或 meet-in-the-middle 拆分密文。
- 关联:[[ctf-crypto-berlekamp-welch-rational-function-interpolation]](有理函数插值恢复分子分母)、[[ctf-crypto-multivariate-elimination-univariate-polynomial]](多元消元到单变量多项式)、[[ctf-crypto-blackbox-chosen-input-mapping]](黑盒映射恢复)。
- 边界:字符集/索引判断错误、已知前缀与密文对不匹配、哈希目标不是整串明文时脚本找不到解;多项式次数高于已知点数时不唯一。
检测与防御
- 这是 CTF 密码题解法,不是真实系统漏洞;对密码设计者的启示是:不要用低次多项式/可插值的代换表作为加密,已知少量明密文对会泄露整张表。
- 使用标准带密钥的原语(AES/ChaCha20 等)和随机 nonce;不要把明文哈希作为可离线校验的 oracle 暴露给攻击者。
- 若必须做字符集替换,使用密钥化的伪随机置换(PRP)并隐藏映射结构;限制攻击者获得已知明密文对的数量。