背包密码

发表于 2024-07-29 阅读次数： Waline：本文字数： 3.5k 阅读时长 ≈ 13 分钟

背包密码学习过程

始发于2023年8月2日，于2024年7月29日更新

在学习背包密码之前，我们需要了解什么是背包问题

背包问题

假定一个背包可以承重$S$，现在有$n$个物品，其重量分别为$a_1,a_2\dots a_n$，试问装哪些物品可以恰好使得背包被装满，而且每个物品最多被装一次。转化成数学式子即是
$$
x_1a_1+x_2a_2+\dots+x_na_n=S
$$
其中$x_i=0或1$

显然我们必须枚举所有的 n 个物品的组合才能解决这个问题，而复杂度也就是$2^n$，这也就是背包加密的妙处所在。

在谈加密过程之前，先了解一下超递增序列

超递增序列

$\begin{Bmatrix}a_1,a_2,\dots,a_n\end{Bmatrix}$是超递增序列，指的是$a_i>a_1+a_2+\dots+a_{i-1}$，即第$i$个数大于前面$i-1$个数之和，也即$a_i>2a_{i-1}$

当明文和超递增序列依次相乘再求和时
$$
x_1a_1+x_2a_2+\dots+x_na_n=S,x_i=
\begin{Bmatrix}
0,1
\end{Bmatrix},
a_i>0
$$
我们可以通过依次比较S与序列中最大的元素大小关系，来确定该元素性质

例如，当$S>a_n$时，说明$x_n=1$

接下来，令$S=S-a_n$，再比较$S$与$r_{n-1}$

通过n次比较，我们即可获得所有x的值

背包加密

背包加密算法流程如下:

加密过程

明文

明文字符串转成二进制，生成明文序列$x = (x_1,x_2,…,x_n),x_i \in (0,1)$

私钥

生成一个超递增序列$r = (r_1,r_2,…,r_n)$作为私钥序列

公钥

生成模数$B$，满足

$$
B>\sum_{i=1}^{n}r_i
$$

即满足$B > 2r_n$，因为$r$是个超递增序列
生成乘数$A$，满足$gcd(A,B)=1$
生成公钥序列$M=\begin{Bmatrix}M_1,M_2,\dots,M_n\end{Bmatrix}$，其中$M_i \equiv Ar_i \mod B$

密文

通过以下式子生成密文
$$
S = \sum_{i=1}^{n}x_iM_i
$$

最后公开$M,A,B,S$

解密过程

计算$A$关于模$B$的逆元$A^{-1}$
计算$S’$

$$
S’\equiv A^{-1}S \equiv A^{-1}\sum_{i=1}^nx_iM_i\equiv A^{-1}\sum_{i=1}^nx_iAr_i \equiv \sum_{i=1}^nx_ir_i \mod B
$$

利用超递增序列$r$的性质，求解明文的二进制
最后把二进制转为字符串

攻击

参数不当

如果乘数$A$，超递增序列$r$的大小选取不当，使得$Ar_i<B$，则$Ar_i \mod B = Ar_i$，这就导致公钥序列$M$是个很明显的超递增序列。

DASCTF5月赛——knapsack

题目：

from Crypto.Util.number import *
from functools import reduce

