TSG CTF Lattice Cryptanalysis

TSG CTF 2023 - Learning with Exploitation 题解

题目给了一份 Sage 代码：在 192 bit 素数域 GF(p) 上生成一个 n = 10, d = 100 的 LWE 实例，公开键是矩阵 A 和向量 T，密文是若干组 (U, v)，每组对应 flag 的一个 8-byte chunk。题目的任务是只凭公开键和密文，把整个 flag 解出来。

from sage.stats.distributions.discrete_gaussian_integer import DiscreteGaussianDistributionIntegerSampler
from sage.crypto.lwe import LWE, samples
from sage.misc.prandom import randrange

p = 0xfffffffffffffffffffffffffffffffeffffffffffffffff
F = GF(p)
d = 100
n = 10
q = p // (2 ** 64)
D = DiscreteGaussianDistributionIntegerSampler(q // d // 6)  # six sigma

lwe = LWE(n=n, q=p, D=D)

public_key = list(zip(*samples(m=d, n=n, lwe=lwe)))
private_key = lwe._LWE__s

def encrypt(m, public_key):
    A, T = public_key
    r = vector([F(randrange(2)) for _ in range(d)])
    U = r * matrix(A)
    v = r * vector(T) + m * q
    return U, v

def decrypt(c, private_key):
    U, v = c
    return int(v - U * private_key + q // 2) // q

这题远没有标准 LWE 那么安全。这里的误差项其实很小，可以使用格规约。

把秘密向量和误差一起塞进格里，让 LLL 辅助寻找哦短向量。看是 LWE，实际上是一个格建模题。

题目中的公开键满足

T=As−e(modp)T = As - e \pmod p

如果误差向量 ee 足够小，那么可以把 (e,s)(e, s) 一起塞进格里，让它变成一个短向量候选。常见构造会把矩阵写成块形式：

B=(IA0pI)B = \begin{pmatrix} I & A \\ 0 & pI \end{pmatrix}

再通过额外权重把“小误差”编码进去。

知识补充

解题思路

先从公开的 A 和 T 出发构造带权格基，真正对应 (e, s) 的那条向量在格里会特别短，LLL 很容易把它翻上来。

一旦得到秘密向量 s ，后面的密文解密就没什么难度了。按题目定义把 U * s 消掉，再按模数比例做 round，把每个 chunk 拼起来就是 flag

def build_weighted_basis(A, T, p, weight):
    d, n = A.nrows(), A.ncols()
    top = block_matrix([[identity_matrix(ZZ, d), matrix(ZZ, A)]])
    bot = block_matrix([[zero_matrix(ZZ, n, d), p * identity_matrix(ZZ, n)]])
    basis = block_matrix([[top], [bot]])
    return diagonal_matrix([weight] * d + [1] * n) * basis


def decode_chunks(ciphertexts, s, p):
    out = []
    for U, v in ciphertexts:
        out.append(round_message(v - U * s, p))
    return b''.join(out)

参考资料

Back