knapsack背包密码算法

发表于 更新于 本文字数： 2.9k 阅读时长 ≈ 3 分钟
有关knapsack背包密码算法的简要笔记

Knapsack 算法

简述

Merkle–Hellman 背包密码系统是最早的之一公钥密码系统，同时也被称作 Knapsack 密码，在 1984 年便被破解，由阿迪·沙米尔（Adi Shamir）提出多项式时间攻击，故该密码为不安全的密码系统。

Merkle-Hellman 是一个公共密钥密码系统，这意味着使用了两个密钥，一个用于加密的公钥和一个用于解密的私钥。它基于子集和问题（背包问题），问题如下：

给定一组整数 \(A\) 和一个整数 \(c\)，找到的子集 \(A\) 总计 \(c\)。通常，已知此问题是 NP 完全 。但是，如果 \(A\) 是超增 ，这意味着集合中的每个元素都大于集合中所有数字的总和，那么问题是“容易的”并且可以通过简单的方法在多项式时间内解决，即使用贪心算法.

在 Merkle-Hellman 中，解密消息需要解决一个看似“硬”的背包问题。私钥包含数字的递增列表 \(W\)，并且公钥包含数字的非超级列表 \(B\)，实际上是“伪装”的 \(W\)。私钥还包含一些“活板门”信息，这些信息可用于转换使用以下内容的硬背包问题 \(B\) 使用一个简单的背包问题 \(W\)。

密钥生成

  1. 选择块大小 \(n\)

  2. 选择一个随机的超增正序列 \(W=(w_1,w_2,\cdots,w_n)\)，其中超增意味着需要满足： \[ w_k>\sum^{k-1}_{i=1}w_i,k\in(1,n],k\in N \]

  3. 选择一个随机整数 \(q\)，满足 \[ q>\sum^{n}_{i=1}w_i \]

  4. 随机选择一个随机整数 \(r\)，满足 \(\gcd(r,q)=1\)，即 \(r\) 与 \(q\) 互质

  5. 计算序列 \(B=(b_1,b_2,\cdots,b_n)\)，其中 \[ b_i=rw_1\pmod{q} \]

公钥即为 \(B\)，私钥为 \((W,q,r)\)

加密

  1. 将明文 \(m\) 二进制编码为序列 \(M=(m_1,m_2,\cdots,m_n)\)，例如明文 5 编码为序列 \(M=(1,0,1)\)

  2. 计算密文 \[ c=\sum^{n}_{i=1}m_ib_i \]

解密

我们将问题转化为寻找 \(W\)，使用贪心算法便可在多项式时间内求解。

  1. 计算模逆 \(F_r=r^{-1}\pmod{q}\)（由于之前满足 \(\gcd(r,q)=1\)，故模逆必存在）

  2. 计算 \(c'=cF_r\pmod{q}\)

  3. 贪婪选取 \(X=(x_1,x_2,\cdots,x_n)\)，使得满足 \[ c'=\sum^{k}_{i=1}w_{x_i} \]

  4. 最后将序列 \(X\) 二进制解码回 \(m\) 即可

实例

密钥生成

生成超增序列 \(W=(2,7,11,21,42,89,180,354),q=881,r=588\)

构造公钥 \[ 2\times588\pmod{881}=295\\ 7\times588\pmod{881}=592\\ 11\times588\pmod{881}=301\\ 21\times588\pmod{881}=14\\ 42\times588\pmod{881}=28\\ 89\times588\pmod{881}=353\\ 180\times588\pmod{881}=120\\ 354\times588\pmod{881}=236 \] 故公钥为 \(B=(295,592,301,14,28,353,120,236)\)

加密

消息 \(m=97\)，二进制编码得到序列 \(M=(0,1,1,0,0,0,0,1)\)

序列相乘 \[ M\cdot B=0\times295+1\times592+1\times301+0\times14+0\times28+0\times353+0\times120+1\times236=1129 \] 故密文即为 \(c=1129\)

解密

计算模逆 \(F_r=r^{-1}\pmod{q}=442\)

计算 \(c'=cF_r\pmod{q}=372\)

使用贪婪算法求解步骤： \[ c'=372,w_8=354\le372\Rightarrow x_8=1\\ c'=372-354=18,w_3=11\le18\Rightarrow x_3=1\\ c'=18-11=7,w_2=7\le7\Rightarrow x_2=1\\ c'=7-7=0 \] 故我们得到序列 \(X=(0,1,1,0,0,0,0,1)\)

故二进制解码得到明文 \(m=97\)

安全性

背包密码系统的安全性依赖于一般背包问题的求解困难（已知公钥求解困难），而超增背包问题的求解简单（已知私钥求解容易）。

Python 实现

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
import gmpy2

def keygen():
    """
    密钥生成
    """
    pk=[]
    sk=[]
    sk.append(m)
    sk.append(int(gmpy2.invert(w,m)))
    D=[]
    binD=[]
    for i in range(Baglenth):
        di=(w*Bag[i])%m
        D.append(di)
        bindi=bin(di)[2:]
        bindi=pad(bindi,h)
        binD.append(bindi)
    U=[]
    V=[]
    for i in range(Baglenth):
        tempu=int(str(binD[i][:j]),2)
        U.append(tempu)
        tempv=int(str(binD[i][j:]),2)
        V.append(tempv)
    e=gmpy2.next_prime(sum(V))+2
    f=gmpy2.next_prime(sum(U))
    assert gmpy2.gcd(e,f)==1
    sk.append(int(e))
    sk.append(int(f))
    for i in range(Baglenth):
        ai=e*U[i]+f*V[i]
        pk.append(int(ai))
    return pk, sk
def Encrypt(plain,pk):
    """
    加密
    """
    mbin=bin(plain)[2:]
    c=0
    mbin=pad(mbin,Baglenth)
    for i in range(Baglenth):
        c=c+int(mbin[i])*pk[i]
    return c
def Decrypt(code, sk, q, r):
    """
    解密
    """
    code = code * pow(r, -1, q) % q
    mbin = []
    for i in sk[::-1]:
        if i > code:
            mbin.append('0')
        else:
            mbin.append('1')
            code -= i
    return int(''.join(code[::-1]), 2)

Knapsack 破解