CTF密码学入门RSA题型实战全解析与Python代码实现在网络安全竞赛CTF中RSA加密算法是最常见的密码学挑战之一。对于刚接触CTF密码学的新手来说掌握RSA的基本原理和常见攻击手法至关重要。本文将深入剖析5种典型的RSA漏洞场景并提供可直接复现的Python解决方案帮助你在比赛中快速破解这类题目。1. RSA基础与标准解密流程RSA加密系统的安全性基于大整数分解的困难性。一个标准的RSA加密涉及以下参数p和q两个大素数n模数n p * qφ(n)欧拉函数φ(n) (p-1)*(q-1)e公钥指数通常为65537d私钥指数满足e*d ≡ 1 mod φ(n)c密文c m^e mod nm明文m c^d mod n标准解密Python实现import libnum from Crypto.Util.number import long_to_bytes # 给定参数 e 65537 p 104046835712664064779194734974271185635538927889880611929931939711001301561682270177931622974642789920918902563361293345434055764293612446888383912807143394009019803471816448923969637980671221111117965227402429634935481868701166522350570364727873283332371986860194245739423508566783663380619142431820861051179 q 140171048074107988605773731671018901813928130582422889797732071529733091703843710859282267763783461738242958098610949120354497987945911021170842457552182880133642711307227072133812253341129830416158450499258216967879857581565380890788395068130033931180395926482431150295880926480086317733457392573931410220501 c 4772758911204771028049020670778336799568778930072841084057809867608022732611295305096052430641881550781141776498904005589873830973301898523644744951545345404578466176725030290421649344936952480254902939417215148205735730754808467351639943474816280980230447097444682489223054499524197909719857300597157406075069204315022703894466226179507627070835428226086509767746759353822302809385047763292891543697277097068406512924796409393289982738071019047393972959228919115821862868057003145401072581115989680686073663259771587445250687060240991265143919857962047718344017741878925867800431556311785625469001771370852474292194 # 计算必要参数 n p * q phi_n (p-1)*(q-1) d libnum.invmod(e, phi_n) # 模反元素计算 m pow(c, d, n) # 解密计算 print(long_to_bytes(m)) # 输出: flag{b4by_R5A}注意实际CTF题目中出题者往往会通过设置特殊参数来弱化RSA的安全性这正是我们需要关注的重点。2. 模数n过小导致的分解攻击当RSA使用的模数n较小时通常小于1024位现代计算机可以在合理时间内将其分解为两个素数p和q从而完全破解加密系统。攻击步骤识别n的位数较小例如小于300位使用因数分解工具如yafu、factordb分解n获得p和q后按照标准流程解密实战案例import libnum from Crypto.Util.number import long_to_bytes e 65537 n 1455925529734358105461406532259911790807347616464991065301847 c 69380371057914246192606760686152233225659503366319332065009 # 使用yafu分解得到的p和q p 1212112637077862917192191913841 q 1201147059438530786835365194567 # 标准解密流程 phi_n (p-1)*(q-1) d libnum.invmod(e, phi_n) m pow(c, d, n) print(long_to_bytes(m)) # 输出: flag{fact0r_sma11_N}因数分解工具对比工具名称适用场景特点yafu中小整数分解(≤200位)自动化程度高支持多线程factordb已知因数查询在线数据库查询速度快msieve大整数分解支持GPU加速适合专业用途3. 共模攻击相同明文多次加密当相同的明文使用相同的n但不同的e加密且e1和e2互质时可以通过扩展欧几里得算法恢复明文而无需知道私钥d。数学原理 存在整数s1和s2使得e1s1 e2s2 1 则明文m (c1^s1 * c2^s2) mod nPython实现import libnum from Crypto.Util.number import long_to_bytes def extended_gcd(a, b): if b 0: return 1, 0, a else: x, y, q extended_gcd(b, a % b) x, y y, (x - (a // b) * y) return x, y, q # 两组加密参数 e1, n1, c1 797, 15944475431088053285580229796309956066521520107276817969079550919586650535459242543036143360865780730044733026945488511390818947440767542658956272380389388112372084760689777141392370253850735307578445988289714647332867935525010482197724228457592150184979819463711753058569520651205113690397003146105972408452854948512223702957303406577348717348753106868356995616116867724764276234391678899662774272419841876652126127684683752880568407605083606688884120054963974930757275913447908185712204577194274834368323239143008887554264746068337709465319106886618643849961551092377843184067217615903229068010117272834602469293571, 11157593264920825445770016357141996124368529899750745256684450189070288181107423044846165593218013465053839661401595417236657920874113839974471883493099846397002721270590059414981101686668721548330630468951353910564696445509556956955232059386625725883038103399028010566732074011325543650672982884236951904410141077728929261477083689095161596979213961494716637502980358298944316636829309169794324394742285175377601826473276006795072518510850734941703194417926566446980262512429590253643561098275852970461913026108090608491507300365391639081555316166526932233787566053827355349022396563769697278239577184503627244170930 e2, n2, c2 521, 15944475431088053285580229796309956066521520107276817969079550919586650535459242543036143360865780730044733026945488511390818947440767542658956272380389388112372084760689777141392370253850735307578445988289714647332867935525010482197724228457592150184979819463711753058569520651205113690397003146105972408452854948512223702957303406577348717348753106868356995616116867724764276234391678899662774272419841876652126127684683752880568407605083606688884120054963974930757275913447908185712204577194274834368323239143008887554264746068337709465319106886618643849961551092377843184067217615903229068010117272834602469293571, 6699274351853330023117840396450375948797682409595670560999898826038378040157859939888021861338431350172193961054314487476965030228381372659733197551597730394275360811462401853988404006922710039053586471244376282019487691307865741621991977539073601368892834227191286663809236586729196876277005838495318639365575638989137572792843310915220039476722684554553337116930323671829220528562573169295901496437858327730504992799753724465760161805820723578087668737581704682158991028502143744445435775458296907671407184921683317371216729214056381292474141668027801600327187443375858394577015394108813273774641427184411887546849 # 验证n相同且e互质 assert n1 n2 assert libnum.gcd(e1, e2) 1 # 扩展欧几里得算法求系数 s1, s2, _ extended_gcd(e1, e2) # 处理负数指数 if s1 0: c1 libnum.invmod(c1, n1) s1 -s1 elif s2 0: c2 libnum.invmod(c2, n2) s2 -s2 # 恢复明文 m (pow(c1, s1, n1) * pow(c2, s2, n1)) % n1 print(long_to_bytes(m)) # 输出: flag{sh4r3_N}4. 低指数攻击与维纳攻击4.1 低加密指数攻击e过小当公钥指数e非常小如e3且明文m较小时可能存在m^e n的情况此时可以直接对密文c开e次方得到明文。攻击条件e非常小通常≤3m^e n即未进行模运算Python解决方案import gmpy2 from Crypto.Util.number import long_to_bytes e 3 n 18970053728616609366458286067731288749022264959158403758357985915393383117963693827568809925770679353765624810804904382278845526498981422346319417938434861558291366738542079165169736232558687821709937346503480756281489775859439254614472425017554051177725143068122185961552670646275229009531528678548251873421076691650827507829859299300272683223959267661288601619845954466365134077547699819734465321345758416957265682175864227273506250707311775797983409090702086309946790711995796789417222274776215167450093735639202974148778183667502150202265175471213833685988445568819612085268917780718945472573765365588163945754761 c 150409620528139732054476072280993764527079006992643377862720337847060335153837950368208902491767027770946661 # 尝试寻找k使得c k*n可开e次方 for k in range(1000000): root, is_exact gmpy2.iroot(c k*n, e) if is_exact: print(long_to_bytes(int(root))) # 输出: flag{Sm4ll_eee} break4.2 维纳攻击d过小当私钥指数d较小时d 1/3 * n^(1/4)可以使用连分数展开的方法在多项式时间内恢复d。维纳攻击Python实现import gmpy2 def wiener_attack(e, n): # 连分数展开 def continued_fractions_expansion(e, n): cf [] while n: q e // n cf.append(q) e, n n, e % n return cf # 渐进分数计算 def convergents(cf): numerators, denominators [], [] for i in range(len(cf)): if i 0: ni, di cf[i], 1 elif i 1: ni, di cf[i]*cf[i-1]1, cf[i] else: ni cf[i]*numerators[i-1] numerators[i-2] di cf[i]*denominators[i-1] denominators[i-2] numerators.append(ni) denominators.append(di) yield (ni, di) cf continued_fractions_expansion(e, n) convergents_list list(convergents(cf)) for (k, d) in convergents_list: if k 0: continue phi (e*d - 1) // k # 解方程x^2 - (n - phi 1)x n 0 b n - phi 1 delta b*b - 4*n if delta 0: p (b - gmpy2.isqrt(delta)) // 2 q (b gmpy2.isqrt(delta)) // 2 if p*q n: return d return None # 示例参数 e 284100478693161642327695712452505468891794410301906465434604643365855064101922252698327584524956955373553355814138784402605517536436009073372339264422522610010012877243630454889127160056358637599704871937659443985644871453345576728414422489075791739731547285138648307770775155312545928721094602949588237119345 n 468459887279781789188886188573017406548524570309663876064881031936564733341508945283407498306248145591559137207097347130203582813352382018491852922849186827279111555223982032271701972642438224730082216672110316142528108239708171781850491578433309964093293907697072741538649347894863899103340030347858867705231 c 350429162418561525458539070186062788413426454598897326594935655762503536409897624028778814302849485850451243934994919418665502401195173255808119461832488053305530748068788500746791135053620550583421369214031040191188956888321397450005528879987036183922578645840167009612661903399312419253694928377398939392827 d wiener_attack(e, n) if d: m pow(c, d, n) print(long_to_bytes(m)) # 输出: flag{very_biiiiig_e} else: print(维纳攻击失败)5. 特殊参数导致的脆弱性5.1 p和q接近时的费马分解当素数p和q非常接近时|p-q|较小可以使用费马分解法快速分解n。费马分解Python实现import gmpy2 from Crypto.Util.number import long_to_bytes 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 (ab, a-b) n 26737417831000820542131903300607349805884383394154602685589253691058592906354935906805134188533804962897170211026684453428204518730064406526279112572388086653330354347467824800159214965211971007509161988095657918569122896402683130342348264873834798355125176339737540844380018932257326719850776549178097196650971801959829891897782953799819540258181186971887122329746532348310216818846497644520553218363336194855498009339838369114649453618101321999347367800581959933596734457081762378746706371599215668686459906553007018812297658015353803626409606707460210905216362646940355737679889912399014237502529373804288304270563 e 0x10001 c 18343406988553647441155363755415469675162952205929092244387144604220598930987120971635625205531679665588524624774972379282080365368504475385813836796957675346369136362299791881988434459126442243685599469468046961707420163849755187402196540739689823324440860766040276525600017446640429559755587590377841083082073283783044180553080312093936655426279610008234238497453986740658015049273023492032325305925499263982266317509342604959809805578180715819784421086649380350482836529047761222588878122181300629226379468397199620669975860711741390226214613560571952382040172091951384219283820044879575505273602318856695503917257 p, q fermat_factor(n) assert p*q n phi_n (p-1)*(q-1) d gmpy2.invert(e, phi_n) m pow(c, d, n) print(long_to_bytes(m)) # 输出: flag{pq_4re_t00_c1o5ed}5.2 已知p高位时的Coppersmith攻击当知道p的大部分高位比特时可以使用Coppersmith定理恢复完整的p。这种方法在CTF中经常出现。SageMath实现在线运行https://sagecell.sagemath.org/# Sage代码 n 0x79e0bf9b916e59286163a1006f8cefd4c1b080387a6ddb98a3f3984569a4ebb48b22ac36dff7c98e4ebb90ffdd9c07f53a20946f57634fb01f4489fcfc8e402865e152820f3e2989d4f0b5ef1fb366f212e238881ea1da017f754d7840fc38236edba144674464b661d36cdaf52d1e5e7c3c21770c5461a7c1bc2db712a61d992ebc407738fc095cd8b6b64e7e532187b11bf78a8d3ddf52da6f6a67c7e88bef5563cac1e5ce115f3282d5ff9db02278859f63049d1b934d918f46353fea1651d96b2ddd874ec8f1e4b9d487d8849896d1c21fb64029f0d6f47e560555b009b96bfd558228929a6cdf3fb6d47a956829fb1e638fcc1bdfad4ec2c3590dea1ed3 p_high 0xd1c520d9798f811e87f4ff406941958bab8fc24b19a32c3ad89b0b73258ed3541e9ca696fd98ce15255264c39ae8c6e8db5ee89993fa44459410d30a0a8af700ae3aee8a9a1d6094f8c757d3b79a8d1147e85be34fb260a970a52826c0a92b46cefb5dfaf2b5a31edf867f8d34d2222900000000000000000000000000000000 pbits 1024 kbits 128 pbar p_high (2^pbits-2^kbits) PR.x PolynomialRing(Zmod(n)) f x pbar x0 f.small_roots(X2^kbits, beta0.4)[0] p x0 pbar print(p , p)后续解密Python代码from Crypto.Util.number import long_to_bytes import gmpy2 # 从Sage输出获得的p p 147305526294483975294006704928271118039370615054437206404408410848858740256154476278591035455064149531353089038270283281541411458250950936656537283482331598521457077465891874559349872035197398406708610440618635013091489698011474611145014167945729411970665381793142591665313979405475889978830728651549052207969 e 0x10001 n 0x79e0bf9b916e59286163a1006f8cefd4c1b080387a6ddb98a3f3984569a4ebb48b22ac36dff7c98e4ebb90ffdd9c07f53a20946f57634fb01f4489fcfc8e402865e152820f3e2989d4f0b5ef1fb366f212e238881ea1da017f754d7840fc38236edba144674464b661d36cdaf52d1e5e7c3c21770c5461a7c1bc2db712a61d992ebc407738fc095cd8b6b64e7e532187b11bf78a8d3ddf52da6f6a67c7e88bef5563cac1e5ce115f3282d5ff9db02278859f63049d1b934d918f46353fea1651d96b2ddd874ec8f1e4b9d487d8849896d1c21fb64029f0d6f47e560555b009b96bfd558228929a6cdf3fb6d47a956829fb1e638fcc1bdfad4ec2c3590dea1ed3 c 0x1b2b4f9afed5fb5f9876757e959c183c2381ca73514b1918d2f123e386bebe9832835350f17ac439ac570c9b2738f924ef49afea02922981fad702012d69ea3a3c7d1fc8efc80e541ca2622d7741090b9ccd590906ac273ffcc66a7b8c0d48b7d62d6cd6dd4cd75747c55aac28f8be3249eb255d8750482ebf492692121ab4b27b275a0f69b15baef20bf812f3cbf581786128b51694331be76f80d6fb1314d8b280eaa16c767821b9c2ba05dfde5451feef22ac3cb3dfbc88bc1501765506f0c05045184292a75c475486b680f726f44ef8ddfe3c48f75bb03c8d44198ac70e6b7c885f53000654db22c8cee8eb4f65eaeea2da13887aaf53d8c254d2945691 q n // p phi_n (p-1)*(q-1) d gmpy2.invert(e, phi_n) m pow(c, d, n) print(long_to_bytes(m)) # 输出: flag{Kn0wn_Hi9h_Bit5}掌握这些RSA攻击技术后你将在CTF密码学挑战中具备更强的解题能力。每种攻击方法都有其特定的适用场景关键在于识别题目中给出的参数特征从而选择正确的攻击路径。