背包密码归纳总结

背包密码的加密逻辑

x1*a1+x2*a2+x3*a3+…+xn*an=c

x1到xn是我们的明文(二进制数字，ascll，或者明文片段)

a1到an是公钥

类型一：超度增背包问题

超递增是指生成的公钥序列满足：

ai>\sum_{k=1}^{i-1} a_k

也就是说生成的第i个数大于前i个之和

解码思路

贪心算法

算法大概的流程是：从右到左看，ai是越来越小的，将密文c与ai做比较，如果c>=ai，那么这一位的二进制数字是1，如果c<ai，那么这一位的二进制数字是0

例题 [MoeCTF 2022]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)

思路及解码代码

a = random.randint(s + 1, 2 * s)显然是超递增序列

解码代码

from Crypto.Util.number import *
with open("附件.txt", "r", encoding="utf-8") as f:
    key = eval(f.readline().strip())
    c = int(f.readline().strip())
print(key)
print(c)
flag_bit = ''
for i in range(len(key)):
    if key[len(key)-i-1]<=c:
        flag_bit += '1'
        c=c-key[len(key)-i-1]
    else:
        flag_bit += '0'
print(flag_bit)
flag=int(flag_bit, 2)
print(flag)
print(long_to_bytes(flag))

类型二：基础背包格

此时生成的公钥序列不是超递增序列，我们需要用LLL算法或者BKZ算法进行解码

格的构造

背包构造的格是这样的

M= \begin{pmatrix} 1 & & & a0\\ & 1 & & a1 \\ & & \ddots & \vdots \\ & & & c \end{pmatrix}

我们预期的情况是

\begin{pmatrix}flag[0],flag[1],\cdots,flag[n],-1\end{pmatrix}* \begin{pmatrix} 1 & & & a0\\ & 1 & & a1 \\ & & \ddots & \vdots \\ & & & c \end{pmatrix}=\begin{pmatrix}flag[0],flag[1],\cdots,flag[n],0\end{pmatrix}

此时我们预期得到的向量是很小的，大概率是可以格出来的

但是某些情况下加密逻辑是这样的

x1*a1+x2*a2+x3*a3+…+xn*an=c (mod p)

也就加了一个mod p的条件

但由于我们模的k是比较小的

此时这样构造格

M= \begin{pmatrix} 1 & & & & a0\\ & 1 & & & a1 \\ & &\ddots & & \vdots \\ & & &1 & c\\ & & & & p \end{pmatrix}

我们预期的情况是这样的

\begin{pmatrix}flag[0],flag[1],\cdots,flag[n],-1,k\end{pmatrix}* M= \begin{pmatrix} 1 & & & & a0\\ & 1 & & & a1 \\ & &\ddots & & \vdots \\ & & &1 & c\\ & & & & p \end{pmatrix}=\begin{pmatrix}flag[0],flag[1],\cdots,flag[n],-1,0\end{pmatrix}

例题 [MoeCTF 2022]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

思路及解码代码

只需要看加密代码cipher += bit*pubKey[i]，注意的是这里的bit是ascll值，并不是二进制数字，那么我们格出来之后，判断最后一位是否是0，进行剪枝即可

最基础的背包密码

解码代码

c=
a=[]
n=len(a)
L = matrix.zero(n + 1)
for i in range(n):
    L[i,i]=1
    L[i,-1]=a[i]
L[-1,-1]=c
res=L.LLL()
# print(res)
for i in res:
    if i[-1]==0:
        print(i)
        for k in i:
            print(chr(abs(k)),end='')

例题 knaspack 1

from random import *
from Crypto.Util.number import *
from secret import flag

assert flag[:5] == b'flag{' and flag[-1:] == b"}"

def enc(alist , p , m):
    mlen = len(m)
    m = bytes_to_long(m)
    mlist = [int(i) for i in bin(m)[2:].rjust(mlen*8 , '0')]
    c = 0
    for i in range(len(alist)):
        c += alist[i] * mlist[i]
        c %= p
    return c

def genkey(mlen , p):
    alist = []
    for i in range(mlen*8):
        alist.append(randint(1 , p))
    return alist


p = getPrime(256)

mlen = len(flag[5:-1])

alist = genkey(mlen , p)
c = enc(alist , p , flag[5:-1])
print(p)
print(c)
print(alist)

思路及解码代码

按上面的思路构造格进行LLL即可

from Crypto.Util.number import *
p=
c=
a=[]
n=len(a)
L = matrix.zero(n + 2)
for i in range(n):
    L[i,i]=1
    L[i,-1]=a[i]
