给定一个 和 以及一组 权重，找出用于生成该 和 的 权重。权重的数值随后被加密在该和中。这个系统依赖于一类可以被轻松解决的背包问题的存在（那些权重被分隔开，以至于它们可以使用类似 贪婪 算法的方式一次“剥离”一个的问题），以及将简单问题转换为困难问题，反之亦然的转换。模乘法被用作 陷门单向函数。简单的背包系统于 1982 年被 Shamir 破解，Graham-Shamir 系统被 Adleman 破解，迭代背包系统于 1984 年被 Ernie Brickell 破解。
背包问题
参见
硬币问题, 贪婪算法, 邮票问题, 子集和问题, 陷门单向函数使用 Wolfram|Alpha 探索
参考文献
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.在 Wolfram|Alpha 中被引用
背包问题引用为
Weisstein, Eric W. "背包问题。" 来自 MathWorld--一个 Wolfram Web 资源。 https://mathworld.net.cn/KnapsackProblem.html