CRYPTO-背包密码

admin
admin
admin
140350
文章
117
评论
2024年7月30日07:54:34评论30 views字数 6858阅读22分51秒阅读模式

在1978年，Merkle和Hellman两位杰出的密码学家正式提出了背包问题，并将其确立为一个重要且富有挑战性的研究课题。他们的这一贡献不仅深化了我们对背包问题的理解，也推动了密码学领域的发展。

Merkle和Hellman之所以将背包问题引入密码学领域，是因为他们发现了背包问题的特殊性质：即它具有天然的隐藏信息的潜力。通过精心构造背包问题的参数和条件，Merkle和Hellman设计出了一种基于背包问题的加密系统。这种系统可以将明文信息转化为背包中的物品组合，而解密过程则需要解决背包问题以恢复原始信息。

Merkle和Hellman的工作引起了密码学界的广泛关注。他们的研究不仅为背包问题在密码学中的应用奠定了理论基础，也为后续的研究者提供了宝贵的启示。越来越多的学者开始致力于背包问题的研究，探索其在密码学中的更多可能性。。

今天，就来深入探讨基于背包问题构造的密码——背包密码。

背包问题

我们都知道密码问题是依靠难解的问题来确保其加密性，背包问题就是背包密码的困难问题。问题如下：

假设一个背包的最多可以承重为W，有n个物体，重量分别为a1,a2,a3……,an,并且每个物品只能被装一次，问装哪些物品可以恰好使得背包装满。

用式子表达就是：

a为物体重量，b表示有或没有，即0或1，0表示没有，1表示有

背包问题是一个历史悠久且极具挑战性的数学问题。在这个问题中，我们有一个固定容量的背包和一系列不同重量的物品。目标是确定一个物品的组合，使得这些物品的总重量恰好等于背包的容量，同时每个物品只能被选择一次。这个问题的关键在于，随着物品数量和背包容量的增加，找到正确组合的难度会急剧上升，使得问题变得极为复杂和难以解决。

在背包密码的应用中，这个问题被巧妙地转化为加密和解密的过程。加密者可以利用背包问题的困难性，通过构造特定的背包和物品组合来隐藏明文信息。解密者则需要解决这个背包问题，才能恢复出原始的明文信息。由于背包问题的复杂性和难以预测性，使得背包密码具有很高的安全性，能够有效地抵御各种攻击。

背包密码

根据上面介绍的背包问题，我们精心构造了背包密码体系。在这个体系中，我们利用所有b的组合作为二进制表示的明文，而a的组合则构成了公钥。这样的设计使得背包密码具有高度的安全性，因为对于大多数人来说，背包难题几乎无法解决，从而无法破解出密文。所以我们也无法破解密文。为了使背包难题可以简单的解决，于是我们就要引入一个特殊的概念——超递增序列

超递增序列

要求序列中每一项都大于前面所有项之和，这样的序列我们称为超递增序列

例如[1,3,6,11,23,45]就是一个超递增序列

解决方法

如果a的组合为一个超递增序列，则an应该大于前面所有的数，因为b为0或1，a不是有就是没有，我们就将W与an进行比较分两种情况：

1、W大于或等于an

如果an没有，前面的所有项之和小于an不可能等于W，所以an一定有

2、W小于an

W小于an则必然是没有an的

于是通过比较W与an的大小判断出bn是0还是1，然后去掉an后对an-1同样操作，直到变成0为止

此外，因为an前面所有的数之和小于an，所以W的最大值不会大于或等于an的两倍，

例子

[1,3,6,11,23,45]为物体重量，背包承重为65，按照上面的方法判断，

[b1,b2,b3,b4,b5]应该为[0,1,1,1,0,1]

代码如下：

def resolve(a,w):b = []    for i in range(len(a)):        an=a[len(a)-i-1]        if w<an:b.insert(0,0)        else:            w=w-anb.insert(0,1)    return ba=[1,3,6,11,23,45]w=65resolve(a,w)#[0, 1, 1, 1, 0, 1]

超递增序列的引入，使得我们在设计背包密码时能够找到一个平衡点。它既保留了背包问题的难解性，保证了密码的安全性，又使得在合法持有者手中，解密过程变得相对简单。这种巧妙的设计使得背包密码成为一种既安全又实用的加密方式，为信息安全领域的发展做出了重要贡献。

值得注意的是，虽然超递增序列使得背包密码在某些情况下变得可解，但这并不意味着背包密码可以被轻易攻破。在实际应用中，我们还需要结合其他安全措施和技术手段，来确保背包密码的安全性得到充分保障。

背包加密

用私钥构建公钥

私钥：

•超递增序列[a1,a2,a3……，an]（所装物体重量）

•例如[1,3,6,11,23,45]

公钥：

•取模数m，要求m大于序列中所有数之和

•取临时密钥n，要求n与m互素

•d=n*amod m

•[d1,d2,d3……，dn]为公钥

•[1,3,6,11,23,45]为例，m取95，n取41，经计算得到的公钥为[41, 28, 56, 71, 88, 40]