L[-2,-2]=1
L[-2,-1]=c
L[-1,-1]=p
res=L.LLL()
# print(res)
flag=0
for i in res:
    if i[-1]==0:
        print(i)
        for k in i[0:-2]:
            flag=(flag<<1)+k
print(flag)
print(long_to_bytes(flag))

类型三：格优化

优化思路

格出来的结果，各分量应该尽可能的平衡，基于此，我们这样构造格

M= \begin{pmatrix} 2 & 0 & \cdots & 0 & a0 \\ 0 & 2 & \cdots & 0 & a1 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 2 & an \\ 1 & 1 & \cdots & 1 & c \end{pmatrix}

如果我们不进行优化，我们最后求出来的结果不是0就是1

优化之后我们的预期是

\begin{pmatrix}flag[0],flag[1],\cdots,flag[n],-1\end{pmatrix}* \begin{pmatrix} 2 & 0 & \cdots & 0 & N a_1 \\ 0 & 2 & \cdots & 0 & N a_2 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 2 & N a_n \\ 1 & 1 & \cdots & 1 & N c \end{pmatrix}=\begin{pmatrix}2*flag[0]+1,2*flag[1]+1,\cdots,2*flag[n]+1,-1\end{pmatrix}

由于flag取0和1

带进去最终结果全部是-1或1，显然更平衡

但注意的是只有加密是二进制的时候才适用

例题 [LilCTF2025]baaaaaag

from Crypto.Util.number import *
import random
from Crypto.Cipher import AES
import hashlib
from Crypto.Util.Padding import pad
from secret import flag

p = random.getrandbits(72)
assert len(bin(p)[2:]) == 72

a = [getPrime(90) for _ in range(72)]
b = 0
t = p
for i in a:
    temp = t % 2
    b += temp * i
    t = t >> 1

key = hashlib.sha256(str(p).encode()).digest()
cipher = AES.new(key, AES.MODE_ECB)
flag = pad(flag,16)
ciphertext = cipher.encrypt(flag)

print(f'a = {a}')
print(f'b = {b}')
print(f"ciphertext = {ciphertext}")

思路及解码代码

直接格是格不出来的，进行格优化之后，进行BKZ，block_size=19的时候解码成功

# 2598513397739972620848
from Crypto.Util.number import *
from Crypto.Cipher import AES
a = 
b = 
ciphertext = 
n=len(a)
L = matrix.zero(n + 1)
for i in range(n):
    L[i,i]=2
    L[i,-1]=a[i]
L[-1:]=1
L[-1,-1]=b
res=L.BKZ(block_size=19)
# print(res)
p_bin=''
for v in res:
    if all(abs(x) <= 1 for x in v):
        print(v)
        for i in v:
            if i==-1:
                p_bin=p_bin+'1'
            if i==1:
                p_bin=p_bin+'0'
print('hahaha')
print(int(p_bin, 2))
print(int(p_bin[::-1], 2))
p=int(p_bin[::-1], 2)
print(p)
key = hashlib.sha256(str(p).encode()).digest()
cipher = AES.new(key, AES.MODE_ECB)
# flag = pad(flag,16)
flag = cipher.decrypt(ciphertext)
print(flag)

类型四：可以通过已知明文降低格密度

格密度算法

d \;=\; \frac{n}{\log_2\!\big(maxa_i\big)}.

(d < 0.94)：低密度，LLL/BKZ + embedding 通常很容易打
(d =1)：临界区，BKZ 可能还行，但更吃参数与构造
(d > 1)：高密度，纯 LLL/小 BKZ 往往不稳，需要更强的攻击或更多信息

Hermite 定理

常数说的是：对任意 $n$ 维格 $\Lambda$，其最短非零向量长度 $\lambda_1(\Lambda)$ 与行列式 $\det(\Lambda)$ 的关系上界。常见表述是定义 Hermite 常数 $\gamma_n$：

\gamma_n \;=\;\sup_{\Lambda\subset\mathbb{R}^n} \frac{\lambda_1(\Lambda)^2}{\det(\Lambda)^{2/n}}

贴一下吧，也不怎么会算

大概就是已知了一些加密了的明文，然后缩小数组，及密文的规模，更容易能够格出来

例题 BackPack

import random
from secret import flag

assert flag.startswith(b'flag{') and flag.endswith(b'}')
assert len(flag) == 18

nbits = 100
a = [random.randint(1<<(nbits-1),1<<nbits) for i in range(len(flag))]
b = sum([i*j for i,j in zip(a,flag)])

