背包密码加密原理

明文 0 0 1 1 0 1
公钥 5 8 12 18 23 36

密文：12 + 18 + 36 = 66

密钥的产生

私钥的产生

（1）以超递增序列构建背包 eg. {2, 8, 18, 33, 65, 144}

（2）选定 m ，n，满足 m 大于递增背包所有元素之和，且 m 与n 互素。

公钥的产生

背包密码的公钥由私钥产生。

私钥: {$a_1$, $a_2$, $a_3$, $a_4$, $a_5$, $a_6$}, $m$, $n$ .

公钥: {$d_1$, $d_2$, $d_3$, $d_4$, $d_5$, $d_6$}

加密过程

（1） 将明文按照公钥序列的长度分组

（2）将序列位置对应为 1 的元素依次取出并求和，每一组皆如此

（3）得到密文c

解密过程

（1）先求出 n 在模 m 下的逆元 $n^{-1}$ 即 $n^{-1}\cdot n\ mod\ m = 1$

（2）求 $c\cdot n^{-1}\ mod\ m$

（3）根据递增背包的性质，则很容易求出二进制明文

代码部分：

判断互质

1
2
3
4
5
6
7
8
9
10
11
12
def judgeCoPrime(a, b):
    # 求最大公因数
    def maxCommonFactor(m, n):
        result = 0
        while  m % n > 0:
            result = m % n
            m = n
            n = result
        return result
    if maxCommonFactor(a, b) == 1:
        return True
    return False

求逆元

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def getInverse(a, b):
    # 扩展的欧几里得算法
    def extGcd(a_, b_, arr):
        if b_ == 0:
            arr[0] = 1
            arr[1] = 0
            return a_
        g = extGcd(b_, a_ % b_, arr)
        t = arr[0]
        arr[0] = arr[1]
        arr[1] = t - int(a_ / b_) * arr[1]
        return g
    # 求a模b的乘法逆x
    arr = [0,1,]
    gcd = extGcd(a, b, arr)
    if gcd == 1:
        return (arr[0] % b + b) % b
    else:
        return -1

初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 初始化
def init(length, interval):
    listV = []  # 超递增向量
    listV_b = []  # 每个元素对应的乘数
    bagCapacity = 1000  # 背包容积
    # 初始化超递增向量与listV_b
    for i in range(length):
        listV.append(sum(listV) + random.randrange(1, interval))
        listV_b.append(0)
    # 求超递增背包的解
    bagCapacityTmp = bagCapacity
    for i in range(len(listV)-1, -1, -1):
        if bagCapacityTmp >= listV[i]:
            bagCapacityTmp -= listV[i]
            listV_b[i] = 1  # listV_b 表示每个元素是否被选入背包
    return listV  # listV是超递增向量

生成密钥函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def creatPKey(listV):
    # listV = init()
    while True:
        k = int(input("输入私钥k(大于%d)：" % (sum(listV))))
        if k <= sum(listV):
            print("输入的k值不合法，请重新设置")
            continue
        while True:
            t = int(input("输入私钥t(与k互素)："))
            if not judgeCoPrime(k, t):
                print("输入的t与k值不互素，请重新输入")
                continue
            break
        break
    inverse_t = getInverse(t, k)
    return k, t, inverse_t

# 产生公钥：
def creatSKey(listV, t, k):
    sKeyList = []  # 公钥序列
    for i in listV:
        sKeyList.append(i * t % k)
    return sKeyList

加密函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 加密
def encrypt(massage, sKeyList):
    massageList = []    # 明文分组后的列表
    ciphertextList = []  # 存储密文的列表
    # 扩充明文消息串
    while len(massage) % len(sKeyList) != 0:
        massage = "0" + massage
    # 对明文进行分组
    for i in range(int(len(massage) / len(sKeyList))):
        start = (i * len(sKeyList))
        end = ((i + 1) * len(sKeyList))
        massageList.append(massage[start : end])
    # 采用内积和的方法加密
    for i in massageList:
        # 此处使用lambda时，要注意类型转换
        multiplyList = list(map(lambda x, y: int(x) * int(y), list(i), sKeyList))
        ciphertextList.append(sum(multiplyList))
    return ciphertextList

