RSA-5 公因子唯密文攻击

知识点

本篇就是简单的对 RSA 的加解密原理有了解即可。

RSA 加解密过程

密钥生成

随机生成两个大质数 $p$​ 和 $q$​ ，计算出 $n = p \times q$​ 和 $\varphi(n) = (p-1) \times (q-1)$​ ，随机选取一个数 $e$​ 满足 $gcd(e, \varphi(n)) = 1$​ ，如此可以计算出一个 $e$​ 关于 $\varphi(n)$​ 单独唯一乘法逆元 $d$​ ，即 $e \times d \equiv 1 \pmod {\varphi(n)}$​​ 。销毁生成的质数 $p$​​ ， $q$​ 和 $\varphi(n)$​ ，同时严格保密 $d$​ 。

则 $(e, n)$ 组成了公钥，$(d, n)$​ 组成了私钥。如果不泄漏额外的信息、不使用过小的质数、不做一些高风险的生成，则只根据公钥 $(e, n)$ 想要计算出私钥 $(d, n)$ 是计算不可行的。

加密过程

将需要加密的消息按某种格式转化为一个或多个数字， CTF 中一般就将 flag 转化为一个数字 $m$ ，然后计算密文 $c = m ^ e \mod n$ 。

考虑到有可能会存在 $m|n$ 的情况，而由于 $n = p \times q$ ，故此时必有 $m|p$ 或者 $m|q$ 。由于 $p$ 和 $q$ 都是质数，所以 $m=p$ 或者 $m=q$ 。一方面这个概率是很小的。另一方面，如果真的这么巧， $m=p$ 或者 $m=q$ 那就按照前面的法则再次重新生成一组 $p$ 和 $q$ ，然后再构建即可。

解密过程

设需要解密的密文为 $c$​ ，则明文对应的数字 $m = c ^ d \mod n$​ 。

$$\because e \times d \equiv 1 \pmod {\varphi(n)} \\ \therefore e \times d = k \times \varphi(n) + 1, k \in Z \\ \because gcd(m, n) = 1 \\ \therefore m^{\varphi(n)}\equiv 1 \pmod n \ ······\ Euler's\ theorem\\ \because c = m^e \mod n \\ \therefore c^d \equiv (m^e)^d \equiv m ^ {e \times d} \equiv m^{k \times \varphi(n) + 1} \equiv m \times ({m^{\varphi(n)}})^k \equiv m \times 1^k \equiv m \pmod n \\$$

例题

题目

听说你很会 RSA，那就来试试这个题吧？

题目文件如下：

c0 = 12502952410838088527503150483929596797238727141664201643187558410249840922504152436250224517080403548062059389683409973687650938762586419744110985448850729975136982015873662423239469666002472418658181351993248952045647782478683559270140577776327884458069961689714906882363593169797260734300696567271488376187248065065563984468167466319934208465782163292359359330164910674523737018524052695536055576797161975994480539782258057370098537210554654603954458785262687110719298699190476472933655285355531596755998549847834125491869413702782087886002808950397489212209891152117119837502620672670815687422888641307478783882977
e0 = 72139
n0 = 17856369450299249300240417754594319685744984306271362335228487220405194857631096284011359857986848821076960874226926737714393646297018747324370622809846185514839714676059356981993982530099951000827533431336401325506082462140332285500707577483905037677602117065091031467322170450559684666914025096755803671915433664939437937804816516035508866079068159739567182663377217792967447156124572947795188521058096842679837360605381559551186754982368005514530448233198527595341171014759122711418942447735731766283632174480765195358486310564977074263282333663871864341877090978938462972860982839123300353384536103080201010734739

c1 = 9384547733853504157318390785046912458511196222462353462023028664899729266352054076415611689002574391950860967536345409289592915457538764852717710003157571221521401291072205484107982843900103534154938051822985662072466001846844585574533699140038987713517144192648862624673218144482699841248660210298844174533657318754921426001957512981087801386625653277886399910645834144762765991903357298629679585245349557478069026629738080047794581524483082446144073639405690639119499338782883109354837581240908330127375460546324198527743083692374967474101467139151979324032468863895068829580824568268103726440735556571123034316708
e1 = 123001
n1 = 22071308942115457335832182465875713995383145364895397657364713036535688658222558643753157659850536063965556369057428474171771813126469244955148735789346018437835659086904851875780175571685586193216813806081776190057076942098077978481924947922724650533721654334713639356753097968139753289849492703857111919237935467490223599516841428322337898964917534526196390937172079744488830015592655476064386735313627313849502065872336220322820904639856670366627463333068604893281969695168395909256416676153728592718883470868137628104814425114014662020885691453249578431902672050119761234316878019953991926874177126966131069938401

