一、背包密碼體制介紹
提到背包密碼體制，我們首先就想到為什麼這個密碼體制和背包有什麼關系，背包二字的由來是因為在1978年Merkle與Hellman提出的MH背包問題，這個問題的總體思路是這樣的，現在有許多不同重量的物體，從中可以任意選擇n件物品放入背包。披露背包中物品的總重量和物品堆；但是所選項目的類型不是公開的。針對這種問題Merkle與Hellman合作設計了一種使用背包問題對資訊進行加密的方法，因為該加密算法涉及到背包問題，是以背包密碼是以得名。
https://link.juejin.cn?target= 二、背包加密算法原理
背包加密算法的總體思路是這樣的，假如A想發送一條資訊，A首先要具有私鑰，并且該密鑰是通過背包問題傳遞的，該私鑰可以生産一個公鑰，發送消息之前必須先使用公鑰進行加密，消息的合法接收者使用私鑰等已知資訊進行解密，這就是背包加密算法的總體思路。
三、背包加密算法步驟
https://link.juejin.cn?target= 3.1 構造遞增序列背包
在背包問題當中，若物品的重量清單是一個超遞增序列，這個問題是很容易的出答案的，解決超遞增序列的背包問題主要有以下幾個步驟：假如有一個背包，背包的重量已知，将這個背包的重量與我們已知的超遞增序列中的最大值進行比較，如果背包的重量小于這個數，那麼這個數不在背包中，如果重量大于或等于這個數，那麼這個數在背包中，用背包的重量減去這個數，得出的結果繼續與序列中的下一個數進行比較，重複比較直到比較完為止。如果背包的總重量減到0則該背包問題得出解，反之則無解。
3.2 以私鑰為基礎構造公鑰
3.3 使用公鑰進行加密
通過以私鑰為基礎構造公鑰，此時當我們拿到公鑰的時候，我們開始使用公鑰進行加密資料，假如我們拿到一個二進制的資料011000110101101110，背包加密算法對該二進制資料加密的主要流程是：
3.4 解密
四、背包密碼體制Python實作
https://link.juejin.cn/?target= 4.1 以私鑰構造公鑰
def create_pubkey(data):
# 構造m 此時m應大于超遞增序列的所有和
# m = sum(data) + 2
# m = 250
m = int(input("請輸入m: "))
# 構造n 這裡的n應當與m互素，這裡先取值為31
# n = 31
# n = 113
n = int(input("請輸入n: "))
# 将序列中的每一個值都乘以n
for i in range(len(data)):
data[i] = data[i] * n
# 序列中的每一個值都對m求餘
for j in range(len(data)):
data[j] = data[j] % m
print("構造的公鑰是{} ".format(data))
return data,m,n
4.2 實用背包密碼算法加密
# 核心代碼
# 将二進制資料進行加密
def encryp(clear_txt,pubkey):
# 定義 密文清單
cipher_list = []
for i in range(len(clear_txt)):
if clear_txt[i] == 1:
cipher_list.append(clear_txt[i] * pubkey[i])
# 密文的值
cipher = sum(cipher_list)
print("加密後的密文為{}".format(cipher))
return cipher
4.3 解密
# 将加密後的資料進行解密
def decryption(cipher,input_list,m,inv_n):
# 私鑰序列和
sumx = 0
# for i in cipher:
sumx = (inv_n * cipher) % m
# for k in range(len(input_list)):
result_list = []
clear_list = []
for s in range(0,7):
for p in itertools.combinations(input_list,s):
if sum(list(p)) == sumx:
result_list = list(p)
# print(result_list)
for l in input_list:
if l in result_list:
clear_list.append(1)
else:
clear_list.append(0)
result_str = ''
for t in clear_list:
result_str = result_str + str(t)
print("解密後的明文為{}".format(result_str))
return True
4.4 實作截圖
我們輸入一個超遞增序列：[2,3,6,13,27,52],m取105，n取31，輸入的m必須滿足大于超遞增序列的和，n必須與m互素，在進行試驗的時候出現了一個錯誤困擾了很久，後來才發現原來超遞增序列其實也是有要求的，那就是每一個元素的選取必須大于前面所有元素之和，這樣的序列才是超遞增序列，然後我們輸入明文資料：011011，輸出加密後的密文為313，公鑰為[62, 93, 81, 88, 102, 37]，機密後的明文為011011，具體截圖請見下圖。