背包密码

N1Key2023/5/12大约 4 分钟背包密码

什么是背包问题

背包问题属于 NP-完全问题

1978年，Merkel 和 Hellman 基于背包（knapsack）问题提出了一种公钥密码体制，称为 MH 体制，其显著特点就是加解密速度快。遗憾的是，这类密码体制所基于的背包问题在通常情况下都能转化为格中的最短向量（或者最近向量）问题，进而用格基约化算法进行求解，因此这类密码体制在现实中是不安全的。

背包问题：给定 n 个正整数 $a_{1}, a_{2}, . . ., a_{n}$ 及一个正整数 s ，已知 s 是某些 $a_{i}$ 之和，试确定这些 $a_{i}$ ，把这个问题称为背包问题。

利用背包问题，可以得到一个加密方法。将 $a_{1}, a_{2}, . . ., a_{n}$ 公开，设 $(m_{1}, m_{2}, . . ., m_{n})$ 为明文， $m_{i} \in (0, 1)$ , 令： $s = \sum_{i = 1}^{n} m_{i} a_{i}$

将 s 作为密文，他是 $a_{1}, a_{2}, . . ., a_{n}$ 的一个部分和。从 s 求解明文就相当于解背包问题。不过对于一般的 $a_{1}, a_{2}, . . ., a_{n}$ 这时合法的接收方也同样难于解密，所以不能用一般的 $a_{1}, a_{2}, . . ., a_{n}$ 设计密码。

超递增序列：
当 $a_{1} < a_{2}, a_{1} + a_{2} < a_{3}, . . ., a_{1} + a_{2} + . . . + a_{n - 1} < a_{n}$ ，这时称 $a_{1}, a_{2}, . . ., a_{n}$ 为超递增序列。

设 $a_{1}, a_{2}, . . ., a_{n}$ 为超递增序列，如果以它为公钥，以 $s = \sum_{i = 1}^{n} m_{i} a_{i}$ 作为明文 $(m_{1}, m_{2}, . . ., m_{n})$ 的密文，则任何人都会从 s 解出 $(m_{1}, m_{2}, . . ., m_{n})$ ，所以这样做不行，必须设法将 $a_{1}, a_{2}, . . ., a_{n}$ 隐藏起来。

1、取正整数 m ,使 $m > a_{1} + a_{2} + . . . + a_{n}$ ,再取正整数 u，使 u 与 m 互素。u 和 m 作为密钥只有接收方知道，令: $b_{i} \equiv u a_{i} (m o d m) ， i = 1, 2, . . ., n$

2、将 $b_{1}, b_{2}, . . ., b_{n}$ 作为公钥，若 $(m_{1}, m_{2}, . . ., m_{n})$ 为明文，令： $s = \sum_{i = 1}^{n} m_{i} b_{i}$ 为密文，发送方将 s 发给接收方。

3、接收方利用辗转相除法可以找到 w，使 $u w \equiv 1 (m o d m)$ ,因为 u 与 m 互素，在接收到 s 后，可以算出 (sw)，使 $s w \equiv (s w) (m o d m)$ ，且 $0 < (s w) < m$ ，则

$s w \equiv \sum m_{i} w u a_{i} \equiv \sum_{i = 1}^{n} m_{i} a_{i} (m o d n)$

显然 $\sum m_{i} a_{i} < \sum a_{i} < m ，可见 \sum m_{i} a_{i} = (s w)$ ，这是一个超递增背包问题，很容易解出明文 $(m_{1}, m_{2}, . . ., m_{n})$

例题：[2022祥云杯] fill

格参考文章： https://www.ruanx.net/lattice-2/

from Crypto.Util.number import *
from random import *
from gmpy2 import gcd
from numpy import dot

nbits = 32
msg = getRandomNBitInteger(nbits)
flag = b'flag{sha256(msg)}'
tmp_m = bin(msg)[2:]
f_list = []
for i in range(len(tmp_m)):
    f_list.append(int(tmp_m[i]))

r_list =[randint(20, 50)]
for i in range(nbits - 1):
    r_list.append(randint(2 * r_list[-1], 3 * r_list[-1]))