c2 = 16788724623049600459567687741284903770847576337003682778789544914671347079561323785131185120932086469895210489475367034578527156528071694431995902868673389428586130216401777391513513559994711461741790551284457423057658532851209666842204227158231456995925565784219320204022327601056710218417866170812648788674333398520522242841275143722887734593854727405816075686851861914125411498011776689696325552339581296388890486735115619863911006645108018675673922734446298387807604010312134081896312087686975740609541494284184559593416433114793381542650256466628701397228139176858995347927447942422896958853648748791650927532205
e2 = 124427
n2 = 25100576965381288052758810434254321501087096615929524705855403931690442414607972413420287317906167318305605168968065012783656230097078148076794250815465919861265662959941934762283116423474545307029296538532681484547164129845970804657930854769930230340199067886597346186918577054097941877236229199992940403141841573589315727227248629208443600264721232299896209956440638466792614458669531203688574216111523926035688888893527944390102171980452827649390878702349217134475404155568814880168450758652789096275231875251392847666518613701355710955592485102570290625530348065767715338159803207073766288066082717072522745994993

c3 = 6327463121097185886003442601389402647428948619161353630130579283044563032970130839035540319580495953927506351697297093648162054165035288723106723321361490196137846766055888606414449696382451013320910742605803509538919952919400819416557671837812385897023338926017162463455157267030278376470610454225678518534828253504016967806331239691914581031689941465243063964838873994687590731079492347595089397524040598043980209150389315313072018331702657903566996672038218517867863085544322781374853423023466611919060746947418814263408830352326912599219679895060904003826791442308198740791671015612494538641438688057391555202877
e3 = 119417
n3 = 13712041213851538160324865021357315734462771303174602128021408826750947122057729542007714803660493810983931116682301456213837637286472658831291084753537817553805900952987831773013668259178315050497248865410403655271934438468536143769145578174785091023225672885936557305820401448264750711630414110310345278513191228800843334008375634007282012019908147047150362152003922779172507198601698027430664028788343212648863624263330369833682898424581836377972889124695597158672441602628955809098022329869438797114093394642176007646270676884804836460889801843413014214077244795013373885346927852416595274707653732907180354507047

c4 = 1900941158854346673149869322196857906070555117555584604208832634698800847248388721025978702864784974025342104538466971126375157270927961382606470875980790238445168262400426097543846214190260168513348041203389951580413506222372459044330116766569804031835873253014816684788983116448230250524229344621708408401015448941270171396048785133084861658529004742138188889168647258495441827905978120262053109005686517442789275137097284111570562460063518755951947042559379209716764212641507876645389922801816702832834530642436041817520032246252073142516133684221415172569084697274771615327624998446223170214638612241689212173015
e4 = 82633
n4 = 10614088207112334796396457761244718324705425252734092771296007026945808681448061878103480092102492673228766034946343026086684152212091637447091758012819511378530678850745347455912656885525773911293543754548380775801375203454130661332418217054402885682574737874348848234030698759270848057209226949532192006068721823268938022270241037201225863751318272528316182228144593719311790268294930467532134380408826833838515499591840530685910610024081499065559722511268246425220807511922634482052892763459007119168030539279419562157785897131571680417013315904301530491133437292140724424491596995270324085587372658978822260295687

c5 = 6679685792184647579741974108239609836295738169094483010267484694973005768813309643675939770616489046769630599316240200212728466063038636568261912551748579861287517463415319012827716352199222523212354039118161756005582251944618135481609204228669597621813574260493046070865613241241527561194368769067168904926326539966960495483801330592039384512903752142311485807655093913443627320370767810603096793238147853100215855118187160325951570413780244109679600047017475167867627330627171112187868097589867093208440752223909473327727775637904127916400463980988780671943594575243201568862808680637410821667892747701101267246302
e5 = 69847
n5 = 14082895340069750195624496854826339506625112043886407716057400491975763565682615324358599521625943482701682587973818614203535242089852507027219502943551439252395834102385713543422992240035766976798628201210682884172910499397950881894189484531458713368702071779515768387560603074195395231205546053377847977139139962281575255410172053491593716534864194443759866533036698178736529157047325842162534702172234710695219385028317480472433012068095732654401548088593201500066504115851050999663052585253401233559592019995006329067999264988201573694387666742725409090282654650800657212428121182797924769468859485888967582628541

