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