子集和问题的两种解决方式-先知社区

背包密码和多维子集和问题(

Multidimensional Subset Sum Problem

。)

●

知识:LLL算法，以及BKZ解决方法，还有MITM(中间相遇算法)算法解决。

简单介绍一些这里所称的背包问题，以子集和问题(Subset Sum Problem)

●

背包问题

非法 TeX 公式

W表示背包的承重，x只能位0或1(这里是0/1背包，完全背包感兴趣可以了解这里仅详细阐述0-1背包)，用来表示选中或不选中。

这种0-1背包问题也叫做子集和问题，给定一个集合，

非法 TeX 公式

它的部分元素的的和等于W，所以叫做子集和。如果不采取任何取巧的方式暴力破解这个问题，实践复杂度位$o(2^n)$,如果n较大这是十分困难的

Merkle–Hellman公钥加密算法（这种加密算法以及不再安全)

●

原理:虽然单纯的背包破解十分复杂，但是如果是超递增背包就能极大降低难度，我们设定初始背包为超递增背包，再利用模数m和乘数w对其进行加密

超递增背包

超递增背包的性质:设定集合:

非法 TeX 公式

,生成一个超递增背包并解逆推出用bag加密后的数，因为超递增背包的特性，这是很容易的

接下来进行公钥加密:

w做乘数，m取模，并且gcd(w,m)=1;

非法 TeX 公式

利用加密后得到

非法 TeX 公式

,得到另一个背包

非法 TeX 公式

B就是公钥，我们利用公钥B对信息进行加密

我们如果n很大我们就需要通过对B的每一个数和c乘w_1，然后模m，最后利用上述相同的方法便能恢复flag下面是完整代码

●

这种加密方式实际上已经不安全了，LLL算法能很轻易的破解背包密码，接下来我们便讲解LLL算法与背包密码

LLL和LLL-BKZ与子集和问题

●

这里所指的0-1背包更多的也被叫做子集和问题，

LLL算法

下面我们做一些格的简单介绍以及这里需要用到的应用

●

什么是格

我们定义一组基向量basis,由这组基向量和整数系所构成的所有点就是格。

例如(1,0)和(0,1)这一组向量就能构建这样的格

这样就构建了一个普通的格，当然我们遇到的大多数格基当然不会像这么简单。我们在子集和中需要应用到的是找格里面最短向量的办法

●

hermite 定理

对应任意n维的格L，都有一个非零向量v属于L，并且

非法 TeX 公式

假设向量v是格L的其中一个向量满足这个定理，并且v和

非法 TeX 公式

大小相差不算多，我们可以判定v是最短非零向量。我们在计算LLL相关题目时，如果不满足这个定理，则需要构造。当然这里并不需要

我们现在可以举例个背包加密的例子

给出最短向量的上限。

2024极客大挑战

已知a,b,p。

接下来构造函数

b=am+c-kp

c=b+kp-am

m=0+m+0

1=[1,0,0]

[1,m,k]*[1,0,b//0,1,-a//0,0,p]=[1,m,c]

如果m和c远远小于a,b,p则[1,m,c]可视为最短向量,通过求出最短向量即可求出m和c。但是这里[1,0,b]不能确定是否一定比[1,m,c]大很多，所以我们可以先尝试构造

这里构造出来，

非法 TeX 公式

补个

非法 TeX 公式

|V|<=|p|*1/3，并且大小接近，但是加了ZZ之后早格的范围变大了一些。

当然这只是简单的举例，知识为了更方便的理解背包密码。

接下来我们讲述LLL算法在子集和问题的应用，以及怎么破解刚刚的Merkle–Hellman公钥加密算法

非法 TeX 公式

这是一个典型的子集和问题，现在我们来构造矩阵。

非法 TeX 公式

来构造一个格,是一个(n+1)(n+1)的矩阵。

非法 TeX 公式

在一定条件下，我们可以利用这个格解除B然后找出x。这里N按理说是大于

非法 TeX 公式

的数，不过我这里试过直接N=1也无所谓

一定的条件，满足格密码的定理，这里我们要求的B就是最短非零向量

●

背包的密度

非法 TeX 公式

一般来说d<0.9408如果d过大则无法完成计算,当然这里所以ai肯定不能用同时乘以某个数的方式来扩大ai

但是用普通的LLL算法无法做到小于0.9所以后面我们可以用BKZ算法来精确。

我们先暂时用LLL算法,待会再引申到BKZ

这里的

非法 TeX 公式

小于0.9这样可以解出p

●

之前讲的都是单维的子集和，现在讲一讲多维的

多维子集和

其实跟单维度区别不大但是计算背包密度d的时候，k表示维度。也就是有几个方程

非法 TeX 公式

构造多维子集和的矩阵

例如有这样几多维矩阵

非法 TeX 公式

我们可以构造如下矩阵

非法 TeX 公式

是一个(n+1)(n+m)的矩阵

在多维运算时，普通的LLL算法即使在满足背包d的条件下也可能无法计算出x所以这里我们需要用到BKZ算法让它更精确，这里先用sagemath的库直接用，原理或许以后有空写一写

●

依然举个例子

用上面哪那个代码生成一组新的多维子集和

很明显可以发现得到的p是最大的。

MITM(中间相遇算法)

●

这个算法效率不算高，这个算法的时间复杂度约为$o(2^{n/2})$，不过这里可以当作了解，并且MITM算法在d超过1左右时也会失效。

这个算法也不难，就是把有n个元素的子集和问题分成两部分计算，python示例如下，把要求的P分成两部分掩码

这里知识演示的一维的，如果是多维的，自行添加约束即可。不过这个算法比较慢，仅作参考