背包密码

背包问题

假设有序列 $\overrightarrow{W}=\{W_0,W_1,\dots ,W_n\}$，需要找到一个子集 $\overrightarrow{w}\subseteq \overrightarrow{W}$，使得 $\sum _{w_i\in \overrightarrow{w}}{w}_i=S$。

这个问题是 NP hard 的。

例如：$\overrightarrow{W}=\{3,34,4,12,5,2\}$，$S=9$，则 $\overrightarrow{w}=\{4,5\}$ 是一个解。

超增背包问题

假设有一个超增序列（SIK） $\overrightarrow{W}=\{W_0,W_1,\dots ,W_n\}$，满足 $W_i>\sum _{j=0}^{i-1}{W}_j$，例如：$\overrightarrow{W}=\{2,3,7,14,30,57,120,251\}$,找到一个子集 $\overrightarrow{w}\subseteq \overrightarrow{W}$，使得 $\sum _{w_i\in \overrightarrow{w}}{w}_i=S$ 是简单的。

假设 $S=186$，则 $\overrightarrow{w}=\{2,7,14,30,57,120\}$ 是一个解。

• 251 > 186，不选 251, 余 186
• 120 ≤ 186，选 120, 余 66
• 57 ≤ 66，选 57, 余 9
• 30 > 9，不选 30, 余 9
• 14 > 9，不选 14, 余 9
• 7 ≤ 9，选 7, 余 2

背包密码

1. Keygen

• 选择一个超增序列 $\overrightarrow{W}=\{W_0,W_1,\dots ,W_n\}$。
• 选择一个模数 $n$，满足 $n>\sum _{i=0}^n{W}_i$。
• 选择 $m$，满足 $gcd(m,n)=1$。
• 计算序列 $\overrightarrow{B}=\{B_0,B_1,\dots ,B_n\}$，其中 $B_i=m\cdot W_i\mathrm{mod}n$。

得到：

• 公钥：$\text{pk}\leftarrow \overrightarrow{B}$。
• 私钥：$\text{sk}\leftarrow \overrightarrow{W},n,m$。

e.g:

$$\begin{array}{rl}\text{sk}& \leftarrow \overrightarrow{W}=(2,3,7,14,30,57,120,251)\\ & n=491\\ & m=41\\ & m^{-1}\mathrm{mod}n=12\\ \\ \text{pk}& \leftarrow \overrightarrow{B}=(82,123,287,83,248,373,10,471)\end{array}$$

2. Encrypt

• 假设明文 $P=[10010110]$
• 密文 $C=\sum _{i=0}^n{P}_i\cdot B_i=82+83+373+10=548$

3. 解密

• 计算 $C^{\prime }=C\cdot m^{-1}\mathrm{mod}n=548\cdot 12\mathrm{mod}491=193$。
• 然后使用超增序列，容易解得 $193=120+57+14+2$，对应明文 $P=[10010110]$。

使用格破解背包密码

从攻击者视角，只知道公钥超递增背包被“扰乱”后的序列：

• 已知：$\overrightarrow{B}=(B_0,\dots ,B_{n-1})$，以及密文 $C$
• 不知：超增序列 $\overrightarrow{W}$、模数 $n$、乘数 $m$

但对任意明文比特向量 $\overrightarrow{P}=(P_0,\dots ,P_{n-1})\in \{0,1{\}}^n$，总有：

$$C\equiv \sum _{i=0}^{n-1}{P}_i{B}_i(\mathrm{mod}n)$$

以及

$$0\le \sum _{i=0}^{n-1}{P}_i{B}_i<n\cdot max{B}_i$$

把解密问题改写成求解短向量的形式

解密的本质是：从所有 $2^n$ 个 0/1 向量里，找到一个满足

$$\sum _{i=0}^{n-1}{P}_i{B}_i=C$$

的向量 $\overrightarrow{P}$。
如果我们能把“所有可能的线性组合”组织进一个格里，那么“正确的那一个组合”就会对应于格中的某个特殊向量（通常是比较短的向量）。
这就把“解背包”转化成了一个格中的最短向量问题。

构造格

$$\mathbb{M}=\left[\begin{array}{cc}{I}_{n\times n}& B_{n\times 1}\\ 0_{m\times n}& -C_{n\times m}\end{array}\right]$$

在这里， $n$ 是背包的维度， $B$ 是公钥列张成的向量， $C$ 是密文列张成的向量，$m$ 指的是密文条数，一般为1。故而也可以写成

$$\left[\begin{array}{cc}{I}_{n\times n}& B_{n\times 1}\\ 0_{1\times n}& -C_{m\times 1}\end{array}\right]$$

任意整数向量 $(x_0,\dots ,x_{n-1},x_n)\in {\mathbb{Z}}^{n+1}$ 乘上这个基，就得到格中的一个向量：

