CTF新手必看：用Python脚本搞定RSA常见攻击（附实战代码）

CTF密码学实战Python脚本破解RSA五大攻击场景在CTF竞赛中RSA加密系统是最常见的密码学挑战之一。本文将带你深入实战通过Python代码复现五种经典RSA攻击场景从基础分解到高级数学技巧每个案例都配有可直接运行的攻击脚本。1. 因数分解攻击当N不够大时RSA的安全性建立在极大整数难以分解的基础上。但当模数N较小时通常指小于1024位我们可以利用在线数据库或本地工具快速分解。实战案例给定N30578675145816634962204467309994126955968568987449100734690153203822106214253e65537密文c21852302692500130397613525359228623357937591161147471234750883538062728964508from Crypto.Util.number import long_to_bytes from gmpy2 import invert, powmod # 已知参数 N 30578675145816634962204467309994126955968568987449100734690153203822106214253 e 65537 c 21852302692500130397613525359228623357937591161147471234750883538062728964508 # 通过factordb.com分解得到 p 8767867843568934765983476584376578389 q 3487583947589437589237958723892346254777 # 计算私钥d phi (p-1)*(q-1) d invert(e, phi) # 解密 m powmod(c, d, N) print(long_to_bytes(m))关键点使用gmpy2库处理大整数运算实际CTF中N小于512位时可尝试本地分解如yafu工具在线分解网站factordb.com收录了已知的素数分解2. 共享素数攻击密钥生成失误当两个不同的RSA密钥意外使用了相同的素数时我们可以通过计算最大公约数(GCD)快速破解。攻击原理若N1p×q1N2p×q2则gcd(N1,N2)pfrom math import gcd from Crypto.Util.number import long_to_bytes, inverse n1 103835296409081751860770535514746586815395898427260334325680313648369132661057840680823295512236948953370895568419721331170834557812541468309298819497267746892814583806423027167382825479157951365823085639078738847647634406841331307035593810712914545347201619004253602692127370265833092082543067153606828049061 n2 115383198584677147487556014336448310721853841168758012445634182814180314480501828927160071015197089456042472185850893847370481817325868824076245290735749717384769661698895000176441497242371873981353689607711146852891551491168528799814311992471449640014501858763495472267168224015665906627382490565507927272073 e 65537 # 找出共享素数 p gcd(n1, n2) q1 n1 // p q2 n2 // p # 计算两个私钥 d1 inverse(e, (p-1)*(q1-1)) d2 inverse(e, (p-1)*(q2-1)) # 双重解密 c 60406168302768860804211220055708551816238816061772464557956985699400782163597251861675967909246187833328847989530950308053492202064477410641014045601986036822451416365957817685047102703301347664879870026582087365822433436251615243854347490600004857861059245403674349457345319269266645006969222744554974358264 m pow(pow(c, d2, n2), d1, n1) print(long_to_bytes(m))防御建议密钥生成时应使用安全的随机数发生器确保每次生成的素数独立随机。3. 低加密指数攻击小明文攻击当公钥指数e很小如3且明文m满足m^e N时直接对密文开e次方即可恢复明文。from gmpy2 import iroot from Crypto.Util.number import long_to_bytes c 25166751653530941364839663846806543387720865339263370907985655775152187319464715737116599171477207047430065345882626259880756839094179627032623895330242655333 # 尝试小指数 for e in range(2, 5): m, exact iroot(c, e) if exact: print(fe{e}: {long_to_bytes(m)})典型场景加密短消息如flag{...}且使用e3时极易受到此攻击。4. 共模攻击相同明文不同密钥当相同的明文用相同的N但不同的e加密且e1和e2互质时可通过扩展欧几里得算法恢复明文。数学基础存在s1,s2使得e1s1 e2s2 1则 m c1^s1 * c2^s2 mod Nfrom Crypto.Util.number import long_to_bytes from gmpy2 import invert, gcdext, powmod n 21058339337354287847534107544613605305015441090508924094198816691219103399526800112802416383088995253908857460266726925615826895303377801614829364034624475195859997943146305588315939130777450485196290766249612340054354622516207681542973756257677388091926549655162490873849955783768663029138647079874278240867932127196686258800146911620730706734103611833179733264096475286491988063990431085380499075005629807702406676707841324660971173253100956362528346684752959937473852630145893796056675793646430793578265418255919376323796044588559726703858429311784705245069845938316802681575653653770883615525735690306674635167111 e1, e2 2767, 3659 c1 20152490165522401747723193966902181151098731763998057421967155300933719378216342043730801302534978403741086887969040721959533190058342762057359432663717825826365444996915469039056428416166173920958243044831404924113442512617599426876141184212121677500371236937127571802891321706587610393639446868836987170301813018218408886968263882123084155607494076330256934285171370758586535415136162861138898728910585138378884530819857478609791126971308624318454905992919405355751492789110009313138417265126117273710813843923143381276204802515910527468883224274829962479636527422350190210717694762908096944600267033351813929448599 c2 11298697323140988812057735324285908480504721454145796535014418738959035245600679947297874517818928181509081545027056523790022598233918011261011973196386395689371526774785582326121959186195586069851592467637819366624044133661016373360885158956955263645614345881350494012328275215821306955212788282617812686548883151066866149060363482958708364726982908798340182288702101023393839781427386537230459436512613047311585875068008210818996941460156589314135010438362447522428206884944952639826677247819066812706835773107059567082822312300721049827013660418610265189288840247186598145741724084351633508492707755206886202876227 # 扩展欧几里得求系数 _, s1, s2 gcdext(e1, e2) # 注意负数指数需要求逆元 if s1 0: c1 invert(c1, n) s1 -s1 if s2 0: c2 invert(c2, n) s2 -s2 m (powmod(c1, s1, n) * powmod(c2, s2, n)) % n print(long_to_bytes(m))5. 广播攻击相同明文广播加密当同一消息用相同的e但不同的N加密e次广播可通过中国剩余定理(CRT)恢复明文。from Crypto.Util.number import long_to_bytes from gmpy2 import iroot, invert e 9 n_list [71189786319102608575263218254922479901008514616376166401353025325668690465852130559783959409002115897148828732231478529655075366072137059589917001875303598680931962384468363842379833044123189276199264340224973914079447846845897807085694711541719515881377391200011269924562049643835131619086349617062034608799, 92503831027754984321994282254005318198418454777812045042619263533423066848097985191386666241913483806726751133691867010696758828674382946375162423033994046273252417389169779506788545647848951018539441971140081528915876529645525880324658212147388232683347292192795975558548712504744297104487514691170935149949, 100993952830138414466948640139083231443558390127247779484027818354177479632421980458019929149817002579508423291678953554090956334137167905685261724759487245658147039684536216616744746196651390112540237050493468689520465897258378216693418610879245129435268327315158194612110422630337395790254881602124839071919, 59138293747457431012165762343997972673625934330232909935732464725128776212729547237438509546925172847581735769773563840639187946741161318153031173864953372796950422229629824699580131369991913883136821374596762214064774480548532035315344368010507644630655604478651898097886873485265848973185431559958627423847, 66827868958054485359731420968595906328820823695638132426084478524423658597714990545142120448668257273436546456116147999073797943388584861050133103137697812149742551913704341990467090049650721713913812069904136198912314243175309387952328961054617877059134151915723594900209641163321839502908705301293546584147, 120940513339890268554625391482989102665030083707530690312336379356969219966820079510946652021721814016286307318930536030308296265425674637215009052078834615196224917417698019787514831973471113022781129000531459800329018133248426080717653298100515701379374786486337920294380753805825328119757649844054966712377, 72186594495190221129349814154999705524005203343018940547856004977368023856950836974465616291478257156860734574686154136925776069045232149725101769594505766718123155028300703627531567850035682448632166309129911061492630709698934310123778699316856399909549674138453085885820110724923723830686564968967391721281, 69105037583161467265649176715175579387938714721653281201847973223975467813529036844308693237404592381480367515044829190066606146105800243199497182114398931410844901178842049915914390117503986044951461783780327749665912369177733246873697481544777183820939967036346862056795919812693669387731294595126647751951, 76194219445824867986050004226602973283400885106636660263597964027139613163638212828932901192009131346530898961165310615466747046710743013409318156266326090650584190382130795884514074647833949281109675170830565650006906028402714868781834693473191228256626654011772428115359653448111208831188721505467497494581] c_list [62580922178008480377006528793506649089253164524883696044759651305970802215270721223149734532870729533611357047595181907404222690394917605617029675103788705320032707977225447998111744887898039756375876685711148857676502670812333076878964148863713993853526715855758799502735753454247721711366497722251078739585, 46186240819076690248235492196228128599822002268014359444368898414937734806009161030424589993541799877081745454934484263188270879142125136786221625234555265815513136730416539407710862948861531339065039071959576035606192732936477944770308784472646015244527805057990939765708793705044236665364664490419874206900, 85756449024868529058704599481168414715291172247059370174556127800630896693021701121075838517372920466708826412897794900729896389468152213884232173410022054605870785910461728567377769960823103334874807744107855490558726013068890632637193410610478514663078901021307258078678427928255699031215654693270240640198, 14388767329946097216670270960679686032536707277732968784379505904021622612991917314721678940833050736745004078559116326396233622519356703639737886289595860359630019239654690312132039876082685046329079266785042428947147658321799501605837784127004536996628492065409017175037161261039765340032473048737319069656, 1143736792108232890306863524988028098730927600066491485326214420279375304665896453544100447027809433141790331191324806205845009336228331138326163746853197990596700523328423791764843694671580875538251166864957646807184041817863314204516355683663859246677105132100377322669627893863885482167305919925159944839, 2978800921927631161807562509445310353414810029862911925227583943849942080514132963605492727604495513988707849133045851539412276254555228149742924149242124724864770049898278052042163392380895275970574317984638058768854065506927848951716677514095183559625442889028813635385408810698294574175092159389388091981, 16200944263352278316040095503540249310705602580329203494665614035841657418101517016718103326928336623132935178377208651067093136976383774189554806135146237406248538919915426183225265103769259990252162411307338473817114996409705345401251435268136647166395894099897737607312110866874944619080871831772376466376, 31551601425575677138046998360378916515711528548963089502535903329268089950335615563205720969393649713416910860593823506545030969355111753902391336139384464585775439245735448030993755229554555004154084649002801255396359097917380427525820249562148313977941413268787799534165652742114031759562268691233834820996, 25288164985739570635307839193110091356864302148147148153228604718807817833935053919412276187989509493755136905193728864674684139319708358686431424793278248263545370628718355096523088238513079652226028236137381367215156975121794485995030822902933639803569133458328681148758392333073624280222354763268512333515] # 中国剩余定理 N 1 for n in n_list: N * n result 0 for i in range(len(n_list)): Ni N // n_list[i] inv_Ni invert(Ni, n_list[i]) result c_list[i] * Ni * inv_Ni m iroot(result % N, e)[0] print(long_to_bytes(m))防御措施使用OAEP填充方案可有效防止此类攻击。进阶工具与防御推荐Python库Crypto.Util.number处理大整数转换gmpy2高性能数学运算sympy符号计算与数论工具安全实践使用至少2048位的N选择适中的e如65537实现PKCS#1 v2.2中的OAEP填充密钥生成时确保素数强随机性掌握这些攻击方法不仅能帮助你在CTF竞赛中得分更能深入理解RSA的实际安全边界。建议读者在本地环境复现每个案例观察不同参数对攻击效果的影响。