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$，具体的格的方法有很多种，脚本内是其中的一种构造

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#

#!/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，然后通过简单运算可以得到结果

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#

# 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分钟的亚子。

# 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}

参考#

• 《Cryptanalysis of two knapsack public-key cryptosystems》
• http://www.dtc.umn.edu/~odlyzko/doc/arch/knapsack.survey.pdf
• https://0xdktb.top/2020/08/02/WriteUp-WMCTF2020-Crypto/
• https://blog.soreatu.com/posts/crypto-research-subset-sum-problem/