超递增背包加解密基础实现

发表于 更新于 分类于
密码学作业罢了

超递增背包加解密基础实现

第4章 公钥密码体制.ppt 下载

超递增背包的最后一个新加入的数 必定大于 前面的所有数的和。

超递增背背包的放入和取出过程，可以理解为二进制数和十进制数的互转。

在此就不详细写算法原理过程了，百度即可。

代码

package.py 仅仅实现对单个数据加密。

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
import re
import random
import math

def check_package(package):
    sum=package[0]
    for i in range(1,len(package)):
        if sum > package[i]:
            return False
        sum += package[i]
    return True

def is_prime(num):
    if num > 1:  # 质数大于 1
        for i in range(2, num):  # 查看因子
            if (num % i) == 0:
                # print(num,"/",i,"=",num/i)
                return False
        else:
            return True
    else:
        return False

def selcet_M(package):
    i = package[-1] * 2
    max = i + 10 #在这里调整 M 的区间，同时影响 W 的值，太大了程序算不来
    M = random.randint(i, max)
    return M

def select_W(M):
    while True:
        W = random.randint(0, M)
        if math.gcd(W, M) == 1:
            return W

def get_pk(package, W, M):
    pb_package = []
    for b in package:
        pb_package.append(W * b % M)
    return pb_package

def encode():
    package = input("请输入背包,空格分开元素，格式为1 2 4 8\n> ")
    package = re.split(r" +", package.strip())
    for i in range(len(package)):
        package[i] = int(package[i])
    print(package)
    if not check_package(package):
        exit("你的输入不满足超递增背包的条件")
    M = selcet_M(package)
    W = select_W(M)
    public_k = get_pk(package, W, M)
    print("M:", M, "\nW:", W, "\npublic_k:", public_k)
    print("secret_k:", package, W, M)
    message = int(input("请输入待加密数字，应该小于背包容量"+str(sum(package))+"\n> "))
    if message>sum(package):
        exit("你输入的加密数字已大于背包的容纳量，请调整背包大小或者分批输入。")
    message = list(bin(message)[2:].zfill(len(package)))
    print(message)
    for i in range(len(message)):
        message[i] = int(message[i])
    cipher_li = []
    for m, k in zip(message, public_k):
            cipher_li.append(m * k)
    return sum(cipher_li) % M

def get_niyuan(W, M):
    niyuan = 1
    while (W * niyuan) % M != 1:
        niyuan += 1
    return niyuan

def decode():
    cipher = int(input("请输入解密的值\n> "))
    print("请输入私钥:W,M,package:")
    M = int(input("M: "))
    W = int(input("W: "))
    package = input("package:原背包,空格分开元素，格式为1 2 4 8\n> ")
    package = re.split(r" +", package.strip())
    for i in range(len(package)):
        package[i] = int(package[i])
    print(package)
    package_sum = get_niyuan(W, M) * cipher % M
    print("package_sum",package_sum)
    text = []
    for i in reversed(package):
        if i <= package_sum:
            text.append("1")
            package_sum -= i
        else:
            text.append("0")
    return int("".join(reversed(text)), 2)

if __name__ == "__main__":
    cipher = encode()
    print("加密后的值为：", cipher)
    print("-" * 10)
    message = decode()
    print("解密后的值为：", message)

运行

思考

现有背包package=[1,2,3,6,13,15]

首先，毫无疑问的是，背包加密输入的值应该是一个整数。然后以整数转二进制的类似形式转为背包公钥对应的二进制序列，且序列长度应和背包长度相同。所以：输入的整数应该小于sum(package) ，否则：将所有的package元素下标置1，背包也无法容纳这个数。也就是说，输入的加密值， 有区间！

那么问题来了，怎么对文件进行背包加密呢？也许可以对文件转16进制序列，构造一个sum(package) > F的背包，构造W和M即可。但是明显这样做的话package太小，易于破解。那么对文件转更高进制序列呢？或是还有其他方法，可以控制文件单元数据在背包区间内，然后流输入加密。

总之，如何用递增背包加密文件还可以深入学习一下。