密码学学习笔记 之 knapsack problem

 

ACM中的背包问题是一种组合优化的NP完全问题，而在密码学中，也有对背包问题的应用。

Subset-sum problems and knapsack cryptosystems

密码学中的利用knapsack problem的加密。大意就是，你公开一个序列，然后你把你的消息转为二进制，如果你消息的这一位是1，就从你序列中取出对应位置的值，最后密文就是你所有取出的值的和。

但是这样就产生一个问题，加密是加过去了。那该怎么解密呢？

蛮力攻击的时间复杂度是O(2^n),就算中途相遇也只能降低到O(2^(n/2))。太难了。。。

那Alice怎么解决这个问题呢？公钥密码系统如何体现呢？

这就看Alice对序列的选择了。她用的是超递增序列。什么是超递增序列呢？就是后一项≥前一项的两倍，也就意味着，后一项大于前面的所有项之和。

有超递增序列后，给你一个密文，你只需要一项一项对比过来，你就能知道加密者选取的元素是哪几个了。

这不难理解。我们将序列中的每一项放到二进制下就很明显。如果第一项的位长是2，那第二项的位长就至少是3，如果第二项位长是3，那么第三项的位长至少是4。如果你的密文最后是个2位长的，那加密者必定是没有用到第三项，必定是用到了第二项，至于有没有用到第一项，那就看密文减掉第二项之后还有没有剩下来了。【当然，这在每一项只能用一次的大前提下】

preparation

Alice准备加密了，首先她先整了一个超递增序列，r = (r1,r2…rn)，然后她生成了两个大数A和B，其中要求B>2rn 也就是B大于这个超递增序列之和啦。然后要需要gcd(A,B)=1，因为之后要求一个A在B下的逆。

encryption

Alice要加密了，她先用她的A和她的超递增序列生成一个新的序列M，其中Mi ≡ A·ri mod B

这个新的序列就是Alice的公钥了，她把这个序列甩给Bob，然后Bob按照之前描述的方式，用这个序列和他的明文生成密文S = x·M = sum{xi·Mi} ，
然后把这传给Alice

decryption

Alice要解密了，她拿到了这个密文S，然后计算

所以这个S’就是密文在超递增序列下的值了，之后再像之前那样判断一下这个S’和序列里面每一项的关系就能解出明文了。【记得从序列大的一端开始判断，如果满足关系别忘了减掉那一项再判断下一项】

伪代码走一波

for i in reverse(r):
    if s >= i:
        m = '1' + m
        s -= i
    else:
        m = '0' + m

table

来个总体流程

attention

同RSA一样，这里对参数的选择也要慎重，不然会出现许多出人意料的问题。

具体实例可参考BJD3rd-knapsack

这里由于对参数A的不当选择，导致序列中较小的项乘以A后并没有被B模掉，也就导致了参数A的泄露。

并且由于这里的超递增序列的生成规则过于简单，只是不断地整除2，所以攻击者能够利用加密后的序列轻易的计算出B来。

further more

之前提到Alice最开始整的一个无序的序列，由于这玩意儿没有陷门(trapdoor)，因此这无法成为一个密码系统。但自从有关LLL的paper发表后，基于背包的密码系统出现了一个大weakness，

这里简短的介绍下Eve怎么去解决这个无序序列的背包问题。不管是序列本身无序，还是超递增序列加密后显得无序的序列。

Eve先构造了一个矩阵

其中这个m1,m2,m3…就是那个无序序列，S就是密文

然后Eve从这个矩阵中，将每一条行向量划分出来，分别为V1,V2,…,Vn,Vn+1

我们现在假设向量x = (x1,x2,x3,…,xn) 是明文，(xi = 0 or 1)

那么这个格中就会有这么一条向量

这个t，因为2xi – 1 = ±1，所以t的模长是 √n，

根据Minkowskl’s First Theorem,

即对于任意n维满秩格基，都有

显然t是格L中的短向量。

所以，如果Eve知道如何找到lattice中的短向量，那么他就可以完成破解了。