c6 = 11995062200940559304387938088828883824548295939002584544656391273356414929502776295265377744345500179948052453300925769171871491208463339658185741637509068366156920267515622620068593848241176071386978374367558205629560627673342087251213569507456980364208555116140399090778336103304291136531521336659388938882856700882958800891517899648867330025657240473949753312907964421862787503867824914952999746493258869480997483608923697572305741767955338490801846396033238181458874105568222637779053534693082865571257349688688922842624366393472524410501810260036353099993677649500749949291603565044623966098600179209412074429883
e6 = 108439
n6 = 16199498009890300793447764109167825482974677554285030558627472987223487860004259356583103155503531178685925169504893515411058240259757324428359095426887034269747878644217523752683634553579913057287644398059017586893029977164135244343504122333634006934037103876230504255167674672093144418281013912912808902905971599505240285885392400151523550762949647179210173098229549706311783129689475114132048763443938043258951953364950585674308621814260674458868228182973077303704563443769739592116083922318868953510704274677478162584676616375773425920438446789132646217986925790472764259290774133446539490236213762194253152322247

c7 = 12176755249559939829777748501116646680153418649466738910905366117745064631662836915488619301498314429549354172737025359641046128628612024524717722551276674280669807507208620745591060054851457315103681028415369195411731801419877650443315390713602987794264303842481280091807586472378552519848358955933616697652024225596658872153663777878579295622228034455356722289684143832045006047862225640432103987032247840238896758667459336821116891541850211915504349908842304457258704800026112137692910072687222111231733101650247191351154256758218153189507886927061465409572119929130002899053277074163278263733802290669197484821705
e7 = 110419
n7 = 17828641241183021783941239587502469972892430175796480087371793912217171381674783170842358755495515944784273205744758714480172394736958586330142487456676865279941155363623422506722632610442232733199296307546196742694775568584168346556731751981417208889691315911849509862094152219902641552292054660672338675535113914157353605444163050142229980564480658815007091890969202384725544282527556106797536749550662610551655135576358329045423749226350283900035242694811054836739550150683977930765170891818518747571579207081129388505693532702466263969554103190321899106550265094309245694759219001939353720393941289634090919320741

c8 = 5909947635537744285592552564610005872954358591574250985734222449277416999367209232286679802450663019443439941403729126629591811701868871023256921934087587910362084575749255028568273966086014134976568998568430403827829388469867464802686806137496178632195070136794008536857968612127910185652888728857438952729689943267086061523840950640567062769260900187535334146066764240482693583239435346317850615963082262241383939819413966136421893038326034158375648763615397874918549425908450932874467935149886884801304828708885508247843003848516851421270429474372752564211003065953838109072660046590415019448343665741687266537049
e8 = 65537
n8 = 18553710870627206223331369643763856913913473133240078247026140923036084570177359456718233496128034989431313681674828414854004159726214543810500612641232548357562979694913888151156847461167763450634717966937365399396569068720500665701215226596289023092619248922689900098446935601568421769995677650167530389780407432129548528877932608961935369834960190184809897757450136080063857136076927849118786912489421295864947436407056075851211434939744721074000319733564472931369699860756889707580129662086971084587283853963849077477433452323077691472330145153548759629047576490640899678121909049191998385853809416290138198894107