def genKey(length):
    A, B = getPrime(64), getPrime(1025)
    Rn = getPrime(1024)
    key1 = [Rn//2**i for i in range(1, length+1)]
    key2 = [i*A % B sfor i in key1]
    return key1,key2


def encrypt(text,key):
    Sum=0
    for i in range(len(text)):
        Sum+=int(text[i])*key[i]
    return Sum

def save(Ciper,Key):
    f1=open("pub.txt","w")
    for i in range(len(Key)):
        f1.write(str(Key[i])+'n')
    f2=open("cip.txt","w")
    f2.write(hex(Ciper))


FLAG = bin(bytes_to_long(flag.encode()))[2:]
Key1,Key2 = genKey(len(FLAG))
Ciper = encrypt(FLAG,Key1)
save(Ciper,Key2)

首先注意到key1是个超递减的序列，而且乘数A非常小。

所以$A$和序列中两个最小值相乘的结果很有可能小于$B$，这样我们可以通过序列中两个最小值求$gcd$来获得$A$，

我们先假设最小的是$a_0$，$a_0-a_n$依次增大

如果能找到两个数满足$a_{i+1}<a_i$，这就说明从$a_i$到$a_{i+1}$存在一次模运算

$A \times a_{i+1}=A \times 2a_i \mod B$

所以有$B = A(2a_i-a_{i+1})$

参考：DASCTF五月月赛暨 BJDCTF 3rd 部分WP-安全客 - 安全资讯平台 (anquanke.com)

背包问题通解

当密度$d = \frac{len(M)}{log_2(max(M_i))}<0.9408$时，LLL算法能通杀这类背包问题

用公钥序列$M= (M_1,M_2,…,M_n)$构造格
$$
\begin{pmatrix}
1 & 0 & … & 0 & M_1\\
0 & 1 & … & 0 & M_2\\
\vdots & \vdots & \ddots & \vdots & \vdots \\
0 & 0 & … & 1 &M_n\\
0 & 0 & … & 0 & S
\end{pmatrix}
$$
假设每一行为$V_i$，例如$V_1=(1,0,…,0,M_1)$，不难理解$V_i$就是格$\mathcal{L}$的基

我们设明文序列为$x=\begin{Bmatrix}x_1,x_2,\dots,x_n \end{Bmatrix}$，$x_i=\begin{Bmatrix}0,1 \end{Bmatrix}$

很明显，对于线性组合$x_1V_1+x_2V_2+\dots+x_nV_n-V_{n+1}$必然在格点上面，因为$x_i$只能取$0$或$1$

则向量$\vec{t}=x_1V_1+x_2V_2+\dots+x_nV_n-V_{n+1}$即$\overrightarrow{t} = (x_1,x_2,\dots,x_n,0)$

而$||\vec{t}||=1$,$det(\mathcal{L})=S^{\frac{1}{n+1}}$

根据$Hermite$定理，$||\vec{t}||<\sqrt{n+1}\times det(\mathcal{L})$

所以$\vec{t}$是格$\mathcal{L}$的最短向量，可以用LLL算法解决

其实就是说会存在一个线性组合：

$$
\begin{pmatrix}
x_1 & x_2 & … & x_n & -1
\end{pmatrix}
\begin{pmatrix}
1 & 0 & … & 0 & M_1\\
0 & 1 & … & 0 & M_2\\
\vdots & \vdots & \ddots & \vdots & \vdots \\
0 & 0 & … & 1 &M_n\\
0 & 0 & … & 0 & S
\end{pmatrix}
=
\begin{pmatrix}
x_1 & x_2 & … & x_n & 0
\end{pmatrix}
$$
进行优化，使用这个格。至于为什么说这个格是更优的,估计是行列式更大些吧
$$
L =
\begin{pmatrix}
2 & 0 & … & 0 & M_1\\
0 & 2 & … & 0 & M_2\\
\vdots & \vdots & \ddots & \vdots & \vdots \\
0 & 0 & … & 2 & M_n\\
1 & 1 & … & 1 & S
\end{pmatrix}
$$
这个对应的线性组合是
$$
\begin{pmatrix}
x_1 & x_2 & … & x_n & -1
\end{pmatrix}
\begin{pmatrix}
2 & 0 & … & 0 & M_1\\
0 & 2 & … & 0 & M_2\\
\vdots & \vdots & \ddots & \vdots & \vdots \\
0 & 0 & … & 2 &M_n\\
1 & 1 & … & 1 & S
\end{pmatrix}
=
\begin{pmatrix}
2x_1-1 & 2x_2-1 & … & 2x_n-1 & 0
\end{pmatrix}
$$

以上内容仅笔者的拙见，欢迎师傅们指点

一些例题

MoeCTF2022——MiniMiniBackPack

from gmpy2 import *
from Crypto.Util.number import *
import random
from FLAG import flag

def gen_key(size):
    s = 1000
    key = []
    for _ in range(size):
        a = random.randint(s + 1, 2 * s)
        assert a > sum(key)
        key.append(a)
        s += a
    return key


m = bytes_to_long(flag)
L = len(bin(m)[2:])
key = gen_key(L)
c = 0

for i in range(L):
    c += key[i]**(m&1)
    m >>= 1

print(key)
print(c)

gen_key生成超递增序列。$c$由背包加密得来，题目把$c$和私钥都给了。

把$c$依次和序列中最大的值比较即可求解

exp:

from Crypto.Util.number import *

key = [...]
c = 2396891354790728703114360139080949406724802115971958909288237002299944566663978116795388053104330363637753770349706301118152757502162

m = ''
for i in reversed(key):
    if c > i:
        m += '1'
        c -= i
    else:
        m += '0'
        c -= 1


flag = long_to_bytes(int(m,2))
print(flag)

MoeCTF2022——knapsack

题目

from random import randint
from Crypto.Util.number import bytes_to_long,long_to_bytes,GCD,inverse
from secret import flag
def bitlength(n):#判断消息长度
	length=len(bin(bytes_to_long(n))[2:])
	return length
def makeKey(n):#生成超递增序列，得到私钥、公钥
	length=len(n)
	privKey = [randint(1, 65536**length)]
	sum = privKey[0]
	for i in range(1, length):
		privKey.append(randint(sum*255 + 1, 65536**(length + i)))
		sum += privKey[i]
	q = 255*randint(privKey[length-1] + 1, 2*privKey[length-1])
	r = randint(1, q)
	while GCD(r, q) != 1:
		r = randint(1, q)
	pubKey = [ r*w % q for w in privKey ]#将超递增序列变为非超递增序列，作为公钥
	return privKey, q, r, pubKey

def encrypt(msg, pubKey):#用公钥加密消息
	cipher = 0
	i = 0
	for bit in msg:
		cipher += bit*pubKey[i]
		i += 1
	return cipher

def decrypt(cipher, privKey, q, r):#用私钥求得超递增序列并解密
	d = inverse(r, q)
	msg = cipher*d % q
	res = b''
	n = len(privKey)
	for i in range(n - 1, -1, -1):
		temp=0
		if msg >= privKey[i]:
			while msg >= privKey[i]:
				temp=temp+1
				msg -= privKey[i]
			res =  bytes([temp]) + res
		else:
			res =  bytes([0]) + res 
	return res
privKey, q, r, pubKey=makeKey(flag)
cipher=encrypt(flag,pubKey)
f=open("pubKey.txt",'w')
f.write(str(pubKey))
f.close()
f=open("cipher.txt",'w')
f.write(str(cipher))
f.close()
print(decrypt(encrypt(flag,pubKey),privKey,q,r))
assert decrypt(encrypt(flag,pubKey),privKey,q,r)==flag

很标准的背包密码加密，由于只给了公钥，用格来做

exp

import libnum
M = []
S = 

n = len(M)
Ge = Matrix.identity(n)
last_row = [0 for x in range(n)]
Ge_last_row = Matrix(ZZ, 1, len(last_row), last_row)

last_col = M[:]
last_col.append(S)
Ge_last_col = Matrix(ZZ, len(last_col), 1, last_col)

Ge = Ge.stack(Ge_last_row)
Ge = Ge.augment(Ge_last_col)

X = Ge.LLL()[0]
print(X)
ans = []
for i in X:
    ans.append(abs(i))
    
print(bytes(ans))

MoeCTF2021——BBBBBBBackpack

from Crypto.Util.number import*
import random

flag = xxxxx
m = bytes_to_long(flag)

backpack = [1]
for i in range(160):
    backpack = backpack + [random.randrange(backpack[-1]*2,backpack[-1]*4)]
print(backpack)

backpack = backpack[::-1]
l_list = []
for i in backpack:
    l_list.append(m//i)
    m = m % i 
print(l_list)
print(m)

'''
[0, 0, 0, 0, 1, 1, 2, 2, 0, 0, 1, 1, 0, 2, 1, 0, 1, 2, 1, 1, 1, 2, 0, 0, 2, 2, 2, 1, 2, 2, 1, 1, 1, 2, 2, 2, 0, 0, 2, 1, 0, 0, 1, 0, 1, 1, 1, 0, 2, 1, 3, 0, 2, 2, 0, 0, 2, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 2, 0, 0, 1, 0, 1, 3, 0, 2, 0, 0, 1, 1, 3, 1, 2, 2, 1, 0, 0, 0, 2, 1, 1, 0, 0, 0, 1, 0, 1, 2, 1, 0, 1, 2, 0, 1, 3, 1, 0, 2, 2, 0, 1, 0, 1, 2, 1, 2, 3, 1, 0, 2, 1, 1, 2, 1, 2, 1, 0, 2, 0, 2, 2, 2, 1, 2, 1, 1, 1, 2, 3, 0, 1, 1, 2, 0, 1, 0, 0, 2, 2, 3, 2, 1, 2, 1, 1, 1, 3, 1, 0]
'''

已知l = m // i
$$
m’ = m \mod s_i
$$
我们可以从中推断，当$L_i=0$时，$m$是不变的，当$L_i = 1,2,3$时，$m’ \equiv m \mod s_i \longrightarrow m’ = m - x×s_i$

而且最后$\frac{m}{1} = 0$，说明最后$m=0$

把$s_i$和$L_i$相乘求和就能得到$m$

from Crypto.Util.number import *

import gmpy2

s = []
l = [0, 0, 0, 0, 1, 1, 2, 2, 0, 0, 1, 1, 0, 2, 1, 0, 1, 2, 1, 1, 1, 2, 0, 0, 2, 2, 2, 1, 2, 2, 1, 1, 1, 2, 2, 2, 0, 0, 2, 1, 0, 0, 1, 0, 1, 1, 1, 0, 2, 1, 3, 0, 2, 2, 0, 0, 2, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 2, 0, 0, 1, 0, 1, 3, 0, 2, 0, 0, 1, 1, 3, 1, 2, 2, 1, 0, 0, 0, 2, 1, 1, 0, 0, 0, 1, 0, 1, 2, 1, 0, 1, 2, 0, 1, 3, 1, 0, 2, 2, 0, 1, 0, 1, 2, 1, 2, 3, 1, 0, 2, 1, 1, 2, 1, 2, 1, 0, 2, 0, 2, 2, 2, 1, 2, 1, 1, 1, 2, 3, 0, 1, 1, 2, 0, 1, 0, 0, 2, 2, 3, 2, 1, 2, 1, 1, 1, 3, 1, 0]

s = list(s[::-1])
n = len(l)
m = 0
for i in range(n):
    m += s[i]*l[i]

print(long_to_bytes(m))

2023天融信杯——easybog

import os
import random
from hashlib import md5
from Crypto.Util.number import *

rr = os.urandom(10)
flag = "flag{"+rr.hex()+"}"
flag_md5 = md5(flag.encode()).hexdigest()
print(flag)

m = bin(bytes_to_long(rr))[2:].zfill(8 * len(rr))
p = getPrime(256)
def encrypt(m):
    pubkey = [random.randint(2,p - 2) for i in range(len(m))]
    enc = 0
    for k,i in zip(pubkey,m):
        enc += k * int(i)
        enc %= p
    return pubkey,enc

pubkey,c = encrypt(m)
f = open("output.txt","w")
f.write(f"p = {p}\n")
f.write(f"pubkey = {pubkey}\n")
f.write(f"c = {c}\n")
f.write(f"flag_md5 = {flag_md5}\n")
f.close()

从encrypt(m)，我们可以知道$c \equiv key_i×m_i \mod p \longrightarrow c = key_i×m_i+kp$

$$
\therefore 0 = \sum_{i=1}^{80}key_im_i + kp - c
$$
造格
$$
\begin{pmatrix}
1 & 0 & … & 0 & 0 &key_1\\
0 & 1 & … & 0 & 0 & key_2\\
\vdots & \vdots & \ddots & \vdots & \vdots &\vdots \\
0 & 0 & … & 1 &0 & key_n\\
0 & 0 & … & 0 & 1 & c \\
0 & 0 & … & 0 & 0 & p
\end{pmatrix}
$$

exp

from Crypto.Util.number import *
import hashlib

p = 85766816683407427477074053090759168259205489535331001301483049660772943816017
pubkey = []
c = 1381426073179447662111620044316177635969142117258054810267264948634812447218
flag_md5 = "cae8243e01090ccd03a66e3a4c52b7ee"

n = len(pubkey)

Ge = Matrix(ZZ,n+2,n+2)
for i in range(n):
    Ge[i,i] = 1
    Ge[i,-1] = pubkey[i]

Ge[-2,-2] = 1
Ge[-2,-1] = c
Ge[-1,-1] = p


L = Ge.BKZ()
ans = ''
for i in Ge.BKZ():
    if i[-1] == 0:
        tmp = i[:-2]
        for j in tmp:
            if abs(j) == 1:
                ans += '1'
            else:
                ans += '0'
        flag = "flag{" + hex(int(ans,2))[2:] + "}"
        flag_md51 = hashlib.md5(flag.encode()).hexdigest()
        if flag_md51 == flag_md5:
            print(flag)

sagemath中的BKZ()可以设置参数，例如BKZ(block_size = 16)，指定了BKZ算法中的块大小。默认情况下是block_size = 20

block_size越大，执行速度越慢，但结果更精确

WKCTF——meet me in the summer

task.py

from random import choice, randint
from Crypto.Util.number import isPrime, sieve_base as primes, getPrime
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from hashlib import md5

flag = b'WKCTF{}'
flag = pad(flag,16)
def myPrime(bits):
    while True:
        n = 2
        while n.bit_length() < bits:
            n *= choice(primes)
        if isPrime(n + 1):
            return n + 1

def encrypt(key, message):
    return pow(65537, message, key)

p = myPrime(512)
q = getPrime(512)
N = p * q
m = [getPrime(512) for i in range(1024)]
enc = [encrypt(N, _) for _ in m]

a = [randint(1,2 ** 50) for i in range(70)]
b = [randint(1,2 ** 50) for i in range(50)]
secret = randint(2**119, 2**120)

ra = 1
rb = 1
for i in range(120):
    if(i < 70):
        if (secret >> i) & 1:
            ra *= a[i]
            ra %= p
    else:
        if (secret >> i) & 1:
            rb *= b[i-70]
            rb %= q


key = md5(str(secret).encode()).hexdigest()[16:].encode()
cipher = AES.new(key,AES.MODE_ECB)

with open("output.txt","w") as f:
    f.write(f'c = {cipher.encrypt(flag).hex()}\n')
    f.write(f'm = {m}\n')
    f.write(f'enc = {enc}\n')
    f.write(f'a = {a}\n')
    f.write(f'b = {b}\n')
    f.write(f'ra = {ra}\n')
    f.write(f'rb = {rb}\n')

此处仅讨论与ra相关的部分,整题wp

根据题意有
$$
ra\equiv a_0k_{70}\times a_1k_{69} \times …\times a_{69}k_1 \mod p
$$
$k_i$表示第一段的第i位，需要注意的是当$k_i = 0$的时候是不需要乘进来的，这里只是写成这样。

因为$p-1$光滑，我们考虑把这个式子变成一个求解离散对数的问题，这样才能利用上$p-1$光滑

我们随便取一个生成元g，然后对等式两边取对数，要注意的是，取对数之后模数应该变成p-1
$$
\log_{g}{ra} \equiv \log_{g}{a_0k_{70}} + \log_{g}{a_1k_{69}} + … + \log_{g}{a_{69}k_1} \mod p - 1
$$
对于这个式子，当$k_i = 1$的时候，$log_g^{a_ik_i} = log_g^{a_i}$，刚刚前面说了$k_i =0$的时候是不需要乘进来的，那这个取离散对数后的式子里面只包括了$k_i = 1$的情况。

因此我们有
$$
\log_{g}{ra} \equiv \log_{g}{a_0} + \log_{g}{a_1} + … + \log_{g}{a_{69}} \mod p - 1
$$
这样就可以写为加法背包了

造格
$$
\begin{pmatrix}
k_{70} & k_{69} & … & k_{1} & 1 & l
\end{pmatrix}
\begin{pmatrix}
1 & 0 & … & 0 & 0 & \log_{g}{a_0}\\
0 & 1 & … & 0 & 0 & \log_{g}{a_1}\\
\vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\
0 & 0 & … & 1 & 0 & \log_{g}{a_{69}}\\
0 & 0 & … & 0 & 1 & \log_{g}{ra}\\
0 & 0 & … & 0 & 0 & p - 1
\end{pmatrix}
=
\begin{pmatrix}
k_{70} & k_{69} & … & k_1 & 1 & 0
\end{pmatrix}
$$

这个格没出，进行优化，造下面这个格
$$
\begin{pmatrix}
k_{70} & k_{69} & … & k_{1} & l & -1
\end{pmatrix}
\begin{pmatrix}
2 & 0 & … & 0 & 0 & \log_{g}{a_0}\\
0 & 2 & … & 0 & 0 & \log_{g}{a_1}\\
\vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\
0 & 0 & … & 2 & 0 & \log_{g}{a_{69}}\\
0 & 0 & … & 0 & 1 & p - 1\\
1 & 1 & … & 1 & 1 & \log_{g}{ra}
\end{pmatrix}
=
\begin{pmatrix}
k_{70}-1 & k_{69}-1 & … & k_1-1 & l-1 & 0
\end{pmatrix}
$$

a = [810922431519561, 446272766988725, 167807402211751, 137130339017755, 214986582563833, 141074297736993, 1116944910925939, 827779449967114, 887541522977945, 698795918391810, 180874459256817, 42309568567278, 148563974468327, 43541894027392, 369461465628947, 226728238060977, 902554563386031, 369980733296039, 495826170604031, 202556971656774, 1124261777691439, 533425503636189, 393536945515725, 242107802161603, 506637008093239, 846292038115984, 686372167052341, 923093823276073, 557898577262848, 719859369760663, 51513645433906, 946714837276014, 24336055796632, 302053499607130, 970564601798660, 1082742759743394, 499339281736843, 13407991387893, 667336471542364, 38809146657917, 29069472887681, 420834834946561, 1044601747029985, 854268790341671, 918316968972873, 737863884666895, 1036231016223653, 792781009835942, 142149344663288, 828341073371968, 186470549619656, 279923049419811, 487848895651491, 737257307326881, 1065005635075133, 628186519179693, 554767859759026, 606623194910240, 497855707815081, 88176594691403, 278020899501967, 440746393631841, 921270589876795, 800698974218498, 437669423813782, 717945417305277, 191204872168085, 791101652791845, 772875127585562, 174750251898037]
ra = 215843182933318975496532456029939484729806294336845406882490936458079210569046120528327121994744424727894554328344229010979127024288283698486557728305231262446
p = 266239931579101788237217833822346198682539336616234011732898866661722928035386747695230192006141430294833011494452114878744414084025005167432139516382471637567

g = 5
tmp = discrete_log(mod(ra,p),mod(g,p))

n = len(a)
A = [discrete_log(mod(a[i],p),mod(g,p)) for i in range(n)]

d = n / log(max(A), 2)
print(CDF(d))

Ge = Matrix(ZZ,n+2,n+2)
for i in range(n):
    Ge[i,i] = 2
    Ge[i,-1] = A[i]
    Ge[-1,i] = 1
    
Ge[-2,-2] = 1
Ge[-2,-1] = p - 1
Ge[-1,-1] = tmp
Ge[-1,-2] = 1
Ge[:,-1] *= 2^200

for line in Ge.BKZ(block_size = 26):
    if line[-1] == 0:
        t = ""
        for i in line[:-2]:
            if i == 1:
                t += "0"        # or 1
            if i == -1:
                t += "1"        # or 0 这两个来回换一下即可
    if len(t) == 70:
        print(t[::-1])
        break
        # 1100100011000011000001010101000010111110000001000010101010100100011011

参考

密码学学习笔记之 knapsack | Van1sh的小屋 (jayxv.github.io)

A-022.pdf (ieice.org)

背包加密 - CTF Wiki (ctf-wiki.org)

-------------已经到底啦！-------------