关于找到lattice中短向量的算法我们称之为reduction algorithm，最著名的就是LLL algorithm了，然后它还有变体LLL-BKZ。

variant

再刚过去不久的2020RCTF中出现了一道有关knapsack problem 的变体，这里用的不是子集之和，而是子集之积

from Cryptodome.Util.number import bytes_to_long, getPrime
import random
import hashlib

sr = random.SystemRandom()
p = getPrime(120)
num = [sr.randint(1,p-1) for i in range(90)]
secret = sr.randint(0, 2**90)
r = 1
for i in range(90):
    if (secret >> i) & 1:
        r *= num[i]
        r %= p

flag = open("flag.txt","rb").read()
h = hashlib.sha256(str(secret).encode('utf-8')).digest()

print(p)
print(num)
print(r)
print(bytes_to_long(h)^bytes_to_long(flag))

蛮力攻击的时间复杂度是2的90次方，即使是中途相遇攻击的时间复杂度也仍然有2的45次方，于此同时还得考虑2的45次方的空间复杂度。

赛后看了国外大佬hellman的脚本才明白了本题的解法。

这一道题的切入点就在于模数p，通过不断地nc，直到获得的模数p具有p-1 smooth的性质（为了方便后面解离散对数），

这个时候再找到一个p的原根，然后对所有的数据利用pohlig算法解一个离散对数，就是开一个log，这样这个子集积的问题就能重新变回子集和的问题了。

from sage.all import *
import ast, sys, subprocess
import hashlib
from random import shuffle
from time import time

#不断nc以获取一个具有p-1 smooth性质的模数p
while True:
    data = subprocess.check_output("nc 124.156.133.6 22298 </dev/null", shell=True).splitlines()
    p = int(data[0])
    nums = ast.literal_eval(data[1].decode())
    r = int(data[2])
    encflag = int(data[3])


    fp1 = factor(p-1)
    print("p-1 =", fp1)

    if all(d < 2**50 for d, e in fp1):    #判断模数是否具有p-1 smooth的性质
        break
    print("too high factor of p-1")

# 解离散对数问题 -> 将子集积问题转化问子集和
F = GF(p)
g = F.primitive_element() #获取原根g
es = []
for num in nums:
    e = F(num).log(g)    #以原根为底数开log，因为循环群中所有的数都能以原根的整数幂次来表示
    print(num, "->", e)
    es.append(e)

r = F(r).log(g)
nums = es
mod = p - 1

#利用LLL解决0-1背包问题
N = 90

nums0 = nums[::]

BS = 30

itr = 0
while True:
    itr += 1
    print(itr, "BS", BS)
    t0 = time()

    nums = nums0[::]
    shuffle(nums)

    h = QQ(1)/2
    #  n1 1 0 0 0 0
    #  n2 0 1 0 0 0
    #  n3 0 0 1 0 0
    #  n4 0 0 0 1 0 
    #   r h h h h h
    # mod 0 0 0 0 0
    m = matrix(QQ, N+2, N+2)
    m.set_column(0, nums + [r, mod])
    m.set_row(N, [r] + [h] * (N+1))
    m[:N,1:N+1] = identity_matrix(N)

    m.set_column(0, 50*m.column(0))

    ml = (m*2).change_ring(ZZ).BKZ(block_size=BS)
    print("time %.3fs" % (time() - t0))

    for irow, row in enumerate(ml):
        if not (-1 <= min(row[:-1]) < max(row[:-1]) <= 1):
            continue
        if row[-1] < 0:
            row = -row
        print("GOOD", irow)
        secret = 0
        for i in range(N):
            if row[1+i] < 0:
                secret |= 1 << nums0.index(nums[i])
        print("secret", secret, "=", hex(secret))

        h = hashlib.sha256(str(secret).encode('utf-8')).digest()
        h = int.from_bytes(h, "big")
        flag = encflag ^ h
        print(int(flag).to_bytes(100, "big").strip(b"x00"))
        quit()

# RCTF{M4th_0f_MuLLLtiplication_2333}