背包密码（一） | Miao-25 Blog

type

status

date

summary

password

🎒背包问题

✅

密码学背包问题（Cryptographic Knapsack Problem）是一种基于背包问题的密码学问题。它是由Merkle和Hellman于1978年提出的，也被称为Merkle-Hellman背包密码。

假定一个背包可以称重 W，现在有 n 个物品，其重量分别为 a1,a2,...,an ，装哪些物品可以恰好使得背包装满，并且每个物品只能被装一次。这其实就是在解这样的一个问题

其中所有的 xi只能为 0 和 1

蛮力攻击的时间复杂度是,就算中途相遇也只能降低到

🔑背包密码

Merkle-Hellman背包算法的思想是将消息编码为背包问题的解。明文分组长度等于堆中物品的个数，并且明文位与xi的值相对应，密文则是计算得到的和值

背包实际上存在两类不同的背包问题：

线性时间内可解

线性时间内不可解

对于易解的背包问题，可以选择超递增序列，那么相应的背包问题容易求解。

超递增背包

超递增是指序列满足如下条件

即第 i 个数大于前面所有数的和。

超递增背包

已知背包向量A=(a1,a2,…,an)，若有以下关系成立：

则称为背包向量A为超递增背包向量。

超递增背包向量问题可以通过贪婪算法求解。

贪婪算法 已知s为背包容积，对A从右向左检查每一元素，判断元素是否在解中。检查时判断如下条件：s≥an，则an在解中，令xn=1；否则令xn=0。依次检查完成后可以即可得到。

🎈

超递增背包问题的解很容易找到，计算其总量并与序列中最大的数比较，如果总重量小于这个数，则它不在背包中，如果总重量大于这个数，则它在背包中，背包重量减去这个数，进而考察序列中下一个最大的数，重复直到结束。如果总重量减为0，那么只有一个解，否则，无解。非超递增序列的背包是困难的问题，它们没有快速算法。要决定哪一项在背包中的唯一方法，是依次测试所有解，直到你得到正确的解为止。最快的算法仍随背包中物品超递增问题困难，对于后者，当你加入一项到序列中，求解只需要再进行一次运算。