格密码笔记二

  • 背包密码（基于子集和问题）

  • NP完全（NP-complete）问题1

一、“背包（knapsack）”

（一）子集和问题

给定一个正整数集合 $(M1,M2,…,Mn)$ 以及一个整数 S. 选择子集使其和等于 S.

例如：$M=(2,3,4,9,14,23)，S=2$.。

我们选取子集 ${3,4,14}$，其和等于 21。

显然，子集和问题可能有唯一解，可能无解，可能多解。我们只考虑至少有一个解的情况。

接下来，我们利用子集和问题的困难性，构建一个公钥密码体系。

首先，取$M=(M1,M2,…,Mn)$为公钥。

Bob 要发送一条消息，将其编码为二进制向量 $x=(x1,x2,…,xn)$，（其中 xi 非 0 即 1）。

然后，Bob 计算$S=\sum^{n}_{i=1}x_iM_i$。

然后将 S 发送给 Alice。 而 Alice 想要解密，必须找到一个合法的 x，这也就相当于找到 M 的子集，使之和等于 S.

如果 Alice 能快速找到合法的 x 而敌手找不到，那么这个密码体系就是有效的，则Alice 解密与 Eve 解密的难度是一样的。

那接下来，考虑如何较快地解决子集和问题。

Eve 把 M 划分成两半，然后对于左边那一半，枚举其所有子集 I，记录子集和$ AI$；对于右边，也同样操作，得到 $B_J$. 如果存在一对 $A{I0},B_{J0}$ 使得它们的和等于 S，那么就解决了问题。

这是Meet In The Middle 算法，核心思想是以空间换时间。纯暴力做法是 O(1) 空间、O(2n) 时间，MITM 将之改进到了 O(2n/2) 空间、O(2n/2) 时间。

（二）超级递增序列上的子集和

称一个序列 $r=(r1,r2,…,rn) $是超级递增序列，

当且仅当满足$r{i+1}≥2{ri},∀ 1≤i≤n−1$

超级递增序列是指“后一个数比前一个数至少大一倍”的序列。

从这个性质出发，对于超级递增序列的子集和问题，我们可以使用贪心算法2

伪代码如下：

1
2
3
4
for i in range(n, 0, -1):
    if S >= r[i]:
        S -= r[i]
        print(r[i])

例如：有 $M=(3,11,24,50,115)$ 是超级递增序列，S=142。

那么首先检查 142>115，故输出 115，S 改为 142−115=27。接下来 50 被忽略，输出 24，S 变为 3。最后输出 3。共输出 115、24、3，生成 x=(1,0,1,0,1)，完成解密。

由此，Merkle 和 Hellman 提出了下面的方案：

  1. Alice 生成一个超级递增序列 r，还选择两个保密的整数 A,B 满足$B>2r_n,gcd(A,B)=1$

  2. Alice 计算一个公钥序列$M≡A⋅r_i\ (modB)$

    显然它不是超级递增序列。乘以 A 起到了混淆的作用。

  3. Bob 要加密 x，他发送$S=x⋅M=\sum^{n}_{i=1}x_iM_i$

  4. Alice 要解密 S，首先计算出$S′≡A^{−1}S\ (modB)$

    然后 Alice 求子集和问题$ (r,S′) $的解，即可解密。

为什么新问题的解就是原问题的解?

我们注意到，$S′≡A^{−1}\sum^{n}{i=1}x_iM_i≡A^{−1}\sum^{n}{i=1}xiAr_i≡\sum^{n}{i=1}x_ir_i\ (modB)$，而 B 是一个非常大的数，故 S 就是 x⋅r 的确切值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
from random import randint
import gmpy2, numpy as np

class MerkleHellman():
    
    def __init__(self, nbits):
        r = [randint(10, 20)]
        for x in range(nbits - 1):
            r.append(randint(2*r[-1], 3*r[-1]))
        
        while True:
            B = randint(2*r[-1] + 1, 3*r[-1])
            A = randint(2*r[-1] + 1, 3*r[-1])
            
            if gmpy2.gcd(A, B) == 1:
                break
        
        print(f'A = {A}, B = {B}')
        print(f'r = {r}')
        
        M = [A*x % B for x in r]
        print(f'M = {M}')
        
        self.A, self.B, self.r, self.M = A, B, r, M
    
    def enc(self, x):
        return np.dot(x, self.M)

    def dec(self, S):
        S = S * gmpy2.invert(self.A, self.B) % self.B
        print(f"S' = {S}")
        
        ans = []
        
        for t in self.r[::-1]:
            if S >= t:
                ans.append(1)
                S -= t
                print(f'find {t}, S <- {S}')
            else:
                ans.append(0)
        
        return ans[::-1]

worker = MerkleHellman(5)
# A = 1049, B = 836
# r = [19, 39, 89, 195, 410]
# M = [703, 783, 565, 571, 386]


c = worker.enc([1,0,1,1,0])
print(c)
# 1839


worker.dec(c)
# S' = 303
# find 195, S <- 108
# find 89, S <- 19
# find 19, S <- 0
# [1, 0, 1, 1, 0]

二、Merkle-Hellman 子集和密码体系

这套公钥加密体系，被称为子集和密码系统，或称背包密码。其核心思想是生成一个超级递增序列，然后用模线性运算进行混淆，将混淆之后的序列作为公钥。

我们之前提到过 MITM 算法。

在 MITM 攻击下，要做到 $2^{80} $时间安全，需要 n>160 的密钥。

