1977年，Merkle與Hellman合作設計了使用背包算法，該算法提出後密碼學界提出了很多背包型加密算法。
基本介紹
- 中文名：Merkle-Hellman背包算法
- 設計者：Merkle與Hellman
- 方法：背包問題實現信息加密
- 年代：1977年
簡介,分類,破解方法,套用領域,
簡介
其工作原理是：假定甲想加密，則先產生一個較易求解的背包問題，並用它的解作為專用密鑰；然後從這個問題出發，生成另一個難解的背包問題，並作為公共密鑰。如果乙想向甲傳送報文，乙就可以使用難解的背包問題對報文進行加密，由於這個問題十分難解，所以一般沒有人能夠破譯密文；甲收到密文後，可以使用易解的專用密鑰解密。
但是，在它發表幾年後，就找到了攻破它的方法。即使如此，它仍然代表著一類很難問題的算法。
分類
背包加密分為加法背包和乘法背包。
1、加法背包：我們知道，1<2,1+2<4,1+2+4<8,1+2+4+8<16,……，那么如果我們選擇這樣一些數，這些數從小到大排列，如果前面所有的數加起來的值總小於後面的數，那么這些數就可以構成一個背包，我們給一個這個背包裡面的某些數的和，這個數就是被加密的數，由這個背包組成這個數只有一種組合方式，這個方式就是秘密了，例如給大家一個封包（2，3，6，12，24，48），由這個背包里的某些數構成的數：86，你知道86怎么來的嗎？當然，你看著背包裡面的內容，可以知道是由2+12+24+48得到的，如果你沒有這個背包，而是直接得到這個86，你知道組成這個86的最小的數是多少嗎？你無法知道，因為加起來等於86的數非常多：85+1=86，84+2=86等等，你是無法知道的，所以，背包加密非常難破。
2、乘法背包：乘法背包比加法背包更複雜，不僅是運算量大了很多，更重要的是你得到的一個被加密了的數據更大，一般都是上億的，而且在許多機密的機關裡面，背包的數據都不是有這個單位，而是用位。我們知道，1<2,1*2<3,1*2*3<7,1*2*3*7<43,1*2*3*7*42<1765, 數字的增長還是很快的，之所以複雜，就是因為數字很大啊！背包的特點是：如果背包裡面的數據按小到大排列，那么，前面所有數據的乘積小於後面的任何一個元素，這個就是背包的特點，是不是很簡單，但是要知道乘積的數字的增長是非常快的！
破解方法
背包加密是一種相當高級的加密方式，不容易破解，而且還原也相對容易，因此採用這種加密方式加密遊戲數據也是非常好的，只要知道背包，就可以輕易算出來。
這么複雜的加密，怎么解密？有如下兩中破解方法： 1.利用孤立點破解；2.利用背包破解。 所謂孤立點，還是以上面的背包為例子，我們可以把密碼設為a，看看得到了什麼密碼？1，如果我們把密碼設為b，得到的密碼為2，同理，可以把背包裡面的所有元素都利用孤立點的方法全部枚舉出來，這樣我們就把背包弄到手了，對下面的破解就不成問題了，是不是很簡單？其實在加密的時候，也許它們會利用異或運算先加密一下，再利用背包加密，這樣更難破，孤立點方法非常有效，但是不是萬能的，要結合前面的方法配合使用！ 利用背包，這個就簡單了，想一想，要加密也得有背包才能完成加密啊，要解密也要背包啊，這就是說，不管是用戶端，還是伺服器端，都會有該背包的，找到該背包不是就解決問題了嗎？怎么找？大家可以稍微找一些書籍學習一下。首先是要了解進制，特別是十六進制、二進制和十進制及其之間的轉換。這些加密方法在大學應該會接觸的。
套用領域
很多數據都需要加密，例如銀行的數據、網路遊戲、軍事機構、行政機構以及其他重要場所。不過雖然這種加密效果非常好，但是加密的程度太大也不現實，一般不會有非常複雜的加密，如果一個數據就幾百位，而且還用非常規進制，那么可以想像電腦要算多久啊，會多么影響速度啊！