print(f'{a = }')
print(f'{b = }')

思路及解码代码

由于flag{和}已知，可以减小规模

a = [860821557828281442941778166659, 803777501490125576839352944446, 1005791873983601117392247346085, 1231852467297005050375360025752, 1150352241055815801801169950798, 1033631711572423166071966000805, 890177812727691819583920502722, 774328120543962049661717901714, 1245456973890441414472116526495, 1028358564218716011754082665529, 1255301095911246652616865738235, 1044268314210406252404807758214, 657259442956498113250060870571, 1012336650574893000661389761761, 634657308746918412136962502475, 777627386546123162588057785533, 678975824788168905519513549577, 1019837548122056307083044320710]
b = 1379609132427499161538242425117756
B=2**50
print('hahahaha')
begin='flag{'
end='}'
mid_a=a[len(begin):-len(end)]
print(len(mid_a))
mid_enc=b
for i in range(len(begin)):
    mid_enc=mid_enc-ord(begin[i])*a[i]
mid_enc=mid_enc-ord(end)*a[-1]
print(mid_enc)
n=(len(mid_a))
print(n)
L = matrix.zero(n + 1)
for i in range(n):
    L[i,i]=1
    L[i,-1]=mid_a[i]*B
L[-1,-1]=mid_enc*B
L=L.LLL()[0]
for i in L:
    print(chr(abs(i)),end='')

类型五: 多个约束方程

其实就是有多个这样的关系

x1*a1+x2*a2+x3*a3+…+xn*an=c

例题 [FZNCTF2025]

from Crypto.Util.number import *
import uuid
import random
from Crypto.Cipher import AES
import hashlib
from Crypto.Util.Padding import pad