另外，如果 r 序列很小，则攻击者可以直接猜测 r，故要保证安全，还需要$r1>2^n$，也就是说$M_i=O(2^{2n}),S=O(2^{2n})$这些条件会导致公钥 M 很大。

例如：n=160 的公钥大概需要 51200 bit 的空间来存放，与之相比，做到 280 安全的 RSA 公钥仅需大概 1000 bit 的空间。

接下来，我们看敌手 Eve 如何通过 lattice 来攻击背包密码。

首先，她拿到公钥 $M=(m_1,…,m_n)$，构造下面的矩阵

这个矩阵的行向量是

这些行向量的（整数系数）线性组合构成了一个 lattice：

$L={a1v_1+a_2v_2+⋯+a_nv_n+a{n+1}v{n+1}:a_1,a_2,…,a{n+1}∈Z}$

背包问题的解，也就是明文 $x=(x1,…,xn)$。L 显然包含$t=\sum^{n}{i=1}x_iv_i−v{n+1}=(2x1−1,2x_2−1,…,2x{n−1},0)$

接下来，既然 xi 全是 0 或 1，那么 t 的前面 n 个参数都是 ±1，导致 t 很短，有 $‖t‖=\sqrt{n}$。而生成这个 lattice 的向量，长度都达到了$ O(2^{2n})$，它们的线性组合能短到$\sqrt{n} $这个程度的，相当稀有，我们甚至可以认为只有 t 这一个。

那么，如果 Eve 可以快速找到lattice 里面的短向量，那么她就可以恢复出明文。

三、lattice reduction（格基规约）算法

在 lattice 里面找短向量的算法，称为 lattice reduction（格基规约）算法。

著名的 LLL 即是一个格基规约算法，它还有变种 LLL-BKZ。

现在我们利用 LLL 算法3来攻击背包密码。

3:格密码基础 5 (Lecture 2, LLL Algorithm) - 知乎 (zhihu.com)

例如：

1
2
3
M = [816358673, 214551389, 683509053, 377954927, 461648693, 819009687, 833612683, 246393449, 258952137, 592274653, 439857687, 164289531, 138621939, 626982035, 733582939, 561376076, 206910526, 470721180, 1105393379, 848577580]
msg = [1,0,1,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,1,0]
S = 6545130222

构造Lattice ：

1
2
3
4
5
6
7
8
9
n = len(M)
L = matrix.zero(n + 1)

for row, x in enumerate(M):
    L[row, row] = 2
    L[row, -1] = x

L[-1, :] = 1
L[-1, -1] = S

运行 LLL 算法进行格基规约：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
res = L.LLL()
print(res)

'''
[-1  1 -1 -1  1 -1  1 -1 -1  1 -1  1 -1 -1  1 -1  1 -1 -1  1  0]
[ 2  2  0  2 -2 -2  2 -2  0  0 -4  2  0  0  0  0  0  0  0  0  0]
[ 0  2  0  0  2 -4  0  2  0  0  4 -2  0  0  0  0  0  0  0  0  0]
[-1 -1  1  1  1 -3 -1 -1  1 -1  3 -1 -1  1  3  1 -1  3  1 -1  3]
[ 2  0  0  0  2  2  0 -2  2  0 -4  2  2 -2 -4  2  0  0  0  0  0]
[-1 -1 -1  1  1  1  1 -1 -1  3 -3  1 -1 -1 -1  1 -1  3 -1 -3  2]
[-4  2  0 -2  0  0  2  0  2  2  2 -2 -2  0  0 -2  0  0 -2 -2 -1]
[-1  1  1  1  3 -1 -1 -1  3  1  1 -3 -1  1  1 -3  1 -1  1  1 -1]
[ 1 -3  1  1 -1 -1  1 -1 -3  1 -1 -1 -5  1  1 -1  1  1  1  1  2]
[ 3 -3 -1 -1  1  1 -3 -1 -1  5 -1 -1  1  1 -1  1 -1  1  1 -1  0]
[ 0  2  0  2  4  0 -2  0 -4  0  0  0 -2  0  0 -2  0  0 -2 -2 -1]
[ 2 -2  0  0  2  0 -2  0  0 -2 -4  4  0  0  0  0  0 -2 -2  0 -2]
[ 1  1  1  1 -3 -3  3  1  3  1  1  1 -3 -3  1  1 -1  1  1 -1  0]
[ 1 -1 -1 -1  1 -1 -3 -1 -1  1  1  1  1  3  3 -5  1  1 -1 -1  1]
[-3  1 -3 -1  3  3  3 -1  1 -1  1 -1  1  1 -1  1 -1  1  1 -1  0]
[ 0  0  2  0  0  0  0  2 -2 -2  2 -6  0  0  0 -2  0  0 -2 -2 -1]
[ 0 -2  0 -4  2  0  2  2  0  2 -2  4 -2  0  0  0  0  2  2  0  2]
[-2 -2 -2 -2  2  0 -2 -2  2  0  0  0  2  0  0 -2 -2  0 -2  4  2]
[ 2 -2  0 -2 -4  0  2  0  0  0 -2  0 -2  2  0 -2 -4  0  0 -4  3]
[-2  0  0 -2  0  0  0  0  0 -2 -4  0 -2 -2 -4  2  2  0  0 -2 -1]
[ 1  1 -1  1  1 -1 -1 -1  1 -3 -1 -3 -3 -1  1  1  1  1 -1  1  3]
'''

第一行的相反向量就是解。