文档网络安全教程【免费下载链接】ctf-wikiCome and join us, we need you!项目地址https://gitcode.com/gh_mirrors/ct/ctf-wiki点击查看免费下载背包加密Knapsack Cryptosystem是密码学史上极具教学价值的经典非对称加密体制它以 NP 完全的「子集和问题」为安全基础利用超递增序列构造陷门实现解密却在提出后不久即被格基规约Lattice Reduction攻破。本篇文章以 CTF-Wiki 仓库中的 knapsack.md 为骨架结合仓库内格论章节的源码级原理佐证完整讲解背包问题的数学定义、超递增序列的生成逻辑、Merkle–Hellman 公私钥生成与加解密流程并复现 2014 年 ASIS CTF Archaic 一题的 LLL 破解全过程。读完本文你将掌握识别背包类加密题目的特征、手动构造密钥以及用格攻击脚本快速还原明文的能力。背包问题的数学本质子集和问题与加密雏形假定一个背包可以称重 W现在有 n 个物品其重量分别为 $a_1, a_2,...,a_n$。我们想知道装哪些物品可以恰好使得背包装满并且每个物品只能被装一次。这其实就是在求解如下方程$$ x_1a_1x_2a_2...x_na_nW $$其中所有的 $x_i$ 只能取 0 和 1。显然我们必须枚举所有 n 个物品的组合才能解决这个问题复杂度为 $2^n$这也就是背包加密的妙处所在——加密方向已知物品集合求组合和是容易的而逆向求解已知和反推组合在公开的普通序列下是困难的。在加密时如果我们想要加密的明文为 x那么可以将其表示为 n 位二进制数然后分别乘上 $a_i$ 再求和即可得到加密结果。也就是说一个 n 比特的明文 v 对应一个 0/1 系数向量加密结果就是对应物品重量的线性组合。为什么必须引入超递增序列上述方案面临一个致命问题解密时我们确实让其他人难以解密密文但我们自己也确实没有办法解密密文——因为合法解密者同样要面对这个 NP 难题。但是当 $a_i$ 是超递增superincreasing序列时我们就有办法解了。所谓超递增是指序列满足如下条件$$ a_i\sum_{k1}^{i-1}a_k $$即第 i 个数大于前面所有数的和。为什么满足这样的条件就可以解密了呢这是因为如果加密后的结果大于 $a_n$那么其前面的系数 $x_n$ 必须为 1反之即便把前面所有数全部装入系数全 1也无法使得等式成立。因此从最大的 $a_n$ 开始从后往前贪心判断就可以立马得到对应的明文。具体解密算法如下令 S 密文值i 从 n 递减到 1若 $S \geq a_i$则 $x_i 1$令 $S S - a_i$否则 $x_i 0$循环结束后 S 应为 0得到的 $x_1x_2...x_n$ 即为明文的二进制位串。从仓库中 knapsack.md 的表述看超递增序列保证了「从高位到低位逐位可判定」的唯一解性质这是整个体制可解密的核心。公开序列带来的隐患但是这样又出现了一个问题由于 $a_i$ 是公开的如果攻击者截获了密文那么它也就很容易去破解这样的密码——直接对公开的普通序列做子集和求解虽然困难但若序列本身就是超递增的攻击者同样可以用上面的贪心算法还原明文。为了弥补这样的问题就出现了 Merkle–Hellman 这样的加密算法我们可以使用初始的背包集作为私钥变换后的背包集作为公钥再稍微改动加密过程即可。Merkle–Hellman 加密体制详解Merkle–Hellman背包加密的核心思想是用模乘运算把一个超递增的私钥序列「打乱」成看似普通的公钥序列只有知道陷门乘数 w 与模数 m的人才能把密文还原回超递增序列上的求解问题。公私钥生成生成私钥私钥就是初始的背包集这里我们使用超递增序列。怎么生成呢可以假设 $a_11$那么 $a_21$ 即可类似的可以依次生成后面的值例如取$$ a_11,\ a_22,\ a_34,\ a_48,\ ... $$每个新元素只需要落在「前 n-1 项之和 1」以上的范围即可保证超递增性质。生成公钥在生成公钥的过程中主要使用了模乘运算。步骤如下生成模乘的模数 m这里要确保$$ m\sum_{i1}^{n}a_i $$即 m 大于私钥序列所有元素之和这一条件保证解密时不会发生模回绕见下文解密部分。选择模乘的乘数 w作为私钥的一部分并且确保$$ gcd(w,m)1 $$即 w 与 m 互素从而保证 w 在模 m 下存在乘法逆元 $w^{-1}$。通过如下公式生成公钥$$ b_i \equiv w a_i \bmod m $$并将这个新的背包集 $b_i$ 和 m 作为公钥发布。私钥则是 $(a_1,...,a_n)$ 与 w。加解密流程加密假设我们要加密的明文为 v其每一个比特位为 $v_i$0/1那么加密的结果为$$ \sum_{i1}^{n}b_iv_i \bmod m $$也就是把明文的二进制位串当作系数对公钥序列做带权求和。对于密文方而言公钥序列 $b_i$ 看起来是普通整数不存在明显的超递增结构因而难以直接贪心还原。解密对于解密方首先可以求得 w 关于 m 的逆元 $w^{-1}$利用扩展欧几里得算法。然后将得到的密文乘以 $w^{-1}$ 即可得到明文这是因为$$ \sum_{i1}^{n}w^{-1}b_iv_i \bmod m\sum_{i1}^{n}a_iv_i \bmod m $$其中使用了 $b_i \equiv w a_i \bmod m$ 的关系。由于每一块的加密消息都是小于 m 的m 大于私钥元素之和也大于任意组合和模运算不会产生回绕求得的结果自然就是明文对应的子集和再配合私钥序列的超递增性质逐位还原出 $v_i$。这里需要特别强调 m 取值条件的作用若 $m \leq \sum a_i$则 $w a_i \bmod m$ 会导致信息丢失解密时无法精确恢复明文因此「m 大于私钥总和」是参数正确性的关键约束。体制被攻破的根本原因该加密体制在提出后两年后即被破译。破译的基本思想是我们不一定需要找出正确的乘数 w即陷门信息只需找出任意模数 $m$ 和乘数 $w$只要使用 $w$ 去乘公开的背包向量 B 时能够产生超递增的背包向量即可。一旦找到这样一组 $(w, m)$攻击者就可以对截获的密文施以与合法解密完全相同的流程乘以 $w^{-1}$ 后在新的超递增序列上贪心还原明文。这意味着陷门并非密码学意义上不可替代的秘密体制的安全假设公开向量与私钥向量在格意义下「不可区分」被证明不成立。从格论看攻击原理为什么「找到任意 $w$、$m$ 使 $wB \bmod m$ 超递增」是可行的这需要从仓库的格论章节理解。CTF-Wiki 的 格概述 明确指出基于格的密码分析是格理论的重要研究方向之一其中第一项就是Knapsack cryptosystems背包密码体制。在 格基本介绍 中格被定义为 m 维欧式空间 $R^m$ 中 n 个线性无关向量 $b_i$ 的所有整系数线性组合$$ L(B){\sum_{i1}^{n}x_ib_i:x_i \in Z} $$其中最短向量问题SVP、最近向量问题CVP是格上公认的困难问题。而 Lenstra–Lenstra–LovaszLLL 算法 正是求解这些问题的近似算法它可以在多项式时间内找到一组「短且近乎正交」的格基。背包密文 $C \sum b_iv_i$ 恰好可以被构造为一个格中的短向量问题若我们构造如下矩阵$$ A \left[ \begin{matrix} 1 0 0 \cdots 0 b_1 \ 0 1 0 \cdots 0 b_2 \ \vdots \vdots \vdots \ddots \vdots \ 0 0 0 \cdots 1 b_n \ 0 0 0 \cdots 0 -C \ \end{matrix} \right] $$那么明文向量 $(v_1,...,v_n,0)$ 正是该格中的一个点其最后一维坐标为 $\sum b_iv_i - C 0$且前 n 维全部为 0/1 构成短向量。当公钥序列 $b_i$ 相对密文 C 较「小」时这个明文向量就是格中的一个极短向量LLL 规约后得到的短向量即直接对应明文位串。这正是破解脚本中用Matrix(ZZ, nbit1, nbit1)构造矩阵后调用A.LLL()的数学依据。实战破解2014 ASIS CTF Quals Archaic 完整复现下面以 2014 年 ASIS Cyber Security Contest Quals 中的Archaic一题为例完整走一遍从读题、分析密钥生成到 LLL 攻击还原 flag 的过程。题目源码分析首先查看源程序secret CENSORED msg_bit bin(int(secret.encode(hex), 16))[2:]首先得到了 secret 的所有二进制位。其次利用如下函数得到 keypair包含公钥与私钥keyPair makeKey(len(msg_bit))仔细分析makeKey函数def makeKey(n): privKey [random.randint(1, 4**n)] s privKey[0] for i in range(1, n): privKey.append(random.randint(s 1, 4**(n i))) s privKey[i] q random.randint(privKey[n-1] 1, 2*privKey[n-1]) r random.randint(1, q) while gmpy2.gcd(r, q) ! 1: r random.randint(1, q) pubKey [ r*w % q for w in privKey ] return privKey, q, r, pubKey可以看出privKey是一个超递增序列每一项都大于此前所有项之和并且得到的 q 比privKey中所有数的和还要大此外我们得到的 r 恰好与 q 互素gcd(r, q) 1。这一切都表明该加密是一个标准的 Merkle–Hellman 背包加密privKey—— 超递增私钥序列q—— 模数 m大于私钥总和r—— 乘数 w与 q 互素pubKey—— 公开的背包向量 $b_i r \cdot privKey_i \bmod q$。果然加密函数就是对于消息的每一位乘以对应的公钥并求和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:]这里cipher即为 $\sum b_iv_i$与上文加密公式完全一致。LLL 格攻击脚本破解脚本直接构造「单位矩阵 公钥 密文」形式的格矩阵并对其实施 LLL 规约import binascii # open the public key and strip the spaces so we have a decent array fileKey open(pub.Key, rb) pubKey fileKey.read().replace( , ).replace(L, ).strip([]).split(,) nbit len(pubKey) # open the encoded message fileEnc open(enc.txt, rb) encoded fileEnc.read().replace(L, ) print start # create a large matrix of 0s (dimensions are public key length 1) A Matrix(ZZ, nbit 1, nbit 1) # fill in the identity matrix for i in xrange(nbit): A[i, i] 1 # replace the bottom row with your public key for i in xrange(nbit): A[i, nbit] pubKey[i] # last element is the encoded message A[nbit, nbit] -int(encoded) res A.LLL() for i in range(0, nbit 1): # print solution M res.row(i).list() flag True for m in M: if m ! 0 and m ! 1: flag False break if flag: print i, M M .join(str(j) for j in M) # remove the last bit M M[:-1] M hex(int(M, 2))[2:-1] print M脚本要点逐行解析读取公钥文件pub.Key去除空格、L后缀与方括号按逗号切分成整数数组得到nbit即明文比特数读取密文文件enc.txt得到整数encoded构造 $(nbit1)\times(nbit1)$ 的整系数矩阵A左上角是 nbit 阶单位矩阵保证行向量前 nbit 维记录明文位最后一列放置公钥元素 $b_i$矩阵右下角放置-int(encoded)调用A.LLL()进行格基规约遍历规约后的所有行找出只含 0 和 1的行——这正是明文对应的系数向量因为加密时明文被分解为 0/1 比特串去掉该行的最后一个数字对应密文列的系数将剩下的 0/1 串还原成十六进制字节串。这里需要注意两点得到的 LLL 攻击矩阵res中只包含 01 值的行才是我们想要的结果因为我们对于明文加密时会将其分解为二进制比特串我们还需要去掉对应那一行的最后一个数字它是 $-\text{encoded}$ 那一列的系数不属于明文位。运行脚本输出295 [1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0] 415349535f3962643364356664323432323638326331393536383830366130373036316365 import binascii binascii.unhexlify(415349535f3962643364356664323432323638326331393536383830366130373036316365) ASIS_9bd3d5fd2422682c19568806a07061ce还原 flag第 295 行的规约结果即为明文的 0/1 系数向量去掉最后一个数字后转换为整数再转为十六进制得到字符串415349535f3962643364356664323432323638326331393536383830366130373036316365用binascii.unhexlify解码后即为最终 flagASIS_9bd3d5fd2422682c19568806a07061ce做题要点总结针对背包类题目可以总结出如下通用判断与攻击流程识别特征题目给出一个较长的公钥数组pubKey与一个整数密文或以二进制串形式给出的密文且加密为逐位乘加求和。若题目源码中出现gcd(r, q) 1、超递增私钥与q sum(privKey)的判断即可确认为 Merkle–Hellman 背包加密。密钥生成逆向私钥序列满足 $a_i \sum_{ki}a_k$模数 m 需大于私钥总和乘数 w 与 m 互素公钥 $b_i \equiv w a_i \bmod m$。解密思路合法解密先求 $w^{-1} \bmod m$将密文乘 $w^{-1}$ 还原到超递增序列再从高位向低位贪心还原明文位串。攻击思路不必恢复真实陷门只需构造「单位矩阵 公钥 密文」的格矩阵调用 LLL 规约筛选只含 0/1 的行即为明文向量相关原理可结合仓库的 格概述、格基本介绍 与 LLL 格基规约算法 深入理解。相关练习题目2017 国赛 classic同样是经典的背包加密题目可以作为本文攻击思路的巩固练习尝试用 LLL 规约脚本自行还原明文。参考本文核心内容继承自 knapsack.md密钥生成、加解密公式与 Archaic 题目源码均出自该文档格论背景参考仓库 格概述、格基本介绍、LLL 格基规约算法 与 CVP 问题背包加密在非对称密码体系中的定位可参考 非对称加密介绍。赞分享文档网络安全教程【免费下载链接】ctf-wikiCome and join us, we need you!项目地址https://gitcode.com/gh_mirrors/ct/ctf-wiki点击查看免费下载相关推荐CTF 非對稱加密深度解析Merkle–Hellman 揹包加密與 LLL 格攻擊實戰ctf-wikiCTF 非對稱加密深度解析Merkle–Hellman 揹包加密與 LLL 格攻擊實戰ctf wiki 本篇指南以 ctf wiki 非對稱加密章節中的揹文档网络安全教程ctf-wiki 格基规约算法LLL实战指南原理推导、整数关系检测与格攻击应用ctf wiki 格基规约算法LLL实战指南原理推导、整数关系检测与格攻击应用 导读 格基规约Lattice Basis Reduction是格密码学文档网络安全教程CTF 中的 RSA Coppersmith 攻击从 LLL 格基约化到广播、相关消息与低解密指数攻击实战解析CTF 中的 RSA Coppersmith 攻击从 LLL 格基约化到广播、相关消息与低解密指数攻击实战解析 本篇技术指南以 Coppersmith 相關攻文档网络安全教程上一篇终极指南在Linux系统上使用Anbox高效运行Android应用下一篇Linux系统制作Windows启动盘终极指南WoeUSB-ng完全教程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 CTF-Wiki 背包加密专题：从超递增序列到 Merkle–Hellman 与 LLL 格基规约攻击实战
文档网络安全教程【免费下载链接】ctf-wikiCome and join us, we need you!项目地址https://gitcode.com/gh_mirrors/ct/ctf-wiki点击查看免费下载背包加密Knapsack Cryptosystem是密码学史上极具教学价值的经典非对称加密体制它以 NP 完全的「子集和问题」为安全基础利用超递增序列构造陷门实现解密却在提出后不久即被格基规约Lattice Reduction攻破。本篇文章以 CTF-Wiki 仓库中的 knapsack.md 为骨架结合仓库内格论章节的源码级原理佐证完整讲解背包问题的数学定义、超递增序列的生成逻辑、Merkle–Hellman 公私钥生成与加解密流程并复现 2014 年 ASIS CTF Archaic 一题的 LLL 破解全过程。读完本文你将掌握识别背包类加密题目的特征、手动构造密钥以及用格攻击脚本快速还原明文的能力。背包问题的数学本质子集和问题与加密雏形假定一个背包可以称重 W现在有 n 个物品其重量分别为 $a_1, a_2,...,a_n$。我们想知道装哪些物品可以恰好使得背包装满并且每个物品只能被装一次。这其实就是在求解如下方程$$ x_1a_1x_2a_2...x_na_nW $$其中所有的 $x_i$ 只能取 0 和 1。显然我们必须枚举所有 n 个物品的组合才能解决这个问题复杂度为 $2^n$这也就是背包加密的妙处所在——加密方向已知物品集合求组合和是容易的而逆向求解已知和反推组合在公开的普通序列下是困难的。在加密时如果我们想要加密的明文为 x那么可以将其表示为 n 位二进制数然后分别乘上 $a_i$ 再求和即可得到加密结果。也就是说一个 n 比特的明文 v 对应一个 0/1 系数向量加密结果就是对应物品重量的线性组合。为什么必须引入超递增序列上述方案面临一个致命问题解密时我们确实让其他人难以解密密文但我们自己也确实没有办法解密密文——因为合法解密者同样要面对这个 NP 难题。但是当 $a_i$ 是超递增superincreasing序列时我们就有办法解了。所谓超递增是指序列满足如下条件$$ a_i\sum_{k1}^{i-1}a_k $$即第 i 个数大于前面所有数的和。为什么满足这样的条件就可以解密了呢这是因为如果加密后的结果大于 $a_n$那么其前面的系数 $x_n$ 必须为 1反之即便把前面所有数全部装入系数全 1也无法使得等式成立。因此从最大的 $a_n$ 开始从后往前贪心判断就可以立马得到对应的明文。具体解密算法如下令 S 密文值i 从 n 递减到 1若 $S \geq a_i$则 $x_i 1$令 $S S - a_i$否则 $x_i 0$循环结束后 S 应为 0得到的 $x_1x_2...x_n$ 即为明文的二进制位串。从仓库中 knapsack.md 的表述看超递增序列保证了「从高位到低位逐位可判定」的唯一解性质这是整个体制可解密的核心。公开序列带来的隐患但是这样又出现了一个问题由于 $a_i$ 是公开的如果攻击者截获了密文那么它也就很容易去破解这样的密码——直接对公开的普通序列做子集和求解虽然困难但若序列本身就是超递增的攻击者同样可以用上面的贪心算法还原明文。为了弥补这样的问题就出现了 Merkle–Hellman 这样的加密算法我们可以使用初始的背包集作为私钥变换后的背包集作为公钥再稍微改动加密过程即可。Merkle–Hellman 加密体制详解Merkle–Hellman背包加密的核心思想是用模乘运算把一个超递增的私钥序列「打乱」成看似普通的公钥序列只有知道陷门乘数 w 与模数 m的人才能把密文还原回超递增序列上的求解问题。公私钥生成生成私钥私钥就是初始的背包集这里我们使用超递增序列。怎么生成呢可以假设 $a_11$那么 $a_21$ 即可类似的可以依次生成后面的值例如取$$ a_11,\ a_22,\ a_34,\ a_48,\ ... $$每个新元素只需要落在「前 n-1 项之和 1」以上的范围即可保证超递增性质。生成公钥在生成公钥的过程中主要使用了模乘运算。步骤如下生成模乘的模数 m这里要确保$$ m\sum_{i1}^{n}a_i $$即 m 大于私钥序列所有元素之和这一条件保证解密时不会发生模回绕见下文解密部分。选择模乘的乘数 w作为私钥的一部分并且确保$$ gcd(w,m)1 $$即 w 与 m 互素从而保证 w 在模 m 下存在乘法逆元 $w^{-1}$。通过如下公式生成公钥$$ b_i \equiv w a_i \bmod m $$并将这个新的背包集 $b_i$ 和 m 作为公钥发布。私钥则是 $(a_1,...,a_n)$ 与 w。加解密流程加密假设我们要加密的明文为 v其每一个比特位为 $v_i$0/1那么加密的结果为$$ \sum_{i1}^{n}b_iv_i \bmod m $$也就是把明文的二进制位串当作系数对公钥序列做带权求和。对于密文方而言公钥序列 $b_i$ 看起来是普通整数不存在明显的超递增结构因而难以直接贪心还原。解密对于解密方首先可以求得 w 关于 m 的逆元 $w^{-1}$利用扩展欧几里得算法。然后将得到的密文乘以 $w^{-1}$ 即可得到明文这是因为$$ \sum_{i1}^{n}w^{-1}b_iv_i \bmod m\sum_{i1}^{n}a_iv_i \bmod m $$其中使用了 $b_i \equiv w a_i \bmod m$ 的关系。由于每一块的加密消息都是小于 m 的m 大于私钥元素之和也大于任意组合和模运算不会产生回绕求得的结果自然就是明文对应的子集和再配合私钥序列的超递增性质逐位还原出 $v_i$。这里需要特别强调 m 取值条件的作用若 $m \leq \sum a_i$则 $w a_i \bmod m$ 会导致信息丢失解密时无法精确恢复明文因此「m 大于私钥总和」是参数正确性的关键约束。体制被攻破的根本原因该加密体制在提出后两年后即被破译。破译的基本思想是我们不一定需要找出正确的乘数 w即陷门信息只需找出任意模数 $m$ 和乘数 $w$只要使用 $w$ 去乘公开的背包向量 B 时能够产生超递增的背包向量即可。一旦找到这样一组 $(w, m)$攻击者就可以对截获的密文施以与合法解密完全相同的流程乘以 $w^{-1}$ 后在新的超递增序列上贪心还原明文。这意味着陷门并非密码学意义上不可替代的秘密体制的安全假设公开向量与私钥向量在格意义下「不可区分」被证明不成立。从格论看攻击原理为什么「找到任意 $w$、$m$ 使 $wB \bmod m$ 超递增」是可行的这需要从仓库的格论章节理解。CTF-Wiki 的 格概述 明确指出基于格的密码分析是格理论的重要研究方向之一其中第一项就是Knapsack cryptosystems背包密码体制。在 格基本介绍 中格被定义为 m 维欧式空间 $R^m$ 中 n 个线性无关向量 $b_i$ 的所有整系数线性组合$$ L(B){\sum_{i1}^{n}x_ib_i:x_i \in Z} $$其中最短向量问题SVP、最近向量问题CVP是格上公认的困难问题。而 Lenstra–Lenstra–LovaszLLL 算法 正是求解这些问题的近似算法它可以在多项式时间内找到一组「短且近乎正交」的格基。背包密文 $C \sum b_iv_i$ 恰好可以被构造为一个格中的短向量问题若我们构造如下矩阵$$ A \left[ \begin{matrix} 1 0 0 \cdots 0 b_1 \ 0 1 0 \cdots 0 b_2 \ \vdots \vdots \vdots \ddots \vdots \ 0 0 0 \cdots 1 b_n \ 0 0 0 \cdots 0 -C \ \end{matrix} \right] $$那么明文向量 $(v_1,...,v_n,0)$ 正是该格中的一个点其最后一维坐标为 $\sum b_iv_i - C 0$且前 n 维全部为 0/1 构成短向量。当公钥序列 $b_i$ 相对密文 C 较「小」时这个明文向量就是格中的一个极短向量LLL 规约后得到的短向量即直接对应明文位串。这正是破解脚本中用Matrix(ZZ, nbit1, nbit1)构造矩阵后调用A.LLL()的数学依据。实战破解2014 ASIS CTF Quals Archaic 完整复现下面以 2014 年 ASIS Cyber Security Contest Quals 中的Archaic一题为例完整走一遍从读题、分析密钥生成到 LLL 攻击还原 flag 的过程。题目源码分析首先查看源程序secret CENSORED msg_bit bin(int(secret.encode(hex), 16))[2:]首先得到了 secret 的所有二进制位。其次利用如下函数得到 keypair包含公钥与私钥keyPair makeKey(len(msg_bit))仔细分析makeKey函数def makeKey(n): privKey [random.randint(1, 4**n)] s privKey[0] for i in range(1, n): privKey.append(random.randint(s 1, 4**(n i))) s privKey[i] q random.randint(privKey[n-1] 1, 2*privKey[n-1]) r random.randint(1, q) while gmpy2.gcd(r, q) ! 1: r random.randint(1, q) pubKey [ r*w % q for w in privKey ] return privKey, q, r, pubKey可以看出privKey是一个超递增序列每一项都大于此前所有项之和并且得到的 q 比privKey中所有数的和还要大此外我们得到的 r 恰好与 q 互素gcd(r, q) 1。这一切都表明该加密是一个标准的 Merkle–Hellman 背包加密privKey—— 超递增私钥序列q—— 模数 m大于私钥总和r—— 乘数 w与 q 互素pubKey—— 公开的背包向量 $b_i r \cdot privKey_i \bmod q$。果然加密函数就是对于消息的每一位乘以对应的公钥并求和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:]这里cipher即为 $\sum b_iv_i$与上文加密公式完全一致。LLL 格攻击脚本破解脚本直接构造「单位矩阵 公钥 密文」形式的格矩阵并对其实施 LLL 规约import binascii # open the public key and strip the spaces so we have a decent array fileKey open(pub.Key, rb) pubKey fileKey.read().replace( , ).replace(L, ).strip([]).split(,) nbit len(pubKey) # open the encoded message fileEnc open(enc.txt, rb) encoded fileEnc.read().replace(L, ) print start # create a large matrix of 0s (dimensions are public key length 1) A Matrix(ZZ, nbit 1, nbit 1) # fill in the identity matrix for i in xrange(nbit): A[i, i] 1 # replace the bottom row with your public key for i in xrange(nbit): A[i, nbit] pubKey[i] # last element is the encoded message A[nbit, nbit] -int(encoded) res A.LLL() for i in range(0, nbit 1): # print solution M res.row(i).list() flag True for m in M: if m ! 0 and m ! 1: flag False break if flag: print i, M M .join(str(j) for j in M) # remove the last bit M M[:-1] M hex(int(M, 2))[2:-1] print M脚本要点逐行解析读取公钥文件pub.Key去除空格、L后缀与方括号按逗号切分成整数数组得到nbit即明文比特数读取密文文件enc.txt得到整数encoded构造 $(nbit1)\times(nbit1)$ 的整系数矩阵A左上角是 nbit 阶单位矩阵保证行向量前 nbit 维记录明文位最后一列放置公钥元素 $b_i$矩阵右下角放置-int(encoded)调用A.LLL()进行格基规约遍历规约后的所有行找出只含 0 和 1的行——这正是明文对应的系数向量因为加密时明文被分解为 0/1 比特串去掉该行的最后一个数字对应密文列的系数将剩下的 0/1 串还原成十六进制字节串。这里需要注意两点得到的 LLL 攻击矩阵res中只包含 01 值的行才是我们想要的结果因为我们对于明文加密时会将其分解为二进制比特串我们还需要去掉对应那一行的最后一个数字它是 $-\text{encoded}$ 那一列的系数不属于明文位。运行脚本输出295 [1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0] 415349535f3962643364356664323432323638326331393536383830366130373036316365 import binascii binascii.unhexlify(415349535f3962643364356664323432323638326331393536383830366130373036316365) ASIS_9bd3d5fd2422682c19568806a07061ce还原 flag第 295 行的规约结果即为明文的 0/1 系数向量去掉最后一个数字后转换为整数再转为十六进制得到字符串415349535f3962643364356664323432323638326331393536383830366130373036316365用binascii.unhexlify解码后即为最终 flagASIS_9bd3d5fd2422682c19568806a07061ce做题要点总结针对背包类题目可以总结出如下通用判断与攻击流程识别特征题目给出一个较长的公钥数组pubKey与一个整数密文或以二进制串形式给出的密文且加密为逐位乘加求和。若题目源码中出现gcd(r, q) 1、超递增私钥与q sum(privKey)的判断即可确认为 Merkle–Hellman 背包加密。密钥生成逆向私钥序列满足 $a_i \sum_{ki}a_k$模数 m 需大于私钥总和乘数 w 与 m 互素公钥 $b_i \equiv w a_i \bmod m$。解密思路合法解密先求 $w^{-1} \bmod m$将密文乘 $w^{-1}$ 还原到超递增序列再从高位向低位贪心还原明文位串。攻击思路不必恢复真实陷门只需构造「单位矩阵 公钥 密文」的格矩阵调用 LLL 规约筛选只含 0/1 的行即为明文向量相关原理可结合仓库的 格概述、格基本介绍 与 LLL 格基规约算法 深入理解。相关练习题目2017 国赛 classic同样是经典的背包加密题目可以作为本文攻击思路的巩固练习尝试用 LLL 规约脚本自行还原明文。参考本文核心内容继承自 knapsack.md密钥生成、加解密公式与 Archaic 题目源码均出自该文档格论背景参考仓库 格概述、格基本介绍、LLL 格基规约算法 与 CVP 问题背包加密在非对称密码体系中的定位可参考 非对称加密介绍。赞分享文档网络安全教程【免费下载链接】ctf-wikiCome and join us, we need you!项目地址https://gitcode.com/gh_mirrors/ct/ctf-wiki点击查看免费下载相关推荐CTF 非對稱加密深度解析Merkle–Hellman 揹包加密與 LLL 格攻擊實戰ctf-wikiCTF 非對稱加密深度解析Merkle–Hellman 揹包加密與 LLL 格攻擊實戰ctf wiki 本篇指南以 ctf wiki 非對稱加密章節中的揹文档网络安全教程ctf-wiki 格基规约算法LLL实战指南原理推导、整数关系检测与格攻击应用ctf wiki 格基规约算法LLL实战指南原理推导、整数关系检测与格攻击应用 导读 格基规约Lattice Basis Reduction是格密码学文档网络安全教程CTF 中的 RSA Coppersmith 攻击从 LLL 格基约化到广播、相关消息与低解密指数攻击实战解析CTF 中的 RSA Coppersmith 攻击从 LLL 格基约化到广播、相关消息与低解密指数攻击实战解析 本篇技术指南以 Coppersmith 相關攻文档网络安全教程上一篇终极指南在Linux系统上使用Anbox高效运行Android应用下一篇Linux系统制作Windows启动盘终极指南WoeUSB-ng完全教程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考