c9 = 12735885686429033879640739395956174135075133581811783796118167363407714580667213466721369104037201817664652644964556923926284840295837696409508702742646530559175905743197529876870473746932385132815431674316309316486696425599080712941289556172942811993265447746288596307877358829408841521350645607919504198556689675640270494342662458256107359525814127463688657253485546812245289075340037231176930491902113143673381295920477018326178593711114670732348409848578587249754453033632949329642135288792883770020754908603033969288249118692670147867052930097979469299474117266386461642611041554206788810988953782211363621539286
e9 = 66877
n9 = 23530284911005014749813886231174095751599986713289171018986389212230597031742222723160627336499206846351638704329995034492027064132269036917283948285801442337275342099108754021469881840530182406190151469366071799723001672482708139253495020521764200922440273121775236997999727665394164083690166641081100925950325548844251315491270509084655834953305656248729664348416035812898648346471101382062978222840436730138667577946883887296778895828853357876327611137634652672526910378546046214528581217796582715400697396143580575222876165549663910562368747118962334207414877016627026057008636527361221899063077801010872867490853

题解

看到题目给出了很多组 $(e_i, n_i)$ ，但是各组中都两两不同，所以不是共模攻击（后面会讲到，这里提一嘴。

那这么多组，肯定就试试互相求求，看能否得到一个有效的最大公因数。

于是贴如下脚本：

import gmpy2

ns = [17856369450299249300240417754594319685744984306271362335228487220405194857631096284011359857986848821076960874226926737714393646297018747324370622809846185514839714676059356981993982530099951000827533431336401325506082462140332285500707577483905037677602117065091031467322170450559684666914025096755803671915433664939437937804816516035508866079068159739567182663377217792967447156124572947795188521058096842679837360605381559551186754982368005514530448233198527595341171014759122711418942447735731766283632174480765195358486310564977074263282333663871864341877090978938462972860982839123300353384536103080201010734739, 22071308942115457335832182465875713995383145364895397657364713036535688658222558643753157659850536063965556369057428474171771813126469244955148735789346018437835659086904851875780175571685586193216813806081776190057076942098077978481924947922724650533721654334713639356753097968139753289849492703857111919237935467490223599516841428322337898964917534526196390937172079744488830015592655476064386735313627313849502065872336220322820904639856670366627463333068604893281969695168395909256416676153728592718883470868137628104814425114014662020885691453249578431902672050119761234316878019953991926874177126966131069938401, 25100576965381288052758810434254321501087096615929524705855403931690442414607972413420287317906167318305605168968065012783656230097078148076794250815465919861265662959941934762283116423474545307029296538532681484547164129845970804657930854769930230340199067886597346186918577054097941877236229199992940403141841573589315727227248629208443600264721232299896209956440638466792614458669531203688574216111523926035688888893527944390102171980452827649390878702349217134475404155568814880168450758652789096275231875251392847666518613701355710955592485102570290625530348065767715338159803207073766288066082717072522745994993, 13712041213851538160324865021357315734462771303174602128021408826750947122057729542007714803660493810983931116682301456213837637286472658831291084753537817553805900952987831773013668259178315050497248865410403655271934438468536143769145578174785091023225672885936557305820401448264750711630414110310345278513191228800843334008375634007282012019908147047150362152003922779172507198601698027430664028788343212648863624263330369833682898424581836377972889124695597158672441602628955809098022329869438797114093394642176007646270676884804836460889801843413014214077244795013373885346927852416595274707653732907180354507047, 10614088207112334796396457761244718324705425252734092771296007026945808681448061878103480092102492673228766034946343026086684152212091637447091758012819511378530678850745347455912656885525773911293543754548380775801375203454130661332418217054402885682574737874348848234030698759270848057209226949532192006068721823268938022270241037201225863751318272528316182228144593719311790268294930467532134380408826833838515499591840530685910610024081499065559722511268246425220807511922634482052892763459007119168030539279419562157785897131571680417013315904301530491133437292140724424491596995270324085587372658978822260295687, 14082895340069750195624496854826339506625112043886407716057400491975763565682615324358599521625943482701682587973818614203535242089852507027219502943551439252395834102385713543422992240035766976798628201210682884172910499397950881894189484531458713368702071779515768387560603074195395231205546053377847977139139962281575255410172053491593716534864194443759866533036698178736529157047325842162534702172234710695219385028317480472433012068095732654401548088593201500066504115851050999663052585253401233559592019995006329067999264988201573694387666742725409090282654650800657212428121182797924769468859485888967582628541, 16199498009890300793447764109167825482974677554285030558627472987223487860004259356583103155503531178685925169504893515411058240259757324428359095426887034269747878644217523752683634553579913057287644398059017586893029977164135244343504122333634006934037103876230504255167674672093144418281013912912808902905971599505240285885392400151523550762949647179210173098229549706311783129689475114132048763443938043258951953364950585674308621814260674458868228182973077303704563443769739592116083922318868953510704274677478162584676616375773425920438446789132646217986925790472764259290774133446539490236213762194253152322247, 17828641241183021783941239587502469972892430175796480087371793912217171381674783170842358755495515944784273205744758714480172394736958586330142487456676865279941155363623422506722632610442232733199296307546196742694775568584168346556731751981417208889691315911849509862094152219902641552292054660672338675535113914157353605444163050142229980564480658815007091890969202384725544282527556106797536749550662610551655135576358329045423749226350283900035242694811054836739550150683977930765170891818518747571579207081129388505693532702466263969554103190321899106550265094309245694759219001939353720393941289634090919320741, 18553710870627206223331369643763856913913473133240078247026140923036084570177359456718233496128034989431313681674828414854004159726214543810500612641232548357562979694913888151156847461167763450634717966937365399396569068720500665701215226596289023092619248922689900098446935601568421769995677650167530389780407432129548528877932608961935369834960190184809897757450136080063857136076927849118786912489421295864947436407056075851211434939744721074000319733564472931369699860756889707580129662086971084587283853963849077477433452323077691472330145153548759629047576490640899678121909049191998385853809416290138198894107, 23530284911005014749813886231174095751599986713289171018986389212230597031742222723160627336499206846351638704329995034492027064132269036917283948285801442337275342099108754021469881840530182406190151469366071799723001672482708139253495020521764200922440273121775236997999727665394164083690166641081100925950325548844251315491270509084655834953305656248729664348416035812898648346471101382062978222840436730138667577946883887296778895828853357876327611137634652672526910378546046214528581217796582715400697396143580575222876165549663910562368747118962334207414877016627026057008636527361221899063077801010872867490853]

