背包问题
首先，我们先来介绍一下背包问题，假定一个背包可以称重 W，现在有 n 个物品，其重量分别为 $a_1, a_2,...,a_n$ 我们想问一下装哪些物品可以恰好使得背包装满，并且每个物品只能被装一次。这其实就是在解这样的一个问题
$$ x_1a_1+x_2a_2+,...,+x_na_n=W $$
其中所有的 $x_i$ 只能为 0 和 1。显然我们必须枚举所有的 n 个物品的组合才能解决这个问题，而复杂度也就是 $2^n$，这也就是背包加密的妙处所在。
在加密时，如果我们想要加密的明文为 x，那么我们可以将其表示为 n 位二进制数，然后分别乘上 $a_i$ 即可得到加密结果。
但是解密的时候，该怎么办呢？我们确实让其他人难以解密密文，但是我们自己也确实没有办法解密密文。
但是当 $a_i$ 是超递增的话，我们就有办法解了，所谓超递增是指序列满足如下条件
$$ a_i>\sum_{k=1}^{i-1}a_k $$
即第 i 个数大于前面所有数的和。
为什么满足这样的条件就可以解密了呢？这是因为如果加密后的结果大于 $a_n$ 的话，其前面的系数为必须 1 的。反之，无论如何也无法使得等式成立。因此，我们可以立马得到对应的明文。
但是，这样又出现了一个问题，由于 $a_i$ 是公开的，如果攻击者截获了密文，那么它也就很容易去破解这样的密码。为了弥补这样的问题，就出现了 Merkle–Hellman 这样的加密算法，我们可以使用初始的背包集作为私钥，变换后的背包集作为公钥，再稍微改动加密过程，即可。
这里虽然说了超递增序列，但是却没有说是如何生成的。
Merkle–Hellman
公私钥生成
生成私钥
私钥就是我们的初始的背包集，这里我们使用超递增序列，怎么生成呢？我们可以假设 $a_1=1$，那么 $a_2$ 大于 1 即可，类似的可以依次生成后面的值。
生成公钥
在生成公钥的过程中主要使用了模乘的运算。
首先，我们生成模乘的模数 m，这里要确保
$$ m>\sum_{i=1}^{i=n}a_i $$
其次，我们选择模乘的乘数 w，作为私钥并且确保
$$ gcd(w,m)=1 $$
之后，我们便可以通过如下公式生成公钥
$$ b_i \equiv w a_i \bmod m $$
并将这个新的背包集 $b_i$ 和 m 作为公钥。
加解密
加密
假设我们要加密的明文为 v，其每一个比特位为 $v_i$，那么我们加密的结果为
$$ \sum_{i=1}^{i=n}b_iv_i \bmod m $$
解密
对于解密方，首先可以求的 w 关于 m 的逆元 $w^{-1}$。
然后我们可以将得到的密文乘以 $w^{-1}$ 即可得到明文，这是因为
$$ \sum_{i=1}^{i=n}w^{-1}b_iv_i \bmod m=\sum_{i=1}^{i=n}a_iv_i \bmod m $$
这里有
$$ b_i \equiv w a_i \bmod m $$
对于每一块的加密的消息都是小于 m 的，所以求得结果自然也就是明文了。
破解
该加密体制在提出后两年后该体制即被破译，破译的基本思想是我们不一定要找出正确的乘数 w（即陷门信息），只需找出任意模数 m′ 和乘数 w′，只要使用 w′ 去乘公开的背包向量 B 时，能够产生超递增的背包向量即可。
例子
这里我们以 2014 年 ASIS Cyber Security Contest Quals 中的 Archaic 为例，题目链接。
首先查看源程序
secret = 'CENSORED'
msg_bit = bin(int(secret.encode('hex'), 16))[2:]首先得到了 secret 的所有二进制位。
其次，利用如下函数得到 keypair，包含公钥与私钥。
keyPair = makeKey(len(msg_bit))仔细分析 makekey 函数，如下
def makeKey(n):
privKey = [random.randint(1, 4**n)]
s = privKey[0]
for i in range(1, n):
privKey.append(random.randint(s + 1, 4**(n + i)))
s += privKey[i]
q = random.randint(privKey[n-1] + 1, 2*privKey[n-1])
r = random.randint(1, q)
while gmpy2.gcd(r, q) != 1:
r = random.randint(1, q)
pubKey = [ r*w % q for w in privKey ]
return privKey, q, r, pubKey可以看出 prikey 是一个超递增序列，并且得到的 q 比 prikey 中所有数的和还要大，此外我们得到的 r，恰好与 q 互素，这一切都表明了该加密是一个背包加密。
果然加密函数就是对于消息的每一位乘以对应的公钥并求和。
def encrypt(msg, pubKey):
msg_bit = msg
n = len(pubKey)
cipher = 0
i = 0
for bit in msg_bit:
cipher += int(bit)*pubKey[i]
i += 1
return bin(cipher)[2:]对于破解的脚本我们直接使用 GitHub 上的脚本。进行一些简单的修改。
import binascii
# open the public key and strip the spaces so we have a decent array
fileKey = open("pub.Key", 'rb')
pubKey = fileKey.read().replace(' ', '').replace('L', '').strip('[]').split(',')
nbit = len(pubKey)
# open the encoded message
fileEnc = open("enc.txt", 'rb')
encoded = fileEnc.read().replace('L', '')
print "start"
# 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()
for i in range(0, nbit + 1):
# print solution
M = res.row(i).list()
flag = True
for m in M:
if m != 0 and m != 1:
flag = False
break
if flag:
print i, M
M = ''.join(str(j) for j in M)
# remove the last bit
M = M[:-1]
M = hex(int(M, 2))[2:-1]
print M输出之后再解码下
295 [1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0]
415349535f3962643364356664323432323638326331393536383830366130373036316365
>>> import binascii
>>> binascii.unhexlify('415349535f3962643364356664323432323638326331393536383830366130373036316365')
'ASIS_9bd3d5fd2422682c19568806a07061ce'需要注意的是，我们得到的 LLL 攻击得到的矩阵 res 的只包含 01 值的行才是我们想要的结果，因为我们对于明文加密时，会将其分解为二进制比特串。此外，我们还需要去掉对应哪一行的最后一个数字。
flag 是 ASIS_9bd3d5fd2422682c19568806a07061ce。
题目
- 2017 国赛 classic