脚本如下：

import gmpy2defcreate_pubkey(data,n,m):assert m>sum(data),gmpy2.gcd(n,m)==1    for i in range(len(data)):        data[i] = data[i] * n % m    print(data)    return data, m, ndata=[1,3,6,11,23,45]n=41m=95create_pubkey(data,n,m)#[41, 28, 56, 71, 88, 40]

用公钥进行加密

假如我们取一个二进制数据011001001011（不够可以补位），加密过程过程如下

•根据公钥是6位，将二进制数分为011001 001011分别加密

•公钥为[41, 28, 56, 71, 88, 40]

011001加密后为：28+56+40=124

001011加密后为：56+88+40=184

•密文为[124,184]

def encrypto(message,pubkey):cipher_list = []    for i in range(len(message)):        if message[i] == 1:           cipher_list.append(message[i] * pubkey[i])    cipher = sum(cipher_list)    print("加密后的密文为",cipher)    return ciphermessage=[0,1,1,0,0,1]pubkey=[41, 28, 56, 71,88, 40]encrypto(message,pubkey)#加密后的密文为 124

用私钥解密

当得到密文后，我们需要用私钥和前面的m和n进行解密，过程如下：

•计算出n的关于m的逆元（即n*n的逆元%m=1）

•将每个密文乘n的逆元在模m，就能用私钥进行求解

•仍以上面的数据为例:n的逆元为51，对密文进行处理

124*51%95=54

184*51%95=74

再用私钥[1,3,6,11,23,45]进行解密（比较an和W的那个方法）得到：

54=[0,1,1,0,0,1]*[1,3,6,11,23,45]

74=[0,0,1,0,1,1]*[1,3,6,11,23,45]

（注意这里不是对54,74进行二进制转换哦）

得到明文011001 001011

import gmpy2defdecrypto(cipher,n,m,private_key):phi_n=gmpy2.invert(n,m)    cip=cipher*phi_n%m    mes=resolve(private_key,cip)    print(mes)    return mesprivate_key=[1,3,6,11,23,45]cipher=124decrypto(cipher,n,m,private_key)

加密解密过程

import gmpy2#解决背包问题def resolve(a,w):    b = []    for i in range(1，len(a)):        an=a[len(a)-i-1]        if w<an:           b.insert(0,0)        else:            w=w-an           b.insert(0,1)    return b


#以私钥生成公钥

defcreate_pubkey(private_key,n,m):    pubkey=[]    for i in range(len(private_key)):       pubkey.append(1)    assert m>sum(private_key),gmpy2.gcd(n,m)==1    for i in range(len(private_key)):        pubkey[i] =private_key[i] * n%m    print('公钥为：',pubkey)    return pubkey


#用生成的公钥加密

defencrypto(message,pubkey):    cipher_list = []    for i in range(len(message)):        if message[i] == 1:           cipher_list.append(message[i] * pubkey[i])    cipher = sum(cipher_list)    print("加密后的密文为",cipher)    return cipher


#处理密文，再用私钥解密

defdecrypto(cipher,n,m,private_key):    phi_n=gmpy2.invert(n,m)    cip=cipher*phi_n%m    mes=resolve(private_key,cip)    print('明文为：',mes)    return mesprivate_key=[1,3,6,11,23,45]n=41m=95message=[0,1,1,0,0,1]pubkey=create_pubkey(private_key,n,m)cipher=encrypto(message,pubkey)mes=decrypto(cipher,n,m,private_key)

#公钥为： [41, 28, 56, 71, 88, 40]
#加密后的密文为 124
#明文为： [0, 1, 1, 0, 0, 1]

补充（一些可能有用的函数）

一些题目中可能会用到的函数

对乱序列表进行重排

#对乱序列表进行重排def relist(pub):    a = pub[:]    c = []    while a:  # 当a不为空时        current_min= min(a)       c.append(current_min)       a.remove(current_min)    return ca=relist(pub)

列表二进制转成十进制数字

deflist_to_int(a):m = 0    for i in range(len(a)):        m += a[i] * 2 **(len(a) - i - 1)    return m

对乱序背包密码进行解密

#对私钥重排def relist(pub):    a = pub[:]    c = []    while a:  # 当a不为空时        current_min= min(a)       c.append(current_min)       a.remove(current_min)    return c#解密def resolve(pub,a,w):    b=[]    for j in range(1,len(a)):        b.append(0)    for i in range(1,len(a)):        an=a[len(a)-i-1]        id=pub.index(an)        if w<an:            b[id:id+1]=[0]        elif w==an:            w = w - an            b[id:id + 1] = [1]        else:            w=w-an            b[id:id+1]=[1]    if w==0:        print('成功')    else:        print('失败,w=',w)    return bdef decrypto(pub,w):    a=relist(pub)    m=resolve(pub,a,w)    return mpub=[10256,299892 , 78079, 158237,  325493403,39577, 2705097, 5549493, 914840, 56822699, 109710911, 19185489]w=329321410m=decrypto(pub,w)print(m)#[1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0]