$$\mathbb{M}\cdot \left[\begin{array}{cc}{X}_{n\times 1}& 1_{1\times 1}\end{array}\right]=\left[\begin{array}{cc}{X}_{n\times 1}& 0_{1\times 1}\end{array}\right]$$

格 $\mathcal{L}$ 中的任意向量可表示为：

$$\overrightarrow{v}=M\cdot \overrightarrow{x}={\left[\begin{array}{c}{x}_0\\ x_1\\ ⋮\\ x_{n-1}\\ \sum _{i=0}^{n-1}{x}_i{B}_i-x_{n}C\end{array}\right]}^T,\text{其中 }\overrightarrow{x}=(x_0,x_1,\dots ,x_n{)}^{\mathrm{\top }}\in {\mathbb{Z}}^{n+1}.$$

对于明文 $\overrightarrow{P}=(P_0,\dots ,P_{n-1})$，并令 $x_i=P_i$（$i=0,\dots ,n-1$），$x_n=1$。则对应的格向量为：

$${\overrightarrow{v}}_{\text{true}}={\left[\begin{array}{c}{P}_0\\ P_1\\ ⋮\\ P_{n-1}\\ \sum _{i=0}^{n-1}{P}_i{B}_i-C\end{array}\right]}^T={\left[\begin{array}{c}{P}_0\\ P_1\\ ⋮\\ P_{n-1}\\ 0\end{array}\right]}^T$$

因为 $\sum P_i{B}_i=C$。因此，${\overrightarrow{v}}_{\text{true}}$ 是格 $\mathcal{L}$ 中的一个向量:

前 $n$ 个分量属于 $\{0,1\}$， 最后一个分量为 0， 欧几里得范数满足 $||\overrightarrow{P}||\le \sqrt{n}$。

由于 $n$ 通常不大，这个向量在高维空间中是非常短的。

利用 格基规约 算法恢复明文

可以通过 LLL 或者 BKZ 等格基规约算法，找到格 $L$ 中的短向量，从而恢复明文 $\overrightarrow{P}$。

攻击步骤如下：

1. 根据公钥 $\overrightarrow{B}$ 和密文 $C$ 构造格基矩阵 $M$；
2. 对 $M$ 应用 LLL 算法，得到一组约简基 $\{{\overrightarrow{b}}_0,{\overrightarrow{b}}_1,\dots ,{\overrightarrow{b}}_n\}$；
3. 检查每个基向量： 若某向量 $\overrightarrow{b}$ 的最后一个分量为 0， 且前 $n$ 个分量均为 0 或 1， 则该向量极可能就是 ${\overrightarrow{v}}_{\text{true}}$；
4. 提取前 $n$ 位作为明文 $\overrightarrow{P}$，并验证 $\sum P_i{B}_i=C$。

Code

Sage

from sage.all import * 
from Crypto.Util.number import *

Length = 16

# 生成私钥: 超增序列
def gen_superincreasing_sequence(length):
    sequence = []
    current_sum = 0
    for _ in range(length):
        next_element = current_sum + randint(1, 10)
        sequence.append(next_element)
        current_sum += next_element
    return sequence, current_sum    

sequence, total_sum = gen_superincreasing_sequence(Length)
print("私钥：",sequence)

私钥： [9, 17, 32, 65, 129, 259, 517, 1033, 2067, 4136, 8270, 16537, 33078, 66151, 132305, 264611]

# 生成模数和乘数
bits = log(total_sum, 2)
p = getPrime(int(bits) + 1)
while True:
    m = randint(2, p - 1)
    if gcd(m, p) == 1:
        break

print("p: ", p)
print("m: ", m)

p:  711751
m:  421763

# 生成公钥
pub_key = []
for i in sequence:
    pub_key.append((i * m) % p)
    
print("公钥: ",pub_key)

公钥:  [237112, 52461, 684898, 368057, 314351, 338714, 255665, 89567, 600897, 621818, 400110, 246682, 45163, 116764, 75315, 572393]

加密

message = [1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0]
# 加密
ciphertext = 0
for i in range(Length):
    ciphertext += message[i] * pub_key[i] % p
    
print("密文: ",ciphertext)

密文:  2613511

解密

# 解密
m_inv = inverse_mod(m, p)
adjusted_ciphertext = (ciphertext * m_inv) % p

def decrypt_superincreasing_sequence(sequence, adjusted_ciphertext):
    decrypted_message = []
    for element in reversed(sequence):
        if adjusted_ciphertext >= element:
            decrypted_message.append(1)
            adjusted_ciphertext -= element
        else:
            decrypted_message.append(0)
    decrypted_message.reverse()
    return decrypted_message

dec = decrypt_superincreasing_sequence(sequence, adjusted_ciphertext)
print("解密：", dec)
assert dec == message

