四元数环离散对数:范数同态降维到素域后 BSGS,MD5(secret) 派生 AES 密钥
ctf/crypto · verified
一句话结论
给定模大素数 p 的四元数 Q、R 且 R = Q^secret(secret < 2^50),不必在非交换环上直接解离散对数:四元数范数 N(a,b,c,d)=a²+b²+c²+d² 满足 N(Q^k)=N(Q)^k mod p,先算出 N(Q)、N(R) 就把问题降为素域 F_p 上的 50-bit 离散对数,用 m≈2^25 的 BSGS 恢复 secret,再用 MD5(str(secret)) 派生 AES 密钥解密 flag。
原理
- 四元数乘法与范数:四元数
(a,b,c,d)的乘法非交换,但范数N(q)=a²+b²+c²+d²是可乘的:N(q1·q2)=N(q1)·N(q2) mod p。因此R=Q^secret两边取范数得到N(R)=N(Q)^secret mod p,指数关系被搬到交换的乘法群F_p^*中。 - 为什么可以降维:
p是大素数,只要N(Q) ≠ 0 mod p,N(Q)就在F_p^*中可逆,N(R)是它的幂;原本四元数环的四维结构不影响这一个标量方程,而secret只有 50 bit,标量 DLP 的难度足够低。 - BSGS:取
m=⌈√(2^50)⌉≈2^25,先存h·g^{-j}(j=0..m-1),再枚举g^{im}(i=0..m),命中时secret=im+j。时间与空间约2^25;若不存全表可改用 Pollard kangaroo 降低内存,代价是更多次乘法。 - 唯一性:
F_p^*是阶为p-1的循环群,解只在模ord(N(Q))意义下唯一。若ord(N(Q)) ≥ 2^50,则区间内只有一个解;若阶较小,会得到多个候选secret,需要用 AES 解密的 PKCS#7 padding 或 flag 前缀逐个验证。 - 密钥派生与解密:原文用
key = MD5(str(secret)).hexdigest().encode()得到 32 字节 ASCII 十六进制串,作为 AES-256 密钥,AES.MODE_ECB解密后unpad得明文。密钥长度与模式由题目代码给定,换题时必须重新确认。 - 为什么这条链成立:题目只暴露了
Q、R和 AES 密文,没有暴露四元数指数运算的实现;范数同态是公开的代数性质,攻击者可以完全绕开四元数快速幂,只做一次标量 BSGS。
触发条件
- 已知大素数
p、四元数Q、R,且R=Q^secret,secret有较小的已知上界(本例<2^50)。 N(Q) mod p ≠ 0,且N(Q)在F_p^*中的阶不小于上界(否则需要多候选验证)。- 加密方式与密钥派生已知(本例 AES-256-ECB +
MD5(str(secret))),密文可获取。 - 有约
2^25次群乘的时间/内存预算(C++/PyPy 更快;Python 纯实现较慢,可用 gmpy2 或编译语言)。
利用步骤
- 读取
p、Q=(a,b,c,d)、R=(a',b',c',d')和 AES 密文。 - 计算两个范数:
g = (a²+b²+c²+d²) mod p、h = (a'²+b'²+c'²+d'²) mod p。 - 在
F_p上做 BSGS:m=⌈√(bound+1)⌉;建立h·g^{-j} → j的表;枚举g^{im}并查表,得到secret=im+j(只接受0 ≤ secret ≤ bound)。 - 若
ord(g)小于bound,会得到多个secret;对每个候选派生密钥、解密并检查 PKCS#7 填充与flag{前缀。 - 用
MD5(str(secret)).hexdigest().encode()作 AES 密钥,ECB 解密并去填充,得到 flag。
PoC
from hashlib import md5
from math import isqrt
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
p = 115792089237316195423570985008687907853269984665640564039457584007913129639747
Q = (123456789, 987654321, 135792468, 864297531)
R = (53580504271939954579696282638160058429308301927753139543147605882574336327145,
79991318245209837622945719467562796951137605212294979976479199793453962090891,
53126869889181040587037210462276116096032594677560145306269148156034757160128,
97368024230306399859522783292246509699830254294649668434604971213496467857155)
enc = b'(\xe4IJ\xfd4%\xcf\xad\xb4\x7fi\xae\xdbZux6-\xf4\xd72\x14BB\x1e\xdc\xb7\xb7\xd1\xad#e@\x17\x1f\x12\xc4\xe5\xa6\x10\x91\x08\xd6\x87\x82H\x9e'
def norm(q):
return sum(x * x for x in q) % p
def bsgs(g, h, bound):
m = isqrt(bound + 1) + 1
table = {}
inv_g = pow(g, -1, p)
cur = h
for j in range(m):
table.setdefault(cur, j) # h * g^{-j}
cur = cur * inv_g % p
giant = pow(g, m, p)
cur = 1
for i in range(m + 1):
if cur in table: # g^{im} == h * g^{-j}
x = i * m + table[cur]
if x <= bound:
yield x
cur = cur * giant % p
for secret in bsgs(norm(Q), norm(R), 2**50):
key = md5(str(secret).encode()).hexdigest().encode()
try:
pt = unpad(AES.new(key, AES.MODE_ECB).decrypt(enc), 16)
except ValueError:
continue
if b'flag' in pt or pt.startswith(b'flag{'):
print(secret, pt)
break
原文代码用字典存 h·g^{-j}、以 g^m 做大步,并用 MD5(str(secret)).hexdigest() 派生 AES 密钥;以上实现保持同一逻辑,仅把候选验证写成生成器。原文未在本机复跑,2^25 规模的 BSGS 需按机器内存调整(可只存哈希或改用 Pollard kangaroo)。
变体与关联
- 内存受限:把 BSGS 换成 Pollard kangaroo/Pollard rho,或分块生成 baby steps;代价是多次群乘。
- 阶不足:若
ord(N(Q))小于指数上界,单个范数方程只能确定secret mod ord;可结合多个可乘同态(如四元数不同共轭/矩阵表示的行列式、其他二次型)做 CRT,或用明文格式筛选候选。 - 其他非交换结构:矩阵群、半直积、四元数代数等只要存在可计算的可乘范数/行列式同态,都可能把指数问题降到交换群;这类“同态泄露指数”是设计密码系统时必须排除的。
- 关联:[[ctf-crypto-semidirect-product-small-order-discrete-log]](非交换/半直积群上的小阶 BSGS)、[[ctf-crypto-small-discrete-log-crt-channel-selection]](小模数 DLP + CRT 恢复指数)、[[crypto-ecc-invalid-point-secp256k1-bsgs]](BSGS 基础)。
检测与防御
- CTF 识别:题目给出“四元数/矩阵/非交换环 + 幂 + 小指数上界”时,先找可乘范数、行列式、迹等标量同态,不要直接实现环上 BSGS 或暴力。
- 防御/设计:不要用“非交换”本身当作 DLP 难度的保证;选择素数阶群、避免存在高效同态到小群的结构,并确保密钥派生使用足够熵的 secret(本例 secret 仅 50 bit,且由 MD5 直接派生)。
- 检测特征:大素数模下的范数/行列式计算、
2^25量级的哈希表或大量pow(g, m, p)调用,可能是此类降维攻击的实现。