1. 項(xiàng)目概述從一道CTF賽題看Rabin密碼系統(tǒng)的實(shí)戰(zhàn)攻防最近在復(fù)盤一些經(jīng)典的CTFCapture The Flag密碼學(xué)賽題2022年網(wǎng)鼎杯的“crypto661-rabin”這道題給我留下了挺深的印象。它沒(méi)有用更常見(jiàn)的RSA而是選擇了Rabin密碼系統(tǒng)作為考點(diǎn)這本身就挺有意思。Rabin算法在教科書和理論介紹里往往被一筆帶過(guò)很多人只知道它“基于整數(shù)分解的困難性”和“解密有四個(gè)可能結(jié)果”但真到了實(shí)戰(zhàn)里面對(duì)一個(gè)具體的、包裝過(guò)的賽題怎么把理論轉(zhuǎn)化成一行行能跑出flag的代碼中間的門道可就多了。這道題的核心就是要求選手在已知Rabin加密的公鑰和密文的情況下恢復(fù)出原始的明文消息。聽(tīng)起來(lái)和RSA很像對(duì)吧但它的解密邏輯和陷阱設(shè)置截然不同。如果你直接用處理RSA的思路去套大概率會(huì)卡住或者得到一堆亂碼。這正體現(xiàn)了CTF密碼學(xué)的魅力——它考驗(yàn)的不是死記硬背而是對(duì)密碼學(xué)原理深刻的理解和靈活的運(yùn)用能力。接下來(lái)我就結(jié)合這道題把Rabin算法的里里外外、在CTF中的常見(jiàn)變形以及我踩過(guò)的坑給大家掰開(kāi)揉碎了講清楚。無(wú)論你是正在備賽的CTF新手還是想深入了解非對(duì)稱加密細(xì)節(jié)的開(kāi)發(fā)者相信都能從中獲得直接的幫助。2. Rabin密碼系統(tǒng)原理深度拆解要攻克這道題絕不能停留在“調(diào)用庫(kù)函數(shù)”的層面必須吃透Rabin的數(shù)學(xué)原理。它比RSA更直接地依賴于大整數(shù)分解的難度。2.1 算法核心簡(jiǎn)潔的數(shù)學(xué)構(gòu)造Rabin加密算法的核心過(guò)程異常簡(jiǎn)潔。密鑰生成選擇兩個(gè)大素?cái)?shù)p和q滿足p ≡ q ≡ 3 (mod 4)。這個(gè)條件是為了讓解密過(guò)程更高效利用Tonelli-Shanks算法求模平方根的特殊情況。計(jì)算模數(shù)n p * q。公鑰就是n私鑰是(p, q)。 你會(huì)發(fā)現(xiàn)公鑰極其簡(jiǎn)單只有一個(gè)n。這和我們熟悉的RSA公鑰(n, e)中e通常取65537不同Rabin的加密指數(shù)e固定為2。加密過(guò)程對(duì)于明文m要求0 m n加密就是計(jì)算密文cc ≡ m^2 (mod n)是的加密就是求明文的平方再模n。從計(jì)算上看它比RSA的模冪運(yùn)算m^e mod n更簡(jiǎn)單。解密過(guò)程這才是Rabin的精華和難點(diǎn)所在。已知密文c和私鑰(p, q)我們需要解方程m^2 ≡ c (mod n)由于n p * q這個(gè)方程等價(jià)于求解以下兩個(gè)方程組的公共解m^2 ≡ c (mod p)m^2 ≡ c (mod q)因?yàn)閜和q是素?cái)?shù)且滿足≡ 3 (mod 4)所以模素?cái)?shù)下的平方根有非常高效的解法計(jì)算c在模p下的解m_p c^((p1)/4) mod p計(jì)算c在模q下的解m_q c^((q1)/4) mod q這里利用了費(fèi)馬小定理和p ≡ 3 (mod 4)的性質(zhì)使得(p1)/4是整數(shù)并且(c^((p1)/4))^2 ≡ c^((p1)/2) ≡ c * c^((p-1)/2) ≡ c (mod p)當(dāng)c是模p的二次剩余時(shí)c^((p-1)/2) ≡ 1 (mod p)。得到m_p和m_q后每個(gè)都有兩個(gè)可能的值正和負(fù)即m_p和p - m_pm_q和q - m_q。然后利用中國(guó)剩余定理CRT將這四個(gè)組合兩兩配對(duì)就能得到原始明文m在模n下的四個(gè)可能的平方根。注意這里有一個(gè)關(guān)鍵點(diǎn)c必須同時(shí)是模p和模q的二次剩余加密解密才能正常進(jìn)行。在CTF題中這通常是默認(rèn)成立的但你需要知道這個(gè)前提。2.2 與RSA的對(duì)比為什么CTF愛(ài)考Rabin理解Rabin和RSA的區(qū)別能幫你更好地把握解題方向。特性Rabin 密碼系統(tǒng)RSA 密碼系統(tǒng)安全性基礎(chǔ)等價(jià)于大整數(shù)分解問(wèn)題已被證明基于大整數(shù)分解和RSA問(wèn)題的困難性未被證明等價(jià)加密指數(shù)固定為 2通常為 65537與φ(n)互質(zhì)即可解密結(jié)果有4個(gè)可能的明文有1個(gè)確定的明文計(jì)算速度加密解密更快計(jì)算平方/平方根相對(duì)較慢模冪運(yùn)算密鑰結(jié)構(gòu)公鑰僅為(n)公鑰為(n, e)CTF常見(jiàn)考點(diǎn)利用解密多解性、選擇密文攻擊、與填充結(jié)合的攻擊低加密指數(shù)、共模攻擊、側(cè)信道、p和q選取不當(dāng)最大的不同就是解密結(jié)果的唯一性。RSA解密永遠(yuǎn)得到一個(gè)確定的結(jié)果而Rabin會(huì)得到四個(gè)。這在CTF中意味著Flag識(shí)別解密后你需要從四個(gè)候選明文中根據(jù)格式如flag{...}、CTF{...}或可讀性人工識(shí)別出正確的那個(gè)。攻擊面Rabin對(duì)選擇密文攻擊是極度脆弱的。如果你能獲取一個(gè)解密Oracle即服務(wù)器能為你解密任意密文并返回四個(gè)結(jié)果之一或全部理論上你可以在多項(xiàng)式時(shí)間內(nèi)分解模數(shù)n。這在CTF中經(jīng)常以“服務(wù)器提供解密服務(wù)”的交互題形式出現(xiàn)。實(shí)操心得很多Rabin的CTF題最后一步解密出來(lái)的四個(gè)結(jié)果里可能只有一個(gè)是符合人類閱讀的ASCII字符串另外三個(gè)是看起來(lái)像亂碼的大整數(shù)。不要輕易放棄任何一個(gè)結(jié)果務(wù)必把它們都轉(zhuǎn)換成字節(jié)看看。有時(shí)候出題人甚至?xí)室獍裦lag放在那個(gè)“看起來(lái)不像”的結(jié)果里。3. “crypto661-rabin” 賽題實(shí)戰(zhàn)還原與解析光講理論不夠過(guò)癮我們直接回到“網(wǎng)鼎杯2022 crypto661-rabin”這道題。通常這類題目會(huì)提供一個(gè)壓縮包或描述里面包含類似以下的信息我根據(jù)常見(jiàn)模式進(jìn)行還原public.key或直接給出n 123456789...一個(gè)很大的整數(shù)ciphertext或encrypted_flagc 987654321...另一個(gè)很大的整數(shù)可能附帶一個(gè)簡(jiǎn)單的encrypt.py腳本展示加密過(guò)程就是c m^2 mod n。我們的任務(wù)很明確已知 (n, c)求 m。3.1 解題第一步分解模數(shù) n這是所有基于分解困難性密碼系統(tǒng)的共同突破口。在CTF中n通常不會(huì)真的不可分解出題人會(huì)用一些有特點(diǎn)的素?cái)?shù)來(lái)構(gòu)造它。嘗試在線分解數(shù)據(jù)庫(kù)對(duì)于不是特別大的n比如小于512位可以嘗試在factordb.com這類網(wǎng)站查詢可能已被收錄。檢查是否為光滑數(shù)使用yafu或sage等工具嘗試分解。如果p和q接近可以用費(fèi)馬分解法。關(guān)注特殊結(jié)構(gòu)在這道“網(wǎng)鼎杯”的題中經(jīng)過(guò)嘗試很可能發(fā)現(xiàn)n可以直接分解或者p和q非常接近以至于(pq)/2接近sqrt(n)(p-q)/2很小。我們可以用以下Python腳本進(jìn)行費(fèi)馬分解的嘗試import gmpy2 from Crypto.Util.number import * n 0xabcdef... # 替換為題目給出的n def fermat_factor(n): a gmpy2.isqrt(n) 1 b2 a*a - n while not gmpy2.is_square(b2): a 1 b2 a*a - n b gmpy2.isqrt(b2) p a b q a - b return int(p), int(q) p, q fermat_factor(n) print(fp {p}) print(fq {q}) print(fn p*q? {n p*q})假設(shè)我們成功分解得到p和q。踩坑記錄一定要驗(yàn)證p和q是否滿足p % 4 3和q % 4 3。雖然理論上Rabin要求這樣但有些CTF題會(huì)故意不滿足這時(shí)解密公式c^((p1)/4)就不適用了需要使用更一般的Tonelli-Shanks算法來(lái)求模平方根復(fù)雜度會(huì)提升。如果發(fā)現(xiàn)不滿足第一時(shí)間要反應(yīng)過(guò)來(lái)。3.2 解題第二步實(shí)現(xiàn)Rabin解密并處理多解得到p和q后我們就可以編寫解密腳本了。核心步驟就是前面原理部分講到的計(jì)算c在模p和模q下的“平方根”。組合所有可能的根。用CRT還原出模n下的四個(gè)可能明文。import gmpy2 from Crypto.Util.number import * # 題目數(shù)據(jù) n 0xabcdef... # 替換 c 0x123456... # 替換 # 分解得到的 p ... q ... assert p * q n assert p % 4 3 and q % 4 3 # 確認(rèn)條件滿足 def rabin_decrypt(c, p, q): Rabin解密返回四個(gè)可能的明文整數(shù) # 計(jì)算模p和模q下的平方根 mp pow(c, (p 1) // 4, p) mq pow(c, (q 1) // 4, q) # 每個(gè)都有兩個(gè)根 r1 mp r2 p - mp s1 mq s2 q - mq # 使用中國(guó)剩余定理組合 def crt(a, m, b, n): 解同余方程組 x ≡ a (mod m), x ≡ b (mod n) g, x, y gmpy2.gcdext(m, n) if (b - a) % g ! 0: return None lcm m // g * n return (a (b - a) // g * x * m) % lcm # 得到四個(gè)候選解 solutions [] for r in (r1, r2): for s in (s1, s2): root crt(r, p, s, q) if root is not None: solutions.append(root) return solutions possible_ms rabin_decrypt(c, p, q) print(fFound {len(possible_ms)} possible plaintexts:) for i, m in enumerate(possible_ms): try: # 嘗試轉(zhuǎn)換為字節(jié)串 flag_candidate long_to_bytes(m) # 通常flag會(huì)有可打印前綴過(guò)濾一下 if bflag in flag_candidate or bCTF in flag_candidate or flag_candidate.isascii(): print(f[{i}] (Possible Flag): {flag_candidate}) else: print(f[{i}] (Hex): {hex(m)[:50]}...) except: print(f[{i}] (Too large or invalid): {hex(m)[:50]}...)運(yùn)行這個(gè)腳本你大概率會(huì)在四個(gè)輸出中看到一個(gè)包含flag{或類似格式的字符串那就是本題的答案。3.3 解題第三步處理填充與編碼上面的腳本假設(shè)明文m直接就是數(shù)字。但在實(shí)際中為了增加安全性同時(shí)也是CTF的考點(diǎn)明文通常會(huì)經(jīng)過(guò)填充Padding和編碼。常見(jiàn)套路明文是字符串的字節(jié)形式比如flag{this_is_a_sample}被直接轉(zhuǎn)換成整數(shù)m。我們的解密腳本最后long_to_bytes就能直接看到。使用了PKCS#1 v1.5或OAEP等填充這會(huì)使明文結(jié)構(gòu)變復(fù)雜直接解密得到的數(shù)字需要解析填充格式才能提取出真·明文。Rabin本身很少直接套用這些復(fù)雜填充但CTF題可能會(huì)模仿。混合了其他編碼如Base64、Hex編碼后的字符串再做加密。解密后得到的是編碼后的文本需要進(jìn)一步解碼。對(duì)于“crypto661-rabin”根據(jù)網(wǎng)鼎杯的風(fēng)格很可能就是第一種最簡(jiǎn)單的情況。但如果遇到更復(fù)雜的情況你的解密腳本就需要增加一個(gè)“后處理”模塊。實(shí)操心得在寫解密腳本時(shí)long_to_bytes后不要只打印十六進(jìn)制縮寫一定要嘗試用decode(utf-8, errorsignore)或者直接print(repr(flag_candidate))看看原始字節(jié)。有時(shí)候flag可能包含不可見(jiàn)字符或特殊結(jié)構(gòu)直接打印會(huì)丟失信息。另外四個(gè)結(jié)果都要仔細(xì)檢查我曾遇到過(guò)flag藏在那個(gè)“看起來(lái)最小”或者“看起來(lái)最大”的整數(shù)對(duì)應(yīng)的字節(jié)串里。4. Rabin在CTF中的進(jìn)階攻擊模式掌握了基礎(chǔ)解密我們來(lái)看看CTF中Rabin更“狡猾”的考法。這能幫你未來(lái)遇到變種題時(shí)快速定位思路。4.1 選擇密文攻擊CCA這是Rabin算法理論上的一個(gè)嚴(yán)重弱點(diǎn)。如果攻擊者可以訪問(wèn)一個(gè)解密Oracle即“你給我任意密文我告訴你對(duì)應(yīng)的一個(gè)明文”那么攻擊者可以通過(guò)精心構(gòu)造的密文來(lái)分解n。簡(jiǎn)化攻擊原理攻擊者隨機(jī)選擇一個(gè)整數(shù)r計(jì)算密文c ≡ r^2 * c (mod n)其中c是目標(biāo)密文。將c發(fā)送給Oracle進(jìn)行解密Oracle返回一個(gè)明文m它是c的四個(gè)平方根之一。由于c ≡ r^2 * c ≡ r^2 * m^2 ≡ (r*m)^2 (mod n)所以m應(yīng)該等于± r*m mod n或± 其他根。攻擊者計(jì)算gcd(m - r*m, n)。如果m是± r*m那么這個(gè)最大公約數(shù)就是1或n沒(méi)用。但如果Oracle返回的是其他根概率為1/2那么gcd(m - r*m, n)就極有可能是p或q從而分解n。CTF中的應(yīng)用題目通常會(huì)給你一個(gè)網(wǎng)絡(luò)服務(wù)你可以發(fā)送加密后的數(shù)據(jù)給它它會(huì)返回解密結(jié)果可能是四個(gè)結(jié)果中的某一個(gè)或者拼接后的全部。你的目標(biāo)就是利用這個(gè)交互分解出n的因子從而解密真正的flag密文。注意在實(shí)際的、安全的Rabin方案中必須引入抗CCA的填充方案如OAEP否則不能直接使用。CTF題為了考察算法本身常常會(huì)省略填充。4.2 已知部分明文或相關(guān)明文攻擊如果攻擊者知道明文m的某些部分信息或者知道多個(gè)明文之間存在某種線性關(guān)系結(jié)合Rabin的數(shù)學(xué)性質(zhì)可能可以構(gòu)建方程來(lái)求解。例如如果知道m(xù)是一個(gè)較短字符串填充到很長(zhǎng)那么m可能小于sqrt(n)。在整數(shù)域下不模nc m^2這個(gè)關(guān)系成立那么直接對(duì)c開(kāi)平方就能得到m完全不需要分解n。這就是“小明文攻擊”。檢查方法在解題時(shí)一個(gè)很好的習(xí)慣是計(jì)算gmpy2.isqrt(c)看看它的平方是否恰好等于c。如果是恭喜你題目比想象中簡(jiǎn)單。4.3 模數(shù)n構(gòu)造不當(dāng)除了p和q接近導(dǎo)致費(fèi)馬分解外還有其他不當(dāng)構(gòu)造p或q過(guò)小可以直接暴力分解或查表。n可以被其他特殊方法分解如Pollards p-1算法當(dāng)p-1的質(zhì)因子都很小時(shí)有效。共模攻擊雖然Rabin公鑰只有n但如果兩套密鑰使用了相同的n或者n1和n2有公因數(shù)同樣可以通過(guò)歐幾里得算法快速分解。5. 實(shí)戰(zhàn)工具鏈與腳本編寫心得工欲善其事必先利其器。處理CTF密碼學(xué)尤其是Rabin這類需要大數(shù)運(yùn)算的題目一套順手的工具和腳本模板能節(jié)省大量時(shí)間。5.1 核心工具推薦Python gmpy2/pycryptodome這是絕對(duì)的主力。gmpy2提供高性能的大整數(shù)運(yùn)算和開(kāi)方、gcd等函數(shù)pycryptodome或舊的pycrypto中的Crypto.Util.number模塊提供了long_to_bytes、bytes_to_long、getPrime等常用函數(shù)不可或缺。pip install gmpy2 pycryptodomeSageMath一個(gè)基于Python的數(shù)學(xué)軟件系統(tǒng)集成了大量數(shù)論、代數(shù)函數(shù)。對(duì)于復(fù)雜的模平方根計(jì)算當(dāng)p % 4 ! 3時(shí)、有限域運(yùn)算Sage是神器。它的Mod(a, p).sqrt()可以輕松求二次剩余根。yafu強(qiáng)大的整數(shù)分解工具適用于在本地嘗試分解中等大小的n數(shù)百位。對(duì)于CTF中的常規(guī)賽題yafu通常能搞定。factordb.com在線分解數(shù)據(jù)庫(kù)。對(duì)于常見(jiàn)的、或之前有人分解過(guò)的n直接查詢可能瞬間得到結(jié)果。5.2 腳本編寫避坑指南類型處理Python原生整數(shù)雖然可以處理大數(shù)但gmpy2.mpz類型在連續(xù)運(yùn)算中效率和功能更優(yōu)。注意gmpy2函數(shù)返回的通常是mpz類型與Pythonint混用時(shí)可能需要顯式轉(zhuǎn)換。import gmpy2 n gmpy2.mpz(12345678901234567890) # 使用gmpy2函數(shù) root gmpy2.isqrt(n) # 與python int交互 if n % 4 3: # do something中國(guó)剩余定理CRT的實(shí)現(xiàn)一定要自己會(huì)寫。雖然gmpy2有g(shù)mpy2.gcdext可以用來(lái)實(shí)現(xiàn)pycryptodome的number模塊也有inverse函數(shù)但理解其原理并能快速寫出正確的CRT合并代碼是關(guān)鍵。def crt(remainders, moduli): 求解同余方程組 x ≡ remainders[i] (mod moduli[i]) total 0 prod 1 for m in moduli: prod * m for r_i, m_i in zip(remainders, moduli): p prod // m_i total r_i * gmpy2.invert(p, m_i) * p return total % prod對(duì)于Rabin的兩兩組合用簡(jiǎn)單的兩兩合并函數(shù)更直觀。結(jié)果驗(yàn)證解密出候選明文m_candidate后一個(gè)重要的驗(yàn)證步驟是檢查pow(m_candidate, 2, n) c是否成立。如果成立說(shuō)明解密過(guò)程在數(shù)學(xué)上是正確的。這是一個(gè)很好的排錯(cuò)手段。編碼與解碼long_to_bytes和bytes_to_long是雙向的。但要注意當(dāng)明文數(shù)字m以0x00開(kāi)頭時(shí)long_to_bytes可能會(huì)丟失這個(gè)開(kāi)頭的零。在有些涉及填充的復(fù)雜場(chǎng)景下這會(huì)導(dǎo)致錯(cuò)誤。此時(shí)可能需要指定字節(jié)長(zhǎng)度如long_to_bytes(m, (n.bit_length()7)//8)。5.3 針對(duì)“crypto661-rabin”的完整解題腳本模板結(jié)合以上所有點(diǎn)一個(gè)健壯的、可用于此類題目的通用腳本模板如下#!/usr/bin/env python3 import gmpy2 from Crypto.Util.number import long_to_bytes, bytes_to_long import sys def fermat_factor(n): 費(fèi)馬分解 a gmpy2.isqrt(n) 1 b2 a*a - n while not gmpy2.is_square(b2): a 1 b2 a*a - n b gmpy2.isqrt(b2) return int(ab), int(a-b) def rabin_decrypt_crt(c, p, q): 使用CRT解密Rabin返回四個(gè)根 assert p % 4 3 and q % 4 3 mp pow(c, (p1)//4, p) mq pow(c, (q1)//4, q) roots_p [mp, p - mp] roots_q [mq, q - mq] roots [] for rp in roots_p: for rq in roots_q: # 解同余方程組: x ≡ rp (mod p), x ≡ rq (mod q) # 使用gmpy2.gcdext g, x, y gmpy2.gcdext(p, q) if (rq - rp) % g ! 0: continue lcm p // g * q root (rp (rq - rp) // g * x * p) % lcm roots.append(int(root)) return roots def main(): # --- 從這里開(kāi)始替換為題目數(shù)據(jù) --- n 0xabcdef... # 模數(shù) c 0x123456... # 密文 # --- 替換結(jié)束 --- print(f[*] n {n}) print(f[*] c {c}) # 嘗試直接開(kāi)方小明文攻擊 m_sqrt gmpy2.isqrt(c) if m_sqrt * m_sqrt c: print(f[!] Found by direct sqrt: {long_to_bytes(int(m_sqrt))}) return # 分解n print(f[*] Factoring n...) # 方法1: 嘗試費(fèi)馬分解適用于p,q接近 try: p, q fermat_factor(n) if p * q n: print(f[] Fermat factorization succeeded!) print(f p {p}) print(f q {q}) else: print(f[-] Fermat failed.) # 這里應(yīng)轉(zhuǎn)向yafu或factordb為演示我們假設(shè)已知p,q # p, q known_p, known_q except Exception as e: print(f[-] Factorization error: {e}) # 假設(shè)我們通過(guò)其他方式知道了p, q # p, q known_p, known_q return # 檢查p,q是否滿足Rabin要求 if not (p % 4 3 and q % 4 3): print(f[!] Warning: p or q not ≡ 3 mod 4. Need general sqrt algorithm.) # 可以使用SageMath的Mod(c, p).sqrt()此處略 return # Rabin解密 print(f[*] Decrypting with Rabin...) possible_plaintexts rabin_decrypt_crt(c, p, q) print(f[] Found {len(possible_plaintexts)} possible plaintexts.) flags [] for idx, m in enumerate(possible_plaintexts): # 驗(yàn)證解密正確性 if pow(m, 2, n) ! c % n: print(f [-] Candidate {idx} failed verification.) continue try: mb long_to_bytes(m) # 嘗試以UTF-8解碼忽略錯(cuò)誤 try: text mb.decode(utf-8) print(f [{idx}] (UTF-8): {text[:80]}) if flag in text or CTF in text: flags.append((idx, text)) except UnicodeDecodeError: # 如果不是UTF-8顯示hex和可能的ASCII部分 print(f [{idx}] (Hex): {mb.hex()[:80]}...) # 檢查是否有可打印ASCII字符 ascii_part .join(chr(b) if 32 b 127 else . for b in mb[:50]) print(f (ASCII): {ascii_part}) if bflag in mb or bCTF in mb: flags.append((idx, mb)) except Exception as e: print(f [{idx}] (Error processing): {e}) if flags: print(f\n[] Potential flag(s) found:) for idx, flag in flags: print(f Candidate {idx}: {flag}) else: print(f\n[-] No obvious flag pattern found. Review the candidates above.) if __name__ __main__: main()這個(gè)模板包含了從分解、解密到結(jié)果篩選和驗(yàn)證的完整流程并加入了小明文攻擊的檢查。你可以把它保存下來(lái)遇到類似的Rabin題目只需替換n和c的值就能快速跑出結(jié)果。6. 從這道題延伸開(kāi)的密碼學(xué)學(xué)習(xí)建議通過(guò)“crypto661-rabin”這道題我們不僅解決了一個(gè)具體問(wèn)題更打開(kāi)了一扇窗看到了公鑰密碼學(xué)中一個(gè)優(yōu)美而直接的設(shè)計(jì)。要在這個(gè)領(lǐng)域走得更遠(yuǎn)我個(gè)人的體會(huì)是不要只停留在“解出題”。每做一道題就去深挖它背后的算法。比如這次遇到Rabin就去讀一讀它的原始論文理解它安全性證明為什么等價(jià)于整數(shù)分解。對(duì)比一下RSA-OAEP和Rabin-Williams填充方案的區(qū)別。動(dòng)手實(shí)現(xiàn)一遍完整的密鑰生成、加密、解密流程甚至模擬一下選擇密文攻擊。建立自己的“武器庫(kù)”。就像上面的腳本模板把常用的數(shù)論函數(shù)CRT、模逆、快速冪、素性檢測(cè)、常見(jiàn)的攻擊腳本費(fèi)馬分解、Pollard-rho、低指數(shù)攻擊都封裝成函數(shù)歸攏到一個(gè)工具包里。下次遇到問(wèn)題你就能快速組合出擊。關(guān)注數(shù)學(xué)。密碼學(xué)的根基是數(shù)學(xué)。模運(yùn)算、群論、有限域、橢圓曲線……這些概念起初可能令人畏懼但當(dāng)你通過(guò)CTF題目反復(fù)應(yīng)用它們時(shí)理解會(huì)越來(lái)越深刻。從Rabin的二次剩余到RSA的歐拉定理再到ECC的離散對(duì)數(shù)數(shù)學(xué)是連接所有點(diǎn)的線。最后回到這道題本身它像是一個(gè)引子提醒我們密碼學(xué)不僅僅是黑盒調(diào)用API。理解原理洞察弱點(diǎn)才能在攻擊與防御的博弈中占據(jù)主動(dòng)。當(dāng)你再看到c m^2 mod n時(shí)希望你的第一反應(yīng)不再是迷茫而是能會(huì)心一笑腦海里清晰地浮現(xiàn)出那四個(gè)平方根以及找到它們的那條路徑。