Knapsack背包密码常见攻击方法

发表于 | 分类于

背包问题

有n个物品，重量分别为a1,a2,…an，每个物品仅能被装一次，选择哪些物品，可以理解为对应位为1，别的位为0，得到背包的重量W。因此，明文为0/1串，密文为背包重量。普通背包问题要还原明文，需要枚举所有的n个物品的组合，复杂度为2^n。

超递增

物品重量第i个值大于前面所有数的和时，可解密。解密时，逆序遍历所有物品，当重量W大于ai，则表示第i位为1，否则为0。

Merkle–Hellman加密算法

私钥

背包物品重量an

公钥

模数m，满足：m>所有an的和

乘数w，满足：gcd(w,m) = 1

公钥bi=w * ai mod m，bn和m组成公钥

加密

明文0/1串vi，依次乘公钥bi，相加模m \(c=\sum_{i=1}^nb_i*v_i\bmod m\)

解密

密文乘以乘数w的逆元w^-1可得明文 \(w^{-1}*c=\sum_{i=1}^nw^{-1}*b_i*v_i=\sum_{i=1}^nw^{-1}*w*a_i*v_i=\sum_{i=1}^na_i*v_i\bmod m\) 因为m>所有an的和，因此所有的ai*vi之和均小于m，通过私钥an，即可求得明文vi

LLL攻击，sample：archaic，ASIS-2014

构造矩阵乘法：KA=Y \(\left[x_1 x_2\dots 1\right]\left[ \begin{matrix} 1 & 0 & \dots & 0 & a_1 \\ 0 & 1 & \ddots & \vdots & \vdots \\ \vdots & \ddots & \ddots & 0 & \vdots \\ 0 & 0 & \dots & 1 & a_n \\ 0 & 0 & \dots & 0 & -c \end{matrix} \right]=\left[x_1 x_2\dots 0\right]\) A作为一个格的基向量组合，通过线性变换（左乘K），得到行向量Y，那么行向量Y，是在由基向量A组成的格上。成功构造出一个让有x_i的向量在已知的格上，那么这个向量还必须满足是该格的最短向量，也即是SVP问题的描述。

1
2
3
4
5
6
7
8
9
10
11
12
13
# create a large matrix of 0's (dimensions are public key length +1)
A = Matrix(ZZ,nbit+1,nbit+1)
# fill in the identity matrix
for i in xrange(nbit):
    A[i,i] = 1
# replace the bottom row with your public key
for i in xrange(nbit):
    A[i,nbit] = pubKey[i]
# last element is the encoded message
A[nbit,nbit] = -int(encoded)

res = A.LLL()
print(res[-1][:-1]) #need to remove last element 0

已知位数的乘数w小，已知等比数列的私钥加密明文，sample：knapsack，BJDctf-2020

乘数w小，则开始的几个bi = ai*w小于m，模m即为自身，因此，取前几个bi求最大公约数，当最大公约数位数匹配，则求得w。遍历公钥，当找到第一个模w不为0的值，表示其大于m，因为

prikey_i * A < B, prikey_i+1 = 2 * prikey_i * A < 2 * B

因此模m，即为减m，利用等比数列，2 * prikey_i * A - pubkey即为m

公钥乘w的逆元invert(w, m)求得私钥