flag = b'FZNCTF{' + bytes(str(uuid.uuid4()).encode()) + b'}'
LEN = len(flag)
flag1, flag2 = flag[:LEN//2],flag[LEN//2:]

# part1
p = getPrime(1024)
x = getPrime(512)
rlist = []
clist = []
slist = []
for i in range(30):
    r = getPrime(512)
    s = getPrime(500)
    c = (r * x + s) % p
    rlist.append(r)
    clist.append(c)
    slist.append(s)

print(f'p = {p}')
print(f'rlist = {rlist}')
print(f'clist = {clist}')

e = 0x10001
m1 = bytes_to_long(flag1)
c1 = pow(m1, e, x)
print(f'c1 = {c1}')

# part2
key=random.getrandbits(64)
assert len(bin(key)[2:])==64
key0 = str(bin(key)[2:])

lista = []
listb = []
for i in range(4):
    a=[getPrime(32) for _ in range(64)]
    b=0
    for j in range(len(key0)):
        b += a[j]*int(key0[len(key0) - j - 1])
    lista.append(a)
    listb.append(b)
print(f'lista={lista}')
print(f'listb={listb}')

key = hashlib.sha256(str(key).encode()).digest()
cipher = AES.new(key, AES.MODE_ECB)
flag2 = pad(flag2,16)
c2 = cipher.encrypt(flag2)
print(f"c2={c2}")

思路及解码代码

我们只看后半部分

主要问题是key的求取，但是，对同一个进行了四组背包密码，当时，尝试使用一组甚至四组加起来尝试没有成功

实际上我们需要构造这样的格子

\begin{pmatrix} 1 & 0 & \cdots & 0 & a00 &a10 &a20 &a30\\ 0 & 1 & \cdots & 0 & a01 &a11 &a21 &a31\\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \vdots & \vdots\\ 0 & 0 & \cdots & 1 & a0n &a1n &a2n &a3n\\ 0 & 0 & \cdots & 0 & c0 &0 &0 &0\\ 0 & 0 & \cdots & 0 & 0 &c1 &0 &0\\ 0 & 0 & \cdots & 0 & 0 &0 &c2 &0\\ 0 & 0 & \cdots & 0 & 0 &0 &0 &c3\\ \end{pmatrix}

这样我们预期的向量解就变成了

\begin{pmatrix}x0,x1,…,xn,0,0,0,0\end{pmatrix}

因此找最后四个分量是0，以及所有向量绝对值小于1，然后aes解码即可

from Crypto.Util.number import *
from Crypto.Cipher import AES
import hashlib
lista=
listb=
c2=
n = len(lista[0])
B=2**50
L = matrix.zero(n + 4)
for i in range(n):
    L[i,i]=1
    L[i,-4]=lista[0][i]*B
    L[i,-3]=lista[1][i]*B
    L[i,-2]=lista[2][i]*B
    L[i,-1]=lista[3][i]*B
L[-4,-4]=listb[0]*B
L[-3,-3]=listb[1]*B
L[-2,-2]=listb[2]*B
L[-1,-1]=listb[3]*B
res=L.LLL()
# print(res)
flag_bin=''
for i in res:
    if i[-4]==0 and i[-3]==0 and i[-2]==0 and i[-1]==0 and all(abs(x) <= 1 for x in i):
        print(i)
        for k in i[0:-4]:
            flag_bin=flag_bin+str(abs(k))
print('ohno')
print(flag_bin)
print(int(flag_bin,2))
key=int(flag_bin[::-1],2)
key = hashlib.sha256(str(key).encode()).digest()
cipher = AES.new(key, AES.MODE_ECB)
# flag2 = pad(flag2,16)
flag2 = cipher.decrypt(c2)
print(f"flag2={flag2}")

类型六：隐藏的背包密码

例题 [ISCTF2025] baby_equation

from Crypto.Util.number import bytes_to_long

print(len(flag)) 
R = RealField(1000)
a,b = bytes_to_long(flag[:len(flag)//2]),bytes_to_long(flag[len(flag)//2:])
x   = R(0.75872961153339387563860550178464795474547887323678173252494265684893323654606628651427151866818730100357590296863274236719073684620030717141521941211167282170567424114270941542016135979438271439047194028943997508126389603529160316379547558098144713802870753946485296790294770557302303874143106908193100)
 
enc = a*cos(x)+b*sin(x) 
 

#1.24839978408728580181183027675785982784764821592156892598136000363397267152291738689909414790691435938223032351375697399608345468567445269769342300325192248438038963977207296241971217955178443170598629648414706345216797043374408541203167719396818925953801387623884200901703606288664141375049626635852e52

思路及解码代码

a，b是明文，cos x和sin x看作公钥，当作背包密码做就可以了

from Crypto.Util.number import *

x=0.75872961153339387563860550178464795474547887323678173252494265684893323654606628651427151866818730100357590296863274236719073684620030717141521941211167282170567424114270941542016135979438271439047194028943997508126389603529160316379547558098144713802870753946485296790294770557302303874143106908193100
c=1.24839978408728580181183027675785982784764821592156892598136000363397267152291738689909414790691435938223032351375697399608345468567445269769342300325192248438038963977207296241971217955178443170598629648414706345216797043374408541203167719396818925953801387623884200901703606288664141375049626635852e52
cx = int(cos(x)*2^1000)
sx = int(sin(x)*2^1000)
c = (c*2^1000)
M = matrix(ZZ, [[1,0,cx],[0,1,sx],[0,0,-c]])
L = M.LLL()[0]
 
long_to_bytes(L[0])+long_to_bytes(L[1])

类型七：bytes_to_long

隐藏背包密码

最初遇到的时候是NSS靶场tangcuxiaojkuai师傅的easy_mod 系列里面的

除此之外，在hgame 2026的babyRSA和[GHCTF 2025]EZ_Fermat_bag_PRO题目中出现了

我们以hgame 2026的babyRSA为例来做，如果后面easy_mod懂差不多的话，出一个文章

bytes_to_long转换机制

每个字节的大小都在0到255

bytes_to_long()的本质作用其实就是把字节流转换成数字流，可以简单的理解256进制

例如：

存在字节

b'\x01\x02\x03'

那么转换的时候就是

c=1\cdot 256^{2} + 2\cdot 256^{1} + 3

手算可以得到66051

我们可以尝试用python输出一下，代码见下：

from Crypto.Util.number import *
m=b'\x01\x02\x03'
print(bytes_to_long(m))

那么我们就可以自定义一个bytes_to_long函数

函数实现

def bytes_to_long(a):
    sum=0
    for i in range(len(a)):
        sum=sum+a[i]*256**(len(a)-i-1)
    return sum

例题 [hgame2026] babyRSA

from Crypto.Util.number import *
from gmpy2 import *
from random import *
import string
k = randint(30, 40)
str = string.digits + string.ascii_letters + "_@"
flag = b"VIDAR{" + "".join([choice(str) for i in range(k)]).encode() + b"}"
p = getPrime(120)
q = getPrime(120)
n = p * q
e = 65537
m = bytes_to_long(flag)
c = pow(m, e, n)
print(f'c = {c}')
print(f'p = {p}')
print(f'q = {q}')

'''
c = 451420045234442273941376910979916645887835448913611695130061067762180161
p = 722243413239346736518453990676052563
q = 777452004761824304315754169245494387
'''

思路及解码代码

p,q很小，才120位，我们发现正常的RSA解不出来，这是因为flag最少是37*8位，即296位，大于240位

所以解出来的是c=bytes_to_long(flag) %p

那么我们想到爆破，但显然是不现实的，按最好的情况算，flag是296位，还得爆破50位左右，我看群里有人都用了超算，没跑出来

我们先看flag的构成

m = 256^{k+1}\,\mathrm{pre} + 256\,m_0 + \mathrm{suf}

pre是‘VIDAR{’,suf是‘}’,m0是由字符string.digits + string.ascii_letters + "_@"组成的，我们可以先减去前面的pre和suf变成下面的形式

c=a_0 + a_1\,\mathrm{256} + a_2\,\mathrm{256}^2 + \cdots + a_{n-2}\,\mathrm{256}^{n-2} + a_{n-1}\,\mathrm{256}^{n-1} \bmod p

a0到an-1是m0的每个字节，都是由string.digits + string.ascii_letters + "_@"构成的，这些数字的大小都在48到122以内，相比256的大小还是比较小的。

和背包密码的形式一样，建立如下的格：

B = 2^{40},\quad L= \begin{pmatrix} 1&0&0&\cdots&0&0&B\\ 0&1&0&\cdots&0&0&B\,\mathrm{256}\\ 0&0&1&\cdots&0&0&B\,\mathrm{256}^2\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots\\ 0&0&0&0&1&0&B\,\mathrm{256}^{k-1}\\ 0&0&0&0&0&1&cB\\ 0&0&0&\cdots&0&0&qB \end{pmatrix}

但是直接格还是不行的，因为我们得保证目标向量的大小差不多

我们预计的目标向量是

(a_0,a_1,\cdots,a_{k-1},0)

但这样格出来的目标向量是不平衡的，a0到a{k-1}的范围是48到122，首先，最后一个分量是0，差距太大，122和48也差距比较大，一个是7位的数，一个是6位的

那我们现在需要优化格，使得格出来的向量相对平衡

我们想到，如果使得目标向量减去平均值，例如122-85是37，48-85是-37，这样位数就差不多了，目标向量相对平衡

那么我们记Ai+85=ai

带入刚刚的公式

c=A_0+85 + (A_1+85)\,\mathrm{256} + (A_2+85)\,\mathrm{256}^2 + \cdots + (A_{n-2}+85)\,\mathrm{256}^{n-2} + (A_{n-1}+85)\,\mathrm{256}^{n-1} \bmod p

将85的可以合成一个大的常数项

c \equiv \sum_{i=0}^{n-1} A_i\,256^{i} \;+\; 85\sum_{i=0}^{n-1} 256^{i} \pmod p

将右边的常数项和密文c合并,就可以变成

c' \equiv \sum_{i=0}^{n-1} A_i\,256^{i} \pmod p

此时我们的目标向量变成了

(A_0,A_1,\cdots,A_{k-1},0)

A0到A{k-1}的大小也就是-37到37，显然目标分量，都是比较接近的

k的话爆破一下就行

解码代码

from Crypto.Util.number import *
import gmpy2
B=2**40
c = 451420045234442273941376910979916645887835448913611695130061067762180161
p = 722243413239346736518453990676052563
q = 777452004761824304315754169245494387
n=p*q
e=65537
d=pow(e,-1,(p-1)*(q-1))
m=pow(c,d,n)
print(int(m))
c=int(m)
prefix = b"VIDAR{"
suffix=b"}"
k = 30
for k in range(30,41):
    c=int(m)
    c -= bytes_to_long(suffix)
    c -=256^(len(suffix) + k)* bytes_to_long(prefix)
    c = c * inverse(256,n) % n
    L=matrix(ZZ,k+2,k+2)
    for i in range(k):
        L[i,i]=1
        L[i,-1]=B*(256^i)
        c -= 256^i*85
    c=c%n
    L[-2,-2]=2**5
    L[-2,-1]=-B*c
    L[-1,-1]=B*n
    res=L.BKZ(block_size=30)
    for j in res:
        if j[-1]==0 and abs(int(j[-2])) ==2**5 and  all(abs(x) <=37 for x in j):
            print(j)
            flag=''
            for char in j[0:-2]:
                flag=flag+chr(int(85+char))
            print(flag[::-1])
    # print(res[0])
    # print(L)
c -= bytes_to_long(suffix)
c -=256^(len(suffix) + k)* bytes_to_long(prefix)
print(c)
print(len(bin(c)))