解密函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# 解密
def decrypt(massage, sKeyList, k, inverse_t):
    pliantextList = []  # 存储明文的列表
    reductListV = []  # 还原后的初始超递增向量
    # 还原超递增向量
    for i in sKeyList:
        reductListV.append(int(i) * inverse_t % k)
    # 计算出用于解密的临时背包容积
    bagCapacityList = []
    for i in massage:
        bagCapacityList.append(int(i) * inverse_t % k)
    # 利用求出的临时背包容积求解背包问题，结果即明文
    for bagCap in bagCapacityList:
        pliantextTmp = []   # 存储密文列表中每个密文解密后的序列
        for i in range(len(reductListV)):
            pliantextTmp.append(0)
        for i in range(len(reductListV) - 1, -1, -1):
            if bagCap >= reductListV[i]:
                bagCap -= reductListV[i]
                pliantextTmp[i] = 1
        pliantextList += pliantextTmp
    # 去除扩充的0并转换为字符串
    start, end = 0, 0
    for i in range(len(pliantextList)):
        if pliantextList[i] != 0:
            break
        end = i + 1
    del pliantextList[start : end]
    pliantextList = map(str, pliantextList)
    pliantext = "".join(pliantextList)
    return pliantext

实验测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
if __name__ == "__main__":
    # listV = [1, 3, 7, 13, 26, 65, 119, 267]
    length = int(input("输入超递增向量元素个数："))
    interval = int(input("输入随机增量："))
    # length, interval = 8, 4
    listV = init(length, interval)
    print("初始向量：", listV)
    k, t, inverse_t = creatPKey(listV)
    print("\n私钥验证成功，分别为  <k：%d>， <t：%d>，<t逆元：%d>" %(k, t, inverse_t))
    sKeyList = creatSKey(listV, t, k)
    print("公钥向量为：", sKeyList, "\n")
    while True:
        choice = input("1、加密    2、解密\n请选择：")
        if choice == "1":
            massage = input("输入明文（01序列）：")
            ciphertextList = encrypt(massage, sKeyList)
            print("加密结果：", ciphertextList)
        elif choice == "2":
            ciphertextList = list(map(int, list(input("输入密文：").split(","))))
            sKeyList = list(map(int, list(input("输入公钥向量：").split(","))))
            k = int(input("输入密钥k："))
            inverse_t = int(input("输入密钥t逆："))
            pliantext = decrypt(ciphertextList, sKeyList, k, inverse_t)
            print("解密结果：", pliantext)

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
import random

# 判断互质
def judgeCoPrime(a, b):
    # 求最大公因数
    def maxCommonFactor(m, n):
        result = 0
        while  m % n > 0:
            result = m % n
            m = n
            n = result
        return result
    if maxCommonFactor(a, b) == 1:
        return True
    return False

# 求逆元
def getInverse(a, b):
    # 扩展的欧几里得算法
    def extGcd(a_, b_, arr):
        if b_ == 0:
            arr[0] = 1
            arr[1] = 0
            return a_
        g = extGcd(b_, a_ % b_, arr)
        t = arr[0]
        arr[0] = arr[1]
        arr[1] = t - int(a_ / b_) * arr[1]
        return g
    # 求a模b的乘法逆x
    arr = [0,1,]
    gcd = extGcd(a, b, arr)
    if gcd == 1:
        return (arr[0] % b + b) % b
    else:
        return -1

# 初始化
def init(length, interval):
    listV = []  # 超递增向量
    listV_b = []  # 每个元素对应的乘数
    bagCapacity = 1000  # 背包容积
    # 初始化超递增向量与listV_b
    for i in range(length):
        listV.append(sum(listV) + random.randrange(1, interval))
        listV_b.append(0)
    # 求超递增背包的解
    bagCapacityTmp = bagCapacity
    for i in range(len(listV)-1, -1, -1):
        if bagCapacityTmp >= listV[i]:
            bagCapacityTmp -= listV[i]
            listV_b[i] = 1  # listV_b 表示每个元素是否被选入背包
    return listV  # listV是超递增向量

