GM 变体加密的弱随机 y 递增:结式消元 + Coppersmith 小根逐位恢复明文
crypto/implementation · verified
一句话结论
GM 变体加密中,bit=0 时密文为 y^2 mod n,bit=1 时为 y^2*x mod n(x 为 Jacobi 符号 1 的非二次剩余);若 y 每轮只增加一个小于 2^48 的小随机数,相邻密文就存在代数关系:用前两组密文构造关于 y 与增量 k 的多项式,结式消去 y 得到 k 的多项式,Coppersmith 求小根 k,回代求 y;再从后往前对每个密文尝试 bit=0/1,若 x*(y+k)^2 - c 存在小根则 bit=1,逐位恢复明文,无需分解 n。
原理
- GM 的安全性依赖“判定模 n 的二次剩余”与分解 n 一样困难;密文的二次剩余性直接编码明文比特。
- 题目实现用递推
y_{i+1} = y_i + k_i,且k_i < 2^48远小于 n;这破坏了 y 的独立性,使相邻密文c_i = x^{bit_i} * y_i^2 mod n之间存在可消元的多项式关系。 - 由
c_0 = x*y_0^2与c_1 = (y_0 + k)^2得两个多项式f1 = x*y^2 - c_0、f2 = (y+k)^2 - c_1;对 y 取结式(Sylvester 矩阵行列式)得到只含 k 的多项式,small_roots()求出小 k。 - 回代后可解出 y;随后从最后一个密文向前遍历:已知当前 y,对每个 c 判断
x*(y+k)^2 - c是否有小根,有则说明该位 bit=1,否则 bit=0。由于 y 与 k 的递推关系,逐位反推即可恢复全部明文。 - 该攻击不分解 n,也不直接判定二次剩余,而是利用加密实现的弱随机性把“判定问题”转化为“小根问题”。
触发条件
- 目标使用 GM 变体:
c = y^2(bit 0)或c = y^2*x(bit 1),x 为 Jacobi=1 的非二次剩余。 - y 的更新方式弱随机(如每次只加一个小整数),使相邻密文存在小增量关系。
- 攻击者能获得公钥 (n, x) 与至少两组连续密文。
利用步骤
- 从
output.txt读取 n、x、密文列表 enc。 - 在
Zmod(n)上定义多项式环,构造f1 = x*y^2 - enc[0]、f2 = (y+k)^2 - enc[1]。 - 对 y 求结式,得到关于 k 的单变量多项式;用
small_roots()求小根 k(若多解,结合后续密文验证)。 - 回代求初始 y:对
f1与f2求 GCD,取系数恢复 y。 - 从 enc 末尾向前遍历:对每个 c 测试
x*(y+k)^2 - c是否有小根,有则 bit=1,否则 bit=0;更新 y。 - 把比特串转回字节,得到 flag。
PoC
# Sage
from Crypto.Util.number import long_to_bytes
exec(open('output.txt').read()) # n, x, enc
P.<y, k> = PolynomialRing(Zmod(n))
f1 = x*y^2 - enc[0]
f2 = (y + k)^2 - enc[1]
f3 = Matrix(f1.sylvester_matrix(f2, y)).determinant()
k = min(f3.univariate_polynomial().monic().small_roots())
def poly_gcd(a, b):
return a.monic() if not b else poly_gcd(b, a % b)
P.<y> = PolynomialRing(Zmod(n))
f1 = x*y^2 - enc[0]
f2 = (y + k)^2 - enc[1]
g = poly_gcd(f1, f2)
y = n - g.coefficients()[0]
flag = 0
P.<k> = PolynomialRing(Zmod(n))
for c in enc[::-1]:
flag <<= 1
if len((x*(y + k)^2 - c).monic().small_roots()):
flag += 1
print(long_to_bytes(flag))
变体与关联
- 弱随机形式可换成小范围随机、低熵种子、LCG 短周期;对应地把增量关系写成多项式并用 Coppersmith/格方法求解。
- 若 x 不是非二次剩余,密文的二次剩余性不再直接编码 bit,需要重新推导。
- 关联:RSA 部分明文/高位泄露的 Coppersmith 小根、截断 LCG 状态恢复、GM 方案的标准实现。
检测与防御
- GM 加密的 y 必须使用密码学安全随机数,且每轮独立采样,不能用“上一轮 y + 小增量”的递推。
- 避免在密文中暴露任何关于 y 的可预测关系;对实现做随机性测试与熵评估。
- 使用经过审计的密码库实现,避免自定义变体;对密钥/随机数生成器做侧信道与可预测性评估。