Lattice
from sage.modules.free_module_integer import IntegerLattice
from Crypto.Cipher import AES
from base64 import b64encode
from hashlib import *
from secret import flag
import signal
n = 75
m = 150
r = 10
N = 126633165554229521438977290762059361297987250739820462036000284719563379254544315991201997343356439034674007770120263341747898897565056619503383631412169301973302667340133958109
def gen(n, m, r, N):
t1 = [ZZ.random_element(-2^15, 2^15) for _ in range(n*m)]
t2 = [ZZ.random_element(N) for _ in range(r*n)]
B = matrix(ZZ, n, m, t1) # B为75*150的矩阵
L = IntegerLattice(B)
A = matrix(ZZ, r, n, t2) # A为10*75的矩阵
C = (A * B) % N # C为10*150的矩阵
return L, C
def pad(s):
return s + (16 - len(s) % 16) * b"\x00"
signal.alarm(60)
token = input("team token:").strip().encode()
L, C = gen(n, m, r, N)
print(C)
key = sha256(str(L.reduced_basis[0]).encode()).digest()
aes = AES.new(key, AES.MODE_ECB)
ct = b64encode(aes.encrypt(pad(flag))).decode()
print(ct)题目生成了一个元素在 间的矩阵 ，和 上的矩阵 。然后给了一个两矩阵相乘再模 的结果 ，即 ，需要我们恢复出原来格的最短向量。
比赛时尝试过构造 ，跑LLL出来的结果很差， BKZ 的话一晚上啥也没出来。。 赛后只找到 Nu1L 队的 wp ，but 也只有个 exp ，一句解释都没，像我这样的菜鸡分析起来就十分吃力了，但聊胜于无嘛，其他几个队连个 wp 都不放呜呜呜。
exp 中构造了一个 维的方阵 如下：
可以看到 左上角为一个 维的单位阵，左下角为零阵，右上角为 的转置数乘 ，右下角为一个 维的单位阵数乘 ，这里乘不乘 得到的结果都是一样的，但神奇的是不乘的话 LLL 耗时会长一些。 跑一遍 LLL 后，取结果的左上角 矩阵，记为 ，取 的核记为 ，最后 跑一遍 BKZ 后的最短向量即为所求。
那么就不难看出有 ，即 至于 为什么左边要拼接一个单位阵，回忆你已经遗忘的线性代数，这种操作是不是似曾相识？没错说的就是矩阵的求逆，求逆矩阵除了伴随矩阵法，还有一种方法就是初等变换法。 例如如下一个矩阵求逆
在右边补上一个单位阵，得到
此时右边的矩阵 即为所求 究其原理，在进行初等行变换的时候，右边的矩阵“记录”下了我们的操作，可以表示为
回到题目中来，有
至于右上角为何是一个 的零阵，我也不知道，但 exp 既然这么断言，姑且就这么认为先，那么我们就推测
即有
得到 ，结合上面 ，推测。。。推测不出来了，然后结合队里大手子的分析如下
记题目中给出的两个矩阵为 和 ，有 若有 ，则 和 互为左右零空间。 因此可以通过构造格 ，使得对格 进行格基规约后可以得到一组基 满足 ，即 的基就是 在模 下的一个左零空间。 接下来对 求解其零空间 就得到了 所在的那个空间上了，这里从有限域化为整数域，即 ，然后因为 中所求的行向量是一个短向量，且矩阵 的行向量是 的行向量的线性组合，因此对 进行格基规约算法就可以把 的短向量给恢复出来。
至此已经有明悟的感觉，但仍是有少许不解，消化一段时间吧。