1.eazy_log

首先加法

2.AAALLL

使用AES加密，需要求出key

1
key = md5(str(f.list()).encode()).digest()

也就是求出f的系数

而f满足

1
f = sample_ternery_poly(Q)

首先定义了一个多项式 这里n=450,无法因式分解，但是有450个根

1
2
roots = [i[0] for i in g.roots()]
print(len(roots))

为什么？

注意到这里 原根的概念、性质及其存在性

  • 知乎

引理3：如果 ，那么
恰好有 d
个根。

然后我们从中选出225个根

然后构造了一个商环 也就是进行模运算，将 小于n的单项式不会有变化

所以f就是在Q上选取了一个449次的多项式，他的系数是-1,0，1由于是有限域p上的，所以-1就是p-1

所以我们的关键就是恢复f的系数

我们已知225个根，假设是r 而我们知道 于是有 那么
那么这就是一个格密码的问题了,注意到这个矩阵是Vandermonde矩阵

可以考虑 Direct Primal Attack 考虑嵌入技术 那么(f|-1)是格中的一个短向量

题目背景是partial vandermonde knapsack
problem，预期是2024Eurocrypt的Key
Recovery Attack on the Partial Vandermonde Knapsack
Problem，不过出题的时候没控制好参数(主要电脑配置带不动论文的实验，还忘了有flatter了)，导致出现了很多非预期，其实对应的就是论文里面最trivial的Direct
Primal
Attack。预期解法需要利用到多项式的输入均为ring下模的多项式g的根。假设这些根是，随机选取其子集，集合元素个数大概为，那么期望其中有一半的元素两两互为逆元，即，然后我们将这些元素两两配对，并观察到在环上有，因此：

两式相加得到： 两式相减得到：
上面两个多项式的维度只有原来的一半，并且由于f是ternary的多项式，其系数是{-1,0,1}，因此新的两个多项式系数也很小，在格上也是短向量，因此我们分别对上面两个多项式使用Direct
Primal
Attack，先求kernel然后在kernel上LLL找短向量，找出来之后相加相减就得到了原始的多项式f。

2.2 PV 背包问题

令 为 中 个不同随机元素的子集。
令 为 中的多项式，其系数从集合
中均匀随机采样。

定义 1 (PV 背包问题)

给定 和集合 ，恢复多项式 。
通常通过索引集 来标识实例更简单，实例可表示为 ，其中 为某个本原根 。

备注 2
当 为素数时，必须假设 的值永远不会包含在内，因为这会为 PV
背包问题提供简单的区分攻击。
因此选择 仅包含本原根。

Definition 2 (q-ary Kernel lattice). Let be any
(full rank) matrix with .
We define the q-ary Kernel lattice of as

If we write , where
,
, then assuming that is invertible, has a basis

If is not invertible, we can
simply re-order the columns to make start with a invertible matrix. The lattice
has dimension and volume . Finding a short vector in this
lattice, i.e., a short element in the kernel of , is usually referred to as the short
integer solution (SIS) problem.

Let denotes the
smallest radius of a closed ball containing at least linearly independent vectors in the
lattice . If for some
, then the lattice
contains a -unique SVP (uSVP)
solution.

我们先构造出

考虑这个多项式的表示 由于解中可能互为逆元，那这样导致是一样的，并没有提供额外的信息，反而增加了格的维度，所以我们只要考虑成对的其中一个就行，于是根据这个造格

这个式子包含了左半边的系数 就是把解带进去的1，x-x^{n-1},还有一列b

现在来构造 即求 这样就能提升到整数域上面 令 则C的右核的前n个分量就是v

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
for i in range(t1):
    basis = [2]
    for j in range(1, n//2):
        basis.append((pow(pairs_x[i][0], j, p) - pow(pairs_x[i][0], n-j, p))%p)
    
    W1.append(basis)
    b1.append((pairs_y[i][0]+pairs_y[i][1])%p)

W1 = matrix(Zmod(p), W1)
b1 = matrix(Zmod(p), b1).T

W1_ = block_matrix([W1, b1], ncols = 2)

pI = p * identity_matrix(n)  # q I_n
C1 = W1_.stack(pI) 
L1 = C1.right_kernel(ZZ)      # 整数核
B1 = L1.basis_matrix()

我们分别求出

的系数 相加除以2就能得到前半段，想减除以2，就能得到后半段

但是这里