一個經典的金鑰體制--揹包公鑰密碼體制。在介紹該問題之前，先介紹下子集和問題。1、子集和問題假設在整數域上有集合S=｛a,b,c,d,e,f.....｝和一個整數sum。那麼找到集合S的一個子集SubS，該子集滿足：該子集中的所有元素相加恰好為sum。比如S=｛1，2，3，4，5，6，7，8｝，sum=15，那麼我們可以找到其子集SubS={7,8}或者｛1，6，8｝等等，這樣的一個問題就是子集和問題。子集合問題是NP完備問題（NP-complete problem），其求解是非常困難的（剛剛筆者所給的例子是一種比較簡單的情況，讀者請不要誤以為該問題很好解決）。我們考慮，子集和問題是否有所謂的特殊情況，而且這種特殊情況我們和容易去求解呢？答案是肯定的。這裡我們將討論下超遞增序列（superincreasing sequence）。即集合S是超遞增的，那麼什麼是超遞增序列呢？首先我們給出超遞增序列的定義。超遞增序列指的是這樣的一個集合，其中。超遞增序列具有什麼好處呢？由其定義，我們可以知道它具有這樣的一個性質：。這個性質對於求解子集和問題是多有幫助呢？筆者下面透過一個例子來給大家演示下超遞增序列的子集和問題的解決辦法。例1：對於超遞增序列M=｛3，11，24，50，115｝，和Sum=142。求解該子集和問題。Step 1：142-115=27>0，故115被選中；Step 2：27-50<0，故50不選；Step 3：27-24=3>0,故24選中；Step 4：3-11<0，故11不選；Step 5：3-3=0，故3選中，演算法結束，找到子集。綜上過程，得到的子集為SubS={3，24，115}。驗證正確。那麼該如何將這個問題變成一個可用的密碼體制？我們只需要將一個超遞增序列透過一些運算得到一個非超遞增序列（簡單的說，就是將超遞增序列偽裝成非遞增序列）。下面我們來介紹由這個問題產生的揹包公鑰密碼體制。2、揹包公鑰密碼體制透過上面的介紹，我們對於子集和問題有了一定的認識。那麼該如何偽裝？和以前一樣，我們先透過一個例子來大概瞭解下。例2：有超遞增序列r={3,11,24,50,115}，Alice選擇A=113，B=250。然後Alice透過下面的運算來偽裝該超遞增序列r。M=113r (mod 250)={89，243，212，150，245}。顯然M不是一個超遞增序列了。M就是公鑰。現在Bob要傳送一個訊息給Alice，這裡我們假設訊息內容x={1,0,1,0,1}（是一個二元字串）。然後S=xM=1*89+0*243+1*212+0*150+1*245=546。S即為密文。Alice接收到Bob傳送的密文S後，解密過程如下：。再透過超遞增序列，我們即可解密得到明文x了。下面給出該金鑰體制過程的描述。（1）Alice：選擇一個超遞增序列，選擇A和B，其中且gcd(A,B)=1。下面計算，。得到公鑰。（2）Bob：二元對字串明文x，用Alice的公鑰計算S=x*M。S是密文。（3）Alice解密：計算，再用超遞增序列的子集和問題解法求解，得到一個解x，該解即是明文。給出該公鑰密碼體制的JAVA實現。

揹包密碼體制是基於“子集之和問題”的難解性，開發出來的公鑰密碼體制。自身具有加解密速度快,揹包問題的NP完全性，易於軟硬體實施等諸多優點,非常適用於微機系統和分散式控制的加密,現在成為了全世界計算機密碼學研究的重點。