文檔網(wǎng)絡(luò)安全教程【免費(fèi)下載鏈接】ctf-wikiCome and join us, we need you!項(xiàng)目地址https://gitcode.com/gh_mirrors/ct/ctf-wiki點(diǎn)擊查看免費(fèi)下載背包加密Knapsack Cryptosystem是密碼學(xué)史上極具教學(xué)價(jià)值的經(jīng)典非對(duì)稱加密體制它以 NP 完全的「子集和問題」為安全基礎(chǔ)利用超遞增序列構(gòu)造陷門實(shí)現(xiàn)解密卻在提出后不久即被格基規(guī)約Lattice Reduction攻破。本篇文章以 CTF-Wiki 倉庫中的 knapsack.md 為骨架結(jié)合倉庫內(nèi)格論章節(jié)的源碼級(jí)原理佐證完整講解背包問題的數(shù)學(xué)定義、超遞增序列的生成邏輯、Merkle–Hellman 公私鑰生成與加解密流程并復(fù)現(xiàn) 2014 年 ASIS CTF Archaic 一題的 LLL 破解全過程。讀完本文你將掌握識(shí)別背包類加密題目的特征、手動(dòng)構(gòu)造密鑰以及用格攻擊腳本快速還原明文的能力。背包問題的數(shù)學(xué)本質(zhì)子集和問題與加密雛形假定一個(gè)背包可以稱重 W現(xiàn)在有 n 個(gè)物品其重量分別為 $a_1, a_2,...,a_n$。我們想知道裝哪些物品可以恰好使得背包裝滿并且每個(gè)物品只能被裝一次。這其實(shí)就是在求解如下方程$$ x_1a_1x_2a_2...x_na_nW $$其中所有的 $x_i$ 只能取 0 和 1。顯然我們必須枚舉所有 n 個(gè)物品的組合才能解決這個(gè)問題復(fù)雜度為 $2^n$這也就是背包加密的妙處所在——加密方向已知物品集合求組合和是容易的而逆向求解已知和反推組合在公開的普通序列下是困難的。在加密時(shí)如果我們想要加密的明文為 x那么可以將其表示為 n 位二進(jìn)制數(shù)然后分別乘上 $a_i$ 再求和即可得到加密結(jié)果。也就是說一個(gè) n 比特的明文 v 對(duì)應(yīng)一個(gè) 0/1 系數(shù)向量加密結(jié)果就是對(duì)應(yīng)物品重量的線性組合。為什么必須引入超遞增序列上述方案面臨一個(gè)致命問題解密時(shí)我們確實(shí)讓其他人難以解密密文但我們自己也確實(shí)沒有辦法解密密文——因?yàn)楹戏ń饷苷咄瑯右鎸?duì)這個(gè) NP 難題。但是當(dāng) $a_i$ 是超遞增superincreasing序列時(shí)我們就有辦法解了。所謂超遞增是指序列滿足如下條件$$ a_i\sum_{k1}^{i-1}a_k $$即第 i 個(gè)數(shù)大于前面所有數(shù)的和。為什么滿足這樣的條件就可以解密了呢這是因?yàn)槿绻用芎蟮慕Y(jié)果大于 $a_n$那么其前面的系數(shù) $x_n$ 必須為 1反之即便把前面所有數(shù)全部裝入系數(shù)全 1也無法使得等式成立。因此從最大的 $a_n$ 開始從后往前貪心判斷就可以立馬得到對(duì)應(yīng)的明文。具體解密算法如下令 S 密文值i 從 n 遞減到 1若 $S \geq a_i$則 $x_i 1$令 $S S - a_i$否則 $x_i 0$循環(huán)結(jié)束后 S 應(yīng)為 0得到的 $x_1x_2...x_n$ 即為明文的二進(jìn)制位串。從倉庫中 knapsack.md 的表述看超遞增序列保證了「從高位到低位逐位可判定」的唯一解性質(zhì)這是整個(gè)體制可解密的核心。公開序列帶來的隱患但是這樣又出現(xiàn)了一個(gè)問題由于 $a_i$ 是公開的如果攻擊者截獲了密文那么它也就很容易去破解這樣的密碼——直接對(duì)公開的普通序列做子集和求解雖然困難但若序列本身就是超遞增的攻擊者同樣可以用上面的貪心算法還原明文。為了彌補(bǔ)這樣的問題就出現(xiàn)了 Merkle–Hellman 這樣的加密算法我們可以使用初始的背包集作為私鑰變換后的背包集作為公鑰再稍微改動(dòng)加密過程即可。Merkle–Hellman 加密體制詳解Merkle–Hellman背包加密的核心思想是用模乘運(yùn)算把一個(gè)超遞增的私鑰序列「打亂」成看似普通的公鑰序列只有知道陷門乘數(shù) w 與模數(shù) m的人才能把密文還原回超遞增序列上的求解問題。公私鑰生成生成私鑰私鑰就是初始的背包集這里我們使用超遞增序列。怎么生成呢可以假設(shè) $a_11$那么 $a_21$ 即可類似的可以依次生成后面的值例如取$$ a_11,\ a_22,\ a_34,\ a_48,\ ... $$每個(gè)新元素只需要落在「前 n-1 項(xiàng)之和 1」以上的范圍即可保證超遞增性質(zhì)。生成公鑰在生成公鑰的過程中主要使用了模乘運(yùn)算。步驟如下生成模乘的模數(shù) m這里要確保$$ m\sum_{i1}^{n}a_i $$即 m 大于私鑰序列所有元素之和這一條件保證解密時(shí)不會(huì)發(fā)生?；乩@見下文解密部分。選擇模乘的乘數(shù) w作為私鑰的一部分并且確保$$ gcd(w,m)1 $$即 w 與 m 互素從而保證 w 在模 m 下存在乘法逆元 $w^{-1}$。通過如下公式生成公鑰$$ b_i \equiv w a_i \bmod m $$并將這個(gè)新的背包集 $b_i$ 和 m 作為公鑰發(fā)布。私鑰則是 $(a_1,...,a_n)$ 與 w。加解密流程加密假設(shè)我們要加密的明文為 v其每一個(gè)比特位為 $v_i$0/1那么加密的結(jié)果為$$ \sum_{i1}^{n}b_iv_i \bmod m $$也就是把明文的二進(jìn)制位串當(dāng)作系數(shù)對(duì)公鑰序列做帶權(quán)求和。對(duì)于密文方而言公鑰序列 $b_i$ 看起來是普通整數(shù)不存在明顯的超遞增結(jié)構(gòu)因而難以直接貪心還原。解密對(duì)于解密方首先可以求得 w 關(guān)于 m 的逆元 $w^{-1}$利用擴(kuò)展歐幾里得算法。然后將得到的密文乘以 $w^{-1}$ 即可得到明文這是因?yàn)?$ \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$ 的關(guān)系。由于每一塊的加密消息都是小于 m 的m 大于私鑰元素之和也大于任意組合和模運(yùn)算不會(huì)產(chǎn)生回繞求得的結(jié)果自然就是明文對(duì)應(yīng)的子集和再配合私鑰序列的超遞增性質(zhì)逐位還原出 $v_i$。這里需要特別強(qiáng)調(diào) m 取值條件的作用若 $m \leq \sum a_i$則 $w a_i \bmod m$ 會(huì)導(dǎo)致信息丟失解密時(shí)無法精確恢復(fù)明文因此「m 大于私鑰總和」是參數(shù)正確性的關(guān)鍵約束。體制被攻破的根本原因該加密體制在提出后兩年后即被破譯。破譯的基本思想是我們不一定需要找出正確的乘數(shù) w即陷門信息只需找出任意模數(shù) $m$ 和乘數(shù) $w$只要使用 $w$ 去乘公開的背包向量 B 時(shí)能夠產(chǎn)生超遞增的背包向量即可。一旦找到這樣一組 $(w, m)$攻擊者就可以對(duì)截獲的密文施以與合法解密完全相同的流程乘以 $w^{-1}$ 后在新的超遞增序列上貪心還原明文。這意味著陷門并非密碼學(xué)意義上不可替代的秘密體制的安全假設(shè)公開向量與私鑰向量在格意義下「不可區(qū)分」被證明不成立。從格論看攻擊原理為什么「找到任意 $w$、$m$ 使 $wB \bmod m$ 超遞增」是可行的這需要從倉庫的格論章節(jié)理解。CTF-Wiki 的 格概述 明確指出基于格的密碼分析是格理論的重要研究方向之一其中第一項(xiàng)就是Knapsack cryptosystems背包密碼體制。在 格基本介紹 中格被定義為 m 維歐式空間 $R^m$ 中 n 個(gè)線性無關(guān)向量 $b_i$ 的所有整系數(shù)線性組合$$ L(B){\sum_{i1}^{n}x_ib_i:x_i \in Z} $$其中最短向量問題SVP、最近向量問題CVP是格上公認(rèn)的困難問題。而 Lenstra–Lenstra–LovaszLLL 算法 正是求解這些問題的近似算法它可以在多項(xiàng)式時(shí)間內(nèi)找到一組「短且近乎正交」的格基。背包密文 $C \sum b_iv_i$ 恰好可以被構(gòu)造為一個(gè)格中的短向量問題若我們構(gòu)造如下矩陣$$ 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)$ 正是該格中的一個(gè)點(diǎn)其最后一維坐標(biāo)為 $\sum b_iv_i - C 0$且前 n 維全部為 0/1 構(gòu)成短向量。當(dāng)公鑰序列 $b_i$ 相對(duì)密文 C 較「小」時(shí)這個(gè)明文向量就是格中的一個(gè)極短向量LLL 規(guī)約后得到的短向量即直接對(duì)應(yīng)明文位串。這正是破解腳本中用Matrix(ZZ, nbit1, nbit1)構(gòu)造矩陣后調(diào)用A.LLL()的數(shù)學(xué)依據(jù)。實(shí)戰(zhàn)破解2014 ASIS CTF Quals Archaic 完整復(fù)現(xiàn)下面以 2014 年 ASIS Cyber Security Contest Quals 中的Archaic一題為例完整走一遍從讀題、分析密鑰生成到 LLL 攻擊還原 flag 的過程。題目源碼分析首先查看源程序secret CENSORED msg_bit bin(int(secret.encode(hex), 16))[2:]首先得到了 secret 的所有二進(jìn)制位。其次利用如下函數(shù)得到 keypair包含公鑰與私鑰keyPair makeKey(len(msg_bit))仔細(xì)分析makeKey函數(shù)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是一個(gè)超遞增序列每一項(xiàng)都大于此前所有項(xiàng)之和并且得到的 q 比privKey中所有數(shù)的和還要大此外我們得到的 r 恰好與 q 互素gcd(r, q) 1。這一切都表明該加密是一個(gè)標(biāo)準(zhǔn)的 Merkle–Hellman 背包加密privKey—— 超遞增私鑰序列q—— 模數(shù) m大于私鑰總和r—— 乘數(shù) w與 q 互素pubKey—— 公開的背包向量 $b_i r \cdot privKey_i \bmod q$。果然加密函數(shù)就是對(duì)于消息的每一位乘以對(duì)應(yīng)的公鑰并求和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 格攻擊腳本破解腳本直接構(gòu)造「單位矩陣 公鑰 密文」形式的格矩陣并對(duì)其實(shí)施 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腳本要點(diǎn)逐行解析讀取公鑰文件pub.Key去除空格、L后綴與方括號(hào)按逗號(hào)切分成整數(shù)數(shù)組得到nbit即明文比特?cái)?shù)讀取密文文件enc.txt得到整數(shù)encoded構(gòu)造 $(nbit1)\times(nbit1)$ 的整系數(shù)矩陣A左上角是 nbit 階單位矩陣保證行向量前 nbit 維記錄明文位最后一列放置公鑰元素 $b_i$矩陣右下角放置-int(encoded)調(diào)用A.LLL()進(jìn)行格基規(guī)約遍歷規(guī)約后的所有行找出只含 0 和 1的行——這正是明文對(duì)應(yīng)的系數(shù)向量因?yàn)榧用軙r(shí)明文被分解為 0/1 比特串去掉該行的最后一個(gè)數(shù)字對(duì)應(yīng)密文列的系數(shù)將剩下的 0/1 串還原成十六進(jìn)制字節(jié)串。這里需要注意兩點(diǎn)得到的 LLL 攻擊矩陣res中只包含 01 值的行才是我們想要的結(jié)果因?yàn)槲覀儗?duì)于明文加密時(shí)會(huì)將其分解為二進(jìn)制比特串我們還需要去掉對(duì)應(yīng)那一行的最后一個(gè)數(shù)字它是 $-\text{encoded}$ 那一列的系數(shù)不屬于明文位。運(yùn)行腳本輸出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ī)約結(jié)果即為明文的 0/1 系數(shù)向量去掉最后一個(gè)數(shù)字后轉(zhuǎn)換為整數(shù)再轉(zhuǎn)為十六進(jìn)制得到字符串415349535f3962643364356664323432323638326331393536383830366130373036316365用binascii.unhexlify解碼后即為最終 flagASIS_9bd3d5fd2422682c19568806a07061ce做題要點(diǎn)總結(jié)針對(duì)背包類題目可以總結(jié)出如下通用判斷與攻擊流程識(shí)別特征題目給出一個(gè)較長(zhǎng)的公鑰數(shù)組pubKey與一個(gè)整數(shù)密文或以二進(jìn)制串形式給出的密文且加密為逐位乘加求和。若題目源碼中出現(xiàn)gcd(r, q) 1、超遞增私鑰與q sum(privKey)的判斷即可確認(rèn)為 Merkle–Hellman 背包加密。密鑰生成逆向私鑰序列滿足 $a_i \sum_{ki}a_k$模數(shù) m 需大于私鑰總和乘數(shù) w 與 m 互素公鑰 $b_i \equiv w a_i \bmod m$。解密思路合法解密先求 $w^{-1} \bmod m$將密文乘 $w^{-1}$ 還原到超遞增序列再從高位向低位貪心還原明文位串。攻擊思路不必恢復(fù)真實(shí)陷門只需構(gòu)造「單位矩陣 公鑰 密文」的格矩陣調(diào)用 LLL 規(guī)約篩選只含 0/1 的行即為明文向量相關(guān)原理可結(jié)合倉庫的 格概述、格基本介紹 與 LLL 格基規(guī)約算法 深入理解。相關(guān)練習(xí)題目2017 國(guó)賽 classic同樣是經(jīng)典的背包加密題目可以作為本文攻擊思路的鞏固練習(xí)嘗試用 LLL 規(guī)約腳本自行還原明文。參考本文核心內(nèi)容繼承自 knapsack.md密鑰生成、加解密公式與 Archaic 題目源碼均出自該文檔格論背景參考倉庫 格概述、格基本介紹、LLL 格基規(guī)約算法 與 CVP 問題背包加密在非對(duì)稱密碼體系中的定位可參考 非對(duì)稱加密介紹。贊分享文檔網(wǎng)絡(luò)安全教程【免費(fèi)下載鏈接】ctf-wikiCome and join us, we need you!項(xiàng)目地址https://gitcode.com/gh_mirrors/ct/ctf-wiki點(diǎn)擊查看免費(fèi)下載相關(guān)推薦CTF 非對(duì)稱加密深度解析Merkle–Hellman 揹包加密與 LLL 格攻擊實(shí)戰(zhàn)ctf-wikiCTF 非對(duì)稱加密深度解析Merkle–Hellman 揹包加密與 LLL 格攻擊實(shí)戰(zhàn)ctf wiki 本篇指南以 ctf wiki 非對(duì)稱加密章節(jié)中的揹文檔網(wǎng)絡(luò)安全教程ctf-wiki 格基規(guī)約算法LLL實(shí)戰(zhàn)指南原理推導(dǎo)、整數(shù)關(guān)系檢測(cè)與格攻擊應(yīng)用ctf wiki 格基規(guī)約算法LLL實(shí)戰(zhàn)指南原理推導(dǎo)、整數(shù)關(guān)系檢測(cè)與格攻擊應(yīng)用 導(dǎo)讀 格基規(guī)約Lattice Basis Reduction是格密碼學(xué)文檔網(wǎng)絡(luò)安全教程CTF 中的 RSA Coppersmith 攻擊從 LLL 格基約化到廣播、相關(guān)消息與低解密指數(shù)攻擊實(shí)戰(zhàn)解析CTF 中的 RSA Coppersmith 攻擊從 LLL 格基約化到廣播、相關(guān)消息與低解密指數(shù)攻擊實(shí)戰(zhàn)解析 本篇技術(shù)指南以 Coppersmith 相關(guān)攻文檔網(wǎng)絡(luò)安全教程上一篇終極指南在Linux系統(tǒng)上使用Anbox高效運(yùn)行Android應(yīng)用下一篇Linux系統(tǒng)制作Windows啟動(dòng)盤終極指南WoeUSB-ng完全教程創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考