欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

背包公钥加密算法Python实现

程序员文章站 2022-07-09 13:46:09
...

本人研究生密码学的大作业

import itertools
import copy
# 从私钥构造公钥
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

# 将二进制数据进行加密
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

# 将加密后的数据进行解密
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


# 下面两个函数是用来求乘法逆元的
def EX_GCD(a,b,arr): #扩展欧几里得
    if b == 0:
        arr[0] = 1
        arr[1] = 0
        return a
    g = EX_GCD(b, a % b, arr)
    t = arr[0]
    arr[0] = arr[1]
    arr[1] = t - int(a / b) * arr[1]
    return g
def ModReverse(a,n): #ax=1(mod n) 求a模n的乘法逆x
    arr = [0,1,]
    gcd = EX_GCD(a,n,arr)
    if gcd == 1:
        return (arr[0] % n + n) % n
    else:
        return -1


if __name__ == "__main__":
    # 将函数生成的超递增序列进行赋值
    input_list = eval('['+input("请输入一个6位数的超递增序列:")+']')
    clear_txt = list(input("请输入要加密的二进制数据(6位):"))
    for t in range(len(clear_txt)):
        clear_txt[t] = int(clear_txt[t])
    my_key = copy.deepcopy(input_list)
    pubkey,m,n = create_pubkey(input_list)
    cipher = encryp(clear_txt,pubkey)
    # print(n,'模',m,'的乘法逆:',ModReverse(n,m))
    # n的逆元
    inv_n = ModReverse(n,m)
    decryption(cipher,my_key,m,inv_n)
    

相关标签: 密码学 密码学