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)