knapack问题

一、总论

背包密码，利用的是子集和问题的困难性

给定一个正整数集合以及整数

求子集的和使得显然直接求解的时间复杂度是

即使使用MIMT攻击，也只能降到

这道题中n=160,无法求解

但如果定义在超级递增序列上，也就是满足的序列，那么有左边是一个跌进，求和得到于是有那这个性质就可以帮助解决背包问题了

如果 $说明里肯定有否则前面的和肯定小于然后扣掉，继续往下$ 小于自然就是没有了

算法（贪心算法）

for i in range(n, 0, -1):
    if S >= r[i]:
        S -= r[i]
        print(r[i])

但显然，问题不会这么简单的，我们可能得到的是混淆版本的背包问题，这就需要用到格了

二、Merkle–Hellman加密

私钥就是前面提到的超递增序列

但是为了看起来不那么明显，我们需要进行混淆

我们考虑生成一个模数m，满足然后一个与m互质的乘数w，那么这就实现了加密

公钥是构成的背包B以及m

假设Bob要加密x，那么那其实我们只要知道w的逆元自然就破解了注意到m显然大于所有之和，所以直接就是等于这就变成S'和a的背包问题了

三、使用lattice进行攻击

我们构造这样的格考虑线性组合 t显然是格中的向量，而且这里2x_1-1,2x2-1都是-1或者1

显然t的长度是相当小的,使用LLL算法，t应该就是最小的基

于是就回复出x了

要记得考虑模

来一道题

from random import *
from Crypto.Util.number import *
from secret import flag

assert flag[:5] == b'flag{' and flag[-1:] == b"}"

def enc(alist , p , m):
    mlen = len(m)
    m = bytes_to_long(m)
    mlist = [int(i) for i in bin(m)[2:].rjust(mlen*8 , '0')]
    c = 0
    for i in range(len(alist)):
        c += alist[i] * mlist[i]
        c %= p
    return c

def genkey(mlen , p):
    alist = []
    for i in range(mlen*8):
        alist.append(randint(1 , p))
    return alist


p = getPrime(256)

mlen = len(flag[5:-1])

alist = genkey(mlen , p)
c = enc(alist , p , flag[5:-1])
print(p)
print(c)
print(alist)

exp

B = []
n = len(B)
p = 67191628496712044464016024110365851526474838182599056919055439699452485213617
c = 54238895788223589463933244676602660551946397184772803204162347611363416949577
L = matrix.zero(n + 2)
for i in range(n):
    L[i,i] = 2
    L[i,-1] = B[i]
L[-2,-2] = 0
L[-2,-1] = p
L[-1,:] = 1
L[-1,-1] = c
res = L.LLL()
print(res[0])
t = res[0][:-2]
print(t)
m = ''
for i in t:
    if i == 1:
        m += '0'
    else:
        m += '1'
m = int(m,2)
flag = long_to_bytes(m)
print(flag)

这里要注意，可能得到的向量是-t，比如这里我们得到的res[0]

(1, -1, -1, 1, -1, 1, -1, -1, 1, -1, -1, 1, -1, -1, -1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 1, -1, -1, 1, -1, -1, -1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, -1, 1, -1, -1, 1, 1, 1, -1, -1, 1, -1, -1, 1, -1, 1, -1, -1, 1, 0)

倒二应该是-1，这里是1，所以我们都得取反

四、HGAME

from Crypto.Util.number import *
import random
from Crypto.Cipher import AES
import hashlib
from Crypto.Util.Padding import pad
from secrets import flag

list = []
bag = []
p=random.getrandbits(64)
assert len(bin(p)[2:])==64
for i in range(4):
    t = p
    a=[getPrime(32) for _ in range(64)]
    b=0
    for i in a:
        temp=t%2
        b+=temp*i
        t=t>>1
    list.append(a)
    bag.append(b)
print(f'list={list}')
print(f'bag={bag}')

key = hashlib.sha256(str(p).encode()).digest()
cipher = AES.new(key, AES.MODE_ECB)
flag = pad(flag,16)
ciphertext = cipher.encrypt(flag)
print(f"ciphertext={ciphertext}")

这里的p就是x，然后这里没有模了，所以不需要p那一行

这里好像直接求逆矩阵就行？

显然不行，这里A是64x4都不满秩，在想什么？

那只能造格了先用一组看看，发现每组都不一样，于是四组一起上这里必须用bkz，LLL精度不够

n = len(list[0])
L = matrix.zero(n + 1,n+4)
l = 10^50
for i in range(n):
    L[i,i] = 2
    L[i,-4] = l*list[0][i]
    L[i,-3] = l*list[1][i] 
    L[i,-2] = l*list[2][i] 
    L[i,-1] = l*list[3][i] 
L[-1, :] = 1
L[-1, -4] = l*bag[0]
L[-1, -3] = l*bag[1]
L[-1, -2] = l*bag[2]
L[-1, -1] = l*bag[3]
t = L.BKZ()
p = ''
for v in t:
    if v[-1] == 0 and 3 not in v and 2 not in v:
        print(v)
        v = v[:-4]
        for i in v:
            if i == 1:
                p += '1'
            else:
                p += '0'
        p = p[::-1]
        p = int(p,2)
        print(p)
key = hashlib.sha256(str(p).encode()).digest()
cipher = AES.new(key, AES.MODE_ECB)
flag = cipher.decrypt(ciphertext)
flag = unpad(flag,16)
print(flag)