約攻擊實戰(zhàn))
文檔網絡安全教程【免費下載鏈接】ctf-wikiCome and join us, we need you!項目地址https://gitcode.com/gh_mirrors/ct/ctf-wiki點擊查看免費下載背包加密Knapsack Cryptosystem是密碼學史上極具教學價值的經典非對稱加密體制它以 NP 完全的「子集和問題」為安全基礎利用超遞增序列構造陷門實現(xiàn)解密卻在提出后不久即被格基規(guī)約Lattice Reduction攻破。本篇文章以 CTF-Wiki 倉庫中的 knapsack.md 為骨架結合倉庫內格論章節(jié)的源碼級原理佐證完整講解背包問題的數學定義、超遞增序列的生成邏輯、Merkle–Hellman 公私鑰生成與加解密流程并復現(xiàn) 2014 年 ASIS CTF Archaic 一題的 LLL 破解全過程。讀完本文你將掌握識別背包類加密題目的特征、手動構造密鑰以及用格攻擊腳本快速還原明文的能力。背包問題的數學本質子集和問題與加密雛形假定一個背包可以稱重 W現(xiàn)在有 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$循環(huán)結束后 S 應為 0得到的 $x_1x_2...x_n$ 即為明文的二進制位串。從倉庫中 knapsack.md 的表述看超遞增序列保證了「從高位到低位逐位可判定」的唯一解性質這是整個體制可解密的核心。公開序列帶來的隱患但是這樣又出現(xiàn)了一個問題由于 $a_i$ 是公開的如果攻擊者截獲了密文那么它也就很容易去破解這樣的密碼——直接對公開的普通序列做子集和求解雖然困難但若序列本身就是超遞增的攻擊者同樣可以用上面的貪心算法還原明文。為了彌補這樣的問題就出現(xiàn)了 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 大于私鑰序列所有元素之和這一條件保證解密時不會發(fā)生?；乩@見下文解密部分。選擇模乘的乘數 w作為私鑰的一部分并且確保$$ gcd(w,m)1 $$即 w 與 m 互素從而保證 w 在模 m 下存在乘法逆元 $w^{-1}$。通過如下公式生成公鑰$$ b_i \equiv w a_i \bmod m $$并將這個新的背包集 $b_i$ 和 m 作為公鑰發(fā)布。私鑰則是 $(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}$ 后在新的超遞增序列上貪心還原明文。這意味著陷門并非密碼學意義上不可替代的秘密體制的安全假設公開向量與私鑰向量在格意義下「不可區(qū)分」被證明不成立。從格論看攻擊原理為什么「找到任意 $w$、$m$ 使 $wB \bmod m$ 超遞增」是可行的這需要從倉庫的格論章節(jié)理解。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 規(guī)約后得到的短向量即直接對應明文位串。這正是破解腳本中用Matrix(ZZ, nbit1, nbit1)構造矩陣后調用A.LLL()的數學依據。實戰(zhàn)破解2014 ASIS CTF Quals Archaic 完整復現(xiàn)下面以 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 規(guī)約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()進行格基規(guī)約遍歷規(guī)約后的所有行找出只含 0 和 1的行——這正是明文對應的系數向量因為加密時明文被分解為 0/1 比特串去掉該行的最后一個數字對應密文列的系數將剩下的 0/1 串還原成十六進制字節(jié)串。這里需要注意兩點得到的 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 行的規(guī)約結果即為明文的 0/1 系數向量去掉最后一個數字后轉換為整數再轉為十六進制得到字符串415349535f3962643364356664323432323638326331393536383830366130373036316365用binascii.unhexlify解碼后即為最終 flagASIS_9bd3d5fd2422682c19568806a07061ce做題要點總結針對背包類題目可以總結出如下通用判斷與攻擊流程識別特征題目給出一個較長的公鑰數組pubKey與一個整數密文或以二進制串形式給出的密文且加密為逐位乘加求和。若題目源碼中出現(xiàn)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 規(guī)約篩選只含 0/1 的行即為明文向量相關原理可結合倉庫的 格概述、格基本介紹 與 LLL 格基規(guī)約算法 深入理解。相關練習題目2017 國賽 classic同樣是經典的背包加密題目可以作為本文攻擊思路的鞏固練習嘗試用 LLL 規(guī)約腳本自行還原明文。參考本文核心內容繼承自 knapsack.md密鑰生成、加解密公式與 Archaic 題目源碼均出自該文檔格論背景參考倉庫 格概述、格基本介紹、LLL 格基規(guī)約算法 與 CVP 問題背包加密在非對稱密碼體系中的定位可參考 非對稱加密介紹。贊分享文檔網絡安全教程【免費下載鏈接】ctf-wikiCome and join us, we need you!項目地址https://gitcode.com/gh_mirrors/ct/ctf-wiki點擊查看免費下載相關推薦CTF 非對稱加密深度解析Merkle–Hellman 揹包加密與 LLL 格攻擊實戰(zhàn)ctf-wikiCTF 非對稱加密深度解析Merkle–Hellman 揹包加密與 LLL 格攻擊實戰(zhàn)ctf wiki 本篇指南以 ctf wiki 非對稱加密章節(jié)中的揹文檔網絡安全教程ctf-wiki 格基規(guī)約算法LLL實戰(zhàn)指南原理推導、整數關系檢測與格攻擊應用ctf wiki 格基規(guī)約算法LLL實戰(zhàn)指南原理推導、整數關系檢測與格攻擊應用 導讀 格基規(guī)約Lattice Basis Reduction是格密碼學文檔網絡安全教程CTF 中的 RSA Coppersmith 攻擊從 LLL 格基約化到廣播、相關消息與低解密指數攻擊實戰(zhàn)解析CTF 中的 RSA Coppersmith 攻擊從 LLL 格基約化到廣播、相關消息與低解密指數攻擊實戰(zhàn)解析 本篇技術指南以 Coppersmith 相關攻文檔網絡安全教程上一篇終極指南在Linux系統(tǒng)上使用Anbox高效運行Android應用下一篇Linux系統(tǒng)制作Windows啟動盤終極指南WoeUSB-ng完全教程創(chuàng)作聲明：本文部分內容由AI輔助生成（AIGC），僅供參考 CTF-Wiki 背包加密專題：從超遞增序列到 Merkle–Hellman 與 LLL 格基規(guī)約攻擊實戰(zhàn)
文檔網絡安全教程【免費下載鏈接】ctf-wikiCome and join us, we need you!項目地址https://gitcode.com/gh_mirrors/ct/ctf-wiki點擊查看免費下載背包加密Knapsack Cryptosystem是密碼學史上極具教學價值的經典非對稱加密體制它以 NP 完全的「子集和問題」為安全基礎利用超遞增序列構造陷門實現(xiàn)解密卻在提出后不久即被格基規(guī)約Lattice Reduction攻破。本篇文章以 CTF-Wiki 倉庫中的 knapsack.md 為骨架結合倉庫內格論章節(jié)的源碼級原理佐證完整講解背包問題的數學定義、超遞增序列的生成邏輯、Merkle–Hellman 公私鑰生成與加解密流程并復現(xiàn) 2014 年 ASIS CTF Archaic 一題的 LLL 破解全過程。讀完本文你將掌握識別背包類加密題目的特征、手動構造密鑰以及用格攻擊腳本快速還原明文的能力。背包問題的數學本質子集和問題與加密雛形假定一個背包可以稱重 W現(xiàn)在有 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$循環(huán)結束后 S 應為 0得到的 $x_1x_2...x_n$ 即為明文的二進制位串。從倉庫中 knapsack.md 的表述看超遞增序列保證了「從高位到低位逐位可判定」的唯一解性質這是整個體制可解密的核心。公開序列帶來的隱患但是這樣又出現(xiàn)了一個問題由于 $a_i$ 是公開的如果攻擊者截獲了密文那么它也就很容易去破解這樣的密碼——直接對公開的普通序列做子集和求解雖然困難但若序列本身就是超遞增的攻擊者同樣可以用上面的貪心算法還原明文。為了彌補這樣的問題就出現(xiàn)了 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 大于私鑰序列所有元素之和這一條件保證解密時不會發(fā)生?；乩@見下文解密部分。選擇模乘的乘數 w作為私鑰的一部分并且確保$$ gcd(w,m)1 $$即 w 與 m 互素從而保證 w 在模 m 下存在乘法逆元 $w^{-1}$。通過如下公式生成公鑰$$ b_i \equiv w a_i \bmod m $$并將這個新的背包集 $b_i$ 和 m 作為公鑰發(fā)布。私鑰則是 $(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}$ 后在新的超遞增序列上貪心還原明文。這意味著陷門并非密碼學意義上不可替代的秘密體制的安全假設公開向量與私鑰向量在格意義下「不可區(qū)分」被證明不成立。從格論看攻擊原理為什么「找到任意 $w$、$m$ 使 $wB \bmod m$ 超遞增」是可行的這需要從倉庫的格論章節(jié)理解。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 規(guī)約后得到的短向量即直接對應明文位串。這正是破解腳本中用Matrix(ZZ, nbit1, nbit1)構造矩陣后調用A.LLL()的數學依據。實戰(zhàn)破解2014 ASIS CTF Quals Archaic 完整復現(xiàn)下面以 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 規(guī)約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()進行格基規(guī)約遍歷規(guī)約后的所有行找出只含 0 和 1的行——這正是明文對應的系數向量因為加密時明文被分解為 0/1 比特串去掉該行的最后一個數字對應密文列的系數將剩下的 0/1 串還原成十六進制字節(jié)串。這里需要注意兩點得到的 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 行的規(guī)約結果即為明文的 0/1 系數向量去掉最后一個數字后轉換為整數再轉為十六進制得到字符串415349535f3962643364356664323432323638326331393536383830366130373036316365用binascii.unhexlify解碼后即為最終 flagASIS_9bd3d5fd2422682c19568806a07061ce做題要點總結針對背包類題目可以總結出如下通用判斷與攻擊流程識別特征題目給出一個較長的公鑰數組pubKey與一個整數密文或以二進制串形式給出的密文且加密為逐位乘加求和。若題目源碼中出現(xiàn)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 規(guī)約篩選只含 0/1 的行即為明文向量相關原理可結合倉庫的 格概述、格基本介紹 與 LLL 格基規(guī)約算法 深入理解。相關練習題目2017 國賽 classic同樣是經典的背包加密題目可以作為本文攻擊思路的鞏固練習嘗試用 LLL 規(guī)約腳本自行還原明文。參考本文核心內容繼承自 knapsack.md密鑰生成、加解密公式與 Archaic 題目源碼均出自該文檔格論背景參考倉庫 格概述、格基本介紹、LLL 格基規(guī)約算法 與 CVP 問題背包加密在非對稱密碼體系中的定位可參考 非對稱加密介紹。贊分享文檔網絡安全教程【免費下載鏈接】ctf-wikiCome and join us, we need you!項目地址https://gitcode.com/gh_mirrors/ct/ctf-wiki點擊查看免費下載相關推薦CTF 非對稱加密深度解析Merkle–Hellman 揹包加密與 LLL 格攻擊實戰(zhàn)ctf-wikiCTF 非對稱加密深度解析Merkle–Hellman 揹包加密與 LLL 格攻擊實戰(zhàn)ctf wiki 本篇指南以 ctf wiki 非對稱加密章節(jié)中的揹文檔網絡安全教程ctf-wiki 格基規(guī)約算法LLL實戰(zhàn)指南原理推導、整數關系檢測與格攻擊應用ctf wiki 格基規(guī)約算法LLL實戰(zhàn)指南原理推導、整數關系檢測與格攻擊應用 導讀 格基規(guī)約Lattice Basis Reduction是格密碼學文檔網絡安全教程CTF 中的 RSA Coppersmith 攻擊從 LLL 格基約化到廣播、相關消息與低解密指數攻擊實戰(zhàn)解析CTF 中的 RSA Coppersmith 攻擊從 LLL 格基約化到廣播、相關消息與低解密指數攻擊實戰(zhàn)解析 本篇技術指南以 Coppersmith 相關攻文檔網絡安全教程上一篇終極指南在Linux系統(tǒng)上使用Anbox高效運行Android應用下一篇Linux系統(tǒng)制作Windows啟動盤終極指南WoeUSB-ng完全教程創(chuàng)作聲明：本文部分內容由AI輔助生成（AIGC），僅供參考