while True:
    A = randint(2 * r_list[-1] + 1, 3 * r_list[-1])
    B = randint(2 * r_list[-1] + 1, 3 * r_list[-1])
    if gcd(A, B) == 1:
        break

M = [A * x % B for x in r_list]

S = dot(f_list, M)
print(S)

seed = getRandomNBitInteger(30)
s = [0] * nbits
s[0] = seed
m = getRandomNBitInteger(20)
c = getPrime(24)
n = 991125622
for i in range(1, nbits):
    s[i] = (s[i-1]*m+c)%n
print(s[0], s[1], s[2])
for t in range(nbits):
    M[t] = M[t] + s[t]
print(M)


'''
492226042629702
562734112 859151551 741682801
M = [19621141192340, 39617541681643, 3004946591889, 6231471734951, 3703341368174, 48859912097514, 4386411556216, 11028070476391, 18637548953150, 29985057892414, 20689980879644, 20060557946852, 46908191806199, 8849137870273, 28637782510640, 35930273563752, 20695924342882, 36660291028583, 10923264012354, 29810154308143, 4444597606142, 31802472725414, 23368528779283, 15179021971456, 34642073901253, 44824809996134, 31243873675161, 27159321498211, 2220647072602, 20255746235462, 24667528459211, 46916059974372]
'''

EXP:

先用 LCG线性同余生成器，利用 s2,s1,s0 求出 s 和 M

from gmpy2 import *


# LCG算法解线性同余方程，求出 s 和 M
n = 991125622
s0, s1, s2 = 562734112, 859151551, 741682801
m = (s2 - s1) * invert(s1 - s0, n) % n
# print(m)
c = (s1 - m * s0) % n
assert is_prime(c)

nbits = 32
s = [0] * nbits
s[0] = s0
for i in range(1, nbits):
    s[i] = (s[i - 1] * m + c) % n

M = [19621141192340, 39617541681643, 3004946591889, 6231471734951, 3703341368174, 48859912097514, 4386411556216,
     11028070476391, 18637548953150, 29985057892414, 20689980879644, 20060557946852, 46908191806199, 8849137870273,
     28637782510640, 35930273563752, 20695924342882, 36660291028583, 10923264012354, 29810154308143, 4444597606142,
     31802472725414, 23368528779283, 15179021971456, 34642073901253, 44824809996134, 31243873675161, 27159321498211,
     2220647072602, 20255746235462, 24667528459211, 46916059974372]
for t in range(nbits):
    M[t] = M[t] - s[t]
# print(M)

然后用 LLL 算法解背包加密

from hashlib import sha256
M = [19620578458228, mpz(39616682530092), mpz(3004204909088), mpz(6231457508054), mpz(3702963666023), mpz(48859283851499), mpz(4385984544187), mpz(11027662187202), mpz(18637179189873), mpz(29985033726663), mpz(20689315151593), mpz(20060155940897), mpz(46908062454518), mpz(8848251127828), mpz(28637097081675), mpz(35930247189963), mpz(20695167327567), mpz(36659598017280), mpz(10923228050453), mpz(29810039803392), mpz(4443991557077), mpz(31801732862419), mpz(23368424737916), mpz(15178683835989), mpz(34641771567914), mpz(44824471397533), mpz(31243260877608), mpz(27158599500744), mpz(2219939459559), mpz(20255089091807), mpz(24667494760808), mpz(46915118179747)]
S = 492226042629702

n = len(M)
L = matrix.zero(n + 1) # 构造n+1 阶0矩阵

for row, x in enumerate(M):
    L[row, row] = 2
    L[row, -1] = x

L[-1, :] = 1
L[-1, -1] = S
res = L.LLL()
print(-res[0]) #注意这里反向量才是解，2x_i - 1 = res[i]
msg = ""
for i in -res[0]:
    if int(i)==-1:
        msg += '0'
    if int(i)== 1:
        msg += '1'
print(msg)        
print('flag{' + sha256(str(int(msg,2)).encode('utf-8')).hexdigest() +"}")