RLWE 挑战:泄露私钥 s 后用 c0+s·c1 解出 delta·m,模 delta 与负噪声修正恢复明文
ctf/crypto · verified
一句话结论
题目实现的是标准 Ring-LWE 公钥加密(R_q = Z_q[x]/(x^n+1),q=2^60、t=2^32、delta=q//t),并把私钥 s 一起打印出来;拿到 s 后计算 c0 + s·c1 = delta·m + (e·u + e1 + s·e2),后面的噪声相对 delta 很小,对每个系数整除 delta(或四舍五入)即可恢复消息多项式,唯一要处理的是负噪声导致的向下取整误差(余数较大时商加 1)。
原理
- 参数与密钥:
n=128,模多项式x^n+1,q=2^60,明文模t=2^32,delta=q//t=2^28。私钥s的系数为 0/1;公钥b = −a·s − e,其中a在Z_q上均匀随机,e是均值 0、标准差 2 的小高斯噪声。 - 加密:
- 明文
m是 flag 的十六进制字符串逐字符取 ASCII(0–9、a–f 的 ASCII 码),补 0 到长度 n,再模 t; c0 = b·u + e1 + delta·m,c1 = a·u + e2,其中u的系数为 0/1,e1/e2为小噪声。- 解密(已知 s):
c0 + s·c1 = (b·u + e1 + delta·m) + s·(a·u + e2);- 代入
b = −a·s − e,−a·s·u + s·a·u抵消,得delta·m + (−e·u + e1 + s·e2); - 噪声项
−e·u + e1 + s·e2(符号不影响量级)的系数远小于delta=2^28,因此对每个系数做//delta(或除以 delta 后取最近的整数)就能恢复m的系数。 - 负噪声修正:若噪声为负,
floor((delta·m + noise)/delta)会比真实m小 1。文章的做法是先取商temp = final // 2^28、再取余temp1 = final % 2^28,若temp1[i] > 100000则把temp[i]加 1(余数接近 delta 说明被向下取整吃掉了 1)。 - 编码还原:
m的每个系数是十六进制字符的 ASCII 码;把恢复出的前 76 个系数转成字符拼成十六进制字符串,再int(hex_str, 16)→long_to_bytes得到 flag(前 76 个字符对应 flag 的十六进制长度,后续为补 0)。 - 为什么成立:RLWE 的安全性依赖私钥 s 保密;题目把 s 与公钥/密文一起输出,等于直接给出解密陷门(decryption oracle)。噪声项虽在,但相对 delta 可忽略,舍入即可纠错。
- 边界:若噪声参数过大或 delta 太小,舍入会出错(需要 Babai 最近平面/格约减);本题参数下直接整除 + 余数修正即可。
触发条件
- 题目/实现基于 Ring-LWE(多项式环
Z_q[x]/(x^n+1))提供公钥、密文,并泄露私钥s(或等价解密陷门)。 - 已知 n、q、t、模多项式与密文多项式
c0/c1(以及可选的a/b/s)。 - 明文按十六进制字符 ASCII 编码进多项式系数。
利用步骤
- 识别 RLWE:看到
poly_mul/poly_add、q=2^60、t=2^32、a/b/s、c0/c1与x^n+1模多项式,即可判定。 - 用私钥计算
final = c0 + s·c1 mod (q, x^n+1)。 - 对每个系数做
q_i = final_i // delta、r_i = final_i % delta;若r_i较大(接近 delta)则q_i += 1。 - 取前
flag_hex_len(题中 76)个系数,按 ASCII 码转字符拼成十六进制字符串,int(s,16)后long_to_bytes。 - 验证 flag 格式;若出现乱码,检查噪声符号、delta 取整方式与字符长度。
PoC
import numpy as np
from Crypto.Util.number import long_to_bytes
n = 128
q = 2**60
t = 2**32
poly_mod = np.array([1] + [0]*(n-1) + [1])
def poly_mul(x, y, z, mod):
from numpy.polynomial import polynomial as poly
init = poly.polymul(x, y)
res = poly.polydiv(init % z, mod)[1] % z
return np.int64(np.round(res))
def poly_add(x, y, z, mod):
from numpy.polynomial import polynomial as poly
init = poly.polyadd(x, y)
res = poly.polydiv(init % z, mod)[1] % z
return np.int64(np.round(res))
final = poly_add(c0, poly_mul(s, c1, q, poly_mod), q, poly_mod)
delta = q // t
temp = (final // delta)[:76]
rem = (final % delta)[:76]
hex_str = ""
for i in range(len(temp)):
hex_str += chr(temp[i] + 1 if rem[i] > 100000 else temp[i])
print(long_to_bytes(int(hex_str, 16)))
变体与关联
- s 未泄露:需要格攻击/LLL 恢复私钥或明文,见
ctf-crypto-ntru-lattice-lll-private-key-recovery、ctf-crypto-lll-hidden-short-vector-kannan-embedding-lwe、crypto-implementation-small-lwe-secret-bruteforce-aes-key。 - 编码变体:明文可直接按位/字节编码到系数;也可能用
q/2偏移编码(Kyber 风格),见ctf-crypto-cdf-comments-qhalf-bit-encoding-aes。 - 噪声修正变体:四舍五入、Babai 最近平面、中心化余数(把
r_i > delta/2视为负)都可替代文章的经验阈值。 - 边界:参数不够“LWE 安全”(q/t 太小、噪声太大)时舍入会失败;需要根据噪声分布选择纠错方式。
检测与防御
- CTF/实现侧:不要把私钥
s、随机种子或解密中间量打印到输出/日志;RLWE 的 s 一旦泄露即等同明文。 - 参数审计:检查 q、t、delta 与噪声分布是否满足解密正确性;避免使用会暴露秘密的调试输出。
- 防御:生产环境使用标准化 KEM/PKE(Kyber 等)并隔离密钥;调试构建中去掉密钥打印。