给定一个 和 以及一组 权重，找出用于生成该 和 的 权重。权重的数值随后被加密在该和中。这个系统依赖于一类可以被轻松解决的背包问题的存在（那些权重被分隔开，以至于它们可以使用类似 贪婪 算法的方式一次“剥离”一个的问题），以及将简单问题转换为困难问题，反之亦然的转换。模乘法被用作 陷门单向函数。简单的背包系统于 1982 年被 Shamir 破解，Graham-Shamir 系统被 Adleman 破解，迭代背包系统于 1984 年被 Ernie Brickell 破解。
背包问题
参见
硬币问题, 贪婪算法, 邮票问题, 子集和问题, 陷门单向函数使用 探索
参考文献
Coppersmith, D. "Knapsack Used in Factoring." §4.6 in Open Problems in Communication and Computation (Ed. T. M. Cover and B. Gopinath). New York: Springer-Verlag, pp. 117-119, 1987.Lichtblau, D. "Solving Knapsack and Related Problems." Unpublished manuscript.Honsberger, R. Mathematical Gems III. Washington, DC: Math. Assoc. Amer., pp. 163-166, 1985.在 中被引用
背包问题引用为
Weisstein, Eric W. "背包问题。" 来自 --一个 资源。 https://mathworld.net.cn/KnapsackProblem.html