背包加密算法

前言

在一次CTF比赛中遇到了，写了10个for嵌套硬爆出来了，复现的时候发现是背包加密。

Merkle–Hellman 公钥加密算法

整体加密流程

import numpy
x = [1,0,0,1,0]#明文对应的2进制数
a = [3,7,16,50,120]# 产生一个超递增序列，称作私钥
#对私钥a进行加密，产生公钥b。
m = 251#选取一个模数
w = 300#选取一个乘数
b = [w * x % m for x in a]#产生公钥
S = numpy.dot(x,b)#加密结果

可以发现，加密十分容易，但解密十分困难，这也是非对称加密的特点。 ### 加密

生成私钥

超递增序列，也就是a中每一位元素需要大于其之前所有元素的和。

a =[randint(20, 50)]
for i in range(nbits - 1):
    a.append(randint(2 * a[-1], 3 * a[-1]))

生成公钥

模数m要求：m > sum(a) 乘数w要求：gcd(w,m) == 1

while True:
    m = randint(2 * a[-1] + 1, 3 * a[-1])
    w = randint(2 * a[-1] + 1, 3 * a[-1])
    if gcd(w, m) == 1:
        break

b = [w * x % m for x in a]

b和m作为公钥。 加密：S = numpy.dot(x,b)

解密

拿到公钥\(M=(m_1,m_2,\ldots,m_n)\)，构造如下矩阵 \[ \begin{bmatrix} 2 & 0 & \ldots & 0 & m_1 \\ 0 & 2 & \ldots & 0 & m_2 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \ldots & 2 & m_n \\ 1 & 1 & \ldots & 1 & S \\ \end{bmatrix} \] 这个矩阵的所有行向量的线性组合构成了一个格，接下来将通过明文的特点和格上的特殊解法来进行解密。

LLL

对于明文\(X=(x_1,x_2,\ldots,x_n)\)这一组数来说，构造一个向量 \[ a=\sum_{i=1}^nx_iv_i-v_{n+1}=(2x_1-1,2x_2-1,\ldots,2x_n-1,0) \] 显然，a向量在格L上。因为X中的所有x只能取值0或1，因此a向量的长度很小，约为\(\sqrt{n}\)，对于很大的格基来说，a向量无疑是格L上的最小向量，因此我们利用LLL算法即可求出a向量。

例题

sum=492226042629702
nbits=32
M=[19620578458228, 39616682530092, 3004204909088, 6231457508054, 3702963666023, 48859283851499, 4385984544187, 11027662187202, 18637179189873, 29985033726663, 20689315151593, 20060155940897, 46908062454518, 8848251127828, 28637097081675, 35930247189963, 20695167327567, 36659598017280, 10923228050453, 29810039803392, 4443991557077, 31801732862419, 23368424737916, 15178683835989, 34641771567914, 44824471397533, 31243260877608, 27158599500744, 2219939459559, 20255089091807, 24667494760808, 46915118179747]
A=Matrix(ZZ,nbits+1,nbits+1)
for i in range(nbits):
    A[i,i]=2
    A[i,-1]=M[i]
for i in range(nbits+1):
    A[-1,i]=1
A[-1,-1]=sum
r=A.LLL()
print(r[0])
#(-1, -1, 1, -1, 1, -1, -1, -1, -1, 1, 1, -1, -1, -1, -1, 1, -1, -1, -1, 1, -1, -1, -1, -1, 1, -1, -1, 1, 1, -1, 1, 1, 0)

这里注意一下，第一行向量中是有+1与-1，需要进行取反，即-1代表1，1代表0。