解密： [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0]

• 构造格

$$\left[\begin{array}{cc}{I}_{n\times n}& A_{n\times 1}\\ 0_{1\times n}& -B_{m\times 1}\end{array}\right]$$

在这里只有一条密文

$$\left[\begin{array}{cc}{I}_{16\times 16}& T_{16\times 1}\\ 0_{1\times 16}& -C_{1\times 1}\end{array}\right]$$

构造格基矩阵

# 生成单位阵 I
I = identity_matrix(Length)
weight = 1
# 零向量
zero_row = Matrix(ZZ, 1, Length, [0]*Length)
# 公钥向量
T_vev = Matrix(ZZ, Length, 1, pub_key) * weight
# 密文向量
C_vev = Matrix(ZZ, 1, 1, [-ciphertext]) * weight
# 拼接分块矩阵
L = block_matrix([[I, T_vev], [zero_row, C_vev]])
print(L)

[       1        0        0        0        0        0        0        0        0        0        0        0        0        0        0        0|  237112]
[       0        1        0        0        0        0        0        0        0        0        0        0        0        0        0        0|   52461]
[       0        0        1        0        0        0        0        0        0        0        0        0        0        0        0        0|  684898]
[       0        0        0        1        0        0        0        0        0        0        0        0        0        0        0        0|  368057]
[       0        0        0        0        1        0        0        0        0        0        0        0        0        0        0        0|  314351]
[       0        0        0        0        0        1        0        0        0        0        0        0        0        0        0        0|  338714]
[       0        0        0        0        0        0        1        0        0        0        0        0        0        0        0        0|  255665]
[       0        0        0        0        0        0        0        1        0        0        0        0        0        0        0        0|   89567]
[       0        0        0        0        0        0        0        0        1        0        0        0        0        0        0        0|  600897]
[       0        0        0        0        0        0        0        0        0        1        0        0        0        0        0        0|  621818]
[       0        0        0        0        0        0        0        0        0        0        1        0        0        0        0        0|  400110]
[       0        0        0        0        0        0        0        0        0        0        0        1        0        0        0        0|  246682]
[       0        0        0        0        0        0        0        0        0        0        0        0        1        0        0        0|   45163]
[       0        0        0        0        0        0        0        0        0        0        0        0        0        1        0        0|  116764]
[       0        0        0        0        0        0        0        0        0        0        0        0        0        0        1        0|   75315]
[       0        0        0        0        0        0        0        0        0        0        0        0        0        0        0        1|  572393]
[-----------------------------------------------------------------------------------------------------------------------------------------------+--------]
[       0        0        0        0        0        0        0        0        0        0        0        0        0        0        0        0|-2613511]

格基规约

# LLL
L_LLL = L.BKZ()
print(L_LLL)

[ 0  0  0  0  0  0 -2 -1  1  0  0  0  0  0  0  0  0]
[ 1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  0]
[ 0  0  0  0  0  0  0  2 -1  0  0  0  0  0 -2  1  0]
[ 1 -1 -1  0 -1  0 -1  0 -1  0 -1  0 -1  0  1 -1  0]
[ 0  0  0  2 -1  0 -2  1  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0 -2  1 -2  1  0  0  0  0  0  0  0  0]
[ 0 -2 -1  1  0  0  0 -2  1  0  0  0  0  0  0  0  0]
[ 0 -1 -1  0  0 -1  1  0  0  1  1 -1  1  0  0  0  1]
[ 1 -1 -1  0 -1  0  1 -1 -1 -2  0  0 -1  0 -1  0  0]
[ 0  0  0  0  0  0  0 -2  1  0  0 -2 -1  1  0  0  0]
[ 1  1  0  1  1  0 -2  1  0 -1  0  0 -1  1  0  0  1]
[ 1  0 -1 -1  0  0  1  0  0  0  1  1 -1 -1  1  0  2]
[ 0  0  2 -1  0  0  0  0  0  0 -2 -1  1  0  0  0  0]
[ 0  0  0  0  2  1 -1  0  0  0 -2 -1 -1 -1 -1  1  0]
[ 2  1 -1  0  0  0  0  0  0  0  0  0  0  2 -1  0  0]
[ 0  1  0  1  1  0  0 -2 -1  0  0  0  1  0  0  0  1]
[ 1  0  0  0 -1  0 -1  1  0 -1 -1  0  1  0  1  2 -1]

提取明文

# 找到最短向量
def fine(L_LLL):
    all_positive = True
    for i in range(Length):
        for row in L_LLL[i][:-1]:
            if row < 0:
                all_positive = False
                break
        if all_positive:
            return L_LLL[i][:-1]
        all_positive = True
res = fine(L_LLL)
print("最短向量: ", res)
assert list(res) == message

最短向量:  (1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0)