0%

Knapsack Problem

最近经常碰到背包问题,所以稍微整理一下

问题描述#

一般我们碰到的都是0 1背包问题,如下,我们已有数字$a_1,a_2…a_n$,从中给它们分别赋予0或者1的权重$w_i$,使得最终的和为$W$,即

$$\sum_1^n w_ia_i = W$$

而在这类问题中,当$n$较大时就是一个$2^n$复杂度的NP问题

解法#

主要通过构造LLL格解决,目前的解法对Knapsack Problem的密度要求为$\frac{n}{log_2(max(pb))}< 0.9408$,具体的格的方法有很多种,脚本内是其中的一种构造

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
from sage.all import *

pk = # public key
ct = # ciphertext
print(ct)
print(len(pk))
n = len(pk)

# Sanity check for application of low density attack
d = n / log(max(pk), 2)
print(CDF(d))
assert CDF(d) < 0.9408

M = Matrix.identity(n) * 2

last_row = [1 for x in pk]
M_last_row = Matrix(ZZ, 1, len(last_row), last_row)

last_col = pk
last_col.append(ct)
M_last_col = Matrix(ZZ, len(last_col), 1, last_col)

M = M.stack(M_last_row)
M = M.augment(M_last_col)

X = M.BKZ()

sol = []
for i in range(n + 1):
testrow = X.row(i).list()[:-1]
if set(testrow).issubset([-1, 1]):
for v in testrow:
if v == 1:
sol.append(0)
elif v == -1:
sol.append(1)
break

s = sol
print(s)

2020 天翼杯 alicehomework#

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
#!/usr/bin/python
from Crypto.Util.number import *
import random
import gmpy2
from secret import flag

def generateKey(bitlen):
u = 2
v = 200
seed = random.randint(3**bitlen,4**bitlen)
sequence = [seed]
s = seed
for i in range(1,bitlen):
seed = random.randint(s + v, u*(s+v))
sequence.append(seed)
s += seed
q = random.randint(s+v, u*(s+v))
r = random.randint(1, q)
while gmpy2.gcd(r, q) != 1:
r = random.randint(1, q)
key = [ r*w % q for w in sequence]
return key


def encrypt(msg, pubKey):
msg_bit = msg
n = len(pubKey)
cipher = 0
i = 0
for bit in msg_bit:
cipher += int(bit)*pubKey[i]
i += 1
return bin(cipher)[2:]

msg = bin(bytes_to_long(flag))[2:]
key = generateKey(len(msg))
enc = encrypt(msg, key)
print key
print int(enc, 2)

从加密的函数看就是01背包问题了,并且给出了公钥和最后的密文,直接带入脚本求出二进制bit,然后通过简单运算可以得到结果

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
from sage.all import *
from Crypto.Util.number import long_to_bytes
pk =
ct =
n = len(pk)

# Sanity check for application of low density attack
d = n / log(max(pk), 2)
print(CDF(d))
assert CDF(d) < 0.9408

M = Matrix.identity(n) * 2

last_row = [1 for x in pk]
M_last_row = Matrix(ZZ, 1, len(last_row), last_row)

last_col = pk
last_col.append(ct)
M_last_col = Matrix(ZZ, len(last_col), 1, last_col)

M = M.stack(M_last_row)
M = M.augment(M_last_col)

X = M.BKZ()

sol = []
for i in range(n + 1):
testrow = X.row(i).list()[:-1]
print(testrow)
if set(testrow).issubset([-1, 1]):
for v in testrow:
if v == 1:
sol.append(0)
elif v == -1:
sol.append(1)
break

s = sol
print(s)
result = [pow(2,len(s)-1-i)*s[i] for i in range(len(s))]
print(long_to_bytes(sum(result)))
# flag{8130e8c14fe4df06558c0a7ebf06f272}

2020 WMCTF babysum#

1
2
3
4
5
6
7
8
9
10
11
12
13
# task.py
from json import dump
from random import SystemRandom

random = SystemRandom()

k, n, d = 20, 120, 0.8

B = 2**(n/d)
A = [random.randint(1, B) for _ in range(n)]
s = sum(A[index] for index in random.sample(range(n), k))

dump((s, A), open("data", "w"))

看了看密度是$0.8<0.9408$,以为用前面的脚本也是可以一把梭,结果改了好多格的构造都不行,最后发现是自己一直都没注意一些东西:比如格求解的条件啊啥的。https://0xdktb.top/2020/08/02/WriteUp-WMCTF2020-Crypto 里写的比较好,但大部分人都是看了出题人的博客2333 https://blog.soreatu.com/posts/crypto-research-subset-sum-problem/。

不过即使看到了博客上的源码,跑这个也是费时费钱。。。听说babysum的大哥sum得100核的机器上跑一个小时才出结果。穷苦人家的孩子只能用四核跑一下babysum,大概15分钟的亚子。

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
# sage
import random
import multiprocessing as mp
from json import load
from functools import partial


def check(sol, A, s):
"""Check whether *sol* is a solution to the subset-sum problem.
"""
return sum(x*a for x, a in zip(sol, A)) == s


def solve(A, n, k, s, ID=None, BS=22):
N = ceil(sqrt(n)) # parameter used in the construction of lattice
rand = random.Random(x=ID) # seed

lat = []
for i,a in enumerate(A):
lat.append([1*(j == i) for j in range(n)] + [N*a] + [N])
lat.append([0]*n + [N*s] + [k*N])

itr = 0
start_time = cputime()
while True:
# 1. initalization
t0 = cputime()
itr += 1
# print(f"[{ID}] n={n} Start... {itr}")


# 2. Zero Force
# (k+1) * (k+2)
# 1 0 ... 0 a0*N N
# 0 1 ... 0 a1*N N
# . . ... . ... .
# 0 0 ... 1 a_k*N N
# 0 0 ... 0 s*N k*N


# 3. Randomly shuffle
l = lat[::]
shuffle(l, random=rand.random)

# 4. BKZ!!!
m = matrix(ZZ, l)
t_BKZ = cputime()
m_BKZ = m.BKZ(block_size=BS)
print(f"[{ID}] n={n} {itr} runs. BKZ running time: {cputime(t_BKZ):.3f}s")


# 5. Check the result
# print(f"[{ID}] n={n} first vector norm: {m_BKZ[0].norm().n(digits=4)}")
for i, row in enumerate(m_BKZ):
if check(row,A,s) and row.norm()^2 == k:
print(row)
return True


def main():
CPU_CORE_NUM = 4

k,n= 20,120
s,A = load(open('data','r'))
solve_n = partial(solve,A,n,k,s)
with mp.Pool(CPU_CORE_NUM) as pool:
reslist = pool.imap_unordered(solve_n,range(CPU_CORE_NUM))
for res in reslist:
if(res):
pool.terminate()
break

if __name__ == "__main__":
main()
'''
(0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0)
/Applications/SageMath-9.0.app/sage babysum.sage 3929.59s user 111.40s system 399% cpu 16:52.48 total
'''

然后丢进check.py,可以得到WMCTF{83077532752999414286785898029842440}

参考#

坚持原创技术分享,您的支持将鼓励我继续创作!