def getPos():
    for i in range(len(ns)):
        for j in range(i+1, len(ns)):
            if gmpy2.gcd(ns[i], ns[j]) > 1:
                print(i, j)
                return

getPos()
# 5 8

所以可以得到第 $5$ 组和第 $9$​ 组是有公因子的。

于是一瞬可以完成分解，然后就可以得到 flag 了。

解密脚本如下：

import gmpy2
from Crypto.Util.number import long_to_bytes

n = 14082895340069750195624496854826339506625112043886407716057400491975763565682615324358599521625943482701682587973818614203535242089852507027219502943551439252395834102385713543422992240035766976798628201210682884172910499397950881894189484531458713368702071779515768387560603074195395231205546053377847977139139962281575255410172053491593716534864194443759866533036698178736529157047325842162534702172234710695219385028317480472433012068095732654401548088593201500066504115851050999663052585253401233559592019995006329067999264988201573694387666742725409090282654650800657212428121182797924769468859485888967582628541
n1 = 18553710870627206223331369643763856913913473133240078247026140923036084570177359456718233496128034989431313681674828414854004159726214543810500612641232548357562979694913888151156847461167763450634717966937365399396569068720500665701215226596289023092619248922689900098446935601568421769995677650167530389780407432129548528877932608961935369834960190184809897757450136080063857136076927849118786912489421295864947436407056075851211434939744721074000319733564472931369699860756889707580129662086971084587283853963849077477433452323077691472330145153548759629047576490640899678121909049191998385853809416290138198894107

p = gmpy2.gcd(n, n1)
assert gmpy2.is_prime(p)

q = n // p
assert gmpy2.is_prime(q)

phi = (p-1)*(q-1)
e = 69847
c = 6679685792184647579741974108239609836295738169094483010267484694973005768813309643675939770616489046769630599316240200212728466063038636568261912551748579861287517463415319012827716352199222523212354039118161756005582251944618135481609204228669597621813574260493046070865613241241527561194368769067168904926326539966960495483801330592039384512903752142311485807655093913443627320370767810603096793238147853100215855118187160325951570413780244109679600047017475167867627330627171112187868097589867093208440752223909473327727775637904127916400463980988780671943594575243201568862808680637410821667892747701101267246302

d = gmpy2.invert(e, phi)
m = pow(c, d, n)

flag = long_to_bytes(m)
print(flag)
# b'flag{baby_RSA_decompose_N_by_gcd}'