為什么要用背包密碼體制設(shè)計密碼？

一個經(jīng)典的密鑰體制--背包公鑰密碼體制。在介紹該問題之前，先介紹下子集和問題。1、子集和問題假設(shè)在整數(shù)域上有集合S=｛a,b,c,d,e,f.....｝和一個整數(shù)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是超遞增的，那么什么是超遞增序列呢？首先我們給出超遞增序列的定義。超遞增序列指的是這樣的一個集合，其中。超遞增序列具有什么好處呢？由其定義，我們可以知道它具有這樣的一個性質(zhì)：。這個性質(zhì)對于求解子集和問題是多有幫助呢？筆者下面通過一個例子來給大家演示下超遞增序列的子集和問題的解決辦法。例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選中，算法結(jié)束，找到子集。綜上過程，得到的子集為SubS={3，24，115}。驗證正確。那么該如何將這個問題變成一個可用的密碼體制？我們只需要將一個超遞增序列通過一些運算得到一個非超遞增序列（簡單的說，就是將超遞增序列偽裝成非遞增序列）。下面我們來介紹由這個問題產(chǎn)生的背包公鑰密碼體制。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就是公鑰。現(xiàn)在Bob要發(fā)送一個消息給Alice，這里我們假設(shè)消息內(nèi)容x={1,0,1,0,1}（是一個二元字符串）。然后S=xM=1*89+0*243+1*212+0*150+1*245=546。S即為密文。Alice接收到Bob發(fā)送的密文S后，解密過程如下：。再通過超遞增序列，我們即可解密得到明文x了。下面給出該密鑰體制過程的描述。（1）Alice：選擇一個超遞增序列，選擇A和B，其中且gcd(A,B)=1。下面計算，。得到公鑰。（2）Bob：二元對字符串明文x，用Alice的公鑰計算S=x*M。S是密文。（3）Alice解密：計算，再用超遞增序列的子集和問題解法求解，得到一個解x，該解即是明文。給出該公鑰密碼體制的JAVA實現(xiàn)。