給定一個 和 以及一組 權重，找出用於生成該 和 的 權重。權重的數值隨後被加密在該和中。這個系統依賴於一類可以被輕鬆解決的揹包問題的存在（那些權重被分隔開，以至於它們可以使用類似 貪婪 演算法的方式一次“剝離”一個的問題），以及將簡單問題轉換為困難問題，反之亦然的轉換。模乘法被用作 陷門單向函式。簡單的揹包系統於 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.tw/KnapsackProblem.html