例题

DASCTF 2024暑期挑战赛

complex_enc

from Crypto.Util.number import * import random from secret import flag def GET_KEY(n):  sum=2     key=[1]     for i in range(n):         r=random.randint(0,1)         x=sum+random.randint(0,n)*r        key.append(x)         sum+=x     return key def enc(m,k):     cipher_list = []     for i in range(len(m)):        if m[i] == 1:            cipher_list.append(m[i] * k[i])     cipher = sum(cipher_list)     return cipher m=bytes_to_long(flag) m = [int(bit) for byte in flag for bit in format(byte, '08b')] key=GET_KEY(len(m)) c=enc(m,key) with open('output.txt', 'w') as f:     f.write(str(c))     f.write(str(key))

首先审计代码，可以看见定义了两个函数GET_KEY以及enc，分析两个函数的作用：

def GET_KEY(n):  sum=2     key=[1]     for i in range(n):         r=random.randint(0,1)         x=sum+random.randint(0,n)*r        key.append(x)         sum+=x     return key

这是一个生成长度为n的密钥的函数，先随机取第一个元素放到key中，同时用sum记录密钥中元素之和，这里的r会随机取0、1，使后面每次生成的元素可能是前面所有数之和，也可能会多一点，将生成的所有元素作为密钥中的元素再将生成的密钥加到key中，并用sum记录所有密钥元素之和，如此循环往复，可以生成一段超递增序列作为密钥。

def enc(m,k): cipher_list = []    for i in range(len(m)):        if m[i] == 1:           cipher_list.append(m[i] * k[i])    cipher = sum(cipher_list)    return cipher

这段加密函数的两个参数，都为列表，且m为由0,1组成的列表，后面对明文进行了处理变成了这个形式，然后这里m只有0,1，就相当于求m和k两个向量的数量积，将m为1的项与k对应的项相乘在求和得到密文。

m = [int(bit) for byte in flag if byte != 0 for bit in format(byte, '08b')]

这段代码会遍历flag 中的每一个字节，并将每个字节转换为8位的二进制字符串，然后将这个字符串中的每一位（作为一个字符）转换为整数，并将这些整数收集到一个列表中，也就是将flag的整形数字变为2进制再将每位存在一个列表中，且要注意，它的首位为0。

思路

这道题主要考察的是背包密码加密，而这里的密钥是一个超递增序列可以帮助我们去很方便的解决这个问题

如果a的组合为一个超递增序列，则第n项an应该大于前面所有的数，因为b为0或1，a不是有就是没有，我们就将W与an进行比较分两种情况：

1、W大于或等于an

如果an没有，前面的所有项之和小于an不可能等于W，所以an一定有

2、W小于an

W小于an则必然是没有an的

于是通过比较W与an的大小判断出bn是0还是1，然后去掉an后对an-1同样操作，直到变成0为止

此外，因为an前面所有的数之和小于an，所以W的最大值不会大于或等于an的两倍，

我们就根据这个思路往不断前推，直到背包里的东西全拿完。

我们就可以根据这个思路来解此题

exp：

from Crypto.Util.number import * #对私钥重排 def relist(pub):     a = pub[:]     c = []     while a:  # 当a不为空时         m = min(a)         c.append(m)        a.remove(m)    return c #解密 def resolve(pub,a,w):     b=[]     for j in range(1,len(a)):         b.append(0)     #用0填充方便后面替换     for i in range(1,len(a)):         an=a[len(a)-i-1]        id=pub.index(an)         if w<an:             None         else:             w=w-an             b[id:id+1]=[1]  #将0替换成1     if w==0:    #说明解密完成         return b def decrypto(pub,w):     a=relist(pub)     m=resolve(pub,a,w)     return m c=  key= m=decrypto(key,c) print(m) ml='' for i in range(len(m)):    ml+=str(m[i]) print(long_to_bytes(int(ml,2))) #b'DASCTF{you_kn0w_b@ckpack_Crypt0?}'

原文始发于微信公众号（火炬木攻防实验室）：CRYPTO-背包密码

免责声明:文章中涉及的程序(方法)可能带有攻击性，仅供安全研究与教学之用，读者将其信息做其他用途，由读者承担全部法律及连带责任，本站不承担任何法律及连带责任；如有问题可邮件联系(建议使用企业邮箱或有效邮箱,避免邮件被拦截，联系方式见首页)，望知悉。
  • 左青龙
  • 微信扫一扫
  • weinxin
  • 右白虎
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2024年7月30日07:54:34
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出)：
                   CRYPTO-背包密码http://cn-sec.com/archives/3005215.html
                  免责声明:文章中涉及的程序(方法)可能带有攻击性，仅供安全研究与教学之用，读者将其信息做其他用途，由读者承担全部法律及连带责任，本站不承担任何法律及连带责任；如有问题可邮件联系(建议使用企业邮箱或有效邮箱,避免邮件被拦截，联系方式见首页)，望知悉.

发表评论

匿名网友 填写信息