背包密码学

本文最后更新于:2022年7月21日 下午

背包密码学

参考文献:

Knapsack Encryption Algorithm in Cryptography - GeeksforGeeks

密码学——公钥密码体系之背包算法1 - 哔哩哔哩 (bilibili.com)

谁能用通俗语言解释一下NP完全问题? - 知乎 (zhihu.com)

假如不太懂模运算可以参考我的另外一篇博客RSA加密算法 - Kamino’s Blog

在密码学领域,于1978年由Ralph MerkleMertin Hellman发明的背包加密算法(Knapsack Encryption Algorithm)是第一个通用的公钥加密算法。这个算法基于一个NP完全问题——背包问题,虽然后面发现这个算法并不安全,但是仍然值得我们学习。

先科普一下什么是NP完全问题:

P问题是一类可以在多项式时间内求解的问题,NP问题是一类可以在多项式时间内验证解是否正确的问题。

显然$P \subseteq NP$,但是目前人们想知道的是$P=NP \ ?$

NP-C或NP完全问题指的是“多项式复杂程度的非确定性问题”,所有的NP问题都可以约化到NP-C问题(即可以用NP-C问题的解法来解决NP问题,但NP-C问题的解法可能时间复杂度更高)。

背包问题指的是:给定一批不同体积的物品和一个背包容积,能够将物品中的几件放进这个背包,使背包刚好装满。

一般来说,解这个问题所需要的时间随着物品个数的增加呈指数增长,但其中包含一类可以在线性时间内可解的问题,背包算法的思想就是将明文看作背包问题的解,明文长度等于物品个数,而密文就是物品体积和。

明文 1 0 1 1 0 1
背包/秘钥 1 4 7 10 17 20
密文 1+ 0+ 7+ 10+ 0+ 20=38

容易解决的背包问题就是使用超递增序列,这种序列的每一项都大于它之前所有项之和,即$a_j>\sum^{j-1}_{i=1}a_i$。比如上面的1 4 7 10 17 20就不是,而2 3 6 13 27 52就是。使用这种序列的话,只需要逐渐取最大的物品放进背包即可。例如总容量70的背包,则先放52,然后发现27放不了,就放13,然后发现6放不了,就放3,最后放2。

下面介绍背包加密算法的具体流程:

  1. 取一个递增序列作为私钥:(2 3 6 13 27 52)
  2. 取一个与序列中所有数互质的整数$n$,再取一个大于所有数的整数$m$($n=31,m=105$)
  3. 计算$a_in\ mod\ m$,得到一个新序列作为公钥(62 93 81 88 102 37
  4. 背包长度为6,所以二进制明文按照6bit分组,1表示存在,0表示不存在,然后计算总体积(明文101101,则公钥加密密文为268
  5. 计算n的乘法逆元$nn^{-1}\equiv1(mod\ 105)$。($n^{-1}=61$)
  6. 计算$密文\times n^{-1}\ mod\ m$,然后解背包问题得到明文。(73=52+13+6+2(101101)