def creatPKey(listV):
    # listV = init()
    while True:
        k = int(input("输入私钥k(大于%d)：" % (sum(listV))))
        if k <= sum(listV):
            print("输入的k值不合法，请重新设置")
            continue
        while True:
            t = int(input("输入私钥t(与k互素)："))
            if not judgeCoPrime(k, t):
                print("输入的t与k值不互素，请重新输入")
                continue
            break
        break
    inverse_t = getInverse(t, k)
    return k, t, inverse_t

# 产生公钥：
def creatSKey(listV, t, k):
    sKeyList = []  # 公钥序列
    for i in listV:
        sKeyList.append(i * t % k)
    return sKeyList

# 加密
def encrypt(massage, sKeyList):
    massageList = []    # 明文分组后的列表
    ciphertextList = []  # 存储密文的列表
    # 扩充明文消息串
    while len(massage) % len(sKeyList) != 0:
        massage = "0" + massage
    # 对明文进行分组
    for i in range(int(len(massage) / len(sKeyList))):
        start = (i * len(sKeyList))
        end = ((i + 1) * len(sKeyList))
        massageList.append(massage[start : end])
    # 采用内积和的方法加密
    for i in massageList:
        # 此处使用lambda时，要注意类型转换
        multiplyList = list(map(lambda x, y: int(x) * int(y), list(i), sKeyList))
        ciphertextList.append(sum(multiplyList))
    return ciphertextList

# 解密
def decrypt(massage, sKeyList, k, inverse_t):
    pliantextList = []  # 存储明文的列表
    reductListV = []  # 还原后的初始超递增向量
    # 还原超递增向量
    for i in sKeyList:
        reductListV.append(int(i) * inverse_t % k)
    # 计算出用于解密的临时背包容积
    bagCapacityList = []
    for i in massage:
        bagCapacityList.append(int(i) * inverse_t % k)
    # 利用求出的临时背包容积求解背包问题，结果即明文
    for bagCap in bagCapacityList:
        pliantextTmp = []   # 存储密文列表中每个密文解密后的序列
        for i in range(len(reductListV)):
            pliantextTmp.append(0)
        for i in range(len(reductListV) - 1, -1, -1):
            if bagCap >= reductListV[i]:
                bagCap -= reductListV[i]
                pliantextTmp[i] = 1
        pliantextList += pliantextTmp
    # 去除扩充的0并转换为字符串
    start, end = 0, 0
    for i in range(len(pliantextList)):
        if pliantextList[i] != 0:
            break
        end = i + 1
    del pliantextList[start : end]
    pliantextList = map(str, pliantextList)
    pliantext = "".join(pliantextList)
    return pliantext

if __name__ == "__main__":
    # listV = [1, 3, 7, 13, 26, 65, 119, 267]
    length = int(input("输入超递增向量元素个数："))
    interval = int(input("输入随机增量："))
    # length, interval = 8, 4
    listV = init(length, interval)
    print("初始向量：", listV)
    k, t, inverse_t = creatPKey(listV)
    print("\n私钥验证成功，分别为  <k：%d>， <t：%d>，<t逆元：%d>" %(k, t, inverse_t))
    sKeyList = creatSKey(listV, t, k)
    print("公钥向量为：", sKeyList, "\n")
    while True:
        choice = input("1、加密    2、解密\n请选择：")
        if choice == "1":
            massage = input("输入明文（01序列）：")
            ciphertextList = encrypt(massage, sKeyList)
            print("加密结果：", ciphertextList)
        elif choice == "2":
            ciphertextList = list(map(int, list(input("输入密文：").split(","))))
            sKeyList = list(map(int, list(input("输入公钥向量：").split(","))))
            k = int(input("输入密钥k："))
            inverse_t = int(input("输入密钥t逆："))
            pliantext = decrypt(ciphertextList, sKeyList, k, inverse_t)
            print("解密